数据结构 - 链表

Summary on linked listsDefinition:struct Nodetint data;Node* nexttypedef Node* NodePtr;NodePtr head;Head

struct Node{ int data; Node* next; }; typedef Node* NodePtr; NodePtr head; Definition: Head Summary on linked lists

bool listEmpty(NodePtr head)return(head--NULL)Operations onintgetHead(NodePtrhead)((unsorted)linkedlistsif (head != NULL) return head->data;else (cout<<"Error"<<endl; exit(l)};NodePtrgetRest(NodePtr head)NodePtr p=NULL;if (head != NULL) p=head->next;return p;(!listEmpty()NodePtr addHead(NodePtr head, int newdata) // or:void addHead(NodePtr& head,int newdata)NodePtr newPtr = new Node;newPtr->data = newdata;newPtr->next = head;return newPtr;//or:head =newPtriNodePtr delHead(NodePtr Head)// or: void delHead(NodePtr& head)if(head= NULL)(NodePtr cur = head;head = head->next;delete cur;return head; // no return for 'void delHeadO

bool listEmpty(NodePtr head) { return (head==NULL); } int getHead(NodePtr head) { if (head != NULL) return head->data; else {cout << “Error” << endl; exit(1);}; } NodePtr getRest(NodePtr head) { NodePtr p=NULL; if (head != NULL) p=head->next; return p; } NodePtr addHead(NodePtr head, int newdata) { // or: void addHead(NodePtr& head, int newdata) { NodePtr newPtr = new Node; newPtr->data = newdata; newPtr->next = head; return newPtr; // or: head = newPtr; } NodePtr delHead(NodePtr Head){ // or: void delHead(NodePtr& head) if(head != NULL){ NodePtr cur = head; head = head->next; delete cur; } return head; // no return for ‘void delHead()’ } Operations on (unsorted) linked lists (! listEmpty())

Operationsonsortedlinkedlists:boollistEmpty(NodePtrhead){NodeptrinsertNode(NodePtr head,int item)// or: void insertNode(Nodeptr& head, int item)(NodePtrdeleteNode(NodePtrhead, int item)// or: void deleteNode(NodePtr& head, int item)((findingtherightpositionshouldbecarefulinimplementation!

bool listEmpty(NodePtr head) { . } NodePtr insertNode(NodePtr head, int item) { // or: void insertNode(NodePtr& head, int item){ . } NodePtr deleteNode(NodePtr head, int item) { // or: void deleteNode(NodePtr& head, int item){ . } Operations on sorted linked lists: (finding the right position should be careful in implementation!)

COMP104LinkedLists/Slide4NodePtr insertNode(NodePtr head,int item)(Nodeptr newp,cur,pre;newp =new Node;newp->data = item;pre = NULL;cur = head;while((cur!=NULL)&&(item>cur->data))(pre = cur;cur = cur->next;if(pre ==NULL)f //insert to head of linked listnewp->next = head;head =newp;Ifthepositionhappenstobetheheadelse(pre->next = newp;new->next = cur;General casereturn head;

COMP104 Linked Lists / Slide 4 NodePtr insertNode(NodePtr head, int item){ NodePtr newp, cur, pre; newp = new Node; newp->data = item; pre = NULL; cur = head; while( (cur != NULL) && (item>cur->data)){ pre = cur; cur = cur->next; } if(pre == NULL){ //insert to head of linked list newp->next = head; head = newp; } else { pre->next = newp; new->next = cur; } return head; } If the position happens to be the head General case

COMP104LinkedLists/Slide5NodePtr deleteNode(NodePtr head,int item)(NodePtr prev=NULL, cur = head;while（(cur!=NULL)&&(item>cur->data)）{prev = cur;cur= cur->next;if(cur!==NuLL&&cur->data==item)if(cur==Head)Head = Head->next;elseprev->next = cur->next;delete cur;return head;

COMP104 Linked Lists / Slide 5 NodePtr deleteNode(NodePtr head, int item){ NodePtr prev=NULL, cur = head; while( (cur!=NULL) && (item > cur->data)){ prev = cur; cur = cur->next; } if ( cur!==NULL && cur->data==item) { if(cur==Head) Head = Head->next; else prev->next = cur->next; delete cur; } return head; }