Help on doubly-link lists on an ADT..... 
Author Message
 Help on doubly-link lists on an ADT.....

Hoping someone can help,...
In a single link-list implementation of a Table ADT:
/* Table ADT*/
#ifndef TABLE_HDR
#define TABLE_HDR
/* Opaque definition of TABLE */
#include "element.h"
#include "boolean.h"
typedef struct table TABLE;
typedef TABLE *Table;
Table CreateTable(void);
Boolean TableEmpty(Table t);
Boolean TableFull(Table t);
int TableSize(Table t);
void ClearTable(Table t);
void Insert(Table t,Key newKey, Element element);
Boolean Delete(Table t,Key key,Element *element);
Boolean Retrieve(Table t,Key key,Element *element);
Boolean Update(Table t,Key key,Element element);
void Traverse(Table t,void (*Process)(Element *));
#endif

...I have defined a stucture for the linked list implementation of the Table
ADT as:

typedef struct node {
    Element entry;
    struct listNode *next;

Quote:
} Node;

struct table {
    Node *tableTop;

Quote:
};

Ive included a recursive implementation for the linked list form of the
table ADT:

#include <stdio.h>
#include "boolean.h"
typedef struct node{
   Element entry;
   struct node *next;

Quote:
} Node;

struct table {
     Node *tableTop;

Quote:
};

#include "table.h"
void Error(char *string)
{ puts(string);

Quote:
}

Table CreateTable(void)
{ Table t;
   t = malloc(sizeof(TABLE));
   t->tableTop = NULL;
   return t;  }

Boolean TableEmpty(Table t)
{ return t->tableTop == NULL;

Quote:
}

Boolean TableFull(Table t)
{ return FALSE;

Quote:
}

int TableNodes(Node *root)
{ if (root == NULL)
       return 0;
   else
       return 1 + TableNodes(root->next);

Quote:
}

int TableSize(Table t)
{
   return TableNodes(t->tableTop);

Quote:
}

Node *ClearNodes(Node *root)
{
   if (root != NULL) {
      root->next = (Node *) ClearNodes(root->next);
      free(root);
      root = NULL;
   }
   return root;

Quote:
}

void ClearTable(Table t)
{
   t->tableTop = (Node *) ClearNodes(t->tableTop);

Quote:
}

Node *MakeNode(Element item)
{
    Node *nodePtr;
    if ((nodePtr=(Node*) malloc(sizeof(Node)))!=NULL)
    {
        AssignElement(item, &(nodePtr->entry));
        nodePtr->next = NULL;
    }
    return nodePtr;

Quote:
}

Node *InsertNode(Node *root,Key newKey,Element element)
{
     Node *temp;
     int res;
     if (root == NULL || (res = CompareKey(root->entry.key,newKey)) == 1) {
        temp = MakeNode(element);
        if (temp == NULL)
           Error("Memory Error\n");
        else {
           temp->next = root;
           root = temp;
        }
     }
     else if (res == 0) {
        Error("Key already here\n");
     }
     else {
        root->next = InsertNode(root->next,newKey,element);
     }
     return root;

Quote:
}

void Insert(Table t,Key newKey, Element element)
{
     t->tableTop = (Node *) InsertNode(t->tableTop,newKey,element);

Quote:
}

Node *DeleteNode(Node *root,Key oldKey,Element *element,Boolean *found)
{  Node *temp;
     if (root == NULL)
        *found = FALSE;
     else if (CompareKey(root->entry.key,oldKey) == 0) {
        AssignElement(root->entry, element);
        *found = TRUE;
        temp = root;
        root = root->next;
        free(temp); }
     else
        root->next = DeleteNode(root->next,oldKey,element,found);
     return root;  }

Boolean Delete(Table t,Key oldKey,Element *element)
{   Boolean found;
     if (t->tableTop == NULL)
        return FALSE;
     else {
        t->tableTop = DeleteNode(t->tableTop,oldKey,element,&found);
        return found; }

Quote:
}

