Array & General List

Section 1 Array

数组的抽象数据类型定义 ADT Array { D={ aj1,j2, ...,,ji,jn|ji=0,...,bi-1, i=1,2,..,n } 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,i=2,...,n } } ADT Array 基本操作

二维数组的定义 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } COL = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1} ROW = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤ j≤b2-2}

基 本 操 作 InitArray(&A, n, bound1, ..., boundn) DestroyArray(&A) 基 本 操 作 InitArray(&A, n, bound1, ..., boundn) DestroyArray(&A) Value(A, &x, index1, ..., indexn) Assign(&A, x, index1, ..., indexn)

InitArray(&A, n, bound1, ..., boundn) 合法，则构造相应的 数组A，并返回OK。

DestroyArray(&A) 操作结果：销毁数组A。

Value(A, &x, index1, ..., indexn) 初始条件： A是n维数组，x为元素变 量，随后是n 个下标值。 操作结果：若各下标不超界，则x赋值 为所指定的A 的元素值，并 返回OK。

Assign(&A, x, index1, ..., indexn) 初始条件： A是n维数组，x为 元素变量，随后是n 个下标值。 操作结果：若下标不超界，则将 x的值赋给所指定的 A的元素，并返回 OK。

一维数组

与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素。 定义 相同类型的数据元素的集合。 一维数组的示例 与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素。 0 1 2 3 4 5 6 7 8 9 35 27 49 18 60 54 77 83 41 02

数组的定义和初始化 class szcl { int e; public: szcl ( ) { e = 0; } szcl ( int value ) { e = value; } int get_value ( ) { return e; } }

main ( ) { szcl a1[3] = { 3, 5, 7 }, *elem; for ( int i = 0; i < 3; i++ ) cout << a1[i].get_value ( ) << “\n”; //静态 elem = a1; for ( int i = 0; i < 3; i++ ) { cout << elem->get_value( ) << “\n”; //动态 elem++; } return 0; }

一维数组(Array) 类的定义

template <class Type> class Array { Type *elements; //数组存放空间 int ArraySize; //当前长度 void getArray ( ); //建立数组空间 public: Array( int Size=DefaultSize ); Array( const Array<Type>& x );

Array<Type> &operator= //数组复制 ( const Array<Type> & A ); ~Array( ) { delete [ ]elements;} Array<Type> &operator= //数组复制 ( const Array<Type> & A ); Type &operator[ ]( int i ); //取元素值 int Length()const{ return ArraySize; } //取数组长度 void ReSize ( int sz ); //扩充数组 }

一维数组 公共操作的实现

template <class Type> void Array<Type> :: getArray ( ) { //私有函数：创建数组存储空间 elements = new Type[ArraySize]; }

template <class Type> Array<Type> :: Array ( int sz ) { ArraySize = sz; getArray ( ); }

template <class Type> Array<Type>::Array(Array<Type> &x){ int n = ArraySize = x.ArraySize; elements = new Type[n]; Type *srcptr = x.elements; Type *destptr = elements; while ( n-- ) * destptr++ = * srcptr++; }

template <class Type> Type& Array<Type>::operator[ ](int i){ if ( i < 0 || i > ArraySize-1 ) { cerr << “数组下标超界” << endl; return NULL; } return elements[i]; } 使用该函数于赋值语句 Pos = Position[i -1] + Number[i -1]

template <class Type> void Array<Type> :: Resize ( int sz ) { if ( sz >= 0 && sz != ArraySize ) { Type * newarray = new Type[sz]; int n = ( sz < ArraySize ) ? sz : ArraySize; //按新的大小确定传送元素个数

Type *destptr=newarray; while (n--)*destptr++=*srcptr++; Type *srcptr=elements; Type *destptr=newarray; while (n--)*destptr++=*srcptr++; delete [ ] elements; elements = newarray; ArraySize = sz; }

多维数组

多维数组是一维数组的推广 多维数组是一种非线性结构。其特点是每一个数据元素可以有多个直接前驱和多个直接后继。 数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。

行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k 二维数组 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k

数组的顺序存储特点 1) 只有引用型操作，没有加工型操作。 2) 数组是多维的结构，而存储空间是 一个一维的结构。

数组元素的遍历 1)以行序为主序(按行排列): 先排最右的下标,依次向左,最后 排最左的下标 2)以列序为主序(按列排列): 先排最左的下标,依次向右,最后 排最右的下标

