API tools faq
paste
veselinsavov

C singly linked lists

veselinsavov
May 14th, 2015
263
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 9.92 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <alloc.h>
  3. #include <stdlib.h>
  4. #include <conio.h>
  5. #include <ctype.h>
  6. #include <string.h>
  7.  
  8. /* function prototypes */
  9. struct node * initnode( char *, int );
  10. void printnode( struct node * );
  11. void printlist( struct node * );
  12. void add( struct node * );
  13. struct node * searchname( struct node *, char * );
  14. void deletenode( struct node * );
  15. void insertnode( struct node * );
  16. void deletelist( struct node * );
  17.  
  18. /* definition of a data node for holding student information */
  19. struct node {
  20.    char name[20];
  21.    int  id;
  22.    struct node *next;
  23. };
  24.  
  25. /* head points to first node in list, end points to last node in list */
  26. /* initialise both to NULL, meaning no nodes in list yet */
  27. struct node *head = (struct node *) NULL;
  28. struct node *end = (struct node *) NULL;
  29.  
  30. /* this initialises a node, allocates memory for the node, and returns   */
  31. /* a pointer to the new node. Must pass it the node details, name and id */
  32. struct node * initnode( char *name, int id )
  33. {
  34.    struct node *ptr;
  35.    ptr = (struct node *) calloc( 1, sizeof(struct node ) );
  36.    if( ptr == NULL )                       /* error allocating node?      */
  37.        return (struct node *) NULL;        /* then return NULL, else      */
  38.    else {                                  /* allocated node successfully */
  39.        strcpy( ptr->name, name );          /* fill in name details        */
  40.        ptr->id = id;                       /* copy id details             */
  41.        return ptr;                         /* return pointer to new node  */
  42.    }
  43. }
  44.  
  45. /* this prints the details of a node, eg, the name and id                 */
  46. /* must pass it the address of the node you want to print out             */
  47. void printnode( struct node *ptr )
  48. {
  49.    printf("Name ->%s\n", ptr->name );
  50.    printf("ID   ->%d\n", ptr->id );
  51. }
  52.  
  53. /* this prints all nodes from the current address passed to it. If you    */
  54. /* pass it 'head', then it prints out the entire list, by cycling through */
  55. /* each node and calling 'printnode' to print each node found             */
  56. void printlist( struct node *ptr )
  57. {
  58.    while( ptr != NULL )           /* continue whilst there are nodes left */
  59.    {
  60.       printnode( ptr );           /* print out the current node           */
  61.       ptr = ptr->next;            /* goto the next node in the list       */
  62.    }
  63. }
  64.  
  65. /* this adds a node to the end of the list. You must allocate a node and  */
  66. /* then pass its address to this function                                 */
  67. void add( struct node *new )  /* adding to end of list */
  68. {
  69.    if( head == NULL )      /* if there are no nodes in list, then         */
  70.        head = new;         /* set head to this new node                   */
  71.    end->next = new;        /* link in the new node to the end of the list */
  72.    new->next = NULL;       /* set next field to signify the end of list   */
  73.    end = new;              /* adjust end to point to the last node        */
  74. }
  75.  
  76. /* search the list for a name, and return a pointer to the found node     */
  77. /* accepts a name to search for, and a pointer from which to start. If    */
  78. /* you pass the pointer as 'head', it searches from the start of the list */
  79. struct node * searchname( struct node *ptr, char *name )
  80. {
  81.     while( strcmp( name, ptr->name ) != 0 ) {    /* whilst name not found */
  82.        ptr = ptr->next;                          /* goto the next node    */
  83.        if( ptr == NULL )                         /* stop if we are at the */
  84.           break;                                 /* of the list           */
  85.     }
  86.     return ptr;                                  /* return a pointer to   */
  87. }                                                /* found node or NULL    */
  88.  
  89. /* deletes the specified node pointed to by 'ptr' from the list           */
  90. void deletenode( struct node *ptr )
  91. {
  92.    struct node *temp, *prev;
  93.    temp = ptr;    /* node to be deleted */
  94.    prev = head;   /* start of the list, will cycle to node before temp    */
  95.  
  96.    if( temp == prev ) {                    /* are we deleting first node  */
  97.        head = head->next;                  /* moves head to next node     */
  98.        if( end == temp )                   /* is it end, only one node?   */
  99.           end = end->next;                 /* adjust end as well          */
  100.        free( temp );                       /* free space occupied by node */
  101.    }
  102.    else {                                  /* if not the first node, then */
  103.        while( prev->next != temp ) {       /* move prev to the node before*/
  104.            prev = prev->next;              /* the one to be deleted       */
  105.        }
  106.        prev->next = temp->next;            /* link previous node to next  */
  107.        if( end == temp )                   /* if this was the end node,   */
  108.            end = prev;                     /* then reset the end pointer  */
  109.        free( temp );                       /* free space occupied by node */
  110.    }
  111. }
  112.  
  113. /* inserts a new node, uses name field to align node as alphabetical list */
  114. /* pass it the address of the new node to be inserted, with details all   */
  115. /* filled in                                                              */
  116. void insertnode( struct node *new )
  117. {
  118.    struct node *temp, *prev;                /* similar to deletenode      */
  119.  
  120.    if( head == NULL ) {                     /* if an empty list,          */
  121.        head = new;                          /* set 'head' to it           */
  122.        end = new;
  123.        head->next = NULL;                   /* set end of list to NULL    */
  124.        return;                              /* and finish                 */
  125.    }
  126.  
  127.    temp = head;                             /* start at beginning of list */
  128.                       /* whilst currentname < newname to be inserted then */
  129.    while( strcmp( temp->name, new->name) < 0 ) {
  130.           temp = temp->next;                /* goto the next node in list */
  131.           if( temp == NULL )                /* dont go past end of list   */
  132.               break;
  133.    }
  134.  
  135.    /* we are the point to insert, we need previous node before we insert  */
  136.    /* first check to see if its inserting before the first node!          */
  137.    if( temp == head ) {
  138.       new->next = head;             /* link next field to original list   */
  139.       head = new;                   /* head adjusted to new node          */
  140.    }
  141.    else {     /* okay, so its not the first node, a different approach    */
  142.       prev = head;   /* start of the list, will cycle to node before temp */
  143.       while( prev->next != temp ) {
  144.           prev = prev->next;
  145.       }
  146.       prev->next = new;             /* insert node between prev and next  */
  147.       new->next = temp;
  148.       if( end == prev )             /* if the new node is inserted at the */
  149.          end = new;                 /* end of the list the adjust 'end'   */
  150.    }
  151. }
  152.  
  153. /* this deletes all nodes from the place specified by ptr                 */
  154. /* if you pass it head, it will free up entire list                       */
  155. void deletelist( struct node *ptr )
  156. {
  157.    struct node *temp;
  158.  
  159.    if( head == NULL ) return;   /* dont try to delete an empty list       */
  160.  
  161.    if( ptr == head ) {      /* if we are deleting the entire list         */
  162.        head = NULL;         /* then reset head and end to signify empty   */
  163.        end = NULL;          /* list                                       */
  164.    }
  165.    else {
  166.        temp = head;          /* if its not the entire list, readjust end  */
  167.        while( temp->next != ptr )         /* locate previous node to ptr  */
  168.            temp = temp->next;
  169.        end = temp;                        /* set end to node before ptr   */
  170.    }
  171.  
  172.    while( ptr != NULL ) {   /* whilst there are still nodes to delete     */
  173.       temp = ptr->next;     /* record address of next node                */
  174.       free( ptr );          /* free this node                             */
  175.       ptr = temp;           /* point to next node to be deleted           */
  176.    }
  177. }
  178.  
  179. /* this is the main routine where all the glue logic fits                 */
  180. int main()
  181. {
  182.    char name[20];
  183.    int id, ch = 1;
  184.    struct node *ptr;
  185.  
  186.    clrscr();
  187.    while( ch != 0 ) {
  188.       printf("1 add a name \n");
  189.       printf("2 delete a name \n");
  190.       printf("3 list all names \n");
  191.       printf("4 search for name \n");
  192.       printf("5 insert a name \n");
  193.       printf("0 quit\n");
  194.       scanf("%d", &ch );
  195.       switch( ch )
  196.       {
  197.           case 1:  /* add a name to end of list */
  198.                    printf("Enter in name -- ");
  199.                    scanf("%s", name );
  200.                    printf("Enter in id -- ");
  201.                    scanf("%d", &id );
  202.                    ptr = initnode( name, id );
  203.                    add( ptr );
  204.                    break;
  205.           case 2:  /* delete a name */
  206.                    printf("Enter in name -- ");
  207.                    scanf("%s", name );
  208.                    ptr = searchname( head, name );
  209.                    if( ptr ==NULL ) {
  210.                        printf("Name %s not found\n", name );
  211.                    }
  212.                    else
  213.                       deletenode( ptr );
  214.                    break;
  215.  
  216.           case 3:  /* list all nodes */
  217.                    printlist( head );
  218.                    break;
  219.  
  220.           case 4:  /* search and print name */
  221.                    printf("Enter in name -- ");
  222.                    scanf("%s", name );
  223.                    ptr = searchname( head, name );
  224.                    if( ptr ==NULL ) {
  225.                        printf("Name %s not found\n", name );
  226.                    }
  227.                    else
  228.                       printnode( ptr );
  229.                    break;
  230.           case 5:  /* insert a name in list */
  231.                    printf("Enter in name -- ");
  232.                    scanf("%s", name );
  233.                    printf("Enter in id -- ");
  234.                    scanf("%d", &id );
  235.                    ptr = initnode( name, id );
  236.                    insertnode( ptr );
  237.                    break;
  238.  
  239.       }
  240.    }
  241.    deletelist( head );
  242. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!