C Programming. trying to write it without using sentinel string. Reference file.

Question

C Programming. trying to write it without using sentinel string.

Reference file.

/*
* LINKED LIST SORTER
*
* This program reads in numbers and sorts them in increasing
* numerical order. The data structure used is a linked list;
* each element looks like this:
*   +--------------+
* | data field | <--- holds the integer that you read in
*   +--------------+
* | next field | <--- holds pointer to next element in
*   +--------------+ linked list (NULL if nothing
*   follows it)
*
* The pointer variable "head" contains a pointer to the first
* element in the linked list (NULL if there are no elements
* in the linked list)
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/*
* structure for the list
*/
struct num {
   int data;       /* data field (number to be sorted) */
   struct num *next; /* points to next element in list */
               /* (NULL pointer if no next element) */
};

/*
* pointer to the first element (the head) of the list
* NULL if there's nothing in the list
*/
struct num *head = NULL;

/*
* create a new node
* and initialize the two fields
*/
struct num *createnode(int n)
{
   struct num *p;       /* pointer to new space */

   /* create the element, reporting errors */
   if ((p = (struct num *) malloc(sizeof(struct num))) == NULL)
       return(NULL);

   /* initialize the element */
   p->data = n;
   p->next = NULL;

   /* return a pointer to the new entity */
   return(p);
}

/*
* insert the element that new points to into the linked list,
* and return a pointer to the (possibly new) head of the list
*/
struct num *insert(struct num *new)
{
   struct num *prev, *temp;

   /* empty list: put head at the front */
   if (head == NULL)
       return(new);

   /* it goes before the first element */
   if (head->data > new->data){
       new->next = head;
       return(new);
   }

   /*
   * now walk the list
   * from here on in, prev->next == temp
   * we'll insert after prev and before temp
   */
   prev = head;
   temp = head->next;
   while(temp != NULL && temp->data < new->data){
       /* advance prev and temp */
       prev = temp;
       temp = temp->next;
   }

   /*
   * here's the insertion
   * make prev->nect the new element
   * and new->next the one temp points to
   */
   new->next = temp;
   prev->next = new;

   /* return the pointer to the head of the list */
   return(head);
}

/*
* the main routine
* read in numbers and sort them
*/
int main(void)
{
   int i;       /* number of numbers read by scanf */
   int n;       /* what scanf read */
   struct num *p;   /* pointer to element for linked list */

   /*
   * loop through the input
   */
   while((i = scanf("%d", &n)) != EOF){

       /* error check; was a number read? */
       if (i == 0){
           /* no; give error and print rest of line */
           fprintf(stderr, "illegal number: ");
           while((i = getchar()) != EOF && i != ' ')
               fputc(i, stderr);
           fputc(' ', stderr);
           continue;
       }

       /* create a new node, and give error on failure */
       if ((p = createnode(n)) == NULL){
           fprintf(stderr,
               "no more memory on input %d ", n);
           exit(1);
       }

       /* insert new element into linked list */
       head = insert(p);
   }

   /* skip to next line, for cleaner output */
   putchar(' ');

   /*
   * print the list
   * start at head, print data field of each element
   * and go on to the next
   */
   for(p = head; p != NULL; p = p->next)
       printf("%d ", p->data);

   /* bye-bye */
   exit(0);
}

Explanation / Answer

