数据结构精品课程ppt7.ppt

1. Doubly Linked List Inserting a Node at a Position Inserting a Node at a Position Deleting a Node at a Position Deleting a Node at a Position 2. Circular Doubly Linked Lists A Watch Band provides a good Real Life analogue for this Data Structure Circular Doubly Linked Lists It might look something like this. Updating a Doubly Linked List dnode.h writeDLinkedList Inserting a node to DLinkedList Deleting a node to DLinkedList Josephus Josephus miniList summary Main Index Contents * * Main Index Contents Abstract Model of a Doubly Linked List Insert/Delete Circular Doubly Linked List Insert/Delete Josephus problem MiniList Class Lecture 7 – Doubly Linked Lists * Main Index Contents Value * Main Index Contents Inserting a Node before curr Position * Main Index Contents DnodeT *newNode, *prevNode;newNode=new dnodeT(item);prevNode=curr-prev;newNode-prev=prevNode;newNode-next=curr;prevNode-next=newNode;Curr-prev=newNode; * Main Index Contents * Main Index Contents DnodeT*prevNode=curr-prev, *succNode=curr-next; prevNode-next=succNode; succNode-prev=prevNode; Delete curr; * Main Index Contents * Main Index Contents template typename T class dnode { public: T nodeValue; dnodeT *prev; dnodeT *next; dnode() { next = this; prev = this; } dnode(const T value): nodeValue(value) { next = this; prev = this; } }; TemplateTypename T Void writeDLinkedList(dnodeT *header, const string separator=“ “) { DnodeT *p=header-next; While(P!=header) { coutp-nodeValueseparator; p=p-next; } } TemplateTypename T DnodeT *insert(dnodeT *curr, const T item) { dnodeT *newNode, *prevNode; newNode=new dnodeT(item); prevNode=curr-prev; newNode-prev=prevNode; newNode-next=curr; prevNode-next=newNode; curr-prev=newNode; return newNode; } TemplateTypename T void *erase(dnodeT *curr) { if(curr-next==curr)return; dnodeT *prevNode=curr-prev, *succNode=curr-next; prevNode-next=succNode; succNode-prev=prevN