C RSS C RSS

Double-linked list in contiguous memory.

Reply

•
•
Join Date: Oct 2006
Posts: 18
Reputation: tehloki is an unknown quantity at this point 
Solved Threads: 0
tehloki tehloki is offline Offline
Newbie Poster

Double-linked list in contiguous memory.

 
0
  #1
Oct 3rd, 2007
I'm trying to implement a Double-Linked List ADT in an array (contiguous memory only, no dynamic allocation at runtime). So far, all my code does is generate a seg fault whenever I try and add a new element. Here's the whole ADT, if anybody feels like looking over it.

FILE: CELEMENT.H

C Syntax (Toggle Plain Text) 
  1. /*
  2.  * ------------------------------------------------------------------
  3.  *    Element.h - Element ADT prototypes/data declarations
  4.  *
  5.  *    Author: David McCaughan (1995, CIS2520 revision 2006)
  6.  * ------------------------------------------------------------------
  7.  */
  8.  
  9. #ifndef ELEMENT_H
  10. #define ELEMENT_H
  11.  
  12.  
  13. /*
  14.  * --- TYPE: Element -------------------------------------------------------
  15.  *    Component element in 2-way linked data structures
  16.  * -------------------------------------------------------------------------
  17.  */
  18. typedef struct Element_t
  19. {
  20.     void            *data;        /* reference to data */
  21.     int         left;        /* reference to index of previous/left element */
  22.     int         right;    /* reference to index of next/right element */
  23. } Element;
  24.  
  25.  
  26. /* --- file: Element.c --- */
  27.  
  28. Element * elementCreate   (Element *, void *);
  29. int       elementDelete   (Element *);
  30. void    * elementGetData  (Element *);
  31. void    * elementSetData  (Element *, void *);
  32. int       elementGetLeft  (Element *);
  33. int       elementGetRight (Element *);
  34. void      elementSetLeft  (Element *, int);
  35. void      elementSetRight (Element *, int);
  36.  
  37.  
  38. #endif

FILE: CELEMENT.C

