《数据结构的算法在C++中的应用》（英文版）Chapter 3 Linear List

Chapter 3 Linear list

Chapter 3 Linear List

3.1 Preface 1. data object- a set of instances or values for example Booleanfalse, true) Digit={0,1,2,3,4,56,78,9} Letter-A B,..Z, a, b,...Z) NaturalNumber= 0, 1, 2,.. Integer={0,+1,-1,+2,-2,+3,-3,…} Stringa,b aa. ab. ac

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 2. data structure is a data object together with the relationships 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.1 Preface ２．data structure is a data object together with the relationships 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=( list size is n if n=0: empty list ifn>o is the first'th(or front)element e. is the last element e; immediately precedes eit

3.2 Linear List L = (e1 , e2 , e3 , …, en ) list size is n if n=0: empty list if n>0: e1 is the first’th (or front) element en is the last element ei immediately precedes ei+1

3.2 Linear list Example Students=Jack, Jill, Abe, Henry, Mary. Judy) Exams=(examl, exam2, exam) Days of Week=(S, M, T, W, Th, F, Sa Months=(Jan, Feb, Mar, Apr,., Nov, Dec

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 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 Operations: Create a linear list determine whether 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 AbstractDate Type Linearlist i instances ordered finite collections of zero or more elements operations CreateD Destroyo IsEmpty (; Length Find(k, x) earch(X Delete(k, x); Insert(k, x) Output(out)

3.2 Linear List ADT specification of a linear list AbstractDateType LinearList { instances ordered finite collections of zero or more 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 Element 1 2 maxsize -I e1.e ength each position of the array is called a cell or a node mapping formula: location(i=i-1

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 formula:location(i)=i-1 e1 e2 e3 en Element 0 1 2 n-1 maxsize-1

3. 3 Formula-based Representation 2. Class definition: program 3. 1 template class Linearlist i public Linearlist(int Maxlistsize =10) Linearlistoi delete[ element bool isemptyo const return length==0; 1 int Length( const(return length) bool find(int k, T&x) const int Search(const T&x)const Linearlist & delete(int k, T&x Linearlist & insert(int k, const T&x) void Output(ostream& out)const private int length; int MaxSize; T*element

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 k,T&x) const; int Search(const T&x) const; LinearList & Delete(int k,T&x); LinearList & Insert(int k, const T&x); void Output(ostream& out) const; private: int length; int MaxSize; T* element; }

3.3 Formula-based Representation 3. operations 1)Constructor template : Linearlist(int MaxListSize) MaxSizemaxlistSize element=new T[MaxSize] length=0

3.3 Formula-based Representation 3. Operations: 1) Constructor: template LinearList::LinearList(int MaxListSize) { MaxSize=MaxListSize; element=new T[MaxSize]; length=0; }