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

1、Chapter 2 Array 2022/7/181OverviewADT of Array Sequence ListADT of PolynomialSpecial Array and Sparse ArrayStringSTL vector, deque,list and string 2022/7/182 Array：The basic mechanism for storing a collection of identically-typed objects. What is an array?2022/7/183The character of array it is linea

2、r structureEach element except the first has a unique predecessor, and each element except the last has a unique successor.Given the size of the element and the start address, we can know the address of any element2022/7/184Definition and initializationTwo way to Define an array: static array,dynami

3、c arrayExample#include class szcl int e; public: szcl ( ) e = 0; szcl ( int value ) e = value; int get_value ( ) return e; 2022/7/185main ( ) szcl a13 = 3, 5, 7 , *elem; for ( int i = 0; i 3; i+ ) cout a1i.get_value ( ) “n”; /print the static array elem = new szcl3; for ( int i = 0; i 3; i+ ) cout g

4、et_value( ) “n”; /print the dynamic array elem+; return 0;Static arrayDynamic array2022/7/186Primitive arrays cant satisfy usWe expect a copy of an array to copy the entire collectionWe expect an array to know how many objects are in its collectionWe expect that when allocated arrays are no longer n

5、eeded, the memory that these arrays consumes is automatically reclaimedHow to do ?2022/7/187ADT of Array Class Declaration #include #include template class Array Type *elements; int ArraySize; /current size void getArray ( ); / dynamic allocate memory for array public: Array( int Size=DefaultSize );

