+#include <stdio.h>
#include <stdlib.h>
+#include <stdbool.h>
#include "clist.h"
link_t* list_new(int value) {
- link_t* link_t_new;
- link_t_new = malloc(sizeof(link_t));
- link_t_new->value = value;
- link_t_new->next = NULL;
- return link_t_new;
+ link_t* link_new;
+ link_new = malloc(sizeof(link_t));
+ link_new->value = value;
+ link_new->next = NULL;
+ return link_new;
}
link_t* list_append(link_t* head, int value) {
- if (head == NULL) {
+ if (head == NULL) {
return head = list_new(value);
} else {
link_t* head_first = head;
while (head->next != NULL) {
- head = head->next;
+ head = head->next;
}
head->next = list_new(value);
return head_first;
link_t* list_prepend(link_t* head, int value) {
link_t* first_link = list_new(value);
-
+
first_link->next = head;
return first_link;
}
link_t* list_insert(link_t* head, unsigned index, int value) {
- link_t* link_insrt = list_new(value);
- link_t* head_first = head;
- //link_t* head_prev = NULL;
- link_t* head_next = NULL;
- for (unsigned i = 0; i < index; i++) {
- head = head->next;
+ if (index == 0) {
+ return list_prepend(head, value);
+ } else if (index == list_count(head)) {
+ return list_append(head, value);
+ } else {
+ link_t* link_insrt = list_new(value);
+ link_t* head_first = head;
+ link_t* head_next = NULL;
+ for (unsigned i = 0; i < index-1; i++) {
+ head = head->next;
+ }
+ head_next = head->next;
+ head->next = link_insrt;
+ head = link_insrt;
+ head->next = head_next;
+ return head_first;
}
- //head_prev = head;
- head->next = link_insrt;
- head_next = head->next;
- head = link_insrt;
- head->next = head_next;
- return head_first;
}
link_t* list_delete(link_t* head, unsigned index) {
- link_t* head_first = head;
link_t* head_prev = NULL;
link_t* head_next = NULL;
-
- if (index == 0) {
+ link_t* head_ret = NULL;
+
+ if (head == NULL) {
+ return NULL;
+ } else if (index == 0) {
head_next = head->next;
free(head);
head = head_next;
- return head;
+ head_ret = head;
} else {
+ link_t* head_first = head;
for (unsigned i = 0; i < index-1; i++) {
head = head->next;
}
free(head);
head = head_prev;
head->next = head_next;
- return head_first;
+ head_ret = head_first;
+ }
+ if (head_ret != NULL) {
+ return head_ret;
+ } else {
+ return NULL;
}
}
+link_t* list_concat(link_t* first, link_t* second) {
+ link_t* head_first = first;
+
+ while (first->next != NULL) {
+ first = first->next;
+ }
+ first->next = second;
+ return head_first;
+}
+
+link_t* list_sort(link_t* head) {
+ int tmp;
+ bool isswaped;
+ link_t* head_first = head;
+
+ do {
+ isswaped = false;
+ while (head->next != NULL) {
+ if (head->value > head->next->value) {
+ tmp = head->value;
+ head->value = head->next->value;
+ head->next->value = tmp;
+ isswaped = true;
+ }
+ head = head->next;
+ }
+ /* Reloop at the beginning of the list until there's values swaped */
+ head = head_first;
+ } while (isswaped);
+ return head_first;
+}
+
+static link_t* _list_merge_sort(link_t* head1, link_t* head2) {
+ link_t* head_result = NULL;
+
+ if (head1 == NULL) {
+ return head2;
+ }
+ if (head2 == NULL) {
+ return head1;
+ }
+ if (head1->value < head2->value) {
+ head_result = head1;
+ head_result->next = _list_merge_sort(head1->next, head2);
+ } else {
+ head_result = head2;
+ head_result->next = _list_merge_sort(head1, head2->next);
+ }
+ return head_result;
+}
+
+link_t* list_merge_sort(link_t* head) {
+ link_t* head1;
+ link_t* head2;
+
+ if (head == NULL || head->next == NULL) {
+ return head;
+ }
+
+ head1 = head;
+ head2 = head->next;
+ while (head2 != NULL && head2->next != NULL) {
+ head = head->next;
+ head2 = head->next->next;
+ }
+ head2 = head->next;
+ head->next = NULL;
+
+ head1 = list_merge_sort(head1);
+ head2 = list_merge_sort(head2);
+ return _list_merge_sort(head1, head2);
+}
+
unsigned list_count(link_t* head) {
- int count = 0;
-
- if (head == NULL) { return count; }
- count = 1;
- while (head->next != NULL) {
+ unsigned count = 0;
+
+ while (head != NULL) {
++count;
head = head->next;
- }
+ }
return count;
}
void list_set(link_t* head, unsigned index, int value) {
+ unsigned count = 0;
- //FIXME: check for the index value validity
- for (unsigned count = 0; count < index; count++) {
+ while (head != NULL && count < index) {
+ ++count;
head = head->next;
}
- head->value = value;
+ if (head != NULL) { head->value = value; }
}
int list_get(link_t* head, unsigned index) {
-
- if (index < list_count(head)) {
- for (unsigned i = 0; i < index; i++) {
- head = head->next;
- }
+ unsigned count = 0;
+
+ while (head != NULL && count < index) {
+ ++count;
+ head = head->next;
+ }
+ if (head != NULL) {
return head->value;
- } else {
+ } else {
return -1;
}
}
-void list_clear(link_t* link) {
+void list_clear(link_t* head) {
+ link_t* next_link = NULL;
+
+ while (head != NULL) {
+ next_link = head->next;
+ free(head);
+ head = next_link;
+ }
+}
+
+void list_display_values(link_t* head) {
+ unsigned i = 0;
- while (link != NULL) {
- link_t* next_link = link->next;
- free(link);
- link = next_link;
+ printf("------Begin------\n");
+ while (head != NULL) {
+ printf("value at [%d]=%d\n", i, head->value);
+ head = head->next;
+ i++;
}
+ printf("------End------\n");
}
repositories / TD_C.git / blobdiff