數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件：chapter3 Linked Lists

1、Software College Northeastern UniversityData StructureSoftware College Northeastern UniversityzLinked Lists zProgramming detailszCommon Error zDoubly Linked Lists z Circularly Linked Listsz examplesz Cursors Implementation of Linked ListsData StructureSoftware College Northeastern UniversityVariable

2、-length arrays?zDirect access to element (By indexing) zArray size is fixed-length -To expand them, you create a new, longer array, and copy the contents of the old array into the new arrayyThis is used by function realloc() in CyThis is slow!z Linear time Insertion/Removal due to shift elementsydue

3、 to contiguous storage in memory yHalf of the list needs to be moved for either operationsData StructureSoftware College Northeastern UniversityVariable-length arrays?zSolution: -The list is not need to store contiguously. -Attach a pointer to each item in the array, which points to the next item. -

4、provides the ability to add or remove the items anywhere in the list in constant timeyThis is a linked listyLinked lists are unbounded (maximum number of items limited only by memory)Data StructureSoftware College Northeastern UniversityThe Linked List data structure012arrayABCArrayHeadABCLinked lis

5、tz An data item plus its pointer is called a nodez A node contains data item and one or more links. - The link is a reference to a node. - The link of last node is set to NULLz a “head” which is a pointer to the first node in the linked list nodeData StructureSoftware College Northeastern University

6、ZHAOQIANSUNLIZHOUWUZHENGWANGH43131NULL3771925Data ItemLinksLIQIANSUNWANGWUZHAOZHENGZHOUAddress1713192531374331HHeaderA simple single Linked ListData StructureSoftware College Northeastern UniversityMemory Storage of linked listWe can access all nodes through pointer “head”Data StructureSoftware Coll

7、ege Northeastern Universityz Each node contains the address of the next one in the list.z We can access the first node through pointer “head”z two important pointer: - head: the reference to the first node - tail: the reference to the last nodeData StructureSoftware College Northeastern UniversityHo

8、w to implementate?Data StructureSoftware College Northeastern UniversityDefinition of the classData StructureSoftware College Northeastern University class List; class ListNode friend class List; private: int data; ListNode *link; ; class List public: private: ListNode *first, *last; ;List is a Frie

9、nd classData StructureSoftware College Northeastern UniversityListNode is a class inside ListData StructureSoftware College Northeastern UniversityLinked List:Inserting a new node(1)y Insert a node with data equal to x after the i-1th element. (i.e., when i = 1, insert the node as the first element;

10、 when index = 2, insert the node after the first element, and so on)y If the insertion is successful, return 1. Otherwise, return 0. (If index is length+1 of the list, the insertion will fail.)zSteps1.Locate i-1th element2. Allocate memory for the new node3. Point the new node to its successor4. Poi

11、nt the new nodes predecessor to the new nodenewNodeith elementData StructureSoftware College Northeastern UniversityzInsert positiony Case 1：insert in front of the first node newnodelink = first ; first = newnode； firstnewnodenewnodefirstLinked List:Inserting a new node(2)Data StructureSoftware Coll

12、ege Northeastern University newnodelink = plink; plink = newnode；newnodepnewnodepLinked List:Inserting a new node(3)Data StructureSoftware College Northeastern University newnodelink = plink; plink = last = newnode；newnodenewnodelastplastpLinked List:Inserting a new node(4)Data StructureSoftware Col

13、lege Northeastern University/ Insert a node with data equal to x after the i-1th / Locate i-1th elementAllocate memory for the new nodeLinked List:Inserting a new node(5)From 0Data StructureSoftware College Northeastern University if ( first = NULL | i = 0 ) /Insert in the front of list newnodelink

14、= first; if ( first = NULL ) last = newnode; first = newnode; else /else newnodelink = plink; if ( plink = NULL ) last = newnode; plink = newnode; return 1; Linked List:Inserting a new node(6)Data StructureSoftware College Northeastern University when we insert a new node： （1）insert before the ith e

15、lement， which pointer should we get first？ （2）illegal inserting position is ? How can we judge inserting position is illegal？ （3）We should change two links when inserting ， Is there an order？Linked List:Inserting a new nodeData StructureSoftware College Northeastern UniversityDelete the ith element