6、 Array( const Array& x );2022/7/188 Array( ) delete elements; Array & operator = /copy array ( const Array & A ); Type& operator ( int i ); /get the ith element Type* operator *( ) const /* operator return elements; int Length ( ) const /get the length return ArraySize; void ReSize ( int sz ); /resi

7、ze the array 2022/7/189 template void Array:getArray ( ) /private function, create the space to store the elements elements = new TypeArraySize; if ( elements = 0 ) ArraySize = 0; cerr Memory Allocation Error endl; return; The interfaces of array class 2022/7/1810 template Array:Array ( int sz ) /co

8、nstructor if ( sz = 0 ) ArraySize = 0; cerr “非法數(shù)組大小” endl; return; ArraySize = sz; getArray ( ); 2022/7/1811 template Array: Array ( const Array & x ) /copy constructor int n = ArraySize = x.ArraySize; elements = new Typen; if ( elements = 0 ) ArraySize = 0; cerr “存儲(chǔ)分配錯(cuò)” endl; return; Type *srcptr =

9、 x.elements; Type *destptr = elements; while ( n- ) * destptr+ = * srcptr+; 2022/7/1812template Type & Array:operator ( int i ) /get the element by index if ( i ArraySize-1 ) cerr “數(shù)組下標(biāo)超界” endl; return NULL; return elementi; Pos = Positioni -1 + Numberi -12022/7/1813 template void Array:Resize (int

10、sz) if ( sz = 0 & sz != ArraySize ) Type * newarray = new Typesz; if ( newarray = 0 ) cerr “存儲(chǔ)分配錯(cuò)” endl; return; int n = ( sz = ArraySize ) ? sz : ArraySize; Type *srcptr = elements; Type *destptr = newarray; while ( n- ) * destptr+ = * srcptr+; delete elements; elements = newarray; ArraySize = sz;

11、2022/7/1814Two-dimensional array three-dimensional arraycolumn index i page index irow index j row index j column index k2022/7/1815LOC ( i ) = LOC ( i -1 ) + l =+ i*lOne-dimensional array2022/7/1816Two-dimensional arrayRow major order: LOC ( i, j ) = a + ( i * m + j ) * lColumn major order:LOC ( i,

12、 j ) = a + ( j * n + i ) * l2022/7/1817dimension values are m1, m2, m3 the address of the element associated with index i, j, kLOC ( i, j, k ) = a + ( i *m2*m3+j*m3+ k )* l Three-dimensional array2022/7/1818dimension values are m1, m2, m3, , mn the address of the element associated with index i1, i2

13、, i3, , inLOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + in-1*mn + in ) * l n-dimensional array2022/7/1819a0a1ai-1aiai+1an-1Sequential mappingSequence listUsing consecutive set of memory locations (Array)Address of element ai Loc(ai ) = Loc( a0 )+ i L Random-access storage2022/7/1820Seque

14、nce list ：Dynamic array template class SeqList Type *data; int MaxSize; int last; /index of the last elementpublic: SeqList ( int MaxSize = defaultSize ); SeqList ( ) delete data; int Length ( ) const return last+1; int Find ( Type & x ) const;Implementation:Sequence list2022/7/1821 int IsIn ( Type

15、& x ); int Insert ( Type & x, int i ); int Remove ( Type & x ); int Next ( Type & x ) ; int Prior ( Type & x ) ; int IsEmpty ( ) return last =-1; int IsFull ( ) return last = MaxSize-1; Type Get ( int i ) return i last？NULL : datai; Interface of sequence list2022/7/1822template SeqList : SeqList ( i

16、nt sz ) /constructor if ( sz 0 ) MaxSize = sz; last = -1; data = new TypeMaxSize; if ( data = NULL ) MaxSize = 0; last = -1; return; Implementation of sequence list2022/7/1823template int SeqList:Find ( Type & x ) const /sequence find x from begin to end int i = 0; while ( i last ) return -1;/failur

17、e else return i; /success 2022/7/1824template int SeqList:IsIn ( Type & x ) /Is x in the List? int i = 0, found = 0 while ( i = last & ! found ) if( datai ! = x ) i +; else found = 1; /success return found; 2022/7/1825Diagram of finding x = 48 x = 502022/7/1826Success: Average Comparing NumberFailur

18、e: n2022/7/1827Insertion如何移動(dòng)？for ( int j = i; j i; j- ) dataj = dataj - 1;2022/7/1828template int SeqList:Insert ( Type & x, int i )/insert x into the list as the ith element if ( i last+1 | last = MaxSize-1 ) return 0; /failure else last+; for ( int j = last; j i; j- ) dataj = dataj -1; datai = x;

19、return 1; /success 2022/7/1829deletion2022/7/1830 template int SeqList:Remove ( Type & x ) /delete x from the list int i = Find (x); /find x if ( i = 0 ) last- ;for ( int j = i; j = last; j+ ) dataj = dataj+1; return 1; /succeed return 0; /failure 2022/7/1831template int SeqList: Next( Type & x ) /G

20、ets the next element in list. int i = Find (x); /find x if ( i = 0 & i last) return i + 1; else return -1; /failure template int SeqList: Prior( Type & x ) /gets the predecessor int i = Find (x); /find x if ( i = 0 & i = last) return i - 1; else return -1; 2022/7/1832順序表用數(shù)組實(shí)現(xiàn)的操作的特點(diǎn)1.通過(guò)元素的存儲(chǔ)順序反映線性表中

21、數(shù)據(jù)元素之間的邏輯關(guān)系；2.可隨機(jī)存取順序表的元素；3.順序表的插入、刪除操作要通過(guò)移動(dòng)元素實(shí)現(xiàn)，效率較低；4.元素較少時(shí)存儲(chǔ)空間的利用率較低。2022/7/1833Example2-1：using sequence list to resolve the union of two set A and B A A B idea：（1）use type SqList to store set LA and LB（2）get element from LB not existent in LA,add them to LA ABApplication:sequence list2022/7/183

22、4template void Union ( SeqList & LA, SeqList LB ) int n = LA.Length ( ); int m = LB.Length ( ); for ( int i = 1; i = m; i+ ) Type x = LB.Get(i); /在LB中取一元素 int k = LA.Find (x); /在LA中搜索它 if ( k = -1 ) /若未找到插入它 LA.Insert (n+1, x); n+; Time complexity：O(ListLength(La)*ListLength(Lb)AB4321Application:seq

23、uence list2022/7/1835Example2-2：using sequence list to compute A-B idea：（1）use type SqList to store ordered list（2) Delete the element which isnt in other list through comparing ABApplication:sequence list2022/7/1836template void Intersection ( SeqList & LA, SeqList & LB ) int n = LA.Length ( ); int

24、 m = LB.Length ( ); int i = 0; while ( i n ) Type x = LA.Get (i); int k = LB.Find (x); if ( k = -1 ) LA.Remove (x); n-; else i+; Application:sequence list2022/7/1837 P = (p0, p1, p2 , pn) Q = (q0, q1, q2, qm) R = (p0+q0, p1+q1, , pm+qm, pm+1, , pn )P(x) = p0 + p1 x + p2 x2 + + pn xnQ(x) = q0 + q1 x

25、+ q2 x2+ + qm xm Addition of two polynomials ,suppose mn R(x)=(p0+q0)+(p1+q1)x+(pn+qm)xm+pm+1 xm+ +pn xnADT of Polynomial2022/7/1838class Polynomial public: Polynomial ( ); int operator ! ( ); /if *this is zero , return 1. else return 0 float Coef ( int e); /return coefficient of the item with e exp

26、onent int LeadExp ( ); /return the max exponent Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x);Polynomial ADT2022/7/1839 Physical representationFirst ： private: (static int degree;array) float coef maxDegree+1; Pn(x) ： pl.degree = n pl.coefi = ai, 0 i n202

27、2/7/1840Second：private: (dynamic int degree;Array ) float * coef; Polynomial:Polynomial (int sz) degree = sz; coef = new float degree + 1; Pn(x)：pl.degree = npl.coefi = ai, 0 i n2022/7/1841Some polynomial only have few nonzero coefficents ： P101(x) = 3 + 5x50 - 14x101 pl.degree = 101 pl.coef = new f

28、loat10230051401250101Method：Only store the nonzero item2022/7/1842第三種： class Polynomial;class term /多項(xiàng)式的項(xiàng)定義friend Polynomial;private: float coef; /系數(shù) int exp; /指數(shù);2022/7/1843class Polynomial public: private: static term termArrayMaxTerms; static int free; /current address of free space / term Polyno

29、mial:termArrayMaxTerms; / int Polynomial:free = 0; int start, finish; 2022/7/1844 A(x) = 2.0 x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101 store two polynomials in termArray2022/7/1845Add two polynomials 結(jié)果多項(xiàng)式另存掃描兩個(gè)相加多項(xiàng)式，若都未檢測(cè)完： 若當(dāng)前被檢測(cè)項(xiàng)指數(shù)相等，系數(shù)相加。 若未變成 0，則將結(jié)果加到結(jié)果多項(xiàng)式。 若當(dāng)前被檢測(cè)項(xiàng)指數(shù)不等，將指數(shù)小者加到結(jié)果多項(xiàng)式。若有一個(gè)多項(xiàng)式已檢測(cè)完，將

30、另一個(gè)多項(xiàng)式剩余部分復(fù)制到結(jié)果多項(xiàng)式。2022/7/1846Polynomial Polynomial:operator+(Polynomial B) Polynomial C; int a =start; int b = B.start; C.start = free; float c; / coefficient of result polynomial while ( a = finish & b : NewTerm ( termArrayb.coef, termArrayb.exp ); b+; break; case : NewTerm ( termArraya.coef, term

31、Arraya.exp ); a+; for ( ; a = finish; a+ ) NewTerm ( termArraya.coef, termArraya.exp ); 2022/7/1848 for ( ; b = maxTerms ) cout Too many terms in polynomials” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; 2022/7/1850Triangle matrix -upper triangle matrix -lower triangle matrixD

32、iagonal matrix Symmetric matrix -It is symmetric to its main counter-diagonalAsymmetric matrixSparse matrix Types of Matrix2022/7/1851Triangle matrix -lower triangle matrix -upper triangle matrixSpecial Matrixa00 0 0 0a10 a11 0 0an-10an-11 an-1n-1a00 a01 a0n-10 a11 a1n-10 0 0 an-1n-12022/7/1852a00 a

33、10 an-10a10 a11 an-11an-10 an-11 an-1n-1a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1Special MatrixSymmetric matrix-It is symmetric to its main counter-diagonal2022/7/1853Store the lower triangle onlyRequired a space: n(n+1)/2a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1k= 0 1 2 3 4 5 6 n(n+1)/2-1 Speci

34、al MatrixWe can store a Symmetric matrix with compressed way a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-12022/7/1854k =i(i+1)/2 +j when i jj(j+1)/2 +i when i ja00 a10 a11 a20 a21 a22 an10 an11 an1n1k= 0 1 2 3 4 5 6 n(n+1)/2-1 For example：address of element a42 in one-dimensional array sa ： k=4*(4+1)/

35、2+2=12 sa12= a42Special Matrix2022/7/1855a00 a11 a 02 0 0 0 0 0 0 0 0 0 a10 a11 a12 a13 0 0 0 0 0 0 0 0a20 a21 a22 a23 a24 0 0 0 0 0 0 00 a31 a32 a33 a34 a35 0 0 0 0 0 00 0 a42 a43 a43 a45 a46 0 0 0 0 00 0 0 a53 a54 a55 a56 a57 0 0 0 0 0 0 0 0 a64 a65 a66 a67 a68 0 0 0 0 0 0 0 0 a75 a76 a77 a78 a79

36、0 0 0 0 0 0 0 0 a86 a87 a88 a89 a810 0 0 0 0 0 0 0 0 a97 a98 a99 a910 a9110 0 0 0 0 0 0 0 a108 a109 a1010 a1011 0 0 0 0 0 0 0 0 0 a119 a1110 a1111d Diagonal matrixd:Width of half bandThe number Non-zero elements:(2d+1)*n-(1+d)*d2022/7/18560 a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 0K= 0 1

37、 2 3 4 5 6 7 8 9 10 11 12 13 14a 00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 00 0 a32 a33 a340 0 0 a43 a44The number of non-zero elements per row: n(2d+1)The address of aij in compressed array :k=i*(2d+1)+d+(j-i)How do we calculate the address of the diagonal matrix that d=2,n=6?？example：d=1Special M

38、atrix2022/7/1857Sparse MatrixA matrix is sparse if it has only a small number of non-zeros.8/6*7 = 8/322022/7/1858Sparse MatrixSparse Matrices in real applications are usually huge. Much space can be saved if we only store non-zeros.Space cost for all matrix entries = O(mXn)Space cost for non-zeros

39、entries = O(t)Problem : if only non-zeros are stored,we also need to store their Location in a matrix.So a good representation is required.2022/7/1859Sparse MatrixSome variables are defined in Sparse Matrix Type:Height numbers of rowsWidth - numbers of column3 Vector Type to store non-zeros entries

40、and their locations. 2022/7/1860Structure Sparse_Matrix isobjects: a set of triples, , where row and column are integers and form a unique combination, and value comes from the set item.functions: for all a, b Sparse_Matrix, x item, i, j, max_col, max_row indexSparse Matrix2022/7/1861Sparse_Marix Cr

41、eate(max_row, max_col) := return a Sparse_matrix that can hold up to max_items = max _row max_col and whose maximum row size is max_row and whose maximum column size is max_col.Sparse_Matrix Transpose(a) := return the matrix produced by interchanging the row and column value of every triple.Sparse_M

42、atrix Add(a, b) := if the dimensions of a and b are the same return the matrix produced by adding corresponding items, namely those with identical row and column values. else return error Sparse Matrix2022/7/1862Sparse_Matrix Multiply(a, b) := if number of columns in a equals number of rows in b ret

43、urn the matrix d produced by multiplying a by b according to the formula: d i j = (aikbkj) where d (i, j) is the (i,j)th element else return error.Sparse Matrix2022/7/1863 A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0row col value0123456782 0 -35 0 150

44、1 124 1 180 2 93 2 245 3 -72 5 14Sparse Matrix2022/7/1864#define MAX_TERMS 101 /* maximum number of terms +1*/typedef struct int col; int row; int value; term;typedef struct int rows; int cols; int terms; term elemMAX_TERMS; Sparse_Matrix;Sparse Matrix2022/7/1865 A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0

