Namespaces
Variants
Views
Actions

Main Page

From cppreference.com
  1. include"arrayList.h"
  2. include<stdio.h>
  3. include<stdlib.h>
  4. include<string.h>
  5. include

struct ArrayList * createArrayList(unsigned initialCapacity) {

   struct ArrayList * newList = (struct ArrayList*) malloc (sizeof(struct ArrayList));
   if(newList == NULL) {
       printf("Could not allocate memory!\n");
       return NULL;
   }
   newList->capacity = initialCapacity;
   newList->size = 0;
   newList->array = (short*) malloc (initialCapacity * sizeof(short));
   if(newList->array == NULL) {
       printf("Could not allocate memory!\n");
       return NULL;
   } else {
       return newList;
   }

}


unsigned arrayListSize(struct ArrayList * list){

   return list->size;

}

void arrayListInsert(struct ArrayList * list, unsigned index, short value){

   if(index > (list->capacity)) { 
   printf("Index > size\n");
   return;
   } else if(list->size == list->capacity) {
       list->array = (short*) realloc (list->array, list->capacity*2 * sizeof(short));  
       list->capacity=list->capacity*2;
       
   }
   if(list->size!=0){
   memmove(&list->array[index+1],&list->array[index],(list->size-index)*(sizeof(short)));
 
   }
   list->array[index] = value;
   list->size++;


}

void arrayListDelete(struct ArrayList * list, unsigned index) {

   int i;
   for(i=index; i<list->size-1; i++) {
       list->array[i] = list->array[i+1];
   }
   list->size-=1;

}


int arrayListSearch(struct ArrayList * list, short value) {

   int i;
   for(i=0;i<list->size;i++){
       if(list->array[i]==value){
           printf("Valoare e pe pozitia%d\n",i);
           return;
       }
   }

}


short arrayListGet(struct ArrayList * list, unsigned index){

   if(index > list->size-1) {
   printf("Index prea mare");
   } else {
   printf(" Elementul de pe poz... este %hd\n",list->array[index]);
   return;
   }
   

}


void arrayListBubbleSort(struct ArrayList * list){

   char done;
   do{
       done=1;
       unsigned i;
       for(i=0;i<list->size; i++) {
           if(list->array[i]>list->array[i+1]){
           float tmp = list->array[i];
           list->array[i]= list->array[i+1];
           list->array[i+1]=tmp;
           done = 0;
           }
       }
   } while(!done);

}


int arrayListBinarySearch(struct ArrayList * list, short value){

   int start = 0;
   int end = list->size-1;
   do {
       unsigned middle = (start + end) / 2;
       if(list->array[middle]==value) {
           return middle;
       }
       if(list->array[middle]>value) {
           end=middle-1;
       } else {
           start = middle+1;
       }
   } while (start>=end);
   return -1;

}


void deleteArrayList(struct ArrayList * list){

   free(list->array);
   free(list);

}


LINKED QUEUE

  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <string.h>
  4. include "lab4.h"


/**

* Funcția alocă memorie și creeaza un nou LinkedQueue de o dimensiune maximă specificată.
* @param maxSize numarul maxim de elemente din coadă sau UNLIMITED_SIZE dacă aceasta 
*  este nelimitată.
* @return pointer la o structura de tip LinkedQueue. 
*/

struct LinkedQueue * createLinkedQueue(unsigned maxSize) {

   struct LinkedQueue * newLinkedQueue = (struct LinkedQueue*) malloc (sizeof (struct LinkedQueue));
   newLinkedQueue->maxSize = maxSize;
   newLinkedQueue->size = 0;
   newLinkedQueue->firstNode = NULL;
   newLinkedQueue->lastNode = NULL;
   return newLinkedQueue;    

}

/**

* Functia intoarce numarul de elemente valide din coada specificata.
* @param queue coada pentru care se cere dimensinea.
* @return numarul de elemente valide din coada queue.
*/

unsigned linkedQueueSize(struct LinkedQueue * queue){

   return queue->size;

}

/**

* Functia intoarce 1 dacă coada specificată este goală.
* @param queue coada pentru care se cere dimensiunea.
* @return 1 dacă coada este goală, 0 dacă nu
*/

int linkedQueueIsEmpty(struct LinkedQueue * queue){

   if (queue->size == 0) {
   return 1;
   } else {
   return 0;  
   }

}

/**

* Functia intoarce 1 dacă coada specificată este plină.
* @param queue coada pentru care se cere dimensiunea.
* @return 1 dacă coada este plină, 0 dacă nu
*/