16、？Linked List:Deleting a new node(1)Data StructureSoftware College Northeastern Universityint List:Remove ( int i ) /Delete the ith element Node *p = first, *q; int k = 0; while ( p != NULL & k i-1 ) p = plink; k+; /locate the i-1th element if (i0 | p = NULL | plink = NULL ) cout “無效的刪除位置無效的刪除位置!n”;

17、return 0; if ( i = 0 ) /delete the first q = first; /q point the deleted node p = first = firstlink; /Update first Linked List:Deleting a new node(2)Data StructureSoftware College Northeastern University else q = plink; plink = qlink; if ( q = last ) last = p; /if necessary update last k = qdata; de

18、lete q; /free the node pointed by q return k;Linked List:Deleting a new node(3)Data StructureSoftware College Northeastern Universitylinking to the first node is called Header, the header cell only contains references to the first.0ana1firstlastfirst0lastData StructureSoftware College Northeastern U

19、niversity newnodelink = plink; if ( plink = NULL ) last = newnode; plink = newnode;Data StructureSoftware College Northeastern University q = plink; plink = qlink; delete q; if ( plink = NULL ) last = p;Data StructureSoftware College Northeastern UniversityTemplate of linked list(1)template class Li

20、st;template class ListNode friend class List; Type data; /結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù) ListNode *link; /結(jié)點(diǎn)鏈接指針結(jié)點(diǎn)鏈接指針public: ListNode ( ); /鏈表結(jié)點(diǎn)構(gòu)造函數(shù)鏈表結(jié)點(diǎn)構(gòu)造函數(shù) ListNode ( const Type& item ); ListNode *NextNode ( ) return link; /給出當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)地址給出當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)地址Data StructureSoftware College Northeastern Universityvoid InsertAfter

21、 ( ListNode *p ); /在當(dāng)前結(jié)點(diǎn)后插入結(jié)點(diǎn)在當(dāng)前結(jié)點(diǎn)后插入結(jié)點(diǎn)p ListNode *RemoveAfter ( ); /摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn);template class List ListNode *first, *last;public: ListNode *GetNode ( const Type& item, ListNode *next ); /創(chuàng)建數(shù)據(jù)為創(chuàng)建數(shù)據(jù)為item，指針為，指針為next的新結(jié)點(diǎn)的新結(jié)點(diǎn)Template of linked list(2)Data StructureSoftware College Northeast

22、ern University List ( const Type & value ) last =first = new ListNode( value ); /構(gòu)造函數(shù)構(gòu)造函數(shù) List ( ); /析構(gòu)函數(shù)析構(gòu)函數(shù) void MakeEmpty ( ); /鏈表置空鏈表置空 int Length ( ) const; /求鏈表長度求鏈表長度 ListNode *Find ( Type value ); ListNode *Find ( int i ); int Insert ( Type value, int i ); Type *Remove ( int i ); Type *Get (

23、 int i ); Template of linked list(3)Data StructureSoftware College Northeastern Universitytemplate ListNode : ListNode ( ) : link (NULL) template ListNode:ListNode( const Type& item ) : data (item), link (NULL) template void ListNode:InsertAfter ( ListNode *p ) plink = link; link = p; Data Structure

24、Software College Northeastern Universitytemplate ListNode*ListNode:RemoveAfter ( ) /摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn) ListNode *tempptr = link; if ( link = NULL ) return NULL; /沒有下一結(jié)點(diǎn)則返回空指針沒有下一結(jié)點(diǎn)則返回空指針 link = tempptrlink; /重新鏈接 return tempptr; /返回下一結(jié)點(diǎn)地址返回下一結(jié)點(diǎn)地址Data StructureSoftware College Northeastern Univer

25、sitytemplate ListNode*List:GetNode ( const Type& item, ListNode *next = NULL ) ListNode *newnode = new ListNode ( item ); newnode link = next; return newnode;template List : List ( )/析構(gòu)函數(shù)析構(gòu)函數(shù) MakeEmpty ( ); delete first; /鏈表置空，再刪去表頭結(jié)點(diǎn)鏈表置空，再刪去表頭結(jié)點(diǎn)Data StructureSoftware College Northeastern University

26、template void List : MakeEmpty ( ) /刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn)刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn) ListNode *q; while ( firstlink != NULL ) q = firstlink; firstlink = qlink; /將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下 delete q; /釋放它釋放它 last = first; /修改表尾指針修改表尾指針Data StructureSoftware College Northeastern Universitytemplate int List:L