C Syntax (Toggle Plain Text) 
  1. /*
  2.  * ------------------------------------------------------------------
  3.  *    Element.c - Element ADT implementation
  4.  *
  5.  *    Author: David McCaughan (1995, CIS*2520 revision 2006)
  6.  * ------------------------------------------------------------------
  7.  */
  8.  
  9. #include <stdlib.h>
  10. #include <stdio.h>
  11. #include "CElement.h"
  12.  
  13.  
  14. /*
  15.  * ---------------------------------------------------------
  16.  *    elementCreate
  17.  *        - Creates new element, initializing contents to
  18.  *          be a reference to the provided data
  19.  * ---------------------------------------------------------
  20.  *    PRE:
  21.  *        n/a
  22.  * ---------------------------------------------------------
  23.  *  POST:
  24.  *        new element is allocated and initialized; returns a
  25.  *        reference to the new element
  26.  * ---------------------------------------------------------
  27.  *    ERRORS:
  28.  *        NULL : memory allocation failure (allocation)
  29.  * ---------------------------------------------------------
  30.  */
  31. Element *elementCreate(Element *new, void *data)
  32. {
  33.     new->data = data;
  34.  
  35.     return(new);
  36.  
  37. } /* elementCreate */
  38.  
  39.  
  40.  
  41. /*
  42.  * ---------------------------------------------------------
  43.  *    elementDelete
  44.  *        - De-allocate memory associated with element
  45.  *          provided
  46.  * ---------------------------------------------------------
  47.  *    PRE:
  48.  *        void
  49.  * ---------------------------------------------------------
  50.  *  POST:
  51.  *        this element is destroyed; returns 0 if this was
  52.  *        NULL, 1 otherwise
  53.  * ---------------------------------------------------------
  54.  *    ERRORS:
  55.  *        void
  56.  * ---------------------------------------------------------
  57.  */
  58. int elementDelete(Element *this)
  59. {
  60.     if (this)
  61.     {
  62.         this->left=-1;
  63.         this->right=-1;
  64.         return(1);
  65.     }
  66.     else
  67.         return(0);
  68.  
  69. } /* elementDelete */
  70.  
  71.  
  72.  
  73. /*
  74.  * ---------------------------------------------------------
  75.  *    elementGetData
  76.  *        - Obtain reference to the data stored in provided
  77.  *          element
  78.  * ---------------------------------------------------------
  79.  *    PRE:
  80.  *        void
  81.  * ---------------------------------------------------------
  82.  *  POST:
  83.  *        returns value of data
  84.  * ---------------------------------------------------------
  85.  *    ERRORS:
  86.  *        void
  87.  * ---------------------------------------------------------
  88.  */
  89. void *elementGetData(Element *this)
  90. {
  91.     return(this->data);
  92.  
  93. } /* elementGetData */
  94.  
  95.  
  96. /*
  97.  * ---------------------------------------------------------
  98.  *    elementSetData
  99.  *        - Reassign reference to the data stored in provided
  100.  *          element
  101.  * ---------------------------------------------------------
  102.  *    PRE:
  103.  *        void
  104.  * ---------------------------------------------------------
  105.  *  POST:
  106.  *        returns previous (overwritten) value of data
  107.  * ---------------------------------------------------------
  108.  *    ERRORS:
  109.  *        void
  110.  * ---------------------------------------------------------
  111.  */
  112. void *elementSetData(Element *this, void *data)
  113. {
  114.     void *save;
  115.  
  116.     save = this->data;
  117.     this->data = data;
  118.  
  119.     return(save);
  120.  
  121. } /* elementSetData */
  122.  
  123.  
  124.  
  125. /*
  126.  * ---------------------------------------------------------
  127.  *    elementGetLeft
  128.  *        - Obtain left reference of the provided element
  129.  * ---------------------------------------------------------
  130.  *    PRE:
  131.  *        void
  132.  * ---------------------------------------------------------
  133.  *  POST:
  134.  *        returns value of left
  135.  * ---------------------------------------------------------
  136.  *    ERRORS:
  137.  *        void
  138.  * ---------------------------------------------------------
  139.  */
  140. int elementGetLeft(Element *this)
  141. {
  142.     return(this->left);
  143.  
  144. } /* elementGetLeft */
  145.  
  146.  
  147.  
  148. /*
  149.  * ---------------------------------------------------------
  150.  *    elementGetRight
  151.  *        - Obtain right reference of the provided element
  152.  * ---------------------------------------------------------
  153.  *    PRE:
  154.  *        void
  155.  * ---------------------------------------------------------
  156.  *  POST:
  157.  *        returns value of right
  158.  * ---------------------------------------------------------
  159.  *    ERRORS:
  160.  *        void
  161.  * ---------------------------------------------------------
  162.  */
  163. int elementGetRight(Element *this)
  164. {
  165.     return(this->right);
  166.  
  167. } /* elementGetRight */
  168.  
  169.  
  170.  
  171. /*
  172.  * ---------------------------------------------------------
  173.  *    elementSetLeft
  174.  *        - Set left element reference of provided element
  175.  * ---------------------------------------------------------
  176.  *    PRE:
  177.  *        void
  178.  * ---------------------------------------------------------
  179.  *  POST:
  180.  *        left is assigned provided reference
  181.  * ---------------------------------------------------------
  182.  *    ERRORS:
  183.  *        void
  184.  * ---------------------------------------------------------
  185.  */
  186. void elementSetLeft(Element *this, int ref)
  187. {
  188.     this->left = ref;
  189.  
  190. } /* elementSetLeft */
  191.  
  192.  
  193.  
  194. /*
  195.  * ---------------------------------------------------------
  196.  *    elementSetRight
  197.  *        - Set right element reference of provided element
  198.  * ---------------------------------------------------------
  199.  *    PRE:
  200.  *        void
  201.  * ---------------------------------------------------------
  202.  *  POST:
  203.  *        right is assigned provided reference
  204.  * ---------------------------------------------------------
  205.  *    ERRORS:
  206.  *        void
  207.  * ---------------------------------------------------------
  208.  */
  209. void elementSetRight(Element *this, int ref)
  210. {
  211.     this->right = ref;
  212.  
  213. } /* elementSetRight */

FILE: CLIST.H

C Syntax (Toggle Plain Text) 
  1. /*
  2.  * ------------------------------------------------------------------
  3.  *    List.h - List ADT prototypes/data declarations
  4.  *
  5.  *    Author: David McCaughan (1995, CIS*2520 revision 2006)
  6.  * ------------------------------------------------------------------
  7.  */
  8.  
  9. #ifndef LIST_H
  10. #define LIST_H
  11.  
  12.  
  13. #include <stdio.h>
  14. #include "CElement.h"
  15.  
  16.  
  17. /*
  18.  * --- TYPE: List ----------------------------------------------------------
  19.  *    A set of objects stored in a 2-way chained linear sequence
  20.  * -------------------------------------------------------------------------
  21.  */
  22. typedef struct List_t
  23. {
  24.     int     element_count;        /* number of elements in list */
  25.     int     position;            /* current (numeric) position in list */
  26.     Element elements[1000];            /* list of elements */
  27.     Element *current;            /* current element */
  28. } List;
  29.  
  30.  
  31. /* --- file: List.c --- */
  32.  
  33. List * listCreate     (void);
  34. int    listDelete     (List *);
  35. int    listClear      (List *);
  36. List * listHead       (List *);
  37. List * listTail       (List *);
  38. List * listPrev       (List *);
  39. List * listNext       (List *);
  40. List * listMoveToNth  (List *, int);
  41. List * listAddAfter   (List *, void *);
  42. List * listAddBefore  (List *, void *);
  43. void * listGetCurrent (List *);
  44. void * listSetCurrent (List *, void *);
  45. void * listDelCurrent (List *);
  46. int    listIsEmpty    (List *);
  47. int    listLength     (List *);
  48. int    listPosition   (List *);
  49.  
  50.  
  51. #endif

FILE: CLIST.C

