数据结构 第5章 数组与广义表.

Presentation on theme: "数据结构 第5章 数组与广义表."— Presentation transcript:

1 数据结构 第5章 数组与广义表

2 第5章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义
5.5 广义表的存储结构 5.6 m元多项式的表示 5.7 广义表的递归算法

3 5.1 数组的定义 ADT Array { 　数据对象： D＝{aj1,j2,...,ji ,...jn |ji =0,...,bi-1, i=1,2,..,n,　　　　　　　　 称 n(>0) 为数组的维数， bi为数组第 i 维的长度，ji为数组元素的第i维下标，aj1,...,jn ∈ElemSet } 　数据关系： R＝{R1, R2, ..., Rn}, Ri＝{<aj1 ,...ji ,...jN , aj1 ,...,ji+1,...,jN > | 0≤jk≤bk-1, 1≤k≤n 且k <> i, 0≤ji≤bi-2, aj1 ,...,ji ,...,jn , aj1 ,...ji+1,...,jn ∈D, i=2,...,n }

4 5.1 数组的定义 基本操作： InitArray(&A, n, bound1, ..., boundn)
　　操作结果：若维数 n 和各维长度合法，则构造相应的数组 A。 　DestroyArray(&A) 　　初始条件：数组 A 已经存在。 　　操作结果：销毁数组 A。 　Value(A, &e, index1, ..., indexn) 　　初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 　　操作结果：若各下标不超界,则e赋值为所指定的A的元素值,并返回OK。 　Assign(&A, e, index1, ..., indexn) 　　操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。 } ADT Array

5 5.2 数组的顺序表示和实现 由于数组类型不作插入和删除的操作，因此只需要通过"顺序映象"得到它的存储结构，即借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 通常有两种映象方法：即“以行(序)为主(序)“row-major的映象方法和”以列(序)为主(序)“ column-major 的映象方法。 将多维数组映射到一维数组的方法 representations of a multidimensional array

6 5.2 数组的顺序表示和实现 以二维数组 a[ m, n]为例，其在内存中的映像
既可以如下排列（行优先）： a00, a01, …, a0,n-1,a10,a11,…,a1,n-1,…am-1,0,…am-1,n-1 也可以如下排列（列优先）： a00, a10, …, am-1,0,a01,a11,…,am-1,1,…a0,n-1,…am-1,n-1 11 12 13 14 15 16 21 22 23 24 25 26 31 32 33 34 35 36 41 42 43 44 45 46 11 12 13 14 15 16 21 22 23 24 25 26 31 32 33 34 35 36 41 42 43 44 45 46 11 21 31 41 12 22 32 42 13 23 33 43 14 24 34 44 15 25 35 45 16 26 36 46

7 5.2 数组的顺序表示和实现 假设二维数组 R[m][n] 中每个数据元素占L个存储地址，并以 LOC(i,j) 表示下标为 (i,j) 的数据元素的存储地址，则该数组中任何一对下标 (i,j) 对应的数据元素在"以行为主"的顺序映象中的存储地址为： 　　　LOC(i,j) = LOC(0,0) + (i*n+j)*L 　　在"以列为主"的顺序映象中的存储地址为： 　　　LOC(i,j) = LOC(0,0) + (j*m+i)*L 　　其中 LOC(0,0) 是二维数组中第一个数据元素（下标为(0,0)）的存储地址，称为数组的 "基地址" 或"基址"。

8 5.2 数组的顺序表示和实现 类似地，假设三维数组 R[p][m][n] 中每个数据元素占 L 个存储地址，并以 LOC(i,j,k) 表示下标为(i,j,k) 的数据元素的存储地址，则该数组中任何一对下标(i,j,k) 对应的数据元素在"以行为主"的顺序映象中的存储地址为： 　　　LOC(i,j,k) = LOC(0,0,0) + (i×m×n + j×n+k)×L