27、ength ( ) const /求單鏈表的長度求單鏈表的長度 ListNode *p = firstlink; /檢測指針檢測指針p指示第一個(gè)結(jié)點(diǎn)指示第一個(gè)結(jié)點(diǎn) int count = 0; while ( p != NULL ) /逐個(gè)結(jié)點(diǎn)檢測逐個(gè)結(jié)點(diǎn)檢測 p = plink; count+; return count;Data StructureSoftware College Northeastern Universitytemplate ListNode*List :Find ( Type value ) /在鏈表中從頭搜索其數(shù)據(jù)值為在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)的結(jié)點(diǎn)

28、ListNode *p = firstlink; /檢測指針檢測指針 p 指示第一個(gè)結(jié)點(diǎn)指示第一個(gè)結(jié)點(diǎn) while ( p != NULL & pdata != value ) p = plink; return p; / p 在搜索成功時(shí)返回找到的結(jié)點(diǎn)地址在搜索成功時(shí)返回找到的結(jié)點(diǎn)地址 / p 在搜索不成功時(shí)返回空值在搜索不成功時(shí)返回空值Data StructureSoftware College Northeastern Universitytemplate ListNode *List : Find ( int i ) /在鏈表中從頭搜索第在鏈表中從頭搜索第 i 個(gè)結(jié)點(diǎn)，不計(jì)頭結(jié)點(diǎn)個(gè)結(jié)點(diǎn)

29、，不計(jì)頭結(jié)點(diǎn) if ( i -1 ) return NULL; if ( i = -1 ) return first; / i 應(yīng)應(yīng) 0 ListNode *p = firstlink; int j = 0; while ( p != NULL & j i ) / j = i 停停 p = plink; j+; return p;Data StructureSoftware College Northeastern Universitytemplate int List : Insert ( Type value, int i ) /將含將含的新元素插入到鏈表第的新元素插入到鏈表第 個(gè)位置個(gè)位

30、置 ListNode *p = Find ( i-1 ); / p 指向鏈表第指向鏈表第 i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if ( p = NULL ) return 0; ListNode *newnode = /創(chuàng)建結(jié)點(diǎn)創(chuàng)建結(jié)點(diǎn) GetNode ( value, plink ); if ( plink = NULL ) last = newnode; plink = newnode; /重新重新鏈接鏈接 return 1;Data StructureSoftware College Northeastern Universitytemplate Type *List:Remove ( int i )

31、/從鏈表中刪去第從鏈表中刪去第 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) ListNode *p = Find (i-1), *q; if ( p = NULL | plink = NULL ) return NULL; q = plink; plink = qlink; /重新鏈接重新鏈接 Type value = new Type ( qdata ); if ( q = last ) last = p; delete q; return &value;Data StructureSoftware College Northeastern Universitytemplate Type *List:Get ( int

32、i ) /提取第提取第 個(gè)結(jié)點(diǎn)的數(shù)據(jù)個(gè)結(jié)點(diǎn)的數(shù)據(jù) ListNode *p = Find ( i ); / p 指向鏈表第指向鏈表第 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if ( p = NULL | p = first ) return NULL; else return & pdata;Data StructureSoftware College Northeastern UniversityArray versus Linked Listsz Linked lists are more complex to code and management than arrays, but they have some

33、distinct advantages.yDynamic: a linked list can easily grow and shrink in size.-We dont need to know how many nodes will be in the list. They are created in memory as needed.-In contrast, the size of a C array is fixed at compilation time.yEasy and fast insertions and deletions-To insert or delete a

34、n element in an array, we need to copy to temporary variables to make room for new elements or close the gap caused by deleted elements.-With a linked list, no need to move other nodes. Only need to reset some pointers.Data StructureSoftware College Northeastern UniversityArrays versus linked listsz

35、Space (storage) considerationsyA linked list requires pointers to nodesyAn array requires the maximum number of elements to be known in advance. If that maximum is not required, space is wasted at the end of the array.Data StructureSoftware College Northeastern UniversityArrays versus linked listszT

36、ime considerationsyMost methods in a linked list require more statements than those in an array, which may indicate more time requiredyArrays are quicker at finding and altering in the middleyLinked lists are quicker at additions and removals in the middleData StructureSoftware College Northeastern