一维数组 a, i = 0 LOC(i) = LOC(i-1)+d = a+i*d, i > 0 0 1 2 3 4 5 6 7 8 9 a 35 27 49 18 60 54 77 83 41 02 d d d d d d d d d d a+i*l LOC(i) = LOC(i-1)+d = a+i*d

二维数组 行优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 d 个存储单元 LOC ( j, k ) = a + ( j * m + k ) * d

二维数组 列优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 d 个存储单元 LOC ( j, k ) = a + ( k * n + j ) * d

三维数组 各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地 址:(按(页/行/列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * d 前i1页总 元素个数 第i1页的 前i2行总元素个数 第 i2 行前 i3 列元素个数

n 维数组 下标为 i1, i2, i3, …, in 的数组元素的 存储地址： LOC ( i1, i2, …, in ) = a + 各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的 存储地址： LOC ( i1, i2, …, in ) = a + ( i1*m2*m3*…*mn + i2*m3*m4*…*mn+ + ……+ in-1*mn + in ) * d

稀疏矩阵 (Sparse Matrix)

非零元素个数远远少于矩阵元素个数

假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为   0.05 的矩阵为稀疏矩阵。

高阶的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零。 以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零。

解决问题的原则 1) 尽可能少存或不存零值元素； 2) 尽可能减少没有实际意义的运算； 3) 操作方便。 即： 1. 能尽可能快地找到与下标值 (i，j)对应的元素， 2. 能尽可能快地找到同一行或 同一列的非零值元。

1) 特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 对称矩阵 三角矩阵 三对角矩阵 2) 随机稀疏矩阵 非零元在矩阵中随机出现

特殊矩阵及其压缩存储 特殊矩阵 1．对称矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 ≤i, j≤n-1 ， 则称A为对称矩阵。 例如，图5-1是一个3*3的对称矩阵。

2．三角矩阵 （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0，具体形式见图5-2(a)。 （2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0，具体形式见图5-2(b)。

3．对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。 例如，图5-3为77的三对角矩阵（即有三条对角线上元素非0）。

压缩存储 1．对称矩阵 若矩阵Ann是对称的，对称的两个元素可以共用一个存储单元，这样，原来n 阶方阵需 n2个存储单元，若采用压缩存储，仅需 n(n+1)/2个存贮单元，将近节约一半存贮单元，这就是实现压缩的好处。但是，将n阶对称方阵存放到一个向量空间s[0]到s[ -1] 中， 我们怎样找到s[k]与a[i][j]的一一对称应关系呢？使我们在s[k]中直接找到a[i][j]。 我们仅以行优先存放分两种方式讨论：

（1）只存放下三角部分 由于对称矩阵关于主对角线对称，故我们只需存放主对角线及主对角线以下的元素。这时， a[0][0]存入s[0]，a[1][0] 存入s[1]，a[1][1]存入 s[2]，…。这时s[k]与a[i][j]的对应关系为： i(i+1)/2+j 当 i≥j k= j(j+1)/2+i 当 i<j 上面的对应关系读者很容易推出：当i≥j 时，aij在下三角部分中，aij前面有i行，共有1+2+3+…+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+…­+i+j=i(i+1)/2+j；当i<j时，aij在上三角部分中，但与aji对称，故只需在下三角部分中找aij即可，故只需将i与j交换即可，即k=j(j+1)/2+i。

