【精品数据结构】Linear List

1、Chapter 3,Linear List,3.1 Preface,1. data object- a set of instances or values for example: Boolean=false,true Digit=0,1,2,3,4,5,6,7,8,9 Letter=A,B,Z,a,b,z NaturalNumber=0,1,2, Integer = 0, +1, -1, +2, -2, +3, -3, String=a,b,aa, ab, ac,3.1 Preface,data structure is a data object together with the re

2、lationships among the instances and among the individual elements that compose an instance Data_Structure=D,R D-data object， R -a set of relationships of all the data members in D.,3.2 Linear List,L = (e1, e2, e3, , en) list size is n if n=0: empty list if n0: e1 is the firstth (or front) element en

3、 is the last element ei immediately precedes ei+1,3.2 Linear List,Example: Students =(Jack, Jill, Abe, Henry, Mary, , Judy) Exams =(exam1, exam2, exam3) Days of Week = (S, M, T, W, Th, F, Sa) Months = (Jan, Feb, Mar, Apr, , Nov, Dec),3.2 Linear List,Operations: Create a linear list determine whether

4、 the list is empty determine the length of the list find the kth of the element search for a given element delete the kth element insert a new element just after the kth,3.2 Linear List,ADT specification of a linear list AbstractDateType LinearList instances ordered finite collections of zero or mor

5、e elements operations Create(); Destroy(); IsEmpty(); Length(); Find(k,x); Search(x); Delete(k,x); Insert(k,x); Output(out); ,3.3 Formula-based Representation,1. Use an array to represent the instance of an object (e1,e2,en) length=n each position of the array is called a cell or a node mapping form

6、ula:location(i)=i-1,Element 0 1 2 n-1 maxsize-1,3.3 Formula-based Representation,2. Class definition: program 3.1,template class LinearList public: LinearList(int MaxListSize =10); LinearList() delete element; bool IsEmpty() const return length= =0; int Length() const (return length); bool Find(int

7、k,T ,3.3 Formula-based Representation,3. Operations: 1) Constructor: template LinearList:LinearList(int MaxListSize) MaxSize=MaxListSize; element=new TMaxSize; length=0; ,3.3 Formula-based Representation,2) bool Find(int k,T private: T data; chainNode *link; ,3.4 Linked Representation,template class

8、 Chain public: Chain( )first=0; Chain( ); bool IsEmpty( )const return first= =0; int Length( ) const; bool Find(int k, T ,3.4 Linked Representation,3.operations 1)delete all the nodes in a chain program 3.9 2)determine the length of a chain program 3.10 3)find the kth element of a chain program 3.11

9、,3.4 Linked Representation,4)search for a chain program 3.12 5)output a chain program 3.13,3.4 Linked Representation,6) Deletion a element of a chain,first = first-link;,3.4 Linked Representation,first get to node just before node to be removed,before= first -link;,3.4 Linked Representation,now chan

10、ge pointer in before,before -link = before -link -link;,before,a,b,c,d,e,null,first,3.4 Linked Representation,Operation deleteprogram 3.14 templateChain ,3.4 Linked Representation,Step 1: get a node, set its data and link fields,ChainNode newNode = new ChainNode(f, first);,7) insert operation -inser

11、t(0,f),3.4 Linked Representation,Step 2: update first,first = newNode;,3.4 Linked Representation,newNode-link=first; first = newNode;,insert(3,f),1. first find node whose index is 3,2. next create a node and set its data and link fields,ChainNode newNode = new ChainNode(f,before -link);,3.finally li

12、nk before to newNode,before-link = newNode;,Two-Step insert(3,f),before = first -link -link; newNode -link = before -link; before -link = newNode;,3.4 Linked Representation,Operation insertprogram 3.15 templateChain ,3.4 Linked Representation,4.Extensions to class chain include some additional funct

13、ions such as: 1)Erasedelete all nodes in a chain 2)Zeroset the first pointer to 0, but dont delete any node 3)Appendadd an element to the end of a chain.(to keep track of the last node in the chain, we use a new private member ChainNode* last.),3.5 simply linked Circular List,figure,3.5 Simply Linke

14、d Circular List With Head Node,3.5 simply linked Circular List,For example: Josephus Problem n=8 m=3 3,6,1,5,2,8,4 7,3.5 simply linked Circular List,#include #include”CircList.h” template void CircList: Josephus(int n,int m) Firster( ); for (int i=0 ; in-1 ; i+) for ( int j=0 ; jm-1 ; j+) Next( ); c

15、out“delete person”getdata( )endl; remove( ); ,3.5 simply linked Circular List,void main( ) CircList clist; int n, m; coutnm; for ( int i=1; i=n; i+) clist.insert(i); clist.Josephus(n,m); ,3.6 Doubly Linked List,figure,3.6 Doubly Linked List,1. Class definition for doubly linked list( program 3-21) t

16、emplate class DoubleNode friend DoubleNode; private: T data; DoubleNode*left, *right; ,template class Doubl public: Double( )LeftEnd = RightEnd = 0; Double( ); int Length( ) const; bool Find(int k, T ,3.6 Doubly Linked List,2. Operations: Insert, Delete,3.6 Doubly Linked List,insert(0,f),firstNode-l

17、link=newNode;,newNode-llink=null; newNode-rlink=firstNode;,firstNode=newNode,3.6 Doubly Linked List,Insert(2,f),beforeNode,newNode-llink=beforeNode; newNode-rlink=beforeNode-rlink;,beforeNode-rlink-llink=newNode; beforeNode-rlink=newNode;,3.6 Doubly Linked List,Delete(1),P=firstNode; firstNode=p-rlink; firstNode-llink=