1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4
  5 typedef struct LinkedNode
  6 {
  7     char * name;
  8     int totalCost;
  9     struct LinkedNode * next;
 10     struct LinkedNode * prev;
 11 } Node;
 12
 13 Node * constructList(Node *, char *, int);
 14 Node * addNode(Node *, char *, int);
 15 void printList(Node *);
 16 void tokenize();
 17 void destroyList(Node *);
 18
 19 void freeNode(Node * temp)
 20 { free(temp->name); free(temp); }
 21
 22 int main(void)
 23 {
 24     Node * head = NULL;
 25     char buffer[51], * name;
 26     int cost;
 27
 28     while (fgets(buffer, sizeof(buffer), stdin) != NULL)
 29     {
 30         tokenize(buffer, &name, &cost);
 31         head = addNode(head, name, cost);
 32     }
 33
 34     printList(head);
 35     destroyList(head);
 36
 37     return EXIT_SUCCESS;
 38 }
 39
 40 Node * addNode(Node * head, char * name, int cost)
 41 {
 42     Node * temp, * prev, * new;
 43
 44     if (head == NULL)   /* if list does not yet exit */
 45         return constructList(head, name, cost);
 46
 47     /* If a list DOES exist, set up the new node */
 48     new = malloc(sizeof(Node));
 49     new->name = malloc(strlen(name) + 1);
 50     strcpy(new->name, name);
 51     new->totalCost = cost;
 52
 53     for (temp = head, prev = head; temp != NULL; prev = temp, temp = temp->next)
 54     {
 55         if (strcmp(new->name, temp->name) < 0)  /* if new node goes BEFORE node */
 56         {                                       /* currently pointed to by temp */
 57             if (temp == head)
 58             {   /* new node becomes head */
 59                 new->next = head;
 60                 head->prev = new;
 61                 head = new;
 62                 return head;
 63             }
 64             else
 65             {   /* inserting in middle of list */
 66                 new->next = temp;
 67                 new->prev = prev;
 68                 prev->next = new;
 69                 temp->prev = new;
 70                 return head;
 71             }
 72         }
 73         else if (strcmp(new->name, temp->name) == 0) /* updating node */
 74         {
 75             freeNode(new);
 76             temp->totalCost += cost;
 77             return head;
 78         }
 79     }
 80     /*end of list */
 81     new->prev = prev;
 82     prev->next = new;
 83     new->next = NULL;
 84     return head;
 85 }
 86
 87 Node * constructList(Node * head, char * name, int cost)
 88 {
88.5 		head = malloc(sizeof(Node));
 89         head->name = malloc(strlen(name) + 1);
 90         head->next = NULL;
 91         head->prev = NULL;
 92         strcpy(head->name, name);
 93         head->totalCost = cost;
 94         return head;
 95 }
 96
 97 void tokenize(char * line, char ** name, int * cost)
 98 {
 99     char * token, * delim = " $.";
100
101     *name = strtok(line, delim);
102     token = strtok(NULL, delim);
103     while (token != NULL)
104     {
105         if (token[0] >= '1' && token[0] <= '9')
106         {
107             *cost = atoi(token);
108             return;
109         }
110         token = strtok(NULL, delim);
111     }
112 }
113
114 void printList(Node * head)
115 {
116     Node * temp;
117     for (temp = head; temp != NULL; temp = temp->next)
118         printf("%s, %d\n", temp->name, temp->totalCost);
119 }
120
121 void destroyList(Node * head)
122 {
123     Node * temp, * next;
124     for (temp = head; temp != NULL; temp = next)
125     {
126			next = temp->next;
127         freeNode(temp);
128     }
129 }