(2) 只存放上三角部分 对于对称阵，除了用下三角形式存放外，还可以用上三角形式存放，这时a[0][0]存入 s[0],a[0][1]存入s[1]，a[0][2]存入 s[2]，…，具体参见图5-5。这时s[k]与a[i][j]的对应关系可以按下面方法推出： 当i≤j时，aij在上三角部分中，前面共有i行，共有n+n-1+…+n-(i-1)=i*n- 个元素，而aij是本行第j-i个元素，故k=i*n- +j-i，当i>j时，交换i与j即可。故s[k]与a[i][j]的对应关系为： i*n- +j-i 当i≤j k= j*n- +i-j 当i>j

2．三角矩阵 （1）下三角矩阵 下三角矩阵的压缩存放与对称矩阵用下三角形式存放类似，但必须多一个存储单元存放上三角部分元素，使用的存储单元数目为n(n+1)/2+1。故可以将nn的下三角矩阵压缩存放到只有n(n+1)/2+1个存储单元的向量中，假设仍按行优先存放，这时s[k]与a[i][j]的对应关系为： i(i+1)/2+j i≥j k= n(n+1)/2 i<j

(2)上三角矩阵 和下三角矩阵的存储类似，共需 n(n+1)/2+1个存贮单元，假设仍按行优先顺序存放，这时s[k]与a[i][j]的对应关系为： i*n-i(i-1)/2 +j-i 当i≤j k= n(n+1)/2 i>j

3．对角矩阵 我们仅讨论三对角矩阵的压缩存贮，五对角矩阵，七对角矩阵等读者可以作类似分析。 在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。 故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，则： s[k]与a[i][j]的对应关系为： 3i-1 当 i=j+1 k= 3i 当i=j 3i+1 当i=j-1

随机稀疏矩阵的顺序压缩存储 一、三元组表示法 二、带辅助行向量的二元组表示法 三、伪地址表示法

稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 行列下标 非零元值 i j v 0 1 2 3 4 5 6 7 8 6 7 8 1 2 12 ma i j v 0 1 2 3 4 5 6 7 8 6 7 8 1 2 12 ma[0].i,ma[0].j,ma[0].v分别存放 矩阵行列维数和非零元个数 1 3 9 3 1 -3 3 6 14 4 3 24 三元组表所需存储单元个数为3(t+1) 其中t为非零元个数 5 2 18 6 1 15 6 4 -7

带辅助行向量的二元组表 增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有： NRA[i]=NRA[i-1]+第i-1行非零元个数(i2) 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 ma j v 0 1 2 3 4 5 6 7 8 矩阵列数和 非零元个数 列下标和 非零元值 0 1 2 3 4 5 6 NRA NRA[0]不用或 存矩阵行数 6 1 3 3 5 6 7 二元组表需存储单元个数为2(t+1)+m+1

伪地址表示法 伪地址：本元素在矩阵中（包括零元素再内） 按行优先顺序的相对位置 伪地址 非零元值 addr v 6 7 2 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 ma addr v 伪地址 非零元值 矩阵行列维数 0 1 2 3 4 5 6 7 8 伪地址表示法需存储单元个数 为2(t+1)

随机稀疏矩阵的链式压缩存储 一、带行指针向量的单链表示法 二、行—列表示法 三、十字链表

带行指针向量的单链表示法 每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义 ^ 1 3 5 7 3 -1 1 -1 2 -2 4 2 需存储单元个数为3t+m

稀疏矩阵的链接表示采用正交链表： 行链表与列链表十字交叉 行链表与列链表都是带表头结点的循环链表。 用表头结点表征是第几行，第几列

稀疏矩阵的结点 (a) 表头结点 (b) 非零元素结点 (c) 建立a[i][j]结点 True next False row col down right down value right (a) 表头结点 (b) 非零元素结点 False i j a[i][j] (c) 建立a[i][j]结点

稀疏矩阵的正交链表表示的示例