C Syntax (Toggle Plain Text) 
  1. /*
  2.  * ------------------------------------------------------------------
  3.  *    List.c - List ADT implementation
  4.  *
  5.  *    Author: David McCaughan (1995, CIS*2520 revision 2006)
  6.  * ------------------------------------------------------------------
  7.  */
  8.  
  9. #include <stdlib.h>
  10. #include <stdio.h>
  11. #include "CList.h"
  12. #include "CElement.h"
  13.  
  14.  
  15. /*
  16.  * ---------------------------------------------------------
  17.  *    listCreate
  18.  *        - Create new list initialized to empty
  19.  * ---------------------------------------------------------
  20.  *    PRE:
  21.  *        void
  22.  * ---------------------------------------------------------
  23.  *    POST:
  24.  *        new list is allocated and initialized; returns a
  25.  *        reference to new list
  26.  * ---------------------------------------------------------
  27.  *    ERRORS:
  28.  *        NULL : memory allocation failure (allocation)
  29.  * ---------------------------------------------------------
  30.  */
  31. List *listCreate(void)
  32. {
  33.     int x=0;
  34.  
  35.     List *new = NULL;        /* new list */
  36.  
  37.     if (!(new = calloc(1,sizeof(List))))
  38.         return(NULL);
  39.  
  40.     new->element_count = 0;
  41.     new->position = 0;
  42.     for (x=0; x<1000; x++)
  43.     {
  44.         new->elements[x].left=-1;
  45.         new->elements[x].right=-1;
  46.     }
  47.     new->current = NULL;
  48.  
  49.     return(new);
  50.  
  51. } /* listCreate */
  52.  
  53.  
  54.  
  55. /*
  56.  * ---------------------------------------------------------
  57.  *    listDelete
  58.  *        - De-allocate all memory associated with provided
  59.  *          list object
  60.  * ---------------------------------------------------------
  61.  *    PRE:
  62.  *        void
  63.  * ---------------------------------------------------------
  64.  *    POST:
  65.  *        this list is destroyed; returns number of elements
  66.  *        that were in the list
  67.  * ---------------------------------------------------------
  68.  *    ERRORS:
  69.  *        void
  70.  * ---------------------------------------------------------
  71.  */
  72. int listDelete(List *this)
  73. {
  74.     int retval = 0;        /* return value */
  75.  
  76.     if (this)
  77.     {
  78.         retval = listClear(this);
  79.         free(this);
  80.     }
  81.  
  82.     return(retval);
  83.  
  84. } /* listDelete */
  85.  
  86.  
  87.  
  88. /*
  89.  * ---------------------------------------------------------
  90.  *    listClear
  91.  *        - De-allocate all memory associated with element
  92.  *          structures of provided list, resetting state of
  93.  *          list to empty
  94.  * ---------------------------------------------------------
  95.  *    PRE:
  96.  *        void
  97.  * ---------------------------------------------------------
  98.  *    POST:
  99.  *        this list is empty; returns number of elements that
  100.  *        were in the list
  101.  * ---------------------------------------------------------
  102.  *    ERRORS:
  103.  *        void
  104.  * ---------------------------------------------------------
  105.  */
  106. int listClear(List *this)
  107. {
  108.     int i;            /* loop index */
  109.     int retval;        /* return value */
  110.  
  111.     /*
  112.      * de-allocate element memory
  113.      */
  114.     if (this->elements)
  115.     {
  116.         for (i = 0; i < 1000; i++)
  117.         {
  118.             this->elements[i].left=-1;
  119.             this->elements[i].right=-1;
  120.         }
  121.     }
  122.  
  123.     /*
  124.      * save number of elements in list then reset to empty
  125.      */
  126.     this->element_count = 0;
  127.     retval = this->element_count;
  128.     this->position = 0;
  129.     this->current = NULL;
  130.  
  131.     return(retval);
  132.  
  133. } /* listClear */
  134.  
  135.  
  136.  
  137. /*
  138.  * ---------------------------------------------------------
  139.  *    listHead
  140.  *        - Adjust position to the beginning of provided list
  141.  *        - NOTE: this operation is non-destructive on an
  142.  *          empty list
  143.  * ---------------------------------------------------------
  144.  *    PRE:
  145.  *        list is non-empty
  146.  * ---------------------------------------------------------
  147.  *    POST:
  148.  *        current & position reference the first element in
  149.  *        this list; returns a reference to this
  150.  * ---------------------------------------------------------
  151.  *    ERRORS:
  152.  *        NULL : list is empty
  153.  * ---------------------------------------------------------
  154.  */
  155. List *listHead(List *this)
  156. {
  157.     if (this->elements != NULL)
  158.     {
  159.         this->current = &this->elements[0];
  160.         this->position = 1;
  161.         return(this);
  162.     }
  163.     else
  164.         return(NULL);
  165.  
  166. } /* listHead */
  167.  
  168.  
  169.  
  170. /*
  171.  * ---------------------------------------------------------
  172.  *    listTail
  173.  *        - Adjust position to the end of provided list
  174.  *        - NOTE: this operation is non-destructive on an
  175.  *          empty list
  176.  * ---------------------------------------------------------
  177.  *    PRE:
  178.  *        list is non-empty
  179.  * ---------------------------------------------------------
  180.  *    POST:
  181.  *        current & position reference the last element in
  182.  *        this list; returns a reference to this
  183.  * ---------------------------------------------------------
  184.  *    ERRORS:
  185.  *        NULL : list is empty
  186.  * ---------------------------------------------------------
  187.  */
  188. List *listTail(List *this)
  189. {
  190.     if (this->elements != NULL)
  191.     {
  192.         this->current = &this->elements[elementGetLeft(this->elements)];
  193.         this->position = this->element_count;
  194.         return(this);
  195.     }    
  196.     else
  197.         return(NULL);
  198.  
  199. } /* listTail */
  200.  
  201.  
  202.  
  203. /*
  204.  * ---------------------------------------------------------
  205.  *    listPrev
  206.  *        - Move the the previous element in the provided list
  207.  * ---------------------------------------------------------
  208.  *    PRE:
  209.  *        list is non-empty; list is not positioned at the
  210.  *        first element
  211.  * ---------------------------------------------------------
  212.  *    POST:
  213.  *        current & postition now reference the element
  214.  *        preceeding the current one in this list; returns a
  215.  *        reference to this
  216.  * ---------------------------------------------------------
  217.  *    ERRORS:
  218.  *        NULL : list is empty
  219.  *        NULL : already at beginning of list
  220.  * ---------------------------------------------------------
  221.  */
  222. List *listPrev(List *this)
  223. {
  224.     /*
  225.      * note that this explicity covers "at beginning of list", and
  226.      * implicitly covers "empty list", and "single element list" cases.
  227.      */
  228.     if (this->current == &this->elements[0])
  229.         return(NULL);
  230.  
  231.     this->current = &this->elements[elementGetLeft(this->current)];
  232.     this->position--;
  233.  
  234.     return(this);
  235.  
  236. } /* listPrev */
  237.  
  238.  
  239.  
  240. /*
  241.  * ---------------------------------------------------------
  242.  *    listNext
  243.  *        - Move the the next element in the provided list
  244.  * ---------------------------------------------------------
  245.  *    PRE:
  246.  *        list is non-empty; list is not positioned at the
  247.  *        last element
  248.  * ---------------------------------------------------------
  249.  *    POST:
  250.  *        current & position now reference the element
  251.  *        succeeding the current one in this list;  returns 
  252.  *        a reference to this
  253.  * ---------------------------------------------------------
  254.  *    ERRORS:
  255.  *        NULL : list is empty
  256.  *        NULL : already at end of list
  257.  * ---------------------------------------------------------
  258.  */
  259. List *listNext(List *this)
  260. {
  261.     /*
  262.      * must explicitly cover "at end of list" as well as "empty list"
  263.      * and "single element list" cases
  264.      */
  265.     if ((this->position >= this->element_count)
  266.             || (!this->elements) || (this->element_count < 2))
  267.         return(NULL);
  268.  
  269.     this->current = &this->elements[elementGetRight(this->current)];
  270.     this->position++;
  271.  
  272.     return(this);
  273.  
  274. } /* listNext */
  275.  
  276.  
  277.  
  278. /*
  279.  * ---------------------------------------------------------
  280.  *    listMoveToNth
  281.  *        - Move to the "Nth" element in the provide dlist
  282.  *        - NOTE: elements are counted from 1 (not 0)
  283.  * ---------------------------------------------------------
  284.  *    PRE:
  285.  *        0 < n <= element_count
  286.  * ---------------------------------------------------------
  287.  *    POST:
  288.  *        current & position now reference the "Nth" element
  289.  *        in this list; returns a reference to this
  290.  * ---------------------------------------------------------
  291.  *    ERRORS:
  292.  *        NULL : element index out of bounds (index)
  293.  * ---------------------------------------------------------
  294.  */
  295. List *listMoveToNth(List *this, int n)
  296. {
  297.     int i;            /* loop index */
  298.     int offset;        /* offset to new location from current */
  299.     int ofor;        /* forward and ...                           */
  300.     int obak;        /*         ... backward offsets respectively */
  301.  
  302.     /*
  303.      * this should avoid ANY illegal situation (i.e. an "nth" element
  304.      * exists) - excepting destructive user interference
  305.      */
  306.     if ((n < 1) || (n > this->element_count))
  307.         return(NULL);
  308.  
  309.     /*
  310.      * determine offset & direction of pointer movement from current:
  311.      * (adds a couple of arithmetic operations over linear search
  312.      * however may save time if movement is highly localized or a
  313.      * regular progression through the list (i.e. by 2s))
  314.      */
  315.  
  316.     obak = (this->position - n + this->element_count) % this->element_count;
  317.     ofor = (n - this->position + this->element_count) % this->element_count;
  318.     offset = (obak < ofor) ? obak : ofor;
  319.     if (ofor < obak)
  320.         /* move forward */
  321.         for (i = 0; i < offset; i++)
  322.             this->current = &this->elements[elementGetRight(this->current)];
  323.     else
  324.         /* move backward */
  325.         for (i = 0; i < offset; i++)
  326.             this->current = &this->elements[elementGetLeft(this->current)];
  327.  
  328.     this->position = n;
  329.  
  330.     return(this);
  331.  
  332. } /* listMoveToNth */
  333.  
  334.  
  335.  
  336. /*
  337.  * ---------------------------------------------------------
  338.  *    listAddAfter
  339.  *        - Insert a new element containing the provided
  340.  *          data reference in list AFTER current element 
  341.  *        - NOTE: current reference remains unchanged
  342.  * ---------------------------------------------------------
  343.  *    PRE:
  344.  *        void
  345.  * ---------------------------------------------------------
  346.  *    POST:
  347.  *        element containing data reference is inserted into
  348.  *        this list AFTER the current one, or is installed as
  349.  *        the new head of the list if it was emtpy; returns
  350.  *        a reference to this
  351.  * ---------------------------------------------------------
  352.  *    ERRORS:
  353.  *        NULL : new_element() failure
  354.  * ---------------------------------------------------------
  355.  */
  356. List *listAddAfter(List *this, void *data)
  357. {
  358.     int x;
  359.  
  360.     Element *new;        /* new element */
  361.  
  362.     if (!(new = elementCreate(new, data)))
  363.         return(NULL);
  364.  
  365.     /*
  366.      * link into list
  367.      */
  368.     if (!this->elements)
  369.     {
  370.         this->elements[0] = *new;
  371.         this->current = this->elements;
  372.         elementSetLeft(this->current,0);
  373.         elementSetRight(this->current,0);
  374.         this->position++;
  375.     }
  376.     else
  377.     {
  378.         for (x=0; x<1000; x++){
  379.             if ((this->elements[x].left==-1)&&(this->elements[x].right==-1))
  380.             {
  381.                 this->elements[x]=*new;
  382.                 break;
  383.             }
  384.         }
  385.         elementSetLeft(new, elementGetLeft(&this->elements[(elementGetRight(this->current))]));
  386.         elementSetLeft(&this->elements[elementGetRight(this->current)],x);
  387.         elementSetRight(new,elementGetRight(this->current));
  388.         elementSetRight(this->current,x);
  389.     }
  390.     this->element_count++;
  391.  
  392.     return(this);
  393.  
  394. } /* listAddAfter */
  395.  
  396.  
  397.  
  398.  
  399. /*
  400.  * ---------------------------------------------------------
  401.  *    listAddBefore
  402.  *        - Insert a new element containing the provided
  403.  *          data reference in list BEFORE current element 
  404.  *        - NOTE: current reference remains unchanged
  405.  * ---------------------------------------------------------
  406.  *    PRE:
  407.  *        void
  408.  * ---------------------------------------------------------
  409.  *    POST:
  410.  *        element containing data reference is inserted into
  411.  *        this list BEFORE the current one, or is installed as
  412.  *        the new head of the list if it was emtpy; returns
  413.  *        a reference to this
  414.  * ---------------------------------------------------------
  415.  *    ERRORS:
  416.  *        NULL : new_element() failure
  417.  * ---------------------------------------------------------
  418.  */
  419. List *listAddBefore(List *this, void *data)
  420. {
  421.     int x;
  422.  
  423.     Element *new;        /* new element */
  424.  
  425.     if (!(new = elementCreate(new, data)))
  426.         return(NULL);
  427.     /*
  428.      * link into list
  429.      */
  430.     if (!this->elements)
  431.     {
  432.         this->elements[0] = *new;
  433.         this->current = this->elements;
  434.         elementSetLeft(this->current,0);
  435.         elementSetRight(this->current,0);
  436.         this->position++;
  437.     }
  438.     else
  439.     {
  440.         for (x=0; x<1000; x++){
  441.             if ((this->elements[x].left==-1)&&(this->elements[x].right==-1))
  442.             {
  443.                 this->elements[x]=*new;
  444.                 break;
  445.             }
  446.         }
  447.  
  448.         elementSetRight(new, elementGetLeft(&this->elements[(elementGetRight(this->current))]));
  449.         elementSetRight(&this->elements[elementGetLeft(this->current)],x);
  450.         elementSetLeft(new,elementGetLeft(this->current));
  451.         elementSetLeft(this->current,x);
  452.         /*
  453.          * must adjust head of list if addition is at front of list
  454.          */
  455.         if (this->current == &this->elements[0])
  456.             this->elements[0] = *new;
  457.     }
  458.     this->element_count++;
  459.     this->position++;
  460.  
  461.     return(this);
  462.  
  463. } /* listAddBefore */
  464.  
  465.  
  466.  
  467. /*
  468.  * ---------------------------------------------------------
  469.  *    listGetCurrent
  470.  *        - Obtain a reference to data from the current
  471.  *          element data in the provided list
  472.  * ---------------------------------------------------------
  473.  *    PRE:
  474.  *        list is non-empty
  475.  * ---------------------------------------------------------
  476.  *    POST:
  477.  *        returns a reference to the data in the current
  478.  *        element in this list
  479.  * ---------------------------------------------------------
  480.  *    ERRORS:
  481.  *        NULL : list is empty
  482.  * ---------------------------------------------------------
  483.  */
  484. void *listGetCurrent(List *this)
  485. {
  486.     if (!this->elements)
  487.         return(NULL);
  488.  
  489.     return(elementGetData(this->current));    
  490.  
  491. } /* listGetCurrent */
  492.  
  493.  
  494.  
  495. /*
  496.  * ---------------------------------------------------------
  497.  *    listSetCurrent
  498.  *        - Reassign a data reference within the current
  499.  *          element of the provided list
  500.  * ---------------------------------------------------------
  501.  *    PRE:
  502.  *        list is non-empty
  503.  * ---------------------------------------------------------
  504.  *    POST:
  505.  *        returns a reference to the previous (overwritten)
  506.  *        data in the current element of this list
  507.  * ---------------------------------------------------------
  508.  *    ERRORS:
  509.  *        NULL : list is empty
  510.  * ---------------------------------------------------------
  511.  */
  512. void *listSetCurrent(List *this, void *data)
  513. {
  514.     void *dval;            /* reference to data value */
  515.  
  516.     if (!this->elements)
  517.         return(NULL);
  518.  
  519.     dval = elementGetData(this->current);
  520.     elementSetData(this->current,data);
  521.  
  522.     return(dval);    
  523.  
  524. } /* listSetCurrent */
  525.  
  526.  
  527.  
  528. /*
  529.  * ---------------------------------------------------------
  530.  *    listDelCurrent
  531.  *        - Remove current element from the provided list and
  532.  *          obtain a reference to the data in the element
  533.  * ---------------------------------------------------------
  534.  *    PRE:
  535.  *        list is non-empty
  536.  * ---------------------------------------------------------
  537.  *    POST:
  538.  *        returns a reference to the data in the current
  539.  *        element in this list which no longer occurs in
  540.  *        the list;  new current element is removed's
  541.  *        successor
  542.  * ---------------------------------------------------------
  543.  *    ERRORS:
  544.  *        NULL : list is empty
  545.  * ---------------------------------------------------------
  546.  */
  547. void *listDelCurrent(List *this)
  548. {
  549.     Element *el;        /* reference to item to be deleted */
  550.     void *dval;            /* reference to data value */
  551.  
  552.     if (!this->elements)
  553.         return(0);
  554.  
  555.     /*
  556.      * note element for deletion
  557.      */
  558.     el = this->current;
  559.  
  560.     /*
  561.      * re-link list to remove current node
  562.      */
  563.     elementSetRight(&this->elements[elementGetLeft(this->current)], elementGetRight(this->current));
  564.     elementSetLeft(&this->elements[elementGetRight(this->current)], elementGetLeft(this->current));
  565.     this->current = &this->elements[elementGetRight(this->current)];
  566.  
  567.     /*
  568.      * SPECIAL CASES:
  569.      */
  570.     /* single element list - deleting only item */
  571.     if (this->element_count == 1)
  572.     {
  573.         listClear(this);
  574.     }
  575.     /* end node removed - wrapping current to first */
  576.     else if (&this->elements[0] == this->current)
  577.         this->position = 1;
  578.     /* first node removed - updating head of list */
  579.     else if (&this->elements[0] == el)
  580.         this->elements[0] = *this->current;
  581.  
  582.     this->element_count--;
  583.  
  584.     dval = elementGetData(el);
  585.     elementDelete(el);
  586.  
  587.     return(dval);
  588.  
  589. } /* listDelCurrent */
  590.  
  591.  
  592.  
  593. /*
  594.  * ---------------------------------------------------------
  595.  *    listIsEmpty
  596.  *        - Determine if provided list is empty
  597.  * ---------------------------------------------------------
  598.  *    PRE:
  599.  *        void
  600.  * ---------------------------------------------------------
  601.  *    POST:
  602.  *        returns 1 if this is empty, 0 otherwise
  603.  * ---------------------------------------------------------
  604.  *    ERRORS:
  605.  *        void
  606.  * ---------------------------------------------------------
  607.  */
  608. int listIsEmpty(List *this)
  609. {
  610.     return(this->element_count == 0);
  611.  
  612. } /* listIsEmpty */
  613.  
  614.  
  615.  
  616. /*
  617.  * ---------------------------------------------------------
  618.  *    listLength
  619.  *        - Determine number of elements (length) in
  620.  *          provided list
  621.  * ---------------------------------------------------------
  622.  *    PRE:
  623.  *        void
  624.  * ---------------------------------------------------------
  625.  *    POST:
  626.  *        returns value of element_count
  627.  * ---------------------------------------------------------
  628.  *    ERRORS:
  629.  *        void
  630.  * ---------------------------------------------------------
  631.  */
  632. int listLength(List *this)
  633. {
  634.     return(this->element_count);
  635.  
  636. } /* listLength */
  637.  
  638.  
  639.  
  640. /*
  641.  * ---------------------------------------------------------
  642.  *    listPosition
  643.  *        - Obtain numeric value of current position in
  644.  *          provided list
  645.  * ---------------------------------------------------------
  646.  *    PRE:
  647.  *        void
  648.  * ---------------------------------------------------------
  649.  *    POST:
  650.  *        returns value of position
  651.  * ---------------------------------------------------------
  652.  *    ERRORS:
  653.  *        void
  654.  * ---------------------------------------------------------
  655.  */
  656. int listPosition(List *this)
  657. {
  658.     return(this->position);
  659.  
  660. } /* listPosition */

