home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pctchnqs / 1992 / number1 / l6.c < prev    next >
Text File  |  1992-01-24  |  3KB  |  74 lines
  1. /*
  2. Suite of functions for maintaining a linked list sorted by
  3. ascending order of the Value field. The list is circular; that is,
  4. it has a dummy node as both the head and the tail of the list.
  5. The dummy node is a sentinel, containing the largest possible
  6. Value field setting. Tested with Borland C++ 3.0 in C mode. */
  7.  
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include "llist.h"
  12.  
  13. /* Initializes an empty linked list of LinkNode structures,
  14.    consisting of a single head/tail/sentinel node, and returns a
  15.    pointer to the list. Returns NULL for failure. */
  16. struct LinkNode *InitLinkedList()
  17. {
  18.    struct LinkNode *Sentinel;
  19.  
  20.    if ((Sentinel = malloc(sizeof(struct LinkNode))) == NULL)
  21.       return(NULL);
  22.  
  23.    Sentinel->NextNode = Sentinel;
  24.    Sentinel->Value = SENTINEL;
  25.    strcpy(Sentinel->Text, "*** sentinel ***");
  26.    return(Sentinel);
  27. }
  28.  
  29. /* Finds the first node in a value-sorted linked list with a value
  30.    field equal to a key value, and returns a pointer to the node
  31.    preceding that node (to facilitate insertion and deletion), or a
  32.    NULL pointer if no such value was found. Assumes the list is
  33.    terminated with a sentinel node containing the largest possible
  34.    value. */
  35. struct LinkNode *FindNodeBeforeValue(struct LinkNode *HeadOfListNode,
  36.    int SearchValue)
  37. {
  38.    struct LinkNode *NodePtr = HeadOfListNode;
  39.  
  40.    while (NodePtr->NextNode->Value < SearchValue)
  41.       NodePtr = NodePtr->NextNode;
  42.  
  43.    if (NodePtr->NextNode->Value == SearchValue) {
  44.       /* Found the search value; success unless we found the
  45.          sentinel (can happen only if SearchValue == SENTINEL) */
  46.       if (NodePtr->NextNode == HeadOfListNode) {
  47.          return(NULL);     /* failure; we found the sentinel */
  48.       } else {
  49.          return(NodePtr);  /* success; return pointer to node
  50.                               preceding the node that was equal */
  51.       }
  52.    } else {
  53.       /* No match; return failure status */
  54.       return(NULL);
  55.    }
  56. }
  57.  
  58. /* Inserts the specified node into a value-sorted linked list, such
  59.    that value-sorting is maintained. Returns a pointer to the node
  60.    after which the new node is inserted. */
  61. struct LinkNode *InsertNodeSorted(struct LinkNode *HeadOfListNode,
  62.    struct LinkNode *NodeToInsert)
  63. {
  64.    struct LinkNode *NodePtr = HeadOfListNode;
  65.    int SearchValue = NodeToInsert->Value;
  66.  
  67.    while (NodePtr->NextNode->Value < SearchValue)
  68.       NodePtr = NodePtr->NextNode;
  69.  
  70.    NodeToInsert->NextNode = NodePtr->NextNode;
  71.    NodePtr->NextNode = NodeToInsert;
  72.    return(NodePtr);
  73. }
  74.