45、 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0row col value0123456782 0 -35 0 150 1 124 1 180 2 93 2 245 3 -72 5 14Sparse MatrixA.rowsA.columnsA.TermsA.elem6782022/7/1866transpose matrixSparse MatrixSparsematrix2022/7/1867Transpose(int *a,int *b,int m,int n)/*Transpose a to b */ int i,j; f

46、or(i=0;im;i+) for(j=0;jcols = a.rows; b-rows = a.cols; b-terms = a.terms; if(b-terms 0) currentp = 0; for(k=0;krows;k+) /*select kth row */ for(i=0;ielemcurrentp.row = k; b-elemcurrentp.col = a.elemi.row; b-elemcurrentp.value = a.elemi.value; currentp+; return *b;Space complexity: O(1) time complexi

47、ty :O(terms*cols) O(m*n2)2022/7/1871Sparse Matrix2022/7/1872Fast-transpose Solution:-Determine the number of elements in each column of the original matrix. -Determine the starting positions of each row in the transpose matrix.Create two array to store the number of elements and starting positions o

48、f each row in transposed matrixScan a.term array,determine the position of a element stored in b.term according to its column and rowStartTime complexity : O(max(Terms, Cols) Space complexity :O(Cols)Sparse Matrix2022/7/1873Sparse_Matrix Fast-Transpose(Sparse_Matrix a) int i,k; int *rowSize,*rowStar

49、t; int p,q; Sparse_Matrix *b; b = (Sparse_Matrix *) malloc(sizeof(Sparse_Matrix); b-cols = a.rows; b-rows = a.cols; b-terms = a.terms; rowSize = (int *)malloc(b-rows *sizeof(int); rowStart = (int *)malloc(b-rows * sizeof(int); for(i=0;irows,i+) *(rowSize+i) = 0;Sparse Matrix2022/7/1874 for(k=0;ka.te

50、rms;k+) rowSizea.elemk.col +; rowStart0 = 0; for(i=1;irows;i+) rowStarti = rowStarti-1 + rowSizei-1; for(k=1;kelemp.row = a.elemk.col; b-elemp.col = a.elemk.row; b-elemp.value = a.elemk.value; rowStartp+; free(rowSize);free(rowStart);return *b;Sparse Matrix2022/7/1875 Strings are a special case of l

51、istsThey are treated separately because the basic operations on strings are different from those of listsAlthough we usually think of strings of characters we could deal with strings of arbitrary elements but, in computing, the major application of strings is in strings of charactersString as ADT202

52、2/7/1876 The characters of a string can be identified by their positionSo, a string S consists of the characters: S0, S1, , Sn-1A contiguous subset of the characters of S is called a substring of SI.e., if 0 i j =0 Relationship：R1| ai-1,ai D,i=2,.,n basic operations： StrAssign（T，chars) condition：cha

53、rs is constant string result：construct a string T equal to chars StrCopy(T，S) condition：String S is existent result：copy the value of string S to String T String as ADT: basic operations2022/7/1879StrEmpty(S) condition：String S is existent result：if S is empty string，return TRUE，else return FALSEStr

54、Compare ( S,T) condition：string S and String T are both existent result：string Sstring T,return value 0,if S=T return 0，else ST, return value 0 StrLength(S) condition： String S is existent result：return the number of chars in string SString as ADT: basic operations2022/7/1880ClearString(S) condition

55、： String S is existent result：clear String S t empty stringConcat（T，S1，S2） condition：string S and String T are both existent result： joins two strings S1 and S2 together to String TSubString（Sub，S，pos,len） condition：String S is existent, 0 pos StrLength(S) and 0 len StrLength(S)-pos+1 result： return

56、s part of a string S from pos to pos_len-1 with string SubString as ADT: basic operations2022/7/1881Index( S,T,pos) condition：String S and T are both existent,and the position is 1 pos StrLength(S) result： returns the position at which string T occurs within String S after position pos, or whether i

57、t exists 0Replace (&S,T,V) condition： String S and T are both existent,and String T is not empty string result：replace the occurrence of string T with string V in string S String as ADT: basic operations2022/7/1882Growing a string: three approachesCreate a string buffer in memory and use just part o

58、f the string initially, using more of the buffer later onE.g. Null character indicates end of used part of the bufferCreate a new third string which is the aggregate size of the other two strings and copy the characters acrossExpensive for large stringsCreate a linked list of chunks of string, rathe

59、r than an arrayTruly unbounded, but overhead involved with maintaining list2022/7/1883Growing a string: three approachesRepresentation 1#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1 ;Programming In C :char str250= “I am a string , My length is longer than 20.”;char str120;printf(“%sn

60、%sn”,str1,str2);strcpy(str1,str2);printf(“%sn%sn”,str1,str2); What will happen?2022/7/1884int Index(char *s,char*t) /return the position at which string t occurs within string s int k; for(k=0 ; sk !=0 ; k+) if(!strncmp(s+k ,t,strlen(t) break; /if they are equal if (sk != 0 ) return k+1; else return