FILE: LISTMENU.C

C Syntax (Toggle Plain Text) 
  1. /* === TESTING LIST TYPE === */
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include "List.h"
  6.  
  7.  
  8. #define BUFSIZE 81
  9.  
  10.  
  11. struct etype
  12. {
  13.     int key;
  14.     char str[10];
  15. };
  16.  
  17.  
  18. int main()
  19. {
  20.     List *tst;
  21.     int opt, misc, savepos;
  22.     char dummy[BUFSIZE];
  23.     struct etype *el, *rel;
  24.  
  25.     if (!(tst = listCreate()))
  26.         exit(-1);
  27.  
  28.     while(1)
  29.     {
  30.         printf("\n\n\nList (<ctrl-C> to quit):\n");
  31.         printf("1  - listClear()\n");
  32.         printf("2  - listHead()\n");
  33.         printf("3  - listTail()\n");
  34.         printf("4  - listPrev()\n");
  35.         printf("5  - listNext()\n");
  36.         printf("6  - listMoveToNth()\n");
  37.         printf("7  - listAddAfter()\n");
  38.         printf("8  - listAddBefore()\n");
  39.         printf("9  - listGetCurrent()\n");
  40.         printf("10 - listSetCurrent()\n");
  41.         printf("11 - listDelCurrent()\n");
  42.         printf("12 - listIsEmpty()\n");
  43.         printf("13 - listLength()\n");
  44.         printf("14 - listPosition()\n");
  45.  
  46.         printf("\n");
  47.         printf("CHOICE: ");
  48.         gets(dummy);
  49.         sscanf(dummy,"%d",&opt);
  50.  
  51.         switch(opt)
  52.         {
  53.             case 1:
  54.                 if ((misc = listClear(tst)) < 0)
  55.                 {
  56.                     fprintf(stderr,"listClear error\n");
  57.                     exit(-1);
  58.                 }
  59.                 else
  60.                     printf("\nList of size %d cleared\n",misc);
  61.                 break;
  62.             case 2:
  63.                 if (!listHead(tst))
  64.                     fprintf(stderr,"\n>>> NO MOVEMENT - List is empty\n");
  65.                 break;
  66.             case 3:
  67.                 if (!listTail(tst))
  68.                     fprintf(stderr,"\n>>> NO MOVEMENT - List is empty\n");
  69.                 break;
  70.             case 4:
  71.                 if (!listPrev(tst))
  72.                     fprintf(stderr,"\n>>> List empty, or already at beginning\n");
  73.                 break;
  74.             case 5:
  75.                 if (!listNext(tst))
  76.                     fprintf(stderr,"\n>>> List empty, or already at end\n");
  77.                 break;
  78.             case 6:
  79.                 printf("\nMove to (n > 0): ");
  80.                 gets(dummy);
  81.                 sscanf(dummy,"%d",&misc);
  82.                 if (!listMoveToNth(tst,misc))
  83.                     fprintf(stderr,"\n>>> List empty, or element %d out of range\n",misc);
  84.                 break;
  85.             case 7:
  86.                 el = malloc(sizeof(struct etype));
  87.                 printf("\nKEY(int)       : ");
  88.                 gets(dummy);
  89.                 sscanf(dummy,"%d", &el->key);
  90.                 printf("STRING(char *) : ");
  91.                 gets(el->str);
  92.                 if (!listAddAfter(tst,el))
  93.                 {
  94.                     fprintf(stderr,"listAddAfter error\n");
  95.                     exit(-1);
  96.                 }
  97.                 break;
  98.             case 8:
  99.                 el = malloc(sizeof(struct etype));
  100.                 printf("\nKEY(int)       : ");
  101.                 gets(dummy);
  102.                 sscanf(dummy,"%d", &el->key);
  103.                 printf("STRING(char *) : ");
  104.                 gets(el->str);
  105.                 if (!listAddBefore(tst,el))
  106.                 {
  107.                     fprintf(stderr,"listAddBefore error\n");
  108.                     exit(-1);
  109.                 }
  110.                 break;
  111.             case 9:
  112.                 if (!(rel = (struct etype *)listGetCurrent(tst)))
  113.                     fprintf(stderr,"\n>>> List is empty\n");
  114.                 else
  115.                     printf("\nELEMENT : Key: %d\n          Str: %s\n",rel->key, rel->str);
  116.                 break;
  117.             case 10:
  118.                 el = malloc(sizeof(struct etype));
  119.                 printf("\nKEY(int)       : ");
  120.                 gets(dummy);
  121.                 sscanf(dummy,"%d", &el->key);
  122.                 printf("STRING(char *) : ");
  123.                 gets(el->str);
  124.                 if (!(rel = listSetCurrent(tst,el)))
  125.                 {
  126.                     fprintf(stderr,"listSetCurrent error\n");
  127.                     exit(-1);
  128.                 }
  129.                 free(rel);
  130.                 break;
  131.             case 11:
  132.                 if (!(rel = (struct etype *)listDelCurrent(tst)))
  133.                     fprintf(stderr,"\n>>> NO DELETION : List is empty\n");
  134.                 else
  135.                 {
  136.                     printf("\nELEMENT : Key: %d\n          Str: %s\n",rel->key, rel->str);
  137.                     free(rel);
  138.                 }
  139.                 break;
  140.             case 12:
  141.                 printf("\nList is %s\n",(listIsEmpty(tst) ? "empty" : "non-empty"));
  142.                 break;
  143.             case 13:
  144.                 printf("\nSize of list : %d\n",listLength(tst));
  145.                 break;
  146.             case 14:
  147.                 printf("\nPosition : %d\n",listPosition(tst));
  148.                 break;
  149.             default:
  150.                 printf("\n>>> ILLEGAL SELECTION\n");
  151.                 break;
  152.         }
  153.         printf("\n============\n\n");
  154.         printf("NEW (CURRENT) STATE:\n");
  155.  
  156.         savepos = listPosition(tst);
  157.  
  158.         listHead(tst);
  159.         if (listIsEmpty(tst))
  160.             printf("List is empty\n");
  161.         else
  162.         {
  163.             do
  164.             {
  165.                 el = listGetCurrent(tst);
  166.                 if (savepos == listPosition(tst))
  167.                 {
  168.                     printf("*>");
  169.                     printf("[%d|%s]",el->key, el-> str);
  170.                     printf("<*  ");
  171.                 }
  172.                 else
  173.                     printf("[%d|%s]  ",el->key, el-> str);
  174.             } while(listNext(tst));
  175.             printf("\n");
  176.         }
  177.  
  178.         listMoveToNth(tst,savepos);
  179.  
  180.         printf("\nHit <enter>...\n");
  181.         gets(dummy);
  182.     }
  183.  
  184.     listDelete(tst);
  185.  
  186. }