稀疏矩阵的抽象数据类型 template<class Type> class SparseMatrix; template<class Type> class Trituple { friend class SparseMatrix <Type> private: int row, col; //非零元素行号/列号 Type value; //非零元素的值 }

template<class Type>class SparseMatrix{ int Rows,Cols,Terms;//行/列/非零元素数 Trituple<Type> smArray[MaxTerms]; public: //三元组表 SparseMatrix (int MaxRow, int Maxcol); SparseMatrix<Type>& Transpose (SparseMatrix<Type>&); //转置

SparseMatrix<Type> &Add (SparseMatrix <Type>a,SparseMatrix<Type>b);//相加 SparseMatrix<Type> &Multiply(SparseMatrix <Type>a,SparseMatrix<Type>b);//相乘 }

稀疏矩阵的转置

一个 mn 的矩阵 A，它的转置矩阵 B 是一个 nm 的矩阵，且 A[i][j] = B[j][i]。即矩阵 A 的行成为矩阵 B 的列，矩阵 A 的列成为矩阵 B 的行。 在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。 稀疏矩阵的转置运算要转化为对应三元组表的转置。

稀疏矩阵

转置矩阵

用三元组表表示的稀疏矩阵及其转置

稀疏矩阵转置算法思想 设矩阵列数为 Cols，对矩阵三元组表扫描Cols 次。第 k 次检测列号为 k 的项。

template <class Type> SparseMatrix<Type>& SparseMatrix<Type> :: Transpose (SparseMatrix<Type>& a) { SparseMatrix<Type> b (a.Cols, a.Rows); b.Rows = a.Cols; b.Cols = a.Rows; b.Terms = a.Terms; if ( a.Terms > 0 ) { int CurrentB = 0;

for ( int k = 0; k < a.Cols; k++ ) for ( int i = 0; i < a.Terms; i++ ) if ( a.smArray[i].col == k ) { b.smArray[CurrentB].row = a.smArray[i].col; b.smArray[CurrentB].col = a.smArray[i].row; b.smArray[CurrentB].value= a.smArray[i].value;

CurrentB++; } return b; 设矩阵三元组表总共有 t 项，上述算法的时间代价为 O ( n* t ) 若矩阵有 200 行，200 列，10,000 个非零元素，总共有 2,000,000 次处理

快速转置算法 1.为加速转置速度，建立辅助数组 rowSize 和 rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。 2.扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 rowStart 表, 按查到的位置直接将该项存入转置三元组表中

for(int i=0;i<a.Cols;i++)rowSize[i]=0; for(i=0;i<a.Terms;i++) rowSize[a.smArray[i].col]++; rowStart[0]=0; for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];

template <class Type> SparseMatrix<Type>& SparseMatrix<Type> :: FastTranspos (SparseMatrix<Type>& a) { int *rowSize = new int[a.Cols]; int *rowStart = new int[a.Cols]; SparseMatrix<Type> b ( a.Cols, a.Rows ); b.Rows = a.Cols; b.Cols = a.Rows; b.Terms = a.Terms;

if ( a.Terms > 0 ) { for (int i=0; i<Cols; i++)rowSize[i]=0; for (i=0; i<Terms; i++) rowSize[smArray[i].col]++; rowStart[0]=0; for (i=1; i<a.Cols; i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];

for ( i = 0; i < a.Terms; i++ ) { int j=rowStart[a.smArray[i].col]; b.smArray[j].row=a.smArray[i].col; b.smArray[j].col=a.smArray[i].row; b.smArray[j].value=a.smArray[i].value; rowStart[a.smArray[i].col]++; } } delete [ ] rowSize; delete [ ] rowStart; return b;

Section 2 General List

1.广义表的概念 n(0)个表元素组成的 有限序列,记作 LS = (a0, a1, a2, …, an-1) LS是表名,ai是表元素,它可以是表(称为 子表),可以是数据元素(称为原子) 2.n为表的长度。n=0的广义表为空表 3.n>0时,表的第一个表元素称为广义表 的表头(head),除此之外,其它表元素组 成的表称为广义表的表尾(tail)

广义表的 抽象数据类型定义

ADT Glist { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系： LR＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n} } ADT Glist 基本操作:

广义表是递归定义的线性结构， LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a,  , ) ) )

