（五）数组和广义表

数组的定义

　　　抽象数据类型

　　　ADT Array{
　　　　数据对象：ji=0,...,bi-1,i=1,2,...,n
　　　　　　　　　D={aj1j2...jn|n(>0)称为数组的维数，bi是数组第i维的长度
　　　　　　　　　ji是数组元素的第i维下表，aj1j2...jn∈ElemSet}
　　　　数据关系：R={R1.R2....,Rn}
　　　　　　　　　Ri={<aj1...ji...jn,aj1...ji+1...jn>|0≤jk≤bk-1,1≤k≤n且k≠i0≤ji≤bi-2　aj1...ji...jn,aj1...ji+1...jn∈D，i=2,...,n}
　　　　基本操作：
　　　　InitArray(&A,n,bound1,...,boundn)
　　　　　操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK
　　　　DestroyArray(&A)
　　　　　操作结果：销毁数组A
　　　　Value(A,&e,index1,...,indexn)
　　　　　初始条件：A是n维数组，e为元素变量，随后是n个下标值
　　　　　操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK
　　　　Assign(&A,e,index1,...,indexn)
　　　　　初始条件：A是n维数组，e为元素变量，随后是n个下标值
　　　　　操作结果：若下标不超界，则将e的值赋给指定的A的元素，并返回OK
　　　　}ADT Array；

　　　二维数组：
　　　　typedef ElemType Array2[m][n];
　　　　等价于
　　　　typedef ElemType Array1[n];
　　　　typedef Array1 Array2[m];

　　　二维数组的两种存储方式:
　　　　以行序为主序:LOC(i,j)=LOC(0,0)+(n×i+j)×L
　　　　以列序为主序:LOC(i,j)=LOC(0,0)+(m×j+i)×L

　　　数组的顺序存储表示:
　　　

　　　#define MAX_ARRAY_DIM 8  //假设数组维数的最大值为8
　　　typedef struct{
　　　　ElemType  *base;  //数组元素基址，由InitArray分配
　　　　int  dim;  //数组维数
　　　　int  *bounds;  //数组维界基址，由InitArray分配
　　　　int  *constants;  //数组映像函数常量基址，由InitArray分配
　　　}Array;

　　　矩阵的压缩存储：
　　　　为多个相同的非零元素分配一个存储空间；对零元素不分配空间

　　　　1.特殊矩阵：
　　　　指值相同的元素或者零元素在矩阵中的分布有一定规律

---

　　　　2.稀疏矩阵：
　　　　一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵

　　　　　抽象数据类型：

　　　　　ADT SpareseMatrix{
　　　　　　数据对象：D={aij|i=1,2,...,m,j=1,2,...,n}
　　　　　　数据关系：R={Row,Col}
　　　　　　　　　　　Row={<ai,j,ai,j+1>|1≤i≤m,1≤j≤n-1}
　　　　　　　　　　　Col={<ai,j,ai+1,j>|1≤i≤m-1,1≤j≤n}
　　　　　　基本操作：
　　　　　　CreateSMatrix(&M)
　　　　　　　操作结果：创建稀疏矩阵M
　　　　　　DestroySMatrix(&M)
　　　　　　　初始条件：稀疏矩阵M存在
　　　　　　　操作结果：销毁稀疏矩阵M
　　　　　　PrintSMatrix(M)
　　　　　　　初始条件：稀疏矩阵M存在
　　　　　　　操作结果：输出稀疏矩阵M
　　　　　　CopySMatrix(M,&T)
　　　　　　　初始条件：稀疏矩阵M存在
　　　　　　　操作结果：由稀疏矩阵M复制到T
　　　　　　AddSMatrix(M,N,&Q)
　　　　　　　初始条件：稀疏矩阵M与N的行数和列数对应相等
　　　　　　　操作结果：求稀疏矩阵的和Q=M+N
　　　　　　SubSMatrix(M,N,&Q)
　　　　　　　初始条件：稀疏矩阵M与N的行数和列数对应相等
　　　　　　　操作结果：求稀疏矩阵的差Q=M-N
　　　　　　MultSMatrix(M,N,&Q)
　　　　　　　初始条件：稀疏矩阵M的列数等于N的行数
　　　　　　　操作结果：求稀疏矩阵乘积Q=M×N
　　　　　　TransposeSMatrix(M,&T)
　　　　　　　初始条件：稀疏矩阵M存在
　　　　　　　操作结果：求稀疏矩阵M的转置矩阵T
　　　　　　}ADT SparseMatrix；

　　　　　　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；