MAKEFILE

C Syntax (Toggle Plain Text) 
  1. CC          =    gcc
  2.  
  3. CFLAGS      =    -Wall -ansi -pedantic
  4. LDFLAGS     =
  5.  
  6. INCLUDES    =
  7. LIBDIRS     =
  8. LIBS        =
  9.  
  10. LISTOBJS    = \
  11.             CList.o\
  12.             CElement.o\
  13.             ListMenu.o
  14.  
  15. default : all
  16.  
  17. all : CListMenu
  18.  
  19. CListMenu : $(LISTOBJS)
  20.     $(CC) $(LIBDIRS) $(LDFLAGS) -o $@ $(LISTOBJS) $(LIBS)
  21.  
  22.  
  23. Element.o: Element.c Element.h
  24.     $(CC) $(CFLAGS) -c Element.c $(INCLUDES)
  25. List.o: List.c List.h Element.h
  26.     $(CC) $(CFLAGS) -c List.c $(INCLUDES)
  27. CElement.o: CElement.c CElement.h
  28.     $(CC) $(CFLAGS) -c CElement.c $(INCLUDES)
  29. CList.o: CList.c CList.h CElement.h
  30.     $(CC) $(CFLAGS) -c CList.c $(INCLUDES)
  31.  
  32. ListMenu.o: ListMenu.c List.h Element.h
  33.     $(CC) $(CFLAGS) -c ListMenu.c $(INCLUDES)
  34.  
  35. clean:
  36.     @ rm *.o
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 7,625
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 715
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Double-linked list in contiguous memory.

 
0
  #2