#define FALSE 0 #define TRUE 1 typedef struct element element; struct element { element *next, *prev; int i; }; int cmp(element *a, element *b) { return a->i - b->i; } /* * This is the actual sort function. Notice that it returns the new * head of the list. (It has to, because the head will not * generally be the same element after the sort.) So unlike sorting * an array, where you can do * * sort(myarray); * * you now have to do * * list = listsort(mylist); */ element *listsort(element *list, int is_circular, int is_double) { element *p, *q, *e, *tail, *oldhead; int insize, nmerges, psize, qsize, i; /* * Silly special case: if `list' was passed in as NULL, return * NULL immediately. */ if (!list) return NULL; insize = 1; while (1) { p = list; oldhead = list; /* only used for circular linkage */ list = NULL; tail = NULL; nmerges = 0; /* count number of merges we do in this pass */ while (p) { nmerges++; /* there exists a merge to be done */ /* step `insize' places along from p */ q = p; psize = 0; for (i = 0; i next == oldhead ? NULL : q->next); else q = q->next; if (!q) break; } /* if q hasn't fallen off end, we have two lists to merge */ qsize = insize; /* now we have two lists; merge them */ while (psize > 0 || (qsize > 0 && q)) { /* decide whether next element of merge comes from p or q */ if (psize == 0) { /* p is empty; e must come from q. */ e = q; q = q->next; qsize--; if (is_circular && q == oldhead) q = NULL; } else if (qsize == 0 || !q) { /* q is empty; e must come from p. */ e = p; p = p->next; psize--; if (is_circular && p == oldhead) p = NULL; } else if (cmp(p,q) next; psize--; if (is_circular && p == oldhead) p = NULL; } else { /* First element of q is lower; e must come from q. */ e = q; q = q->next; qsize--; if (is_circular && q == oldhead) q = NULL; } /* add the next element to the merged list */ if (tail) { tail->next = e; } else { list = e; } if (is_double) { /* Maintain reverse pointers in a doubly linked list. */ e->prev = tail; } tail = e; } /* now p has stepped `insize' places along, and q has too */ p = q; } if (is_circular) { tail->next = list; if (is_double) list->prev = tail; } else tail->next = NULL; /* If we have done only one merge, we're finished. */ if (nmerges prev != p) printf(" [REVERSE LINK ERROR!]"); } p = p->next; } while (is_circular ? (p != head) : (p != NULL)); printf(" "); head = listsort(head, is_circular, is_double); printf(" after:"); p = head; do { printf(" %d", p->i); if (is_double) { if (p->next && p->next->prev != p) printf(" [REVERSE LINK ERROR!]"); } p = p->next; } while (is_circular ? (p != head) : (p != NULL)); printf(" "); } } } return 0; } This code can handle singly and doubly linked lists, and circular and linear lists too. For any serious application, you'll probably want to remove the conditionals on `is_circular' and `is_double' to adapt the code to your own purpose. #include #include struct node { struct node *prev; int n; struct node *next; }*h,*temp,*temp1,*temp2,*temp4; void insert1(); void insert2(); void insert3(); void traversebeg(); void traverseend(int); void sort(); void search(); void update(); void delete(); int count = 0; void main() { int ch; h = NULL; temp = temp1 = NULL; printf(" 1 - Insert at beginning"); printf(" 2 - Insert at end"); printf(" 3 - Insert at position i"); printf(" 4 - Delete at i"); printf(" 5 - Display from beginning"); printf(" 6 - Display from end"); printf(" 7 - Search for element"); printf(" 8 - Sort the list"); printf(" 9 - Update an element"); printf(" 10 - Exit"); while (1) { printf(" Enter choice : "); scanf("%d", &ch); switch (ch) { case 1: insert1(); break; case 2: insert2(); break; case 3: insert3(); break; case 4: delete(); break; case 5: traversebeg(); break; case 6: temp2 = h; if (temp2 == NULL) printf(" Error : List empty to display "); else { printf(" Reverse order of linked list is : "); traverseend(temp2->n); } break; case 7: search(); break; case 8: sort(); break; case 9: update(); break; case 10: exit(0); default: printf(" Wrong choice menu"); } } } /* TO create an empty node */ void create() { int data; temp =(struct node *)malloc(1*sizeof(struct node)); temp->prev = NULL; temp->next = NULL; printf(" Enter value to node : "); scanf("%d", &data); temp->n = data; count++; } /* TO insert at beginning */ void insert1() { if (h == NULL) { create(); h = temp; temp1 = h; } else { create(); temp->next = h; h->prev = temp; h = temp; } } /* To insert at end */ void insert2() { if (h == NULL) { create(); h = temp; temp1 = h; } else { create(); temp1->next = temp; temp->prev = temp1; temp1 = temp; } } /* To insert at any position */ void insert3() { int pos, i = 2; printf(" Enter position to be inserted : "); scanf("%d", &pos); temp2 = h; if ((pos < 1) || (pos >= count + 1)) { printf(" Position out of range to insert"); return; } if ((h == NULL) && (pos != 1)) { printf(" Empty list cannot insert other than 1st position"); return; } if ((h == NULL) && (pos == 1)) { create(); h = temp; temp1 = h; return; } else { while (i next; i++; } create(); temp->prev = temp2; temp->next = temp2->next; temp2->next->prev = temp; temp2->next = temp; } } /* To delete an element */ void delete() { int i = 1, pos; printf(" Enter position to be deleted : "); scanf("%d", &pos); temp2 = h; if ((pos < 1) || (pos >= count + 1)) { printf(" Error : Position out of range to delete"); return; } if (h == NULL) { printf(" Error : Empty list no elements to delete"); return; } else { while (i next; i++; } if (i == 1) { if (temp2->next == NULL) { printf("Node deleted from list"); free(temp2); temp2 = h = NULL; return; } } if (temp2->next == NULL) { temp2->prev->next = NULL; free(temp2); printf("Node deleted from list"); return; } temp2->next->prev = temp2->prev; if (i != 1) temp2->prev->next = temp2->next; /* Might not need this statement if i == 1 check */ if (i == 1) h = temp2->next; printf(" Node deleted"); free(temp2); } count--; } /* Traverse from beginning */ void traversebeg() { temp2 = h; if (temp2 == NULL) { printf("List empty to display "); return; } printf(" Linked list elements from begining : "); while (temp2->next != NULL) { printf(" %d ", temp2->n); temp2 = temp2->next; } printf(" %d ", temp2->n); } /* To traverse from end recursively */ void traverseend(int i) { if (temp2 != NULL) { i = temp2->n; temp2 = temp2->next; traverseend(i); printf(" %d ", i); } } /* To search for an element in the list */ void search() { int data, count = 0; temp2 = h; if (temp2 == NULL) { printf(" Error : List empty to search for data"); return; } printf(" Enter value to search : "); scanf("%d", &data); while (temp2 != NULL) { if (temp2->n == data) { printf(" Data found in %d position",count + 1); return; } else temp2 = temp2->next; count++; } printf(" Error : %d not found in list", data); } /* To update a node value in the list */ void update() { int data, data1; printf(" Enter node data to be updated : "); scanf("%d", &data); printf(" Enter new data : "); scanf("%d", &data1); temp2 = h; if (temp2 == NULL) { printf(" Error : List empty no node to update"); return; } while (temp2 != NULL) { if (temp2->n == data) { temp2->n = data1; traversebeg(); return; } else temp2 = temp2->next; } printf(" Error : %d not found in list to update", data); } /* To sort the linked list */ void sort() { int i, j, x; temp2 = h; temp4 = h; if (temp2 == NULL) { printf(" List empty to sort"); return; } for (temp2 = h; temp2 != NULL; temp2 = temp2->next) { for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next) { if (temp2->n > temp4->n) { x = temp2->n; temp2->n = temp4->n; temp4->n = x; } } } traversebeg(); }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.