37、UniversityzIterator class of list is used to traverse nodes of list.zpriciple：y Iterator class is friend of List and ListNodey Iterator refer to the nodes of list。yData member current point to the node currently usedy Iterator privides some test and find operationData StructureSoftware College North

38、eastern University enum Boolean False, True ;template class List;template class ListIterator;template class ListNode /表結(jié)點(diǎn)表結(jié)點(diǎn)friend class List ;friend class ListIterator ;public: private: Type data; ListNode *link; Template definition(1)Data StructureSoftware College Northeastern Universitytemplate c

39、lass List /鏈表類鏈表類public: private: ListNode *first, *last;template class ListIterator public: ListIterator ( const List & l ) : list ( l ), current ( l.first-link ) /構(gòu)造函數(shù)構(gòu)造函數(shù): 引用鏈表引用鏈表 private: list list; ListNode * current;Template definition(2)Data StructureSoftware College Northeastern Universityt

40、emplate Boolean ListIterator : NotNull ( ) /檢查鏈表中當(dāng)前元素是否非空檢查鏈表中當(dāng)前元素是否非空 if ( current != NULL ) return True; else return False;currentcurrentcase 1 return True case 2 return FalseTemplate definition(3)Data StructureSoftware College Northeastern Universitytemplate Boolean ListIterator:NextNotNull ( ) /

41、檢查鏈表中下一元素是否非空檢查鏈表中下一元素是否非空 if ( current != NULL & currentlink != NULL ) return True; else return False; currentcurrentcase 1 return True case 2 return FalseTemplate definition(4)Data StructureSoftware College Northeastern Universitytemplate ListNode* ListIterator : Firster ( ) /返回鏈表中頭結(jié)點(diǎn)的地址返回鏈表中頭結(jié)點(diǎn)的地

42、址 current = list.first; return current;list.firstcurrent list with headerTemplate definition(5)Data StructureSoftware College Northeastern Universitytemplate Type * ListIterator : First ( ) /返回鏈表中第一個(gè)元素的地址返回鏈表中第一個(gè)元素的地址 if ( list.firstlink != NULL ) current = list.first-link; return ¤tdata; else

43、 current = NULL; return NULL; list.firstcurrent list with headerTemplate definition(5)Data StructureSoftware College Northeastern Universitytemplate Type* ListIterator : Next ( ) /返回鏈表中當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址返回鏈表中當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址 if ( current != NULL & currentlink != NULL ) current = currentlink; return & curren

44、tdata; else current = NULL; return NULL; currentcurrentTemplate definition(6)Data StructureSoftware College Northeastern Universityint sum ( const List &l ) ListIterator li ( l ); /鏈表為空時(shí)返回鏈表為空時(shí)返回0 int *p= li.First( ); retval = 0 /指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) while ( p != null ) /鏈表未掃描完鏈表未掃描完retval += *p; /累加累加 p=

45、 li.Next( ); return retval;Data StructureSoftware College Northeastern UniversityVariations of Linked ListszTwo problems - we cant get back to the beginning of the list - from the end, and we cant go backwards through the list. zSo, circular linked lists and doubly linked lists were invented.Data St

46、ructureSoftware College Northeastern UniversityVariations of Linked ListszCircular linked listsyThe last node points to the first node of the listyHow do we know when we have finished traversing the list? (Tip: check if the pointer of the current node is equal to the head.)HeadABData StructureSoftwa

47、re College Northeastern Universitytemplate class CircList;template class CircListNode friend class CircList;public: CircListNode ( Type d = 0, CircListNode *next = NULL ) : data ( d ), link ( next ) /構(gòu)造函數(shù)構(gòu)造函數(shù)private: Type data; CircListNode *link; Implementation of Circular linked lists(1)Data Struc

48、tureSoftware College Northeastern Universitytemplate class CircList public: CircList ( Type value ); CircList ( ); int Length ( ) const; Boolean IsEmpty ( ) return firstlink = first; Boolean Find ( const Type & value ); Type getData ( ) const; void Firster ( ) current = first; Boolean First ( ); Boo

49、lean Next ( ); Implementation of Circular linked lists(2)Data StructureSoftware College Northeastern University Boolean Prior ( ); void Insert ( const Type & value); void Remove ( );private: CircListNode *first, *current, *last;Implementation of Circular linked lists(3)Data StructureSoftware College