Oct 4th, 2007
>all my code does is generate a seg fault whenever I try and add a new element.
That makes perfect sense. Here's how you call elementCreate:
C Syntax (Toggle Plain Text) 
  1. Element *new;        /* new element */
  2.  
  3. if (!(new = elementCreate(new, data)))
  4.   return(NULL);
And here's the definition of elementCreate:
C Syntax (Toggle Plain Text) 
  1. Element *elementCreate(Element *new, void *data)
  2. {
  3.   new->data = data;
  4.   return(new);
  5. } /* elementCreate */
So tell me, where does the new point to?
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C Forum
Thread Tools Search this Thread



* adobe api array arrays binarysearch calculate centimeter char cm convert copyanyfile copypdffile cprogramme createcopyoffile createprocess() csyntax directory dynamic feet fflush file floatingpointvalidation fork forloop frequency getlasterror getlogicaldrivestrin givemetehcodez global graphics gtkgcurlcompiling gtkwinlinux hacking hardware highest homework i/o ide inches incrementoperators intmain() iso km linked linkedlist linux linuxsegmentationfault list locate logical_drives loopinsideloop. match matrix microsoft motherboard mqqueue mysql oddnumber odf open opendocumentformat opensource openwebfoundation pattern pdf performance pointer posix power program programming pyramidusingturboccodes read recursion recv recvblocked repetition scanf scheduling segmentationfault send shape single socketprograming socketprogramming stack standard strchr string suggestions test unix urboc user variable voidmain() whythiscodecausesegmentationfault win32api windows.h
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC