Help on doubly-link lists on an ADT.....
Author |
Message |
Neil #1 / 2
|
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 |
|
|
David Rubi #2 / 2
|
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 |
|
|
|