50、 Northeastern UniversityVariations of Circular Linked ListszCircular linked listsyconstruct an empty Circular linked list CircList ( const Type & value ) last =first = new CircListNode( value ); first-link = first; List ( const Type & value ) last =first = new ListNode( value ); Data StructureSoftwa

51、re College Northeastern Universitytemplate CircListNode*List :Find ( Type value ) /在鏈表中從頭搜索其數(shù)據(jù)值為在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)的結(jié)點(diǎn) CircListNode *p = firstlink; /檢測指針檢測指針 p 指示第一個(gè)結(jié)點(diǎn)指示第一個(gè)結(jié)點(diǎn) while ( p != first & pdata != value ) p = plink; return (p!=first)?p:NULL; / p 在搜索成功時(shí)返回找到的結(jié)點(diǎn)地址在搜索成功時(shí)返回找到的結(jié)點(diǎn)地址 / p 在搜索不成功時(shí)返回

52、空值在搜索不成功時(shí)返回空值Linked Lists: Searching in a CLLData StructureSoftware College Northeastern UniversityVariations of Linked ListszDoubly linked listsyEach node points to not only successor but the predecessoryThere are two NULL: at the first and last nodes in the listyAdvantage: given a node, it is easy

53、 to visit its predecessor. Convenient to traverse lists backwardsHeadABData StructureSoftware College Northeastern University Doubly linked listsData StructureSoftware College Northeastern Universitytemplate class DblList;template class DblNode friend class DblList;private: Type data; /數(shù)據(jù)數(shù)據(jù) DblNode

54、*lLink, *rLink; /指針指針 DblNode ( Type value, /構(gòu)造函數(shù)構(gòu)造函數(shù) DblNode *left, DblNode *right ) : data (value), lLink (left), rLink (right) Implementation of Doubly linked lists(1)Data StructureSoftware College Northeastern University DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) ;template

55、 class DblList public: DblList ( Type uniqueVal ); DblList ( ); int Length ( ) const; int IsEmpty ( ) return firstrlink = first; int Find ( const Type & target ); Type getData ( ) const;Implementation of Doubly linked lists(2)Data StructureSoftware College Northeastern University void Firster ( ) cu

56、rrent = first; int First ( ); int Next ( ); int Prior ( ); int operator ! ( ) return current != NULL; void Insert ( const Type & value ); void Remove ( );private: DblNode *first, *current;Implementation of Doubly linked lists(3)Data StructureSoftware College Northeastern UniversityDoubly linked list

57、s:Data StructureSoftware College Northeastern UniversityDoubly Linked Lists:constructingtemplate DblList:DblLIst ( Type uniqueVal ) /雙向循環(huán)鏈表的構(gòu)造函數(shù)雙向循環(huán)鏈表的構(gòu)造函數(shù), 創(chuàng)建表頭結(jié)點(diǎn)創(chuàng)建表頭結(jié)點(diǎn) first = new DblNode ( uniqueVal ); firstrLink = firstlLink = first; current = NULL;Data StructureSoftware College Northeastern Uni

58、versitytemplate int DblList:Find ( const Type & target ) /在雙向循環(huán)鏈表中搜索含在雙向循環(huán)鏈表中搜索含target的結(jié)點(diǎn)，的結(jié)點(diǎn)，/搜索成功返回搜索成功返回1，否則返回，否則返回0。 DblNode *p = firstrLink; while ( p != first & pdata != target ) p = prLink; /循鏈搜索循鏈搜索 if ( p != first ) current = p; return 1; return 0;Doubly Linked Lists:searchingAnother method

59、?Data StructureSoftware College Northeastern University1. plLink = current;2. prLink =currentrLink;3. currentrLink = p;4. current = currentrLink;5. currentrLinklLink = current;Doubly Linked Lists:Inserting(1)Data StructureSoftware College Northeastern Universitytemplate void DblList:Insert ( const T

60、ype & value ) if ( current = NULL ) /空表情形空表情形 current = firstrLink = new DblNode ( value, first, first ); else /非空表情形非空表情形 currentrLink =new DblNode ( value, current, currentrLink ); current = currentrLink; currentrLinklLink = current;Doubly Linked Lists:Inserting(2)Data StructureSoftware College No