int linkedQueueIsFull(struct LinkedQueue * queue){

   if (queue->size == queue->maxSize) {
   return 1;
   } else {
   return 0;
   }

}

/**

* Functia inserează elementul newString în coadă.
* @param queue coada la care se adaugă elementul.
* @param newString elementul ce trebuie adăugat.
*/

void linkedQueuePush(struct LinkedQueue * queue, char * newString){

   if(queue->size == queue->maxSize) {
       printf("Coada este plina");
       return;
   }
   struct SimplyLinkedNode * tmpNode = (struct SimplyLinkedNode*) malloc (sizeof (struct SimplyLinkedNode));
   tmpNode->next = NULL;
   tmpNode->string = newString;
   if(!linkedQueueSize(queue)) {
       queue->firstNode = tmpNode;
       }else{
       queue->lastNode->next = tmpNode;
       }
       queue->lastNode = tmpNode;
       queue->size++;

}

/**

* Functia extrage următorul element din coadă.
* @return următorul element din coadă sau NULL dacă coada este goală.
*/

char * linkedQueuePop(struct LinkedQueue * queue) {

   if(linkedQueueIsEmpty(queue)) {
       printf("Coada este goala");
       return NULL;
   }
   struct SimplyLinkedNode * tmpNode = queue->firstNode;
   queue->firstNode = queue->firstNode->next;
   if(linkedQueueSize(queue)==1){
       queue->lastNode = NULL;      
   }
   queue->size--;
   char * returnString = tmpNode->string;
   free(tmpNode);
   return returnString;

}

/**

* Functia întoarce următorul element din coadă, fără a-l extrage.
* @return următorul element din coadă sau NULL dacă coada este goală.
*/

char * linkedQueuePeek(struct LinkedQueue * queue){

   if(linkedQueueIsEmpty(queue)){
   printf("Coada este goala");
   return NULL;
   }
   return queue->firstNode->string;

}

/**

* Functia dezalocă memoria folosită de coada specificată.
* @param queue coada care trebuie ștearsă.
*/

void deleteLinkedQueue(struct LinkedQueue * queue) {

   int i;
   struct SimplyLinkedNode * tmpNode = queue->firstNode;
   struct SimplyLinkedNode * tmpNode2;
   for(i=0;i<queue->size;i++){
       free(tmpNode->string);
       tmpNode2=tmpNode->next;
       free(tmpNode);
       tmpNode=tmpNode2; 
   }
   free(queue);
   }


TREEMAP

  1. include "server.h"
  2. include <stdio.h>
  3. include <stdlib.h>
  4. include "treeMap.h"


struct TreeMap * createTreeMap() {

   struct TreeMap * newTreeMap = (struct TreeMap*) calloc (1, sizeof(struct TreeMap));
   return newTreeMap;

}

unsigned treeMapSize(struct TreeMap * map) {

   return map->size;

}

char treeMapIsEmpty(struct TreeMap * map) {

   if(map->size == 0) {
       return 1;
   } else return 0;

}

char treeMapHasKey(struct TreeMap * map, char * key) { struct TreeNode * tmpNode = map->root; while (tmpNode != NULL) { if (compare(tmpNode->pair.key, key) == 0) { return 1; } else if (compare(tmpNode->pair.key, key) > 0) { tmpNode = tmpNode->left; } else if (compare(tmpNode->pair.key, key) < 0) { tmpNode = tmpNode->right; } } return 0; }

void treeMapPut(struct TreeMap * map, char * key, struct Server value) { if (treeMapIsEmpty(map) == 1) { struct TreeNode * newNode = (struct TreeNode *)calloc(1, sizeof(struct TreeNode)); newNode->pair.key = key; newNode->pair.server = value; newNode->parent = newNode->left = newNode->right = NULL; map->root = newNode; map->size++; return; } else { struct TreeNode * tmpNode = map->root; while (1) { if (compare(tmpNode->pair.key, key) == 0) { tmpNode->pair.key = key; tmpNode->pair.server = value; return; } else if (compare(tmpNode->pair.key, key) > 0 && tmpNode->left != NULL) { tmpNode = tmpNode->left; } else if (compare(tmpNode->pair.key, key) > 0 && tmpNode->left == NULL) { struct TreeNode * newNode = (struct TreeNode *)calloc(1, sizeof(struct TreeNode)); newNode->pair.key = key; newNode->pair.server = value; newNode->parent = tmpNode; tmpNode->left = newNode; map->size++; return; } else if (compare(tmpNode->pair.key, key) < 0 && tmpNode->right != NULL) { tmpNode = tmpNode->right; } else if (compare(tmpNode->pair.key, key) < 0 && tmpNode->right == NULL) { struct TreeNode * newNode = (struct TreeNode *)calloc(1, sizeof(struct TreeNode)); newNode->pair.key = key; newNode->pair.server = value; newNode->parent = tmpNode; tmpNode->right = newNode; map->size++; return; } } } }


