#include "src/lib/ll.h"\r
\r
+#ifdef OTHERMERGELISTSTIFF\r
+int listLength(node_t * item)\r
+{\r
+ node_t * cur = item;\r
+ int size = 0;\r
+\r
+ while (cur->next != NULL)\r
+ {\r
+ ++size;\r
+ cur = cur->next;\r
+ }\r
+\r
+ return size;\r
+}\r
+\r
void print_list(node_t * head)\r
{\r
node_t * current = head;\r
\r
- while (current != NULL)\r
+ while (current->next != NULL)\r
{\r
- printf("[%u] %d\n", current->id, current->val);\r
+ printf("[%u]= %d\n", current->id, current->val);\r
current = current->next;\r
}\r
}\r
\r
return retval;\r
}\r
+#else\r
+/* Takes two lists sorted in increasing order, and splices\r
+ their nodes together to make one big sorted list which\r
+ is returned. */\r
+struct node* SortedMerge(struct node* a, struct node* b)\r
+{\r
+ /* a dummy first node to hang the result on */\r
+ struct node dummy;\r
+\r
+ /* tail points to the last result node */\r
+ struct node* tail = &dummy;\r
+\r
+ /* so tail->next is the place to add new nodes\r
+ to the result. */\r
+ dummy.next = NULL;\r
+ while (1)\r
+ {\r
+ if (a == NULL)\r
+ {\r
+ /* if either list runs out, use the\r
+ other list */\r
+ tail->next = b;\r
+ break;\r
+ }\r
+ else if (b == NULL)\r
+ {\r
+ tail->next = a;\r
+ break;\r
+ }\r
+ if (a->data <= b->data)\r
+ Movenode(&(tail->next), &a);\r
+ else\r
+ Movenode(&(tail->next), &b);\r
+\r
+ tail = tail->next;\r
+ }\r
+ return(dummy.next);\r
+}\r
+\r
+struct node* LL_merge(struct node* a, struct node* b)\r
+{\r
+ /* a dummy first node to hang the result on */\r
+ struct node dummy;\r
+\r
+ /* tail points to the last result node */\r
+ struct node* tail = &dummy;\r
+\r
+ /* so tail->next is the place to add new nodes\r
+ to the result. */\r
+ dummy.next = NULL;\r
+ Movenode(&(tail->next), &a);\r
+ a = a->next;\r
+ tail = tail->next;\r
+ while (1)\r
+ {\r
+ if (a == NULL)\r
+ {\r
+ /* if either list runs out, use the\r
+ other list */\r
+ tail->next = b;\r
+ break;\r
+ }\r
+ else if (b == NULL)\r
+ {\r
+ tail->next = a;\r
+ break;\r
+ }\r
+ if (a->data <= b->data)\r
+ Movenode(&(tail->next), &a);\r
+ else\r
+ Movenode(&(tail->next), &b);\r
+\r
+ tail = tail->next;\r
+ }\r
+ return(dummy.next);\r
+}\r
+\r
+/* The function removes duplicates from a sorted list */\r
+void removeDuplicates(struct node* head)\r
+{\r
+ /* Pointer to traverse the linked list */\r
+ struct node* current = head;\r
+ \r
+ /* Pointer to store the next pointer of a node to be deleted*/\r
+ struct node* next_next;\r
+\r
+ /* do nothing if the list is empty */\r
+ if (current == NULL)\r
+ return;\r
+ \r
+ /* Traverse the list till last node */\r
+ while (current->next != NULL)\r
+ {\r
+ /* Compare current node with next node */\r
+ if (current->data == current->next->data)\r
+ {\r
+ /* The sequence of steps is important */\r
+ next_next = current->next->next;\r
+ free(current->next);\r
+ current->next = next_next;\r
+ }\r
+ else /* This is tricky: only advance if no deletion */\r
+ {\r
+ current = current->next;\r
+ }\r
+ }\r
+}\r
+\r
+/* UTILITY FUNCTIONS */\r
+/* Movenode() function takes the node from the front of the\r
+ source, and move it to the front of the dest.\r
+ It is an error to call this with the source list empty.\r
+\r
+ Before calling Movenode():\r
+ source == {1, 2, 3}\r
+ dest == {1, 2, 3}\r
+\r
+ Affter calling Movenode():\r
+ source == {2, 3}\r
+ dest == {1, 1, 2, 3} */\r
+void Movenode(struct node** destRef, struct node** sourceRef)\r
+{\r
+ /* the front source node */\r
+ struct node* newnode = *sourceRef;\r
+ assert(newnode != NULL);\r
+\r
+ /* Advance the source pointer */\r
+ *sourceRef = newnode->next;\r
+\r
+ /* Link the old dest off the new node */\r
+ newnode->next = *destRef;\r
+\r
+ /* Move dest to point to the new node */\r
+ *destRef = newnode;\r
+}\r
+#endif\r
+\r
+/* Function to insert a node at the beginging of the\r
+ linked list */\r
+void pushll(struct node** head_ref, int new_data)\r
+{\r
+ /* allocate node */\r
+ struct node* new_node =\r
+ (struct node*) malloc(sizeof(struct node));\r
+\r
+ /* put in the data */\r
+ new_node->data = new_data;\r
+\r
+ /* link the old list off the new node */\r
+ new_node->next = (*head_ref);\r
+\r
+ /* move the head to point to the new node */\r
+ (*head_ref) = new_node;\r
+}\r
+\r
+/* Function to print nodes in a given linked list */\r
+void printList(struct node *node)\r
+{\r
+ while (node!=NULL)\r
+ {\r
+ printf("%d ", node->data);\r
+ node = node->next;\r
+ }\r
+}\r
+#endif\r
#ifndef __LL_H__\r
#define __LL_H__\r
#include <stdio.h>\r
+#include <stdlib.h>\r
+#include <assert.h>\r
#include "src/lib/16_tail.h"\r
\r
+//#define OTHERMERGELISTSTIFF\r
+\r
+/* Link list node_t */\r
typedef struct node\r
{\r
struct node *prev;\r
rgb_t d;\r
- int val;\r
+ int data;\r
struct node *next;\r
word id;\r
} node_t;\r
\r
+#ifdef OTHERMERGELISTSTIFF\r
+int listLength(node_t * item);\r
void print_list(node_t * head);\r
void pushe(node_t * head, int val);\r
void pushs(node_t ** head, int val);\r
int pop(node_t ** head);\r
int remove_last(node_t * head);\r
int remove_by_index(node_t ** head, int n);\r
+#else\r
+/* pull off the front node of the source and put it in dest */\r
+void Movenode(struct node** destRef, struct node** sourceRef);\r
+struct node* SortedMerge(struct node* a, struct node* b);\r
+struct node* LL_merge(struct node* a, struct node* b);\r
+void pushll(struct node** head_ref, int new_data);\r
+void printList(struct node *node);\r
+void removeDuplicates(struct node* head);\r
+#endif\r
\r
#endif\r
*/\r
#include "src/lib/ll.h"\r
\r
+#if 0\r
+//def OTHERMERGELISTSTIFF\r
+\r
void\r
main(int argc, char *argv[])\r
{\r
int i;\r
- node_t * head = NULL; node_t * heao = NULL;\r
- head = malloc(sizeof(node_t)); heao = malloc(sizeof(node_t));\r
- head->val = 0; heao->val = 9;\r
- head->next=NULL; heao->next=NULL;\r
- head->id=0; heao->id=0;\r
+ node_t * vga = NULL; node_t * imgpal = NULL;\r
+ vga = malloc(sizeof(node_t)); imgpal = malloc(sizeof(node_t));\r
+ vga->val = 24; imgpal->val = 9;\r
+ vga->next=NULL; imgpal->next=NULL;\r
+ vga->id=0; imgpal->id=0;\r
\r
- for(i=1; i<\r
+ printf(" ");\r
+ for(i=1; i<=\r
//PAL_SIZE\r
- 7\r
+ 6\r
; i++)\r
{\r
if(!(i%3)) printf("\n ");\r
printf("%d,", i);\r
- pushe(head, i);\r
+ pushe(vga, i);\r
}\r
\r
- printf("\n");\r
+ printf("\n\n ");\r
\r
- for(i=8; i>0; i--)\r
+ for(i=4; i>0; i--)\r
{\r
if(!(i%3)) printf("\n ");\r
printf("%d,", i);\r
- pushe(heao, i);\r
+ pushe(imgpal, i);\r
+ }\r
+ printf("\n");\r
+\r
+ printf("size of vga = %d\n", listLength(vga));\r
+//#if 0\r
+ printf("\n=======================\n");\r
+ printf("vga list printings\n=======================\n");\r
+ print_list(vga);\r
+ printf("\n=======================\n");\r
+ printf("imgpal list printings\n=======================\n");\r
+ print_list(imgpal);\r
+// printf("\n=======================\n");\r
+//#endif\r
+ i=1;//skip overscan\r
+ while(i!=listLength(imgpal))\r
+ {\r
+ \r
}\r
- print_list(head);\r
+ free(vga);\r
+ free(imgpal);\r
+}\r
+#else\r
+#if 0\r
+/* C/C++ program to merge two sorted linked lists */\r
+// from http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/\r
+\r
+/* Drier program to test above functions*/\r
+void main()\r
+{\r
+ /* Start with the empty list */\r
+ struct node* res = NULL;\r
+ struct node* a = NULL;\r
+ struct node* b = NULL;\r
+\r
+ /* Let us create two sorted linked lists to test\r
+ the functions\r
+ Created lists, a: 5->10->15, b: 2->3->20 */\r
+ pushll(&a, 15);\r
+ pushll(&a, 10);\r
+ pushll(&a, 4);\r
+ pushll(&a, 3);\r
+ pushll(&a, 2);\r
+ pushll(&a, 1);\r
+ pushll(&a, 0);\r
+\r
+ pushll(&b, 20);\r
+ pushll(&b, 3);\r
+ pushll(&b, 2);\r
+ pushll(&b, 4);\r
+\r
printf("\n");\r
- print_list(heao);\r
- free(head);\r
- free(heao);\r
+ printf("The 2 Linked List are: \n");\r
+ printList(a); printf("\n");\r
+ printList(b); printf("\n");\r
+\r
+ /* Remove duplicates from linked list */\r
+ res = SortedMerge(a, b);\r
+// res = LL_merge(a, b);\r
+ \r
+ printf("Merged Linked List is: \n");\r
+ printList(res);\r
+}\r
+#endif\r
+/* C Program to remove duplicates from a sorted linked list */\r
+\r
+/* Drier program to test above functions*/\r
+void main()\r
+{\r
+ /* Start with the empty list */\r
+ struct node* head = NULL;\r
+ \r
+ /* Let us create a sorted linked list to test the functions\r
+ Created linked list will be 11->11->11->13->13->20 */\r
+ push(&head, 20);\r
+ push(&head, 13);\r
+ push(&head, 13); \r
+ push(&head, 11);\r
+ push(&head, 11);\r
+ push(&head, 11); \r
+ \r
+ printf("\n Linked list before duplicate removal ");\r
+ printList(head); \r
+ \r
+ /* Remove duplicates from linked list */\r
+ removeDuplicates(head); \r
+ \r
+ printf("\n Linked list after duplicate removal "); \r
+ printList(head); \r
+ \r
}\r
+#endif\r
projects / 16.git / commitdiff