广义表是一个多层次的线性结构 例如： D D=(E, F) E F 其中: E=(a, (b, c)) F=(d, (e)) a ( ) d ( ) e b c

广义表的基本操作 1） 创建广义表L； 2） 销毁广义表L； 3） 已有广义表L，由L复制得到广义表T； 4） 求广义表L的长度； 5） 求广义表L的深度； 6） 判广义表L是否为空； 7） 取广义表L的表头； 8） 取广义表L的表尾； 9） 在L中插入元素作为L的第i个元素； 10）删除广义表L的第i个元素； 11）遍历广义表L，用函数 traverse( )处理每个元素；

广义表的特性 有次序性 有深度 可递归 有长度 可共享 A = ( ) B = ( 6, 2 ) C = ( ‘a’, ( 5, 3, ‘x’ ) ) D = ( B, C, A ) E = ( B, D ) F = ( 4, F )

广义表的分类 （1）线性表：元素全部是原子的广义表。 （2）纯表：与树对应的广义表。 （3）再入表：与图对应的广义表(允许结点共享) 。 （4）递归表：允许有递归关系的广义表，例如E=(a,E)。 这四种表的关系满足： 递归表再入表 纯表  线性表

广义表的表示 表中套表情形下的广义表链表表示 只包括整数和字符型数据的广义表链表表示  5 12 ‘s’ 47 ‘a’  5 2 6 3 list1 5 12 ‘s’ 47 ‘a’ 只包括整数和字符型数据的广义表链表表示  list2 5 2 6 3 10    3 2 4 14 9 3  表中套表情形下的广义表链表表示

广义表的存储表示 A  0 1 B  0 1 1 6 1 2 B C A D  0 1 3 3 3  C 0 1 2 ‘a’ 3  0 1 B  0 1 1 6 1 2 B C A D  0 1 3 3 3  C 0 1 2 ‘a’ 3  0 1 1 5 1 3 2 ‘x’ B D  E 0 1 3 3  F 0 1 1 4 3

广义表 LS = ( 1, 2, …, n ) 的结构特点

1)广义表中的数据元素有相对次序 广义表的长度定义为最外层包含元素 个数 广义表的深度定义为所含括弧的重数 “原子”的深度为 0 　“空表”的深度为 1

4) 广义表可以共享 5) 广义表可以是一个递归的表 递归表的深度是无穷值 递归表的长度是有限值 任何一个非空广义表 LS = ( 1, 2, …, n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, …, n) 两部分

例如: D=(E, F)=((a,(b, c)),F) Head(D)=E Tail(D)=(F) Head(E)=a Tail(E)=((b, c)) Head(((b, c)))=(b, c) Tail(((b, c)))=( ) Head((b, c))=b Tail((b, c))=(c) Head((c))=c Tail((c))=( )

广 义 表 的基本操作

InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);

插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历 Traverse_GL(L, Visit());

广义表结点定义 utype value tlink

结点类型 utype = 0, 表头；= 1, 整型原子；= 2, 字符型原子；= 3, 子表 值value utype=0时, 存放引用计数(ref)；utype=1时, 存放整数值(intinfo)；utype=2时, 存放字符型数据(charinfo)；utype=3时, 存放指向子表表头的指针(hlink) 尾指针tlink utype=0时, 指向该表第一个结点；utype0时, 指向同一层下一个结点

广义表的类定义 class GenList; //GenList类的前视声明 class GenListNode;//广义表结点类的前 struct Items { //仅有结点信息的项 friend class GenlistNode; friend class Genlist; int utype; //＝0 / 1 / 2 / 3