9 5.2 数组的顺序表示和实现 template<class T> class Array1D {
Sahni array1d..h template<class T> class Array1D { friend ostream& operator<< (ostream&, const Array1D<T>&); public: Array1D(int size = 0); Array1D(const Array1D<T>& v); // copy constructor ~Array1D() {delete [] element;} T& operator[](int i) const; int Size() {return size;} Array1D<T>& operator=(const Array1D<T>& v); Array1D<T> operator+() const; // unary + Array1D<T> operator+(const Array1D<T>& v) const; Array1D<T> operator-() const; // unary minus Array1D<T> operator-(const Array1D<T>& v) const; Array1D<T> operator*(const Array1D<T>& v) const; Array1D<T>& operator+=(const T& x); Array1D<T>& ReSize(int sz); private: int size; T *element; // 1D array }; Code from the book: Sartaj Sahni, Data Structures, Algorithms, and Applications in C++ 后面有 大字版本

10 5.2 数组的顺序表示和实现 template<class T> class Array1D {
Sahni array1d..h template<class T> class Array1D { friend ostream& operator<< (ostream&, const Array1D<T>&); public: Array1D(int size = 0); Array1D(const Array1D<T>& v); // copy constructor ~Array1D() {delete [] element;} T& operator[](int i) const; int Size() {return size;} ……………………………………… };

11 5.2 数组的顺序表示和实现 template<class T> class Array1D { ……………………..
Sahni array1d..h template<class T> class Array1D { …………………….. Array1D<T>& operator=(const Array1D<T>& v); Array1D<T> operator+() const; // unary + Array1D<T> operator+(const Array1D<T>& v) const; Array1D<T> operator-() const; // unary minus Array1D<T> operator-(const Array1D<T>& v) const; Array1D<T> operator*(const Array1D<T>& v) const; Array1D<T>& operator+=(const T& x); Array1D<T>& ReSize(int sz); private: int size; T *element; // 1D array };

12 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T>::Array1D(int sz){ // Constructor for one-dimensional arrays. if (sz < 0) throw BadInitializers(); size = sz; element = new T[sz]; } 构造函数

13 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T>::Array1D(const Array1D<T>& v) {// Copy constructor for one-dimensional arrays. size = v.size; element = new T[size]; // get space for (int i = 0; i < size; i++) // copy elements element[i] = v.element[i]; } 构造函数

14 5.2 数组的顺序表示和实现 重载 [ ] template<class T>
Sahni array1d..h 重载 [ ] template<class T> T& Array1D<T>::operator[](int i) const {// Return reference to element i. if (i < 0 || i >= size) throw OutOfBounds(); return element[i]; }

15 5.2 数组的顺序表示和实现 if (this != &v) {// not self-assignment size = v.size;
Sahni array1d..h 重载 赋值运算 template<class T> Array1D<T>& Array1D<T>::operator=(const Array1D<T>& v) { // Overload assignment operator. if (this != &v) {// not self-assignment size = v.size; delete [] element; // free old space element = new T[size]; // get right amount for (int i = 0; i < size; i++) // copy elements element[i] = v.element[i]; } // if return *this; }

16 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T> Array1D<T>:: operator+(const Array1D<T>& v) const {// Return w = (*this) + v. if (size != v.size) throw SizeMismatch(); // create result array w Array1D<T> w(size); for (int i = 0; i < size; i++) w.element[i] = element[i] + v.element[i]; return w; }

17 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T> Array1D<T>:: operator-(const Array1D<T>& v) const {// Return w = (*this) - v. if (size != v.size) throw SizeMismatch(); // create result array w Array1D<T> w(size); for (int i = 0; i < size; i++) w.element[i] = element[i] - v.element[i]; return w; }

18 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T> Array1D<T>::operator-() const {// Return w = -(*this). // create result array w Array1D<T> w(size); for (int i = 0; i < size; i++) w.element[i] = -element[i]; return w; }

19 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T> Array1D<T>::operator*(const Array1D<T>& v) const {// Return w = (*this) * v. Pairwise multiply. if (size != v.size) throw SizeMismatch(); // create result array w Array1D<T> w(size); for (int i = 0; i < size; i++) w.element[i] = element[i] * v.element[i]; return w; }

20 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T>& Array1D<T>::operator+=(const T& x){ // Add x to each element of (*this). for (int i = 0; i < size; i++) element[i] += x; return *this; }

21 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> ostream& operator<<(ostream& out, const Array1D<T>& x) {// Put the elements of x into the stream out. for (int i = 0; i < x.size; i++) out << x.element[i] << " "; return out; }

22 5.2 数组的顺序表示和实现 template<class T>
Sahni array1d..h template<class T> Array1D<T>& Array1D<T>::ReSize(int sz) {// Change the size to sz. // Do not copy array elements to new space. if (sz < 0) throw BadInitializers(); delete [] element; size = sz; element = new T [size]; return *this; }

23 5.2 数组的顺序表示和实现 #include <iostream.h> #include "array1d.h"
Sahni array1d..cpp #include <iostream.h> #include "array1d.h" void main(void){ try { Array1D<int> X(10), Y, Z; for (int i=0; i < 10; i++) X[i] = i; cout << "X[3] = " << X[3] << endl; cout << "X is " << X << endl; Y = X; cout << "Y is " << Y << endl; X += 2; cout << "X incremented by 2 is " << X << endl; Z = (Y + X) * Y; cout << "(Y + X) * Y is " << Z << endl; cout << "-(Y + X) * Y is " << -Z << endl; } catch (...) { cerr << "An exception has occurred" << endl;}

24 5.2 数组的顺序表示和实现 Sahni书一维数组实现的代码： code
复杂性： 构造和析构 (1)，如果T是C++内部数据类型 (size)，如果T是用户定义的类 下标 [ ]， (1) 其它，O( size)

25 5.2 数组的顺序表示和实现 Sahni 类似地，可以定义二维数组。

26 5.2 数组的顺序表示和实现 教材上有任意维数组实现的例子 数组：A 维数：dim 各维长度（界）：bounds[] 则
A[i0,i1,…,idim-1]的地址为： A首地址 + idim-1+idim-2*bounds[dim-1] +…+i1*bounds[dim-1]*…*bounds[2] +i0*bounds[dim-1]*…*bounds[2]*bounds[1]

27 5.2 数组的顺序表示和实现 一般性的问题： 二维数组A，每个元素占字节数b，元素A[i1][j1] 地址为a1， A[i2][j2]地址为a2，则A[i3][j3]的地址是？ 行优先/列优先？

28 5.2 数组的顺序表示和实现 用vector表示矩阵 vector< vector<T> > matrix;
template <typename T> class matrix{ public: matrix(int numRows = 1, int numCols = 1, const T& initVal = T()); vector<T>& operator[] (int i); const vector<T>& operator[](int i) const; int rows() const; int cols() const; void resize(int numRows, int numCols); private: int nRows, nCols; vector<vector<T> > mat; };

29 5.2 数组的顺序表示和实现 template <typename T>
matrix<T>::matrix(int numRows, int numCols, const T& initVal): nRows(numRows), nCols(numCols), mat(numRows, vector<T>(numCols,initVal)) {}

30 5.2 数组的顺序表示和实现 template <typename T>
vector<T>& matrix<T>::operator[] (int i){ if (i < 0 || i >= nRows) throw indexRangeError( "matrix: invalid row index", i, nRows); return mat[i]; } const vector<T>& matrix<T>::operator[] (int i) const{ throw indexRangeError("matrix: invalid row index", i, nRows);

31 5.2 数组的顺序表示和实现 template <typename T>
int matrix<T>::rows() const { return nRows; } int matrix<T>::cols() const return nCols;

32 5.2 数组的顺序表示和实现 template <typename T>
void matrix<T>::resize(int numRows, int numCols){ int i; // handle case of no size change with a return if (numRows == nRows && numCols == nCols) return; // assign the new matrix size nRows = numRows; nCols = numCols; // resize to nRows rows mat.resize(nRows); // resize each row to have nCols columns for (i=0; i < nRows; i++) mat[i].resize(nCols); }

33 5.3 矩阵的压缩存储 5.3.1 特殊矩阵的压缩存储方法 5.3.2 稀疏矩阵的压缩存储方法

34 5.3.1 特殊矩阵的压缩存储方法 1. 对称矩阵 a[i,j] = a[j,i] 1<=i,j<=n
用以维数组sa存储矩阵，则元素之间的对应关系(sa[k]与a[i,j]） i>=j k =i(i-1)/2+j-1 i<j k = j(j-1)/2+i-1

35 5.3.1 特殊矩阵的压缩存储方法 2. 三角矩阵 上三角矩阵中aij和sa[k]之间的对应关系 K = ?

36 5.3.1 特殊矩阵的压缩存储方法 3. 对角矩阵:若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵。 K = f(i,j), f=?

37 5.3.1 特殊矩阵的压缩存储方法 由于特殊矩阵中的非零值元素在矩阵中的分布有着一定的规律，则可将这些非零值元连续存储在一个一维数组中。即矩阵中的任何一个元和它们在一维数组中的位置之间存在着某种"转换关系"，并且这种转换关系可以用数学公式表示之。

38 5.3.2 稀疏矩阵的压缩存储方法 如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵(Sparse matrix)。至于矩阵中究竟含多少个零值元才被称为是稀疏矩阵，一般没有一个确切的定义。 假设在 m*n 的矩阵中有 t 个非零值元，称δ=t/(m*n)为矩阵的稀疏因子，通常认定δ≤0.05的矩阵为稀疏矩阵。

39 5.3.2 稀疏矩阵的压缩存储方法 一、三元组顺序表 const MAXTERMS=12500; // 假设非零元个数的最大值为12500
typedef struct { 　　　int i, j; 　　　　　　　// 该非零元的行号和列号 　　　ElemType e; 　　　　// 该非零元的值 } Triple; 　　　　　　　　　// 三元组 　Triple data[MAXTERMS + 1]; // 非零元三元组表，data[0] 未用 int rows, cols, terms;　// 矩阵的行数、列数和非零元的个数 } TSMatrix;　　　　　　　　　// 三元组顺序表 在data域中表示非零元的三元组是以行序为主序顺序排列的，这将有利于进行某些矩阵运算。

40 5.3.2 稀疏矩阵的压缩存储方法 三元组顺序表示例：转置运算 a.data i j e 1 2 12 1 3 9 3 1 -3
1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 b.data i j e 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 ？？？

41 5.3.2 稀疏矩阵的压缩存储方法 Status TransposeSMatrix( const TSMatrix &M, TSMatrix &T){ // 采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 < T.terms){ q = 1; for( col = 1; col <= M.cols; col++) for( p=1; p<=M.terms; p++) if(M.data[p].j == col){ T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; q++; } return OK; }// TransposeSMtrix 后面有 大字版本

42 5.3.2 稀疏矩阵的压缩存储方法 Status TransposeSMatrix( TSMatrix M, TSMatrix &T){
T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 < T.terms){ q = 1; for( col = 1; col <= M.cols; col++) // ………code in next page…………… } return OK; }// TransposeSMtrix

43 5.3.2 稀疏矩阵的压缩存储方法 Status TransposeSMatrix( TSMatrix M, TSMatrix &T){
…… for( col = 1; col <= M.cols; col++) for( p=1; p<=M.terms; p++) if(M.data[p].j == col){ T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; q++; } }// TransposeSMtrix 其时间复杂度为 O(cols * terms) 当稀疏因子接近1时，为 O( rows * cols^2) 教材P100，算法5.2 如何修改使其时间复杂度为O( rows * cols)

44 5.3.2 稀疏矩阵的压缩存储方法 快速转置 Status FastTransposeSMatrix(const TSMatrix &M, TSMatrix &T){ T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 < T.terms){ for(col=1;col<=M.cols;col++) num[col]=0; for(t=1;t<=M.terms;t++) num[M.data[t].j]++; cpot[1]=1; for(col=2;col<=Mu.col;col++) cpot[col]=cpot[col-1]+num[col-1]; // q = 1; // for( col = 1; col <= M.cols; col++) for( p=1; p<=M.terms; p++){ col = M.data[p].j; q=cpot[col]; T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; cpot[col]++; } // for } // if return OK; }// TransposeSMtrix 后面有 大字版本

45 5.3.2 稀疏矩阵的压缩存储方法 快速转置 Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T){ T.rows = M.cols; T.cols = M.rows; T.terms = M.terms; if( 0 < T.terms){ for(col=1;col<=M.cols;col++) num[col]=0; for(t=1;t<=M.terms;t++) num[M.data[t].j]++; cpot[1]=1; for(col=2;col<=Mu.col;col++) cpot[col]=cpot[col-1]+num[col-1]; // … ………….. See next page } return OK; }// TransposeSMtrix

46 5.3.2 稀疏矩阵的压缩存储方法 快速转置 Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T){ …………………………. // q = 1; // for( col = 1; col <= M.cols; col++) for( p=1; p<=M.terms; p++) col = M.data[p].j; q=cpot[col]; T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; cpot[col]++; } …………………………… }// TransposeSMtrix 空间换时间

47 二、行逻辑链接的顺序表 行逻辑链接的三元组顺序表的结构定义 为了便于随机存取任意一行的非零元
const MAXMN = 500; 　　　　 // 矩阵行数和列数的最大值 const MAXTERMS=12500; // 假设非零元个数的最大值为12500 typedef struct { 　Triple data[MAXSIZE + 1]; 　 // 非零元三元组表，data[0] 未用 　int rpos[MAXMN + 2];　// 指示各行第一个非零元在data中的位置 　int rows, cols, terms;　　// 矩阵的行数、列数和非零元的个数 } RLSMatrix; 　　　　　　　　// 行逻辑链接顺序表

48 三、十字链表 稀疏矩阵的十字链表存储表示 非零元和位置在操作过程中变化较大时
typedef struct OLNode { 　// 结点结构定义 　　int i, j; // 该非零元的行和列下标 　　ElemType e; 　　struct OLNode *right, *down; // 非零元所在行表和列表的后继链域 } *OLink; typedef struct {// 链表结构定义 　　　OLink *rhead, *chead; // 行和列链表头指针向量基址由 // CreateSMatrix分配 　　　int mu, nu, tu;　　　 // 稀疏矩阵的行数、列数和非零元个数 } CrossList;

49 三、十字链表 稀疏矩阵的十字链表存储表示 typedef struct OLNode { // 结点结构定义
非零元和位置在操作过程中变化较大时 typedef struct OLNode { 　　 // 结点结构定义 　　　int i, j; // 该非零元的行和列下标 　　　ElemType e; 　　　struct OLNode *right, *down; // 该非零元所在行表和列表的后继链域 } *OLink; typedef struct {// 链表结构定义 　　　OLink *rhead, *chead; // 行和列链表头指针向量基址由 // CreateSMatrix分配 　　　int mu, nu, tu;　　　 // 稀疏矩阵的行数、列数和非零元个数 } CrossList;

50 三、十字链表 稀疏矩阵的创建 Status CreateSMatrix_OL( CrossList &M){
if( M) free( M); scanf( &m, &n, &t); M.mu:=m; M.nu:=n; M.tu:=t; if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink)))) exit(OVERFLOW); if(!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink)))) exit(OVERFLOW); M.rhead[]=M.chead[]=NULL; …

51 三、十字链表 … for(scanf(&i,&j,&e); i!=0; scanf(&i,&j,&e)){
if(!(p=(OLNode*)malloc(sizeof(OLNode)))) exit(OVERFLOW); p->i=i; p->j=j; p->e=e; if(M.rhead[i]==NULL||M.rhead[i]->j>j){ p->right=M.rhead[i];M.rhead[i]=p; }else{ for(q=M.rhead[i]; (q->right)&&q->right->j<j;q=q->right); p->right=q->right;q->right=p; }

52 三、十字链表 … if(M.chead[j]==NULL||M.chead[j]->i>i){
p->down=M.chead[j];M.chead[j]=p; }else{ for(q=M.chead[j]; (q->down)&&q->down->i<i;q=q->down); p->down=q->down;q->down=p; } return OK;

53 三、十字链表 稀疏矩阵的和 A=A+B 初始，令pa和pb分别指向A和B的第一行的第一个非零元素的节点。 每一行，依次处理B在本行中所有节点
pa==NULL || pa->j>pb->j pa!=NULL && pa->j<pb->j pa!=NULL && pa->j==pb->j 列链表的修改 若非最后一行，令pa、pb指向下一行的第一个非零元节点，继续（2），否则结束。

54 5.4 广义表的定义 GList： {ei| ei is atom or ei is GList} 广义表：线性表的推广 一些例子：
B = (e) C = (a, (b, c, d)) D = (A, B, C) E = (a, E)

55 5.4 广义表的定义 Ls=( a1，a2，…，ai，…，an) Ls是广义表的名字，n为它的长度。
若ai是广义表，则称它为Ls的子表。 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a2，…，an)称为Ls的表尾。 广义表是递归定义的

56 5.4 广义表的定义 广义表常用表示 ① E=() ② L=(a，b) ③ A=(x，L)=(x，(a，b))
　④ B=(A，y)=((x，(a，b))，y) 　 B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。 　⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y)) 　C的长度为2，两个元素都是子表。 　⑥ D=(a，D)=(a，(a，(a，(…)))) 　D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。

57 5.4 广义表的定义 ADT GList{ 数据对象： 数据关系： 基本操作： } ADT GList
InitGlist(&L); 操作结果:创建空的广义表L CreateGList(&L,S); 初始条件:S是广义表的书写形式串 操作结果:由S创建广义表L DestroyGlist(&L); 初始条件:广义表L存在 操作结果:销毁广义表L CopyGlist(&T,L); 初始条件:广义表L存在 操作结果:由广义表L复制得到广义表T GListLength(L); 初始条件:广义表L存在 操作结果:求广义表L的长度,即元素个数 GListDepth(L); 初始条件:广义表L存在 操作结果:求广义表L的深度 GlistEmpty(L); 初始条件:广义表L存在 操作结果:判断广义表L是否为空 GetHead(L); 初始条件:广义表L存在 操作结果:取广义表L的头 GetTail(L); 初始条件:广义表L存在 操作结果:取广义表L的尾 D = { ei | i=1,2,…,n; n>=0; ei IN AtomSet 或 ei IN GList, AtomSet 为某个数据对象 } InsertFirst_GL(&L,e); 初始条件:广义表L存在 操作结果:插入元素e作为广义表L的第一元素 DeleteFirst_GL(&L,&e); 初始条件:广义表L存在 操作结果:删除广义表L的第一元素,并用e返回其值 Traverse_GL(L,Visit()); 初始条件:广义表L存在 操作结果:遍历广义表L,用函数Visit处理每个元素 R = { <ei-1,ei> | ei-1,ei IN D, 2<=i<=n }

58 5.5 广义表的存储结构 由于广义表的元素类型不一定相同，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。 采用链式存储结构,每个数据元素可用一个结点表示: (1)表结点，用以表示子表 (2)原子结点，用以表示原子

59 5.5 广义表的存储结构 广义表的头尾链表存储表示 typedef enum{ ATOM,LIST} elemtag;
表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域； 而原子域只需两个域：标志域和值域。 typedef enum{ ATOM,LIST} elemtag; typedef struct glnode{ elemtag tag; union{ atomtype atom; struct { struct glnode *hp,*tp; }ptr; }; } *glist;

60 5.5 广义表的存储结构 广义表的扩展线性链表存储表示 typedef enum{ ATOM,LIST} elemtag;
表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域； 而原子节点的表尾域不用。 typedef enum{ ATOM,LIST} elemtag; typedef struct glnode{ elemtag tag; union{ atomtype atom; struct glnode *hp; }; struct glnode *tp; } *glist;

61 5.6 m元多项式的表示 多项式：P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 可以写成如下形式： P(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15 任何m元多项式都可以先分解出一个主变元，然后再分解出第二个变元，…，由此，一个m元多项式首先是其主变元的多项式，而其系数又是第二个变元的多项式，…，由此可以用广义表来表示m元多项式。 P=z((A,2),(B,1),(15,0)) 其中： A = y((C,3),(D,2)) C = x((1,10),(2,6)) D = x((3,5)) B = y((E,4),(F,1)) E = x((1,4),(6,3)) F = x((2,0))

62 5.6 m元多项式的表示 可类似于广义表的第二种存储结构来定义表示m元多项式的广义表的存储结构。
typedef struct MPNode{ ElemTag tag; int exp; union{ float coef; struct MPNode *hp; }; struct MPNode *tp; } *MPList;

63 5.6 m元多项式的表示 P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 P=z((A,2),(B,1),(15,0)) A = y((C,3),(D,2)) C = x((1,10),(2,6)) D = x((3,5)) B = y((E,4),(F,1)) E = x((1,4),(6,3)) F = x((2,0)) 在每一层上增设一个表头节点并利用exp指示该层的变元（可用一维数组存储多项式中的所有变元，exp域存储的事该变元在一维数组中的下标）。头指针所指节点中的exp表示多项式中变元的个数。

64 5.6 m元多项式的表示 P 1 ３ ^ 1 1 2 1 15 ^ 1 1 3 1 2 ^ 1 1 4 1 ^ 1 5 3 ^ 1 2 ^ 1 10 1 6 2 ^ 1 4 1 3 6 ^ z y x

65 5.7 广义表的递归算法 广义表的深度、复制等运算 由于广义表本身的特性，有关的操作用递归的实现显得自然和简洁。

66 5.7 广义表的递归算法 求广义表的深度 广义表的深度定义为广义表中括弧的重数，是广义表的一种度量。例如，多元多项式广义表的深度为多项式中变元的个数。 深度公式: （1）maxdh(p)=0 当原子p->tag=0 （2）maxdh(p)=1 当空表(p->tag=1&&p->hp=NULL) （3）maxdh(p)=max(maxdh(p1),...,maxdh(pn))+1 其余情况 其中p=(p1,p2,...,pn)

67 5.7 广义表的递归算法 复制广义表 任何一个非空广义表均可分解成表头和表尾。 复制的递归实现只需分别复制表头和表尾即可。