　　　　　　图示：
　　　　　　　

　　　　　　b.行逻辑链接的顺序表：
　　　　　　

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

　　　　　　c.十字链表：
　　　　　　

　　　　　　typedef struct OLNode{
　　　　　　　　int  i,j;  //该非零元的行和列下标
　　　　　　　　ElemType  e;
　　　　　　　　struct OLNode *right, *down;  //该非零元所在行表和列表的后继链域
　　　　　　}OLNode,*OLink;
　　　　　　typedef struct{
　　　　　　　　OLink  *rhead, *chead;  //行和列链表头指针向量基址由CreateSMatrix分配
　　　　　　　　int  mu,nu,tu;  //稀疏矩阵的行数、列数和非零元个数
　　　　　　}CorssList;

　　　　　　图示：
　　　　　　　

---

　　　　3.三角矩阵：
　　　　上三角矩阵
　　　　下三角矩阵

　　　　4.对称矩阵：
　　　　　n^2个元二维数组压缩存储到n(n+1)/2个元的一位数组
　　　　　k=
　　　　　{ i(i-1)/2+j-1 当i≥j
　　　　　{ j(j-1)/2+i-1 当i<j
　　　图示：
　　　

广义表

　　广义表的定义：
　　　LS=(a1,a2,…,an)
　　　n为广义表的长度
　　　ai可以是单个元素，也可以是广义表，
　　　分别成Wie广义表LS的原子和字表

　　当广义表非空时，称第一个元素a1为LS的表头(Head),称其余元素组成的表(a2,…,an)是LS的表尾(Tail)

　　图示：
　　　

　　GetHead(D)=A, GetTail(D)=(B,C),GetHead((B,C))=B, GetTail((B,C))=(C)

　　()和(())不同，前者为空表，长度为0，后者长度为1，可分解为表头、表尾均为空表()

　　结论：
　　1.列表的元素可以是子表，子表的元素还可以是子表图表示，圆圈表示列表，方块表示原子
　　2.列表可以是一个递归的表，即列表也可以是其本身的一个子表例如E=(a,E)，相当于E=(a,(a,(a,…)))

　　存储结构：
　　　1.头尾链表存储表示：
　　　

　　　typedef enum{ATOM,LIST}ElemTag;  //ATOM==0;原子，LIST==1；子表
　　　typedef struct{
　　　　　ElemTag  tag;  //公共部分，用于区分原子节点和表节点
　　　　　union{
   　　　　　AtomType  atom;  //atom是原子节点的值域，AtomType由用户定义
   　　　　　struct{struct GLNode *hp,*tp}ptr;
　　　　　　　//ptr是表节点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
  　　　　};
　　　}*GList;

　　　2.扩展线性链表存储表示：
　　　

　　　typedef enum{ATOM,LIST}ElemTag;  //ATOM==0;原子，LIST==1；子表
　　　typedef struct{
　　　　　ElemTag  tag;  //公共部分，用于区分原子节点和表节点
　　　　　union{
   　　　　　AtomType  atom;  //atom是原子节点的值域，AtomType由用户定义
   　　　　　struct GLNode *hp;  //表节点的表头指针
   　　　　};
  　　　　struct GLNode  *tp;  //相当于线性链表的next，指向下一个元素节点
　　　}*GList;

三元组代表

#include<iostream>
using namespace std;

const int MAXSIZE=12501;
typedef int ElemType;
typedef struct{
	int i,j;
	ElemType val;
}Triple;

typedef struct{
	Triple data[MAXSIZE];
	int mu,nu,tu;
}TSMatrix;

typedef int Status;
const int OK=1;
const int ERROR=0;

Status TransporseSMatrix(TSMatrix M, TSMatrix &T){
	//将三元组M转置并以行为主序得到T
	//按列循环
	T.mu=M.nu;
	T.nu=M.mu;
	T.tu=M.tu;
	if(M.tu){

		int num=0;
		for(int col=1;col<=M.nu;col++){
			for(int pos=1;pos<=M.tu;pos++){
				if(M.data[pos].j==col){
					T.data[num].i=M.data[pos].j;
					T.data[num].j=M.data[pos].i;
					T.data[num].val=M.data[pos].val;
					num++;
				}
			}
		}
	}
	return OK;
}

Status FastTransporseSMatrix(TSMatrix M, TSMatrix &T){
	//将三元组M转置并以行为主序得到T
	//辅助数组法O(mu*nu)
	T.mu=M.nu;
	T.nu=M.mu;
	T.tu=M.tu;
	if(M.tu){

		int num[MAXSIZE];
		int cpos[MAXSIZE];
		for(int col=1;col<=M.nu;col++) num[i]=0;
		for(int t=1;t<=M.tu;t++) ++num[M.data[t].j];

		cpos[1]=1;
		for(int col=2;col<=M.nu;col++) cpos[col]=cpos[col-1]+num[col-1];
		for(int t=1;t<M.tu;t++){
			int col=M.data[t].j;
			T.data[cpos[col]].i=M.data[t].j;
			T.data[cpos[col]].j=M.data[t].i;
			T.data[cpos[col].val=M.data[t].val;
			cpos[col]++;
		}

	}

	return OK;
}

typedef struct{
	Triple data[MAXSIZE];
	int rpos[MAXSIZE];
	int mu,nu,tu;
}RLSMatrix;

Status MultSMatrix(RLSMatrix M,RLSMatrix N, RLSMatrix &Q){
	if(M.nu!=N.mu) return ERROR;
	Q.mu=M.mu;
	Q.nu=N.nu;
	Q.tu=0;
	if(M.tu*N.tu!=0){
		for(int row=1;row<=M.mu;row++){
			int ctemp[N.nu];
			fill(ctemp,ctemp+M.nu,0);
			int rnum=0;

			if(row<M.mu) rnum=M.rpos[row+1];
			else	rnum=M.tu+1;

			for(int rp=M.rpos[row];rp<rnum;rp++){

				int brow=M.data[rp].j;
				int bnum=0;
				if(brow<N.tu) bnum=N.rpos[brow+1];
				else bnum=N.tu+1;

				for(int bp=N.rpos[brow];bp<bnum;bp++){
					int bcol=N.data[bp].j;
					ctemp[bcol]=M.data[rp].val*N.data[bp].val;
				}
			}

			bool first=false;

			for(int i=1;i<=Q.nu;i++){
				if(ctemp[i]!=0){
					Q.tu++;
					if(!first){
						first=true;
						Q.rpos[row]=Q.tu;
					}
					Q.data[Q.tu].i=row;
					Q.data[Q.tu].j=i;
					Q.data[Q.tu].val=ctemp[i];
				}
			}
		}
	}
}

十字链表代码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -10
#define OVERFLOW_ -2

typedef int Status;
typedef int QElemType;
typedef int ElemType;

//------稀疏矩阵的十字链表存储表示----
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;

class SMatrix_OL {
public:
	Status InitSMatrix_OL(CrossList &M);
	//十字链表初始化
	Status PushSMatrix_OL(CrossList &M, OLink p);
	//向矩阵中插入新非零元素
	Status CreateSMatrix_OL(CrossList &M);
	//创建系数矩阵M，采用十字链表存储表示
	Status DestroySMatrix_OL(CrossList &M);
	//若稀疏矩阵存在，则销毁十字链表
	Status PrintSMatrix_OL(CrossList M);
	//若稀疏矩阵存在，则输出稀疏矩阵
	Status CopySMatrix_OL(CrossList M, CrossList &T);
	//若稀疏矩阵存在，则将M复制至T
	Status AddSMatrix_OL(CrossList M, CrossList N, CrossList &Q);
	//若稀疏矩阵M和N的行数和列数对应相等，则求和Q=M+N
	Status TransposeSMatrix_OL(CrossList M, CrossList &T);
	//若稀疏矩阵存在，则求M的转置矩阵T
	Status MulSMatrix_OL(CrossList M, CrossList N, CrossList &Q);
	//若稀疏矩阵M的列数等于N的行数，则求积Q=M*N
	Status SubSMatrix_OL(CrossList M, CrossList N, CrossList &Q);
	//若稀疏矩阵M与N的行数和列数对应相等，求差Q=M-N
};

Status SMatrix_OL::InitSMatrix_OL(CrossList &M) {
	//十字链表初始化
	//if (!(M.rhead = (OLink * )malloc((M.mu + 1) * sizeof(OLink)))) exit(OVERFLOW_);
	//if (!(M.chead = (OLink * )malloc((M.nu + 1) * sizeof(OLink)))) exit(OVERFLOW_);
	if (!(M.rhead = new OLink[M.mu + 1])) exit(OVERFLOW_);
	if (!(M.chead = new OLink[M.nu + 1])) exit(OVERFLOW_);
	for (int i = 0;i < M.mu + 1;i++) M.rhead[i] = NULL;
	for (int i = 0;i < M.nu + 1;i++) M.chead[i] = NULL;
	return OK;
}

Status SMatrix_OL::PushSMatrix_OL(CrossList &M, OLink p) {
	//向矩阵中插入新非零元素
	int i, j;

	i = p->i;
	j = p->j;

	if (M.rhead[i] == NULL || M.rhead[i]->j > j) { //若大于原有列或者行空
		p->right = M.rhead[i];
		M.rhead[i] = p;
	}
	else {	//若小于原有列（即暗示行非空）
		OLink q;
		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 {
		OLink q;
		for (q = M.chead[j];q->down&&q->down->i < i;q = q->down); //寻找在列表中的插入位置
		p->down = q->down;q->down = p;
	}//完成列插入
	return OK;
}

Status SMatrix_OL::CreateSMatrix_OL(CrossList &M) {
	//创建系数矩阵M，采用十字链表存储表示
	cin >> M.mu >> M.nu >> M.tu; //输入矩阵的行数、列数和非零元个数
	InitSMatrix_OL(M);

	for (int h = 0;h < M.tu;h++) {
		int i, j, e;
		cin >> i >> j >> e;
		OLNode * p;
		//if (!(p = (OLNode * )malloc(sizeof(OLNode)))) exit(OVERFLOW_);
		if (!(p = new OLNode)) exit(OVERFLOW_);
		p->i = i; p->j = j; p->e = e;  //生成结点
		PushSMatrix_OL(M, p); //插入
	}
	return OK;
}

Status SMatrix_OL::DestroySMatrix_OL(CrossList &M) {
	//若稀疏矩阵存在，则销毁十字链表
	OLink p;
	for (int i = 1;i < M.mu + 1;i++) { //按行表进行销毁
		while (M.rhead[i]) {
			p = M.rhead[i]->right;
			free(M.rhead[i]);
			M.rhead[i] = p;
		}
	}
	/* for (int i = 1;i < M.nu+1;i++) { //按列表进行销毁
		while(M.chead[i]) {
			p = M.chead[i]->down;
			free(M.chead[i]);
			M.chead[i] = p;
		}
	}*/
	return OK;
}

Status SMatrix_OL::PrintSMatrix_OL(CrossList M) {
	//若稀疏矩阵存在，则输出稀疏矩阵
	OLink p, q;

	int sub;
	for (int i = 1;i < M.mu + 1;i++) {
		if (!M.rhead[i]) {  //该行全为零元素
			int j = 0;
			while (j != M.nu) {
				cout << "0";
				if (j != M.nu - 1)
					cout << " ";
				j++;
			}
		}
		else {
			for (int j = 1;j < M.rhead[i]->j;j++) {//打印行首零元素
				cout << "0 ";
			}
			q = M.rhead[i];
			while (q) {
				cout << q->e;
				if (q->j != M.nu)
					cout << " ";
				sub = M.nu - q->j;//计算列数与当前行头指针的列标差，方便最后打印行末零元素
				p = q->right;
				for (int j = 1;p&&j < p->j - q->j;j++) {
					cout << "0 ";
				}
				q = p;
			}
			for (int j = 1;j <= sub;j++) {  //打印行尾零元素
				cout << "0";
				if (j != sub)
					cout << " ";
			}
		}
		cout << endl;
	}
	return OK;
}

Status SMatrix_OL::CopySMatrix_OL(CrossList M, CrossList &T) {
	//若稀疏矩阵存在，则将M复制至T
	T.mu = M.mu;
	T.nu = M.nu;
	T.tu = M.tu;
	InitSMatrix_OL(T);
	OLink p;
	for (int i = 1;i < M.mu + 1;i++) {
		OLink m = M.rhead[i];
		while (m) {
			//if (!(p = (OLNode * )malloc(sizeof(OLNode)))) exit(OVERFLOW_);
			if (!(p = new OLNode)) exit(OVERFLOW_);
			//p = m;  //指针！！！！！我讨厌指针！！
			p->i = m->i;
			p->j = m->j;
			p->e = m->e;
			m = m->right;
			PushSMatrix_OL(T, p);
		}
	}
	return OK;
}

Status SMatrix_OL::AddSMatrix_OL(CrossList M, CrossList N, CrossList &Q) {
	//若稀疏矩阵M和N的行数和列数对应相等，则求和Q=M+N
	Q.mu = M.mu;Q.nu = M.nu;Q.tu = 0;
	InitSMatrix_OL(Q);//初始化
	OLink p, m, n;
	for (int i = 1;i < M.mu + 1;i++) {
		m = M.rhead[i];n = N.rhead[i];
		while (m || n) {
			//if (!(p = (OLNode * )malloc(sizeof(OLNode)))) exit(OVERFLOW_);
			if (!(p = new OLNode)) exit(OVERFLOW_);
			if (!n || (m&&m->j < n->j)) {
				//p = m; 同上
				p->i = m->i;
				p->j = m->j;
				p->e = m->e;
				m = m->right;
				PushSMatrix_OL(Q, p); //插入结点
				Q.tu++;
			}
			else if (!m || (n&&m->j > n->j)) {
				//p = n;
				p->i = n->i;
				p->j = n->j;
				p->e = n->e;
				n = n->right;
				PushSMatrix_OL(Q, p); //插入结点
				Q.tu++;
			}
			else if (m->j == n->j) {
				//p = m;  错误示范
				p->i = m->i;
				p->j = m->j;
				p->e = m->e + n->e;
				m = m->right;
				n = n->right;
				if (p->e != 0) {
					PushSMatrix_OL(Q, p); //插入结点
					Q.tu++;
				}
			}
		}
	}
	return OK;
}

Status SMatrix_OL::SubSMatrix_OL(CrossList M, CrossList N, CrossList &Q) {
	//若稀疏矩阵M与N的行数和列数对应相等，求差Q=M-N
	Q.mu = M.mu;Q.nu = M.nu;Q.tu = 0;
	InitSMatrix_OL(Q);//初始化
	OLink p, m, n;
	for (int i = 1;i < M.mu + 1;i++) {
		m = M.rhead[i];n = N.rhead[i];
		while (m || n) {
			//if (!(p = (OLNode * )malloc(sizeof(OLNode)))) exit(OVERFLOW_);
			if (!(p = new OLNode)) exit(OVERFLOW_);
			if (!n || (m&&m->j < n->j)) {
				//p = m; 同上
				p->i = m->i;
				p->j = m->j;
				p->e = m->e;
				m = m->right;
				PushSMatrix_OL(Q, p); //插入结点
				Q.tu++;
			}
			else if (!m || (n&&m->j > n->j)) {
				//p = n;
				p->i = n->i;
				p->j = n->j;
				p->e = -(n->e);
				n = n->right;
				PushSMatrix_OL(Q, p); //插入结点
				Q.tu++;
			}
			else if (m->j == n->j) {
				//p = m;  错误示范
				p->i = m->i;
				p->j = m->j;
				p->e = m->e - n->e;
				m = m->right;
				n = n->right;
				if (p->e != 0) {
					PushSMatrix_OL(Q, p); //插入结点
					Q.tu++;
				}
			}
		}
	}
	return OK;
}

Status SMatrix_OL::MulSMatrix_OL(CrossList M, CrossList N, CrossList &Q) {
	//若稀疏矩阵M的列数等于N的行数，则求积Q=M*N
	OLink p;
	OLink m, n;

	Q.mu = M.mu;Q.nu = N.nu;Q.tu = 0;
	InitSMatrix_OL(Q);

	for (int i = 1;i < M.mu + 1;i++) {
		for (int j = 1;j < N.nu + 1;j++) {
			m = M.rhead[i];n = N.chead[j];
			//if(!(p = (OLNode * )malloc(sizeof(OLink))))exit(OVERFLOW_);
			if (!(p = new OLNode))exit(OVERFLOW_);
			p->e = 0;
			while (m && n) {
				if (m->j == n->i) {
					p->i = i;
					p->j = j;
					p->e += m->e * n->e;
					m = m->right;
					n = n->down;

				}
				else if (m->j < n->i)
					m = m->right;
				else
					n = n->down;
			}
			if (p->e != 0) {
				PushSMatrix_OL(Q, p); //插入结点
				Q.tu++;
			}
		}
	}
	return OK;
}

Status SMatrix_OL::TransposeSMatrix_OL(CrossList M, CrossList &T) {
	//若稀疏矩阵存在，则求M的转置矩阵T
	OLink p;
	OLink m;

	T.mu = M.nu;T.nu = M.mu;T.tu = 0;
	InitSMatrix_OL(T);
	for (int i = 1;i < M.mu + 1;i++) {
		m = M.rhead[i];
		while (m) {
			//if(!(p = (OLNode * )malloc(sizeof(OLink))))exit(OVERFLOW_);
			if (!(p = new OLNode))exit(OVERFLOW_);
			p->i = m->j;
			p->j = m->i;
			p->e = m->e;
			m = m->right;
			PushSMatrix_OL(T, p); //插入结点
			T.tu++;
		}
	}
	return OK;
}

赏

Thank you for inviting me to have candy.

支付宝

微信