union { //联合 int ref; //utype=0, 存放引用计数 int intinfo; //utype=1, 存放整数值 char charinfo; //utype =2, 存放字符 GenListNode *hlink; //utype =3, 存放指向子表的指针 }value; }

class GenListNode {//广义表结点类定义 friend class Genlist; private: int utype; //＝0 / 1 / 2 / 3 GenListNode * tlink; //下一结点指针

union { //联合 int ref; //utype=0, 存放引用计数 int intinfo; //utype=1, 存放整数值 char charinfo; //utype=2, 存放字符 GenListNode *hlink; //utype =3, 存放指向子表的指针 } value;

public: GenListNode ( ) : utype (0), tlink (NULL),value.ref (0){ } //构造函数,建表头结点 GenListNode ( int t, GenListNode *next =NULL ){ } //构造函数：建表结点

Items& Info ( GenListNode *elem ); //返回表元素elem的值 int nodetype ( GenListNode *elem ) { return elem->utype; } //返回表元素elem的数据类型 GenListNode& setInfo ( Items&x ); //将表元素中的值修改为x };

class GenList { //广义表类定义 private: GenListNode *first; //广义表头指针 GenListNode *Copy( GenListNode *ls ); //复制一个ls指示的无共享非递归表 int depth ( GenListNode *ls ); //计算由 ls 指示的非递归表的深度

int equal ( GenListNode *s, GenListNode *t); //比较以s和t为表头的两个表是否相等 void Remove (GenListNode *ls ); //释放以 ls 为表头结点的广义表 public: Genlist ( ); // 构造函数 ~GenList ( ); //析构函数 GenListNode& Head(); // 返回表头

GenList& Tail ( ); //返回表尾 GenListNode *First ( ); //返回第一个元素 GenListNode * Next ( GenListNode *elem ); //返回表元素elem的直接后继元素 void setNext ( GenListNode *elem1, GenListNode *elem2 ); //将elem2插到表中元素elem1后

int Createlist ( GenListNode *ls, char * s ); //从广义表的字符串描述 s 出发, void Copy ( const GenList & ls); //广义表的复制 int depth ( ); //计算一个非递归表的深度 int Createlist ( GenListNode *ls, char * s ); //从广义表的字符串描述 s 出发, //建立一个带表头结点的广义表结构 }

广义表结点类的存取成员函数 Items& GenListNode :: Info ( GenListNode * elem ) { Items *pitem = new Items; pitem->utype = elem->utype; pitem->value = elem->value; return * pitem; }

GenListNode& GenListNode :: setInfo ( Items &x ) { //修改表元素的值为 x utype = x.utype; value = x.value; }

广义表类的构造和访问成员函数 Genlist :: GenList ( ) { //构造函数 first = new GenListNode( ); first->utype = 0; first->value.ref = 1; first->tlink = NULL; }

Items& GenList :: Head ( ) { //若广义表非空，则返回其第一个 元素的值，否则函数没有定义 if (first->tlink==NULL)return NULL; Items * temp = new Items; //非空表 temp->utype = frist->tlink->utype; temp->value = frist->tlink->value; return * temp; //返回类型及值 }

GenList& GenList :: Tail ( ) { //若广义表非空，则返回广义表除第一 个元素外其它元素组成的表, 否则函数 没有定义 if (frist->tlink==NULL)return NULL; GenList * temp; //非空表 temp->first = Copy ( first ); return * temp; }

GenListNode * GenList :: First ( ) { if (first->tlink==NULL)return NULL; return first->tlink; } GenListNode * GenList :: Next ( GenListNode *elem ) { if (elem->tlink==NULL)return NULL; return elem->tlink;

广义表的复制算法 void GenList :: Copy ( const GenList& ls ) { first = Copy ( ls.first ); //共有函数 }

GenListNode* GenList :: Copy ( GenListNode* ls ) {//私有函数 GenListNode *q = NULL; if ( ls != NULL ) { q = new GenListNode ( ls->utype, NULL ); switch ( ls->utype ) { case 0: q->value.ref = ls->value.ref; break;

case 1: q->value.intgrinfo = ls->value.intgrinfo; break; case 2: q->value.charinfo = ls->value.charinfo; break; case 3: q->value.hlink = Copy (ls->value.hlink); } q->tlink = Copy (ls->tlink);} return q; }

  

求广义表的深度 例如，对于广义表 E (B (a, b), D (B (a, b), C (u, (x, y, z)), A ( ) ) ) 1 1 1 1 2 3 4

广义表的深度 一个广义表的深度是指该广义表展开后所含括号的层数。 例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3; . （a）A=(b,c) （b）B=(a,A) （c）C=(A,B) 广义表用树或图来表示

int GenList::depth(GenListNode *ls){ if(ls->tlink==NULL)return 1; //空表 GenListNode *temp=ls->tlink;int m=0; while(temp!=NULL){ //在表顶层横扫 if(temp->utype==3){//结点为表结点 int n=depth(temp->value.hlink); if (m<n)m=n;} //m记最大深度 temp = temp->tlink;} return m+1; }

int GenList :: depth ( ) { return depth ( first ); }

广义表的删除算法

1.若结点数据为‘x’,删除。可能做循环连续删除。 2.若结点数据不为‘x’，不执行删除。 3.若结点为子表，递归在子表执行删除。 扫描子链表 1.若结点数据为‘x’,删除。可能做循环连续删除。 2.若结点数据不为‘x’，不执行删除。 3.若结点为子表，递归在子表执行删除。 ls  0 1 1 5 3 3 1 2   0 1 2 ‘x’ 2 ‘y’ 0 1 3  0 1 2 ‘x’

void delvalue(GenListNode * ls, const value x){ //在广义表中删除所有含 x 的结点 if ( ls->tlink != NULL ) { //非空表 GenListNode * p = ls->tlink; while ( p != NULL && //横扫链表 ( ( p->utype == 1 && p->value.intinfo == x ) || ( p->utype == 2 && p->value.charinfo == x ) ) {

ls->tlink=p->tlink; delete p; //删除 p = ls->tlink;//指向同一层后继结点 } if (p!=NULL){ if (p->utype==3) //在子表中删除 delvalue ( p->value.hlink, x ); delvalue(p,x); //在后续链表中删除

GenList :: ~GenList ( ) { //析构函数 Remove ( first ); }

void GenList :: Remove ( GenListNode *ls ) { //私有函数：释放以 ls 为表头指针 广义表 ls->value.ref --; //引用计数减1 if ( ls->value.ref == 0 ) { //如果减到0 GenListNode *p = ls, *q;//横扫表顶层

while ( p->tlink != NULL ) { q = p->tlink; //到第一个结点 if ( q->utype == 3 ) //递归删除子表 Remove ( q->value.hlink ); p->link = q->link; delete q; }

本章小结 1．多维数组在计算机中有两种存放形式：行优先和列优先。 2．行优先规则是左边下标变化最慢，右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。 3．列优先规则是右边下标变化最慢，左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。 4．对称矩阵关于主对角线对称。为节省存储单元，可以进行压缩存储，对角线以上的元素和对角线以下的元素可以共用存储单元。 5．三角矩阵有上三角矩阵和下三角矩阵之分，为节省内存单元，可以采用压缩存储。 6．稀疏矩阵的非零元排列无任何规律，为节省内存单元，进行压缩存储时，可以采用三元组表示方法，即存储非零元素的行号、列号和值。若干个非零元有若干个三元组，若干个三元组称为三元组表。 7．广义表为线性表的推广，里面的元素可以为原子，也可以为子表，故广义表的存储采用动态链表较方便。