Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <string.h>
- #include <stdio.h>
- #include <time.h>
- #ifndef LINKEDLIST_H_
- #define LINKEDLIST_H_
- #include <stdlib.h>
- #include <string.h>
- #include <stdio.h>
- typedef struct Person
- {
- char *name;
- char *surname;
- char *dateBirth;
- char *email;
- char *phone;
- char *address;
- }Person;
- typedef struct Member
- {
- Person *person;
- struct Member *previous;
- struct Member *next;
- }Member;
- typedef struct List
- {
- Member *first;
- Member *last;
- }List;
- extern List *createList();
- extern void deleteList(List *head);
- extern void addElement(List *head, Person *person);
- extern void deleteElement(List *head, Person *person);
- extern Person *searchElement(List *head, char *name, char *surname);
- extern void sortList(List *head);
- extern void quickSort(Member *first,Member *last);
- extern Member *partition(Member *first,Member *last);
- extern void swap(Member *a,Member *b);
- extern List *mergeSort(List *head);
- extern List *merge(List *left, List *right);
- extern Member *center(List *head);
- extern void printPerson(Person *person);
- extern void printList(List *head);
- extern Person *createPerson(char *name, char *surname, char *dateBirth, char *email, char *phone, char *address);
- #endif
- List *createList()
- {
- List *head = (List*)malloc(sizeof(List));
- head->first = NULL;
- head->last = NULL;
- return head;
- }
- void deleteList(List *head)
- {
- Member *first = head->first;
- if (first == NULL)return;
- while (first != NULL)
- {
- Member *tmp = first;
- first = first->next;
- free(tmp->person->name);
- free(tmp->person->surname);
- free(tmp->person->dateBirth);
- free(tmp->person->email);
- free(tmp->person->phone);
- free(tmp->person->address);
- free(tmp->person);
- free(tmp);
- }
- }
- void addElement(List *head, Person *person)
- {
- Member *last = head->last;
- Member *newMem = (Member*)malloc(sizeof(Member));
- newMem->person = person;
- newMem->previous = newMem->next = NULL;
- if (last == NULL)
- {
- head->first = head->last = newMem;
- return;
- }
- last->next = newMem;
- newMem->previous = last;
- head->last = newMem;
- }
- void deleteElement(List *head, Person *person)
- {
- if (head == NULL || person == NULL)return;
- Member *member = head->first;
- while (member != NULL && member->person != person)member = member->next;
- if (member == NULL)return;
- if (member == head->first)
- {
- if (member == head->last)
- {
- head->first = head->last = NULL;
- }
- else
- {
- head->first = head->first->next;
- head->first->previous = NULL;
- }
- }
- else
- {
- if (member == head->last)
- {
- head->last = head->last->previous;
- head->last->next = NULL;
- }
- else
- {
- member->previous->next = member->next;
- }
- }
- free(member->person->name);
- free(member->person->surname);
- free(member->person->dateBirth);
- free(member->person->email);
- free(member->person->phone);
- free(member->person->address);
- free(member->person);
- free(member);
- }
- Person *searchElement(List *head, char *name, char *surname)
- {
- Member *tmp = head->first;
- while (tmp != NULL)
- {
- if (strcmp(tmp->person->name, name) == 0 && strcmp(tmp->person->surname, surname) == 0)
- return tmp->person;
- tmp=tmp->next;
- }
- return NULL;
- }
- void sortList(List *head)
- {
- quickSort(head->first,head->last);
- }
- void quickSort(Member *first,Member *last)
- {
- if (first!= NULL && last!=NULL && first!=last && first!=last->next)
- {
- Member *p = partition(first,last);
- quickSort(first, p->previous);
- quickSort(p->next,last);
- }
- }
- Member *partition(Member *first,Member *last)
- {
- Person *pivot=last->person;
- Member *i=first->previous;
- Member *j=first;
- for(j;j!=last;j=j->next)
- {
- if(strcmp(j->person->surname,pivot->surname)<0)
- {
- i=(i==NULL) ? first : i->next;
- swap(i,j);
- }
- }
- i =(i==NULL)? first : i->next;
- swap(i,last);
- return i;
- }
- void swap(Member *a,Member *b)
- {
- Person *tmp=a->person;
- a->person=b->person;
- b->person=tmp;
- }
- List *mergeSort(List *head)
- {
- if (head->first == NULL || head->first == head->last)return head;
- Member *mid = center(head);
- if (mid->next != NULL)mid->next->previous = NULL;
- List *left = createList();
- List *right = createList();
- right->first = mid->next;
- right->last = mid->next == NULL ? NULL : head->last;
- left->first = head->first;
- left->last = mid;
- left->last->next=NULL;
- left = mergeSort(left);
- right = mergeSort(right);
- return merge(left, right);
- }
- List *merge(List *left, List *right)
- {
- if (left->first == right->first && left->last == right->last)
- {
- free(right);
- return left;
- }
- Member *leftMem = left->first;
- Member *rightMem = right->first;
- Member *tmp;
- if(rightMem==NULL)return left;
- if(leftMem==NULL)return right;
- if (strcmp(leftMem->person->name, rightMem->person->name)<0)
- {
- tmp = leftMem;
- leftMem = leftMem->next;
- }
- else
- {
- tmp = rightMem;
- rightMem = rightMem->next;
- }
- left->first = tmp;
- while (leftMem != NULL && rightMem != NULL)
- {
- if (strcmp(leftMem->person->name, rightMem->person->name)<0)
- {
- tmp->next = leftMem;
- leftMem->previous = tmp;
- tmp = leftMem;
- leftMem = leftMem->next;
- }
- else
- {
- tmp->next = rightMem;
- rightMem->previous = tmp;
- tmp = rightMem;
- rightMem = rightMem->next;
- }
- }
- if (leftMem != NULL)
- {
- tmp->next = leftMem;
- leftMem->previous = tmp;
- }
- else if (rightMem != NULL)
- {
- tmp->next = rightMem;
- rightMem->previous = tmp;
- }
- while (tmp->next != NULL)
- {
- tmp = tmp->next;
- }
- left->last = tmp;
- free(right);
- return left;
- }
- Member *center(List *head)
- {
- Member *slower = head->first;
- if (slower->next == NULL)return slower;
- Member *faster = slower->next;
- while (slower != NULL && faster->next != NULL)
- {
- slower = slower->next;
- faster = faster->next->next;
- }
- return slower;
- }
- void printPerson(Person *person)
- {
- if (person == NULL)return;
- printf("%s %s %s %s %s %s\n", person->name, person->surname, person->dateBirth, person->email, person->phone, person->address);
- }
- void printList(List *head)
- {
- Member *tmp = head->first;
- while (tmp != NULL)
- {
- printPerson(tmp->person);
- tmp = tmp->next;
- }
- }
- Person *createPerson(char *name, char *surname, char *dateBirth, char *email, char *phone, char *address)
- {
- Person *person = (Person*)malloc(sizeof(Person));
- person->name = name;
- person->surname = surname;
- person->dateBirth = dateBirth;
- person->email = email;
- person->phone = phone;
- person->address = address;
- return person;
- }
- char *allocate(char *a);
- int main()
- {
- srand(time(NULL));
- char* names[]={"Adam","Bartosz","Cyprian","Danuta","Eustachy","Frania","Gabriel","Halina"};
- char* surnames[]={"Kowalski","Nowak","Job","Kolasa","Perdek","Slowik","Wisniewski","Rinner"};
- char* birthDates[]={"01-01-1991","02-02-1992","03-03-1993","04-04-1994",
- "05-05-1995","06-06-1996","07-07-1997","08-08-1998"};
- char* emails[]={"adam.kowalski@gmail.com","bartosz.nowak@gmail.com","cyprian.job@gmail.com","danuta.kolasa@gmail.com",
- "eustachy.perdek@gmail.com","frania.slowik@gmail.com","gabriel.wisniewski@gmail.com","halina.rinner@gmail.com"};
- char* numbers[]={"111111111","222222222","333333333","444444444","555555555","666666666","777777777","888888888"};
- char* adresses[]={"Krakow","Warszawa","Plock","Gdynia","Rzeszow","Katowice","Wroclaw","Poznan"};
- int N=8;
- List* head=createList();
- int i=0;
- for(i=0;i<N;i++)
- {
- Person *person=createPerson(allocate(names[rand()%8]),allocate(surnames[rand()%8]),allocate(birthDates[rand()%8]),allocate(emails[rand()%8]),allocate(numbers[rand()%8]),allocate(adresses[rand()%8]));
- addElement(head,person);
- }
- printf("\n");
- printList(head);
- sortList(head);
- printf("Posortowane:\n");
- printList(head);
- printf("\n");
- printf("Szukany element:\n");
- Person *searched=searchElement(head,"Eustachy","Nowak");
- if(searched!=NULL)printPerson(searched);
- printf("\n");
- printf("Usuniety element:\n");
- deleteElement(head,searched);
- printList(head);
- deleteList(head);
- return 0;
- }
- char *allocate(char *a)
- {
- char *b=(char*)malloc(strlen(a)+1);
- strcpy(b,a);
- return b;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement