第二章-线性表(1)--英文.ppt

1、Chapter Two,List,2.1 List,A finite set of n（ 0） elements with the same characteristics (a0, a1, a2, a3, ., an-1) 0= i n ai is element and n is the length,( Ordered or Linear Lists “Ordered” means that each element has a position in the list ),Definition,Characteristics,A finite set; Only one “the fi

2、rst” element; Only one “the last” element; Every Element except the first one has only one predecessor; Every Element except the last one has only one successor,Preliminaries,Empty List contains no elements; Length The number of elements stored; Head The beginning of the list; Tail The end of the li

3、st; Sorted list The elements positioned in ascending order of value; Unsorted list have no particular relationship between element values and positions.,Operations on the ordered List,Find the length of the list, n; Read the list from left to right ; Retrieve the i-th element,0= i =n-1; Store a new

4、value into the i-th position, 0= i =n-1;,Insert a new element at position i, 0= i =n-1 causing elements numbered i, i+.n to become numbered i+1, i+2, ., n+1; Delete the element at position i, 0= i =n-1 causing elements numbered i+1, ., n to become numbered i, i+1, ., n-1;,class LinearList / 对象: L =

5、( a0, a1, , an-1) 或 ( ), ai浮点数, 0i n public: LinearList ( ); / 构造函数，创建一个空表 int Length( ); / 返回该实例的长度 void LeftToRight( ); / 从左到右遍历全部元素 float Retrieve( int i ); / 返回第i个元素的值 void Store( int i, float v ); / 将v的值赋予第i个元素 void Insert( int i, float v ); / 将v作为第i个元素插入 float Delete( int i ); / 删除第i个元素并返回其值 ;

6、,The ADT definition of ordered list,2.2 Array-Based List,The most common way to represent an ordered list is by an array,a consecutive set memory locations a set of pairs: ( Index,value) a sequential mapping (the array index i, the list element ai),LOC(a i+1)=LOC(a i) + Length,LOC(a i+1)=LOC(a1)+Len

7、gth*i,Random Access,Retrieve and modify the values of random elements in the list in a constant amount of time,Representation of array-based list,#define maxSize Typedef int T; Typedef struct T datamaxSize; int n; SeqList; /静态表示 Typedef int T; Typedef struct T *data; int maxSize, n; SeqList; /动态表示,I