Boolean RetrieveNode(Node *root,Key newKey,Element *element)
{
     if (root == NULL)
        return FALSE;
     else if (CompareKey(root->entry.key,newKey) == 0) {
        AssignElement(root->entry,element);
        return TRUE; }
     else
        return RetrieveNode(root->next,newKey,element); }

Boolean Retrieve(Table t,Key newKey,Element *element)
{ if (t->tableTop == NULL)
        return FALSE;
     else
        return RetrieveNode(t->tableTop,newKey,element); }

Boolean UpdateNode(Node *root,Key oldKey,Element element)
{ if (root == NULL)
        return FALSE;
     else if (CompareKey(root->entry.key,oldKey) == 0) {
        AssignElement(element,&(root->entry));
        return TRUE; }
     else
        return UpdateNode(root->next,oldKey,element); }
Boolean Update(Table t,Key oldKey,Element element)
{  if (t->tableTop == NULL)
        return FALSE;
     else
        return UpdateNode(t->tableTop,oldKey,element); }
void TraverseNodes(Node *root,void (* Process)(Element *))
{ if (root != NULL) {
      Process(&(root->entry));
      TraverseNodes(root->next,Process);  }}
void Traverse(Table t,void (* Process)(Element *))
{    TraverseNodes(t->tableTop,Process); }

In what way do I show this for a doubly-link list?? Any thoughts
appreciated.
Neil



Sat, 02 Apr 2005 20:30:30 GMT  
 Help on doubly-link lists on an ADT.....

Quote:

> Hoping someone can help,...
> In a single link-list implementation of a Table ADT:

[snip]

Quote:
> typedef TABLE *Table;

Generally speaking, hiding pointers in typedefs is considered bad style
because it makes the code difficult to read, especially by someone who
did not write it; a variable declared as

    Table t;

is suddenly assigned to NULL or dereferenced or passed as a
pointer-argument.

    Table *t;

makes all these surprises moot and allows

    Table    static_table;
    Table   *t = &static_table;

rather than

    TABLE    static_table;
    Table    t = &static_table;

and such.

[snip]

Quote:
> ...I have defined a stucture for the [singly-] linked list implementation of the Table
> ADT as:

> typedef struct node {
>     Element entry;
>     struct listNode *next;
> } Node;

> struct table {
>     Node *tableTop;
> };

[snip]

Quote:
> In what way do I show this for a doubly-link list?? Any thoughts
> appreciated.

Typically, a doubly-linked list has...two links:

    typedef struct Node Node;
    struct Node {
        Element    elt;     /* some opaque data */
        Node      *next;
        Node      *prev;
    };

Suggesting an alternative implementation, your list can be declared as

    Node    list;

where list.next is the *first* element of the list, and list.prev is
NULL. List.elt can remain indeterminate since it is a dummy element.
This way, you don't need a special case to handle the creation of a new
list. You just add elements to the head of list. This also allows you to
treat any Node in the list as the head of a sub-list which is often
useful.

Adding and deleting Nodes is just a matter of adjusting pointers: for
example,

    add_after(Node *n, Element *e);

operates by allocating a new Node, nn, for e, and adjusting nn->next,
nn->prev, n->next->prev, and n->prev->next to accommodate the new Node.
Calling

    add_after(&list, &e);

for example, will add an element to the head of your list.

        david

--
...the use of keys+commands required a higher level of mental planning
to organise the interaction, which apparently obscures the perception
of the passage of time...
        -- forsyth on Tognazzini's "Tog on Interface"



Sat, 02 Apr 2005 23:51:24 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Need help with doubly linked lists

2. Please I need some help -- traversing trough a doubly linked list--

3. help! doubly linked lists

4. Doubly Linked Lists...HELP PLEASE (sorry if this a repost)

5. HELP: problem with doubly linked list

6. Help wanted for doubly linked lists

7. HELP PLEASE: singly/doubly linked lists

8. help with doubly linked list

9. linked list(ADT) problems

10. How to write c program to create linked list of staff records using ADT

11. Linked Lists and ADT

12. Sorting on a doubly linked list

 

 
Powered by phpBB® Forum Software