数据结构（C语言版）严蔚敏吴伟民编著第5章数组和广义表

程序员文章站 2022-05-22 15:05:40

...

数据结构（C语言版）严蔚敏吴伟民编著第5章数组和广义表

前言
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
- 5.3.1 特殊矩阵
- 5.3.2 稀疏矩阵
5.4 广义表的定义
5.5 广义表的存储结构

前言

前几章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。本章讨论的两种数据结构——数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。

5.1 数组的定义

类似于线性表，抽象数据类型数组可形式化定义为：
ADT Array{
数据对象：j_i=0,…,b_i-1, i = 1, 2, …,n,
D={a_j1j2…jn}，n(>0)称为数组的维数，b_i是数组第i维的长度，j_i是数组元素的第i维的下标，a_j1j2…jn∈ElemSet
}
从上数定义中可知，n维数组总共含有 ∑ i = 1 n b i \sum_{i=1}^{n} b_i ∑i=1nbi 个元素，每个元素都受着n个关系的约束。n为数组可以看成是线性表的推广。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，同理一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。数组一旦定义，它的维数和维界就不再改变，因此除了结构的初始化和销毁之后，数组只有存取元素和修改元素值的操作。

5.2 数组的顺序表示和实现

由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不发生变动。因此，采用顺序存储结构表示数组是自然的事了。由于存储单元是一维的结构，而数组是多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。二维数组可有两种存储方式：一种是以列序为主序的存储方式，一种是以行序作为主序的存储方式。在扩展BASIC、PL/1、COBOL、PASCAL和C语言中，用的都是以行序为主序的存储结构，而在FORTRAN语言中，用的是以列序为主序的存储结构。
假设每个数据元素占L个存储单元，则二维数组A中任一元素a_ij的存储位置可由下式确定：
LOC(i,j) = LOC(0,0)+(b₂×i + j)L
式中，LOC(i,j)是a_ij的存储位置，LOC(0,0)是a₀₀的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。n维数组的数据元素存储位置计算同理。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。

// 数组的顺序存储表示
#include<stdarg.h>   // 标准头文件，提供宏va_start、va_arg和va_end，用于存取变长参数表
#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为8
typedef struct{
	ElemType  *base;    // 数组元素基址，由InitArray分配
	int         dim;    // 数组维数
	int     *bounds;    // 数组维界基址，由InitArray分配
	int  *constants;    // 数组映像函数常量基址，由InitArray分配
}Array;

Status InitArray(Array &A, int dim, ...){
	// 若维数dim和各维长度合法，则构造相应的数组A，并返回OK
	if(dim<1||dim > MAX_ARRAY_DIM) return ERROR;
	A.dim = dim;
	A.bounds = (int *)malloc(dim*sizeof(int));
	if(!A.bounds) exit(OVERFLOW);
	// 若各维长度合法，则存入A.bounds，并求出A的元素总数elemtotal
	elemtotal = 1;
	va_start(ap, dim);     // ap为va_list类型，是存放变长参数表信息的数组
	for(i = 0; i < dim; ++i){
		A.bounds[i] = va_arg(ap, int);
		if(A.bounds[i] <0) return UNDERFLOW;
		elemtotal *= A.bound[i];
	}
	va_end(ap);
	A.base = (ElemType *)malloc(elemtotal * sizeof(ElemType));
	if(!A.base) exit(OVERFLOW);
	// 求映像函数的常数c1，并存入A.constants[i-1],i = 1,...,dim 
	A.constants = (int *)malloc(dim * sizeof(int));
	if(!A.constants) exit(OVERFLOW);
	A.constants[dim - 1] = 1;  // L = 1,指针的增减以元素的大小为单位
	for(i = dim -2; i >= 0; --i)
		A.constants[i] = A.bounds[i+1] * A.constants[i+1];
	return OK;
}

Status DestroyArray(Array &A){
	// 销毁数组A
	if(!A.base) return ERROR;
	Free(A.base); A.base = NULL;
	if(!A.bounds) return ERROR;
	free(A.bounds); A.bounds = NULL;
	if(!A.constants) return ERROR;
	free(A.constants) A.constants = NULL;
	return OK;
}

Status Locate(Array A, va_list ap; int &off){
	// 若ap指示的各下标值合法，则求出该元素在A中相对地址off
	off = 0;
	for(i = 0; i < A.dim ; ++i){
		ind = va_arg(ap,int);
		if(ind <0 || ind >= A.bounds[i]) return OVERFLOW;
		off += A.constants[i] * ind;
	}
	return OK;
}

Status Value(Array A, ElemType &e,...){
	// A是n维数组，e为元素变量，随后是n个下标值，若各下标不超界，则e赋值为所指定的A的元素值，并返回OK
	va_start(ap,e);
	if((result = Locate(A,ap,off)<=0)) return result;
	e = *(A.base + off);
	return OK;
}

Status Assign(Array &A, ElemType e, ...){
	// A是n维数组，e为元素变量，随后是n个下标值，若下标不超界，则将e的值赋给所指定的A的元素，并返回OK
	va_start(ap,e);
	if((result = Locate(A,ap, off)) <= 0) return result;
	*(A.base + off) = e;
	return OK;
}

5.3 矩阵的压缩存储

矩阵是很多科学与工程计算问题中研究的数学对象，在此，我们感兴趣的是如何存储矩阵的元，从而使矩阵的各种运算能有效地运行。通常，用高级语言编制程序时，都是用二维数组来存储矩阵元。然而在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元只分配一个存储空间，对零元不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵，反之称为稀疏矩阵。

5.3.1 特殊矩阵

对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n²个元压缩存储到n(n+1)/2个元的空间中。不失一般性，我们可以行序为主序存储其下三角，包括对角线中元。
这种压缩存储的方法同样也适用于三角矩阵。所谓下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为常数c或零的n阶矩阵。则除了和对称矩阵一样，只存储其下（上）三角中的元之外，再加一个存储常数c的存储空间即可。
在数值分析中经常出现的还有另一类特殊矩阵是对角矩阵。对这种矩阵，我们也可按照某个原则（或以行为主，或以对角线的顺序）将其压缩到一维数组上。
然而，在实际应用中我们还会遇到另一类矩阵，其非零元较零元少，且分布没有一定规律，我们称之为稀疏矩阵。

5.3.2 稀疏矩阵

假设在m×n的矩阵中，有t个元素不为零。零δ=t/(m×n)，称δ为矩阵的稀疏因子，通常认为δ≤0.05时称为稀疏矩阵。
一个三元组（i,j,a_ij）唯一确定了矩阵A中的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

三元组顺序表
假设以顺序存储结构来表示三元组，则可得稀疏矩阵的一种压缩存储方式——我们称之为三元组顺序表。

// 稀疏矩阵的三元组顺序表存储表示
#define MAXSIZE 12500   // 假设非零元个数的最大值为12500
typedef struct{
	int       i, j;   // 该非零元的行下标和列下标
	ElemType     e;   
}Triple;

typedef struct{
	Triple data[MAXSIZE + 1];  // 非零元三元组表，data[0]未用
	int mu, nu, tu;            // 矩阵的行数、列数和非零元个数
}TSMatrix

data域中表示非零元的三元组是以行序为主序排列的，这样做将有利于进行某些矩阵运算。下面讨论如何在这种压缩存储结构下如何实现矩阵的转置运算。
假设a和b是TSMatrix型的变量，分别表示矩阵M和T，如何由a得到b？
（1）将矩阵的行列值相互交换
（2）将每个三元组中的i和j相互调换
（3）重排三元组之间的次序便可实现矩阵的转置
前两条是容易做到的，关键是第三条，如何使b.data中的三元组是以T的行（M的列）为主序依次排列的。可以有两种处理方法：
（1）按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。换句话说，按照矩阵M的列序来进行转置。为了找到M的每一列中所有的非零元素，需要对其三元组a.data从第一行起整个扫描一遍，由于a.data是以M的行序为主序来存放每个非零元的，由此得到的恰是b.data应有的顺序。算法如下：

Status TransposeSMatrix(TSMatrix M,TSMatrix &T){
	// 采用三元组表存储表示，求稀疏矩阵M的转置矩阵T
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
	if(T.tu){
		q = 1;
		for(col = 1; col <= M.nu; ++col)
			for(p = 1; p<= M.tu; ++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;
}// TransposeSMatrix

这个算法，主要的工作是在p和col的两重循环中完成的，故算法的时间复杂度为O(nu×tu)，即和M的列数及非零元的个数的乘积成正比。对于一般算法的转置算法为:

for(col = 1; col <= nu; ++col)
	for (row = 1; row <= mu; ++ row)
		T[col][row]= M[row][col];

其时间复杂度为O(mu×nu)，当非零元的个数tu和mu×nu同数量级时，其算法复杂度为O(mu×nu²)了，虽然节省了存储空间，但时间复杂度变高了，因此上述算法仅适用于tu<< mu×nu的情况。
（2）按照a.data中三元组的次序进行转置，并将转置后的三元组置于b中恰当的位置。如果能预先确定M中的每一列（即T中的每一行）的第一个非零元在b.data中应有的位置，那么在对a.data中的三元组依次作转置时，便可直接放在b.data中恰当位置上去。为了确定这些位置，在转置前，应当求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data应有的位置。
在此，需要附设num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有：
cpot[1] = 1;
cpot[col] = cpot[col -1 ]+ num[col - 1] 2≤col≤a.nu
这种转置方法称为快速转置，其算法如下：

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
	// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
	if(T.tu){
		for (col = 1; col = M.nu; ++col) num[col] = 0;
		for (t= 1; t<= M.tu; ++t) ++num[M.data[t].j]; // 求M中每一列含非零元个数,j代表着列数，data[t]代表着数据元素				
		cpot[1] = 1;
		// 求第col列中第一个非零元在b.data中的序号
		for(col = 2; col <= M.nu; ++col) cpot[col] = cpot[col - 1]+num[col -1];
		for(p=1; p<=M.tu; ++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];
		}
	}
	return OK;
}// FastTransposeSMatrix

这个算法仅比前一个算法多用了两个辅助变量。从时间上来看，算法中有4个并列的单循环，循环次数分别为nu和tu，因而总的时间复杂度为O(nu+tu)。在M的非零元个数tu和mu×nu等数量级时，其时间复杂度为0(mu×nu)，和经典算法的时间复杂度相同。
三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若按行号存取某一行的非零元，则需从头开始查找。
2. 行逻辑链接的顺序表
为了便于随机处理任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置算法中创建的，指示行信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种带行链接信息的三元组表为行逻辑链接的顺序表，其类型描述如下：

typedef struct{
	Triple data[MAXSIZE + 1];     // 非零元三元组表
	int   rpos[MAXRC + 1];        // 各行第一个非零元的位置表
	int  mu,nu,tu;                // 矩阵的行数、列数和非零元个数
}// RLSMatrix;

十字链表
当矩阵中的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。如在作将矩阵B加到矩阵A上的操作时，由于非零元的插入或删除将会引起A.data中元素的移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。
在链表中，每个非零元可用一个含5个域的结点表示，其中i、j和e这3个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。

// 稀疏矩阵的十字链表存储表示
typedef struct OLNode{
	int         i, j;         // 该非零元的行和列下标
	ElemType       e;         
	struct OLNode  *right, *down; // 该非零元所在行表和列表的后继链域
}OLNode; *OLink;

typedef struct{
	OLink  *rhead, *chead;  // 行和列链表头指针向量基址由CreateSMatrix分配
	int mu, nu, tu;         // 稀疏矩阵的行数、列数和非零元个数
}CrossList;

Status CreateSMatrix_OL(CrossList &M){
	// 创建稀疏矩阵M，采用十字链表存储表示
	if(M) free(M);
	scanf(&m, &n, &t);     // 输入M的行数、列数和非零元个数
	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;    // 初始化行列头指针向量，各行列链表为空链表
	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;}   // 完成行插入
			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;}      // 完成列插入			
			}		
		} // else
	}// for
	return OK;
}// CreateSMatrix_OL

对于m行n列且有t个非零元的稀疏矩阵，上述算法的执行时间为O(t×s)，s=max{m,n}，这是因为每建立一个非零元的结点时都要寻查它在行表和列表中的插入位置，此算法对非零元输入的先后次序没任何要求。反之，若按以行序为主序的次序依次输入三元组，则可将建立十字链表的算法改写成O(t)数量级的。

5.4 广义表的定义

广义表一般记作：
LS = (α₁，α₂，…，α_n)
其中，LS是广义表的名称，n是它的长度。在线性表的定义中，α_i（1≤i≤n）只限于单个元素。而在广义表的定义中，α_i可以是单个元素，也可以是广义表，分别称为广义表LS的原子表和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素α₁为LS的表头，称其余元素组成的表 (α₂，α₃，…，α_n)是LS的表尾。
显然，广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。可推出列表的3个重要结论：
（1）广义表的元素可以是广义表，而广义表的元素还可以是广义表…由此，广义表是一个多层次的结构，可以用图形象的表示。
（2）广义表可为其他广义表所共享。
（3）广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。

5.5 广义表的存储结构

由于广义表 (α₁，α₂，…，α_n)中的数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。
如何设定结点的结构？由于列表中的数据元素可能为原子或列表，由此需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。从上节可知：若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由3个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域，其形式定义如下：

// 广义表的头尾链表存储表示
typedef enum{ATOM,LIST} ElemTag; // ATOM == 0:原子，LIST == 1：子表
typedef struct GLNode{
	ElemTag tag;            // 公共部分，用于区分原子结点和表结点
	union{                  // 原子结点和表结点的联合部分
		AtomType atom;      // atom是原子结点的值域，AtomType由用户定义
		struct{ struct GLNode *hp, *tp;}ptr; // ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
	};
}*GList;                    // 广义表类型

也可以采用另一种结点结构的链表表示列表，其形式化定义说明如下：

// 广义表的扩展线性链表存储表示
typedef enum{ATOM,LIST} ElemTag; // ATOM == 0:原子，LIST == 1：子表
typedef struct GLNode{
	ElemTag tag;            // 公共部分，用于区分原子结点和表结点
	union{                  // 原子结点和表结点的联合部分
		AtomType atom;      // atom是原子结点的值域，AtomType由用户定义
		struct GLNode *hp;  // 表结点的表头指针
	};
	struct GLNode     *tp;  // 相当于线性表的next，指向下一个元素结点
}*GList;                    // 广义表类型GList是一种扩展的线性链表

相关标签：数据结构 C语言数据结构 c语言

上一篇：孙尚香为什么后来没有回到刘备的身边？是刘备不想让她回来吗？

下一篇： Largest Rectangle in a Histogram POJ - 2559(栈的运用)

数据结构（C语言版）严蔚敏吴伟民编著第5章数组和广义表