8、mplementation of some operations of list,template LinearList:LinearList ( int sz ) /构造函数 if ( sz 0 ) MaxSize = sz; last = -1; data = new TMaxSize; if (data=NULL) cerr “Allocation Error” endl; exit(1); ,Initialize,template LinearList:LinearList (LinearList ,Initialize,template LinearList:reSize (int

9、newSize) if (newSize=0) cerr “Invalid Size of Array” endl; exit; if (newArray != maxSize) T *newArray = new TnewSize; if (newArray = NULL) cerr “Allocation Error” endl; exit(1); int n = last+1; / int n = min(last+1, newSize) T *srcptr = data; T *desptr = newArray; while (n-) *desptr+ = *srcptr +; de

10、lete data; data = newArray, maxSize = newSize; ,Extend Storage Space,template int LinearList:Search ( T ,Sequence Search,x = 48 x = 50,Sequence Search,The Average Comparing Number for successful search (ACN),pi is Search probability for ith element ci is Comparing Number for ith element,If the searc

11、h probabilities are the same for all elements, then p0=p1=.=pn-1=1/n, so,The ACN for un-successful search is n,template int LinearList:Insert ( T /插入成功 ,Element Insertion,Element Insertion,Average Moving Number,template int LinearList:Remove ( T /表中没有x ,Element deletion,Element deletion,Average Movi

12、ng Number,Application Sets Operations,template void Union ( LinearList ,Union of Set A and Set B (AB) (putting the elements of set B into set A),template void Intersection ( LinearList ,Intersection of Set A and Set B(AB),Application - Polynomial,There are n+1 terms in n degree Pn(x) function P of x

13、 with n degree,A(x) = 3x2 + 2x + 4,B(x) = x4 + 10 x3 + 3x2 +1,Pn (x) = an xn + an-1 xn-1 + .a1x + a0,Coefficients系数 a0, a1, a2, , an Exponents 指数i 0, 1, 2, , n The largest exponent is its degree.,class Polynomial public: Polynomial ( ); /构造函数 int operator ! ( ); /判是否零多项式 float Coef ( int e); int Lea

14、dExp ( ); /返回最大指数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x);/求值 evaluate ,The ADT of Polynomial,Polynomial representation,The first： private: Static Array (静态数 int degree; 组表示) float coef maxDegree+1; Pn(x) can be represented as： pl.degree = n pl.coef

15、i = ai 0 i n,The second：private: Dynamic Array (动态数 int degree; 组表示) float * coef; Polynomial:Polynomial (int sz) degree = sz; coef = new float degree + 1; These two storage representations are suitable to polynomials with consecutive exponents. But they are not suitable for Sparse polynomials: P101

16、(x) = 3 + 5x50 - 14x101,The third representation： class Polynomial; /forward declaration class term friend Polynomial; private: float coef; / Coefficients int exp; / Exponents ;,class Polynomial /Definition of Polynomial public: private: static term termArrayMaxTerms; / term Array static int free; /

17、location of free /静态数据成员在类声明外分配空间和初始化 / term Polynomial:termArrayMaxTerms; / int Polynomial:free = 0; int start, finish; /多项式始末位置 ,A(x) = 2.0 x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101,Two Polynomials are stored in termArray,Addition of two polynomials,The result is stored in the termArray Scan two po

18、lynomials, if not the end, compare two exponents:,If the same, add two coefficients; if the result is not 0, insert into the result polynomial; If not the same, insert the term with smaller exponent into the result polynomial; If one polynomial is ended, copy remain terms of another polynomial into

19、the result polynomial;,Polynomial Polynomial:Add ( Polynomial B ) Polynomial C; int a = start; int b = B.start; C.start = free; float c; while ( a = finish ,case : NewTerm ( termArraya.coef, termArraya.exp ); a+; for ( ; a=finish; a+ ) /a未检测完时 NewTerm ( termArraya.coef, termArraya.exp );,for ( ; b=B

20、.finish; b+ ) /b未检测完时 NewTerm ( termArrayb.coef, termArrayb.exp ); C.finish = free-1; return C; ,void Polynomial:NewTerm ( float c, int e ) /把一个新的项加到多项式C(x)中 if ( free = maxTerms ) cout Too many terms in polynomials” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; ,Add new term i

21、nto the result polynomial C(x),m is the non zero-term number of A A.finish = A.start+ m-1 n is the non zero-term number of B B.finish = B.start + n-1 The number of iteration is bounded by (m + n -1) The worst-case is O ( m + n ),Analysis,2.3 linked List,The simple data structures of array-based list

22、 (a0, a1, a2, a3, ., an-1) A finite set; Only one “the first” element; Only one “the last” element; Every Element except the first one has only one predecessor; Every Element except the last one has only one successor,Data object,Linear List (a0, a1, a2, a3, , an-1) The representation of it : Array

23、and a sequential mapping,The property of these representations are :,Data object,a consecutive (Successive) set memory locations a sequential mapping (the array index i, the list element ai) The order of elements in the Array is the same as the order in the Linear List a set of pairs: ( index, value

24、),LOC(a i+1)=LOC(a i) + Length,Random Access,Access any data object in the list and get its value in a constant amount of time,constant,Sequential storage schema,The Disadvantage : The operations of insertion and deletion will cost more time,1,2,i+1,a1,a2,ai,a i+1,an,1,2,i,i+1,n-1,a1,a2,ai,a i+1- i,

25、an- n-1,a n-1,a n-1-n-2,elements numbered i+1,.n to become elements numbered i, i+1,.n-1,a i-1,a i-1,O(n),ai,a1,a2,ai,a i+1,an,a n-1,a1,a2,ai-i+1,a i+1-i+2,an-n+1,a n-1-n,a,1,2,i,i+1,n,n+1,elements numbered i,.n to become elements numbered i+1,.n+1,O(n),A Linked List (Chain),A single Linked List (Ch

26、ain),Why? The advantages,Singly Linked List,The basic element (component ) is a Node。There are 2 items (fields):,Data object,(Location /address) Pointer of the next element,The properties of the Linked list structure:,a 0,a 3,a 1,a 2,First,Last,The nodes can be in anywhere of the memory, dont have t

27、o be stored in the sequential schema The Logic order dont have to be the same in the physical order.,The List can be easily extended,first,newnode,newnode,first,O(1),(Before insertion) (After Insertion),first,Before deletion,After deletion,O(1),The disadvantage,It takes O(n) time to look for a node,

28、 if giving the node number or the value of the element.,Representing List in C+,defining a List Node and a List Multi-Classes ListNode class List class,class List; /declaration for List class ListNode /Definition for ListNode friend class List; / List as a friend class private: int data; / data item

29、 ListNode *link; / link item ; class List /Definition for List public: /Operations private: ListNode *first, *last; /The pointers for. ;,class List /Nested definition public: /Operations private: class ListNode public: int data; ListNode *link; ; ListNode *first, *last; ;,The operations on List,Crea

30、tion Insertion Deletion,void List: Create2() first =new ListNode(10); first-link = new ListNode(20); ListNode:ListNode (int element = 0) / constructor data = element; link = 0; ,Insertion,Case one：Insert new node at head of the list newnodelink = first ; first = newnode；,（Before insertion） （After in

31、sertion),first,newnode,first,newnode,Case two：Insertion within the list newnodelink = plink; plink = newnode；,（Before insertion） （After insertion),Case three：Insertion at the tail of the list newnodelink = plink; plink = last = newnode；,（Before insertion） （After insertion),int List:Insert ( const in

32、t x, const int i ) /在链表第i个结点处插入新元素x ListNode *p = first; int k = 0; while ( p != NULL /创建新结点,其数据为x,指针为0,if ( first = NULL | i = 0 ) /插在表前 newnodelink = first; if ( first = NULL ) last = newnode; first = newnode; else /插在表中或末尾 newnodelink = plink; if ( plink = NULL ) last = newnode; plink = newnode;

33、return 1; ,t-link = x-link; x-link = t;,void List: Insert50(ListNode *x) ListNode *t =new ListNode(50); If (!first) / insert into empty list first = t; return; /exit List: Insert50 t-link = x-link; x-link = t; ,Case one: Delete the first node q = first; first = firstlink; delete q; Case two: Delete

34、the node within or at the tail of the list q = plink; plink = qlink; delete q;,Deletion,int List:Delete ( int i, int ,if ( i = 0 ) /删除表中第1个结点 q = first; /q保存被删结点地址 p = first = firstlink; /修改first else /删除表中或表尾元素 q = plink; plink = qlink; /重新链接 if ( q = last ) last = p; /可能修改last x = qdata; delete q;

35、 /删除q return true; ,void List: Delete(ListNode *x, ListNode *y) / y precedes x and let y= =0 iif x = = first if (!y) first = first-link; else y-link = x-link; delete x; ,Comparison of List Implementation,MEMORY ALLOCATED The size of array-based lists must be predetermined before the array can be all

36、ocated, Linked list only need space for the objects actually on the list and there is no limit to the number of elements on the linked list; SPACE EFFICIENCY To array based list, there is no wasted space for the individual element. Linked lists require that a pointer be added to every list node;,ACC

37、ESS Array-based lists are faster for random access by position (O(1). In contrast single linked lists have no explicit access to the previous element, and access by position requires that we march down the list from the front to the specified position (O(n); INSERT and REMOVE Given a pointer to a su

38、itable location in the list, the insert and remove functions for linked lists require only O(1) times. Array-based list must shift the remainder of the list up or down within the array. This requires O(n) time in the average and worst cases.,A reusable Linked List Class,Implementing Linked Lists wit

39、h Template It is easy for class to be reused List -int, ListNode It means the members of ListNode can be accessed by members of List,The Template of the Single Linked List,template class List; template class ListNode friend class List; Type data; /Node data ListNode *link; /Node Pointer public: List

40、Node ( ); /Constructor ListNode ( const Type /Next Node Address,ListNode *GetNode ( const Type,template ListNode : ListNode ( ) : link (NULL) template ListNode: ListNode( const Type /*this,Some Implementations,template ListNode *ListNode:GetNode ( const Type template ListNode *ListNode:RemoveAfter (

41、 ) ,template ListNode *ListNode:RemoveAfter ( ) ListNode *tempptr = link; if ( link = NULL ) return NULL; /If no next node, return NULL link = tempptrlink /Build the link return tempptr; /return the address of the next node ,template class List ListNode *first, *last; public: List ( const Type /Dest

42、ructor,void MakeEmpty ( ); /Make the list Empty int Length ( ) const; /The length of the List ListNode *Find ( Type value ); ListNode *Find ( int i ); int Insert ( Type value, int i ); Type *Remove ( int i ); Type *Get ( int i ); ; template List : List ( ) /Destructor MakeEmpty ( ); delete first; /Make the List empty，Delete the first Node ,while ( p != NULL ,template void List : MakeEmpty ( ) /Delete all Nodes in a List except the first one ListNode *q; while ( firstlink != NULL )