数据结构课件_02LinearList.pdf
Data Structures Linear Structure Teacher : Wang Wei 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 Linear List Definition ( a0, a1, …, an-1)，n≥1 // ai : element , a finite set ( )， // empty L= 0 ≤ i – correspondence or mapping • Two operations: – Retrieve – Store • Array can be used to implement other abstract data types • The simplest one might be: Ordered or linear list • Now we will use the C++ class to define an ADT 王伟, 计算机工程系, 东南大学 1 Operations (操作) on linear list, including： （1）Find the length n of the list （2）Read the list from left to right ( or right to left) （3）Retrieve the ith element, 0≤ i < n （4）Store a new value into the ith position, 0≤ i < n （5）Insert a new element at the position i, 0 ≤ i < n • i,i+1,…,n–1 to i+1,i+2,…,n （6）Delete the element at position i, 0 ≤ i < n • i+1,i+2,…,n–1 to I,i+1,…,n–2 王伟, 计算机工程系, 东南大学 Linear List ADT or GeneralArray class LinearList { // 对象: L = ( a0, a1, …, an-1) 或 ( ), aiT/type, 0 ≤ i < 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个元素并返回其值 }; Generally specified as a C++ (template) class 王伟, 计算机工程系, 东南大学 How to represent ordered list efficiently? Sequential mapping Use array : ai index i Complexity Random access any element, T(n) = O(1) float Retrieve(int i); // if (iIndexSet) return the float associated with i in the // array;else throw an exception. void Store(int i, float x); // if (iIndexSet) replace the old value associated with i // by x; else throw an exception. 王伟, 计算机工程系, 东南大学 2 Operations Insert and Delete void Insert(int i, float x); // insert x as the indexth element, elements // with theIndex >= index have their index increased by 1 void Delete(int i); // remove and return the indexth element, // elements with higher index have their index reduced by 1 王伟, 计算机工程系, 东南大学 Insert template bool Insert (T data[], int i, T x) { //将新元素x插入到表中第i (1≤i≤n+1) 个表项位置 if (n == maxSize) return false; if (i < 1 || i > n+1) return false; for (int j = n; j >= i; j--) data[j] = data[j-1]; data[i-1] = x; n++; }; //表满 //参数i不合理 //定位,依次后移 //插入(第 i 表项在data[i-1]处) return true; //插入成功 王伟, 计算机工程系, 东南大学 Analysis • Insert into ith position, need move backward from data[i-1] to data [n-1] n-1-(i-1)+1 = n-i+1 • Average Moving Number – when pi =1/n, and for all position , 1≤i≤n+1 1 n 1 1 ( n i 1) n 1 ( n 1 0) n 1 i 1 1 n ( n 1) n ( n 1) 2 2 AMN = 王伟, 计算机工程系, 东南大学 3 Remove //通过引用型参数 x 返回被删元素 template bool Remove (T data[], int i, T & x) { //从表中删除第 i (1≤i≤n) 个表项 if (n == 0) return false; //表空 if (i < 1 || i > n) return false; //参数i不合理 x = data[i-1]; for (int j = i; j <= n-1; j++) //定位,依次前移,填补 data[j-1] = data[j]; n--; return true; }; 王伟, 计算机工程系, 东南大学 Analysis • If removed the ith term, need to move forward from i+1th to nth n-(i+1)+1 = n-i • AMN : AMN = n1 1 n 1 ( n 1) n (n i ) n i 1 n 2 2 when pi =1/n, and 1≤i≤n-1 – 王伟, 计算机工程系, 东南大学 Search typedef T; // templateint int search(T data[], int Size, T & x) { //在表中顺序搜索与给定值 x 匹配的表项 //找到则函数返回该表项是第几个元素， //顺序搜索 for (int i = 1; i <= Size; i++) if ( data[i-1] == x ) return i; //表项序号和表项位置差1 return 0; //搜索失败 }; 王伟, 计算机工程系, 东南大学 4 Analysis • Average Comparing Number Success: n ACN = pi ci i 1 when pi =1/n (等概率) 1 n 1 i n (1 2 n) n i 1 1 (1 n) n 1 n 2 2 n ACN = Unsuccess : ACN =王伟,n计算机工程系, 东南大学 Data Structures Polynomial Teacher : Wang Wei 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 Polynomial ADT class Polynomial { // p(x)=a0xe0+,…,+ anxen // a set of ordered pairs of // where ai is a nonzero float coefficient // and ei is a non-negative exponent public: Polynomial ( ); // Construct the polynomial p(x)=0 王伟, 计算机工程系, 东南大学 5 void AddTerm (Exponent e, Coefficient c); // add the term to *this, so that it can be initialized Polynomial Add (Polynomial poly); // return the sum of the polynomials *this and poly Polynomial Mult (Polynomial poly); // return the product of the polynomials *this and poly float Eval ( float f); // evaluate polynomial *this at f and return the result } 王伟, 计算机工程系, 东南大学 Polynomial Representation 1 private: int degree; // degree MaxDegree float coef[MaxDegree+1]; a.degree = ? // n a.coef[i] = ? // an-i , 0 i n // Simple algorithms for many operations When a.degree << MaxDegree, representation 1 is very poor in memory use. 王伟, 计算机工程系, 东南大学 Polynomial Representation 2 To improve, define variable sized data member as: private: int degree; float *coef; // Polynomial::Polynomial(int d) { int degree=d; coef= new float[degree+1]; // } 王伟, 计算机工程系, 东南大学 6 Polynomial Representation 3 class Polynomial; // forward declaration class Term { friend Polynomial; private: float coef; // coefficient int exp; // exponent }; class Polynomial { public: // …… private: Term *termArray; int capacity; // size of termArray int terms; // number of nonzero terms }; 王伟, 计算机工程系, 东南大学 Addition Use presentation 3 to obtain C = A +B A(x)=3x2+ 2x+4 B(x)=x4+ 10x3+ 3x2+1 Idea: Because the exponents are in descending order, can adds A(x) and B(x) term by term to C(x) The terms of C are entered into its termArray by calling function NewTerm If the space in termArray is not enough, its capacity is doubled 王伟, 计算机工程系, 东南大学 Polynomial Polynomial::Add (Polynomial b) { // return the sum of the polynomials *this and b Polynomial c; int aPos=0, bPos=0; while (( aPos < terms) && (b < b.terms)) if (termArray[aPos].exp==b.termArray[bPos].exp) { float t = termArray[aPos].coef + termArray[bPos].coef if ( t ) c.NewTerm (t, termArray[aPos].exp); aPos++; bPos++; } else if (termArray[aPos].exp < b.termArray[bPos].exp) { c.NewTerm (b.termArray[bPos].coef, b.termArray[bPos].exp); bPos++; } 王伟, 计算机工程系, 东南大学 7 else { c.NewTerm (termArray[aPos].coef, termArray[aPos].exp); aPos++; } } // end of while // add in the remaining terms of *this for ( ; aPos < terms; aPos++ ) c.NewTerm(termArray[aPos].coef, termArray[aPos].exp ); // add in the remaining terms of b for ( ; bPos < b.terms; bPos++ ) c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp); return c; } 王伟, 计算机工程系, 东南大学 void Polynomial::NewTerm(const float theCoeff, const int theExp) { // add a new term to the end of termArray if (terms == capacity) { // double capacity of termArray capacity *= 2; term *temp = new term[capacity]; // new array copy(termArray, termAarry + terms, temp); delete [ ] termArray; // deallocate old memory termArray = temp; } termArray[terms].coef = theCoeff; termArray[terms++].exp = theExp; } 王伟, 计算机工程系, 东南大学 Data Structures Matrix Teacher : Wang Wei 1. Ellis Horowitz,etc., Fundamentals of Data Structures in C++ 2. 金远平, 数据结构 3. http://inside.mines.edu/~dmehta/ 4. 殷人昆, 数据结构 王伟, 计算机工程系, 东南大学 8 Representation A natural way a[m][n] access element by a[i][j], easy operations But for sparse matrix, wasteful of both memory and time Alternative way store nonzero elements explicitly 0 as default 王伟, 计算机工程系, 东南大学 Sparse Matrix ADT class SparseMatrix { // a set of , where row, column are // non-negative integers and form a unique combination; // value is also an integer. public: SparseMatrix ( int r, int c, int t); // creates a rc SparseMatrix with a capacity of t nonzero // terms SparseMatrix Transpose ( ); // return the SparseMatrix obtained by transposing *this SparseMatrix Add ( SparseMatrix b); SparseMatrix Multiply ( SparseMatrix b); }; 王伟, 计算机工程系, 东南大学 Sparse Matrix Representation Triple Sorted in ascending order by class SparseMatrix; class MatrixTerm { friend class SparseMatrix; private: int row, col, value; }; 王伟, 计算机工程系, 东南大学 9 Need also the number of rows the number of columns the number of nonzero elements in class SparseMatrix private: int rows, cols, terms, capacity; MatrixTerm *smArray; 王伟, 计算机工程系, 东南大学 Triple representation 王伟, 计算机工程系, 东南大学 Transposing (转置) a Matrix 2-dimensional (二维) representation if an element is at position [ i ][ j ] in the original matrix then it is at position [ j ][ i ] in the transposed matrix for (int j=0; j < columns; j++) for (int i=0; i < rows; i++) B[j][i] = A[i][j]; T(n)=O(cols* rows) 王伟, 计算机工程系, 东南大学 10 First try the transpose : for (each row i) take element (i, j, value) store it in (j, i, value) 王伟, 计算机工程系, 东南大学 Improvement: for (all elements in col j) store (i, j, value) of the original matrix as (j, i, value) of the transpose Since the rows are in order Locate elements in the correct column order 王伟, 计算机工程系, 东南大学 Further improvement : If use some more space to store some knowledge about the matrix Can do much better : doing it in O(cols + terms) 王伟, 计算机工程系, 东南大学 11 FastTranspose Algorithm Step1: get Acol value Acol is the number of elements in each column of *this Step2: Brow = Acol Brow is the number of elements in each row of B Step3: obtain Bstart Bstart is the starting point in B of each of its rows Step4: move the elements of *this one by one into their right position in B 王伟, 计算机工程系, 东南大学 RowSize= RowStart= [0] [1] [2] [3] [4] [5] 2 1 2 2 0 1 2 3 5 7 7 0 + 王伟, 计算机工程系, 东南大学 SparseMatrix SparseMatrix::FastTranspos ( ) { // return the transpose of *this in O(terms+cols) time SparseMatrix b(cols, rows, terms); if (terms > 0) { // nonzero matrix int *rowSize = new int[cols]; int *rowStart = new int[cols]; // compute rowSize[i] = number of terms in row i of b fill(rowSize, rowSize + cols, 0); // initialze for (i=0; i=0)) i=f[i]; // try for m if ( str[j]==str[i+1]) f[j]=i+1; // fm(j-1)+1 else f[j]= -1; } } 王伟, 计算机工程系, 东南大学 17
数据结构课件_02LinearList.pdf