struct Server treeMapGet(struct TreeMap * map, char * key) { struct TreeNode * tmpNode = map->root; while (tmpNode != NULL) { if (compare(tmpNode->pair.key, key) == 0) { return tmpNode->pair.server; } else if (compare(tmpNode->pair.key, key) > 0) { tmpNode = tmpNode->left; } else if (compare(tmpNode->pair.key, key) < 0) { tmpNode = tmpNode->right; } } struct Server nullServer; nullServer.cpuFrequencyGhz = 0; nullServer.cpuType[0] = '\0'; nullServer.diskCapacityTerraBytes = 0; nullServer.hardwareAddress[0] = '\0'; nullServer.hostname[0] = '\0'; nullServer.ipv4[0] = '\0'; nullServer.ramMemoryGigaBytes = 0; return nullServer; }


void treeMapRemove(struct TreeMap * map, char * key) {

   struct TreeNode * tmpNode = map->root;
   char direction;
   while(tmpNode != NULL){
       if(compare(tmpNode->pair.key, key) == 0) {
       break;    
       }
       if(compare(tmpNode->pair.key, key)){
           tmpNode = tmpNode->left;
           direction = -1;
       }
       if(compare(tmpNode->pair.key, key) < 0){
           tmpNode = tmpNode->right;
           direction = 1;
       }
   }
   if(treeMapHasKey(map,key) == 0){
       return;
   } 
   if(tmpNode->left == NULL && tmpNode->right == NULL) {
       if(direction == -1) {
           tmpNode->parent->left = NULL;  
       } else {
           tmpNode->parent->right = NULL;                 
       }
       free(tmpNode);
       map->size--;
       return;
   }
   if(tmpNode->left == NULL && tmpNode->right != NULL) {
       if(direction == -1) {
           tmpNode->parent->left = tmpNode->left;
       } else {
           tmpNode->parent->right = tmpNode->right;
       }
       free(tmpNode);
       map->size--;
       return;
   }
   if(tmpNode->left != NULL && tmpNode->right == NULL) {
       if(direction == -1) {
           tmpNode->parent->left = tmpNode->left;
       } else {
           tmpNode->parent->right = tmpNode->left;
       }
       free(tmpNode);
       map->size--;
       return;
   }
   if(tmpNode->left != NULL && tmpNode->right != NULL) {
       struct TreeNode * minSubtreeNode = tmpNode->right;
       while(minSubtreeNode != NULL){   
               minSubtreeNode = minSubtreeNode->left;
       }
       tmpNode->pair = minSubtreeNode->pair;
       
       treeMapRemove(map, minSubtreeNode);
       }
          

}

void deleteTreeMap(struct TreeMap * map) {

   deleteTreeNode(map->root); 
   free(map);

} void deleteTreeNode(struct TreeNode * node) {

   if(node != NULL) {
       deleteTreeNode(node->left);
       free(node);
       deleteTreeNode(node->right);
       free(node);
   }
   

}


struct Server readFromKeyboard() { struct Server server; scanf("%s", server.hostname); scanf("%u%u%u%u", &server.ipv4[0], &server.ipv4[1], &server.ipv4[2], &server.ipv4[3]); scanf("%u%u%u%u%u%u", &server.hardwareAddress[0], &server.hardwareAddress[1], &server.hardwareAddress[2], &server.hardwareAddress[3], &server.hardwareAddress[4], &server.hardwareAddress[5]);


printf("CPU:"); scanf("%s", server.cpuType); printf("Frequency:"); scanf("%f", &server.cpuFrequencyGhz); printf("Ram:"); scanf("%f", &server.ramMemoryGigaBytes); printf("Disk:"); scanf("%f", &server.diskCapacityTeraBytes); return server; }


int main() { struct TreeMap * map = createTreeMap(); unsigned i; struct Server server; while(1) { server = readFromKeyboard(); if(strcmp(server.hostname,"-")==0){ break; } treeMapPut(map,server.hostname,server); }

   deleteTreeMap(map);

return 0; }


HASHSET

  1. include "linkedList.h"
  2. include "person.h"
  3. include "hashSet.h"


/**

* Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
* @return un pointer la o structura de tip HashSet.
*/

struct HashSet * createHashSet() {

   struct HashSet * set = (struct HashSet*) calloc (1,sizeof(struct HashSet));
   return set;

}

/**

* Functia intoarce numarul de elemente din multime.
* @param set multimea a carei dimensiuni este ceruta.
* @return numarul de elemente din multime.
*/

unsigned hashSetSize(struct HashSet * set) {

   return set->size;

}

/**

* Functia intoarce 1 dacă mulțimea nu conține nici un element.
* @param set multimea de interes.
* @return 1 dacă mulțimea este goală, 0 în rest.
*/

char hashSetIsEmpty(struct HashSet * set){

   if (set->size == 0) {
       return 1;
   } else {
       return 0;
   }

}

/**

* Functia adauga elementul dat in multime daca acesta nu exista. Daca
*  exista deja, functia nu are nici un efect.
* @param set multimea in care trebuie adaugat elementul.
* @param person elementul ce trebuie adaugta.
*/

void hashSetPut(struct HashSet * set, struct Person person) {

   unsigned persHash = hash(person);  
   if(linkedListSearch(&set->array[persHash],person)==-1) {
       linkedListInsert(&set->array[persHash],0,person);
       set->size++;
   }

}

/**

* Functia elimina elementul dat din multime daca acesta exista. Daca
*  nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param person elementul ce trebuie eliminat.
*/

void hashSetRemove(struct HashSet * set, struct Person person){

   unsigned persHash = hash(person);
   if(linkedListSearch(&set->array[persHash],person)) {
       linkedListDelete(set->array[persHash],linkedListSearch(set->array[persHash]));
       set->size--;
   }

}

/**

* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param person elementul cautat.
* @return 1 daca elementul exista in multime, 0 daca nu.
*/

char hashSetContains(struct HashSet * set, struct Person person){

   if(linkedListSearch(&set->array[hash(person)],person)) {
       return 1;
   } else {
       return 0;
   }

}

void deleteHashSet(struct HashSet * set) { unsigned i; for (i = 0; i < MAX_HASH; i++) { struct ListNode * tmpNode = set->array[i].firstNode; while (tmpNode != NULL) { struct ListNode * node = tmpNode; tmpNode = tmpNode->next; free(node); } } free(set); }


MERGE AND SORT

struct ArrayList * createArrayList(unsigned initialCapacity) {

   struct ArrayList * newList = (struct ArrayList *) malloc(sizeof (struct ArrayList));
   if (newList == NULL) {
       return NULL;
   }
   newList->size = 0;
   newList->capacity = initialCapacity;
   newList->array = (short *) malloc(initialCapacity * sizeof (short));
   return newList;

}

void deleteArrayList(struct ArrayList * list) {

   free(list->array);
   free(list);

}

void mergeSort(short * array, unsigned start /*inclusiv*/, unsigned end /* exclusisv*/) {

   if (end - start == 1) return;
   unsigned middle = (start + end) / 2;
   mergeSort(array, start, middle);
   mergeSort(array, middle, end);
   short tmpArray[end - start];
   unsigned i = start; // indexul in prima jumatate
   unsigned j = middle; // indexul in a doua jumatate
   unsigned k = 0; //index in tmpArray
   while (i != middle && j != end) {
       if (array[i] <= array[j]) {
           tmpArray[k++] = array[i++];
       } else {
           tmpArray[k++] = array[j++];
       }
   }
   if (i != middle) {
       memcpy(tmpArray + k, array + i, (middle - i) * sizeof (short));
   } else if (j != end) {
       memcpy(tmpArray + k, array + j, (end - j) * sizeof (short));
   }
   memcpy(array + start, tmpArray, (end - start) * sizeof (short));

}

void arrayListMergeSort(struct ArrayList * list) {

   mergeSort(list->array, 0 /*inclusiv*/, list->size /* exclusiv*/);

}

void quickSort(short * array, unsigned start /*inclusiv*/, unsigned end /* inclusiv*/) {

   if (start == end) return;
   
   unsigned pivot = start;
   unsigned index = end;
   int direction = -1;
   
   while(pivot != index){
       if((direction == -1 && array[pivot] > array[index]) ||
               (direction == 1 && array[index] > array[pivot])){
           short tmpValue = array[pivot];
           array[pivot] = array[index];
           array[index] = tmpValue;
           
           unsigned tmpIndex = index;
           index = pivot;
           pivot = tmpIndex;
           
           direction = -direction;
       }
       
       index += direction;
   }
   
   if(pivot != start) quickSort(array, start, pivot - 1);
   if(pivot != end) quickSort(array, pivot + 1, end);

}

void arrayListQuickSort(struct ArrayList * list) {

   quickSort(list->array, 0 /*inclusiv*/, list->size - 1 /*inclusiv*/);

}