数据结构课件_04LinkedLists.pdf
Data Structures Linked Lists Teacher : Wang Wei 1 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 王伟, 计算机工程系, 东南大学 4. 殷人昆, 数据结构 Memory Layout Layout of L = (a,b,c,d,e) using an array representation A linked representation uses an arbitrary layout 2 王伟, 计算机工程系, 东南大学 Linked Representation c a e d b first pointer (or link) in e is NULL use a variable first to get to the first element a 王伟, 计算机工程系, 东南大学 3 Linked Lists first BAT CAT … EAT WAT 0^ • In linked list, insertion / deletion of arbitrary elements is much easier : first … BAT FAT … / HAT GAT x 4 王伟, 计算机工程系, 东南大学 Chain • Linear list • Each element is stored in a node • Nodes are linked together using pointers • The last node has a NULL (or 0) pointer • a normal way to draw a Linked List first a b c d e NULL 5 王伟, 计算机工程系, 东南大学 Chain Node Representation template class ChainNode { private: T data; ChainNode *link; data link // constructors come here }; 王伟, 计算机工程系, 东南大学 6 The Template Class Chain template class Chain { public: Chain() {first = 0;} // constructor, empty chain ~Chain(); // destructor bool IsEmpty() const {return first == 0;} // other methods defined here private: ChainNode* first; }; 王伟, 计算机工程系, 东南大学 7 Destructor templatechain::~chain() // Chain destructor. Delete all nodes in chain. { while (first != NULL) // delete first { ChainNode* next = first->link; delete first; first = next; } } 王伟, 计算机工程系, 东南大学 8 The Method IndexOf template int Chain::IndexOf(const T& theElement) const { // search the chain for theElement ChainNode* currentNode = first; int index = 0; // index of currentNode while (currentNode != NULL && currentNode->data != theElement) { // move to next node currentNode = currentNode->next; index++; } // make sure we found matching element if (currentNode == NULL) return -1; else return index; } 王伟, 计算机工程系, 东南大学 9 Insert An Element Template void Chain::Insert(int theIndex, const T& theElement) { if(theIndex<0) throw “Bad insert index”; // insert at front if(theIndex == 0) first = new chainNode(theElement, first); 王伟, 计算机工程系, 东南大学 10 else { // find predecessor of new element ChainNode* p = first; for (int i = 0; i < theIndex - 1; i++) { if (p == 0) throw “Bad insert index”; p = p->next; } // insert after p p->link = new ChainNode(theElement, p->link); } } 王伟, 计算机工程系, 东南大学 11 Remove An Element template void Chain::Delete(int theIndex) { if (first == 0) throw “Cannot delete from empty chain”; ChainNode* deleteNode; if (theIndex == 0) { // remove first node from chain deleteNode = first; first = first->link; } 王伟, 计算机工程系, 东南大学 12 else { // use p to get to beforeNode ChainNode* p = first; for (int i = 0; i < theIndex - 1; i++) { if (p == 0) throw “Delete element does not exist”; p = p->next; } deleteNode = p->link; p->link = p->link->link; } delete deleteNode; } 13 王伟, 计算机工程系, 东南大学 a singly-linked Circular List firstNode a b c d e • To check whether a pointer current points to the last node of a circular list currentlink == first • Functions for insertion into and deletion from must ensure –The link field of the last node points to the first node of the list upon completion 14 王伟, 计算机工程系, 东南大学 a singly-linked Circular List lastNode a b c d e • Suppose want to insert a new node at the front of the list – Move down the entire length of the list until find the last node • It is more convenient – Access pointer of the list points to the last node 王伟, 计算机工程系, 东南大学 15 template void CircularList::InsertFront(const T& e) { // insert the element e at the “front” of the circular list *this // where last points to the last node in the list ChainNode* newNode = new ChainNode(e); // nonempty list if (last) { newNodelink = lastlink; lastlink = newNode; } else { last = newNode; newNodelink = newNode; } } 16 王伟, 计算机工程系, 东南大学 Doubly Linked List firstNode NULL a lastNode b c e d NULL • A node in doubly linked list has at least 3 field Left-link data Right-link 王伟, 计算机工程系, 东南大学 17 Doubly Linked Circular List lastNode a b c d e firstNode p == pllinkrlink == prlinkllink 王伟, 计算机工程系, 东南大学 18 Doubly Linked Circular List With Header Node headerNode lastNode a b c d e headerNode Empty Doubly Linked Circular List With Header Node 王伟, 计算机工程系, 东南大学 19 class DblList; class DblListNode { friend class DblList; private: int data; DblListNode *left, *right; }; class DblList { public: // List manipulation operations // … private: DblListNode *first; // points to head node }; 王伟, 计算机工程系, 东南大学 20 Delete void DblList::Delete(DblListNode *x ) { if(x == first) throw “Deletion of head node not permitted”; else { x→left→right = x→right; x→right→left = x→left; delete x; } } x 王伟, 计算机工程系, 东南大学 21 Insert void DblList::Insert(DblListNode *p, DblListNode *x ) { // insert node p to the right of node x p→left = x; p→right = x→right; x→right→left = p; x→right = p; // (1) // (2) // (3) // (4) } x p (1) (4) (3) (2) 王伟, 计算机工程系, 东南大学 22 Data Structures Generalized Lists Teacher : Wang Wei 23 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 Generalized Lists ( GL : 广义表) • Definition – Is a finite sequence of n ≥0 elements – Let : A = (a0, a1, a3, …, an-1) • • • – A is the mane of the generalized list ai is either an atom or a sublist , 0 ≤ i ≤ n-1 – Atoms are represented by lowercase letters – All sumlist names are represented by capital letters n is its length If n ≥1 • a0 is the head of A • (a1, a3, …, an-1) is tail of A 王伟, 计算机工程系, 东南大学 24 • A=( ) – the null or empty list; its length is zero; • B=(a,(b, c) ) – length is two – first element is atom a, second element is linear list (b,c) • C( B,B, ( ) ) – Length is three – First two elements are list B, third element is null list • D=( a, D) – Recursive list; length is two – D corresponds to (a,(a,(a,…) infinite list 王伟, 计算机工程系, 东南大学 25 王伟, 计算机工程系, 东南大学 26 GenListNode Template class GenList; // forward declaration enum Boolean {FALSE, TRUE}; Template class GenListNode { friend class GenList; private: Boolean tag; union { char data; GenListNode *dlink; }; GenListNode *link; }; 王伟, 计算机工程系, 东南大学 27 GenList class Template class GenList { public: // operations (表处理操作) private: GenListNode *first; }; 王伟, 计算机工程系, 东南大学 28 template //公有函数 void GenList::Copy(const GenList & P) first = Copy(P.first); //调用私有函数 }; template GenListNode*GenList::Copy(GenListNode * p) { GenListNode *q = 0; if (p) { // p不是空表 q = new GenListNode; // 复制表头 qtag = ptag; if (!ptag) qdata = pdata; // 原子 else qdlink = Copy(pdlink); // 子表 qlink = Copy(plink); // 复制表尾 } return q; } 王伟, 计算机工程系, 东南大学 29 GenList Depth 1, empty Depth(LS) 0, atom 1 max {Depth(α )}, other , n 1 i 0 i n 1 Example E (B (a, b), D (B (a, b), C (u, (x, y, z)), A ( ) ) ) 王伟, 计算机工程系, 东南大学 30
数据结构课件_04LinkedLists.pdf
