数据结构-数组（稀疏矩阵转置）和广义表

1、数组

定义

数组是一种用于存储多个相同类型数据的集合，其元素在内存中连续存放并按照一定的顺序排列。这种有序性和连续性使得数组在访问时具有较高的效率。数组的特点包括所有元素具有相同的数据类型、可以通过索引快速访问任意元素、支持各种操作如遍历和排序等，并且数组的定义和初始化方式在不同编程语言中有所不同。

1）数组存储地址计算

数组存储地址的计算主要依赖于数组的起始地址、元素的数据类型（即每个元素所占的字节数）以及元素的下标位置

一维数组的存储地址计算

首元素地址：假设一维数组A的首地址为L，且每个元素占用C个字节。则数组中任意元素A[i]的地址可以通过公式Loc(A[i]) = L + i * C来计算。
示例：如果数组A的首地址是1000，每个元素占4个字节，那么A[3]的地址就是1000 + 3 * 4 = 1012。

二维数组的存储地址计算

行优先存储：在行优先存储中，二维数组的元素按照行的顺序依次存储。对于二维数组B[m][n]，元素B[i][j]的地址计算公式为Loc(B[i][j]) = Loc(B[0][0]) + (i * n + j) * C，其中C是每个元素占用的字节数。
列优先存储：在列优先存储中，二维数组的元素按照列的顺序依次存储。对于二维数组B[m][n]，元素B[i][j]的地址计算公式为Loc(B[i][j]) = Loc(B[0][0]) + (j * m + i) * C。
示例：假设有一个3x4的二维数组B，按行优先存储，首地址为1000，每个元素占2个字节。那么B[2][3]的地址就是1000 + (2*4 + 3) * 2 = 1026。

多维数组的存储地址计算

对于更高维度的数组，地址计算方法类似，只是需要考虑更多维度的索引和步长。
例如，按行优先存储的三维数组D[m][n][p]的元素D[i][j][k]的地址计算公式为Loc(D[i][j][k]) = Loc(D[0][0][0]) + ((i * n * p + j * p + k) * C)。
列优先：Loc(D[i][j][k]) = Loc(D[0][0][0]) + (knm+j*m+i)*C

示例

数组A[9][3][5][8],首地址为100，每个元素占4个字节，求a[8][2][4][7]的地址

①行优先

100+(8358+258+48+7)*4

②列优先

100+(7539+439+29+8)*4

2）稀疏矩阵的转置

三元组顺序表

由于稀疏矩阵中含有大量的零元素，空间利用率很低，所以需要三元组顺序表来表示稀疏矩阵中的非零元素，它通过行优先的顺序将非零元素及其位置信息存储在一个线性表中，节省存储空间并简化运算

结构定义

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

①普通矩阵转置

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

②三元组顺序表转置稀疏矩阵

Status TransposeSMatrix(TSMatrix M, TSMatrix &T){//采用三元组表存储表示，求稀疏矩阵M的转置矩阵TT.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

③稀疏矩阵的快速转置

如果能预先确定就诊M中每一列（即T中的每一行）的第一个非零元在b.data中应有的位置，那么在对a.data中的三元组一次作转置时，便可直接放到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

接下来就可以利用num和cpot向量快速确定转置后各元素在三元组表中的位置，提高运行效率

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵TT.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中每一列含非零元个数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];//当一列的第一个元素转置完成后，下一个需要转置的是三元组表的下一个位置}//for}//ifreturn OK;
//FastTransposeSMatrix

3）十字链表

十字链表是一种用于表示稀疏矩阵的特殊存储结构，它通过行优先的顺序将非零元素及其位置信息存储在一个线性表中。每个节点包含五个字段：行号、列号、值、向下指针和向右指针，从而形成一个十字交叉的链表结构。这种结构不仅节省了存储空间，还提高了运算效率，并使得对稀疏矩阵的操作更加灵活和高效。

结构定义

typedef struct OLNode{int i,j;//该非零元的行和列下标ElemType e;struct OLNode *right,*down;//该非零元所在行表和列表的后继链域
}OLNode; *OLink;typedef struct{OLink *rhead,*chead;int mu,nu,tu;//稀疏矩阵的行数、列数、非零元总数
}CrossList;

2、广义表

定义

广义表是一种非线性的数据结构，它允许表中的元素既可以是单个数据项（原子），也可以是另一个广义表。这种结构使得广义表能够表示复杂的嵌套关系和层次结构。广义表的特点包括其元素的多样性（可以是原子或其他广义表）、结构的灵活性（可以嵌套任意深度）以及操作的复杂性（如求表头、表尾等）。在存储上，广义表通常采用链式结构来表示，以方便处理其复杂的嵌套关系。

1）基本操作

①GetHead

获取广义表的第一个元素，可以是原子，可以是列表

②GetTail

除了广义表中第一个元素的所有其他元素的集合，无论该元素是什么，都需要在外面额外套上一个（），即使是空表，或该值本来就有（）

该部分主要是在给出一个广义表时能正确获取表头和表尾

2）构造存储结构的两种方法

表头表尾

结构定义

typedef struct GLNode{ElemTag tag;//公共部分，用于区分原子结点和表结点union{//原子结点和表结点的联合部分AtomType atom;//atom是原子结点的值域，AtomType由用户定义struct{struct GLNode *hp,*tp;}ptr;//ptr是表结点的指针域，ptr.hp和[tr.tp分别指向表头和表尾};
}*GList;//广义表类型

示例：
A = （）
B = （e）
C = （a，（b，c，d））
D = （A，B，C）
E = （a，E）//递归表 E = （a，（a，（a，…）））

另一种方法我还没理解，就不在这里说了

3）递归算法

由于广义表的定义本身就具有一定的递归性，且其子表问题与其本身的问题具有极高相似度、关联性，所有递归算法与广义表操作具有极好的适配性

①求广义表深度

int GListDepth（GList L）｛//采用头尾链表存储结构，求广义表L的深度。if C!L） return 1；// 空表深度1if (L—> tag == ATOM) return 0;// 原子深度 0for (max=0, pp=L; PP; pp=pp->ptr. tp) {dep = GListDepth（pp—>Ptr.hp）；// 求以 pp—>ptr.hp 为头指针的子表深度if (dep > max) max = dep;}return max + 1；//非空表的深度是各元素的深度的最大值+1
}// GListDepth

②复制广义表

Status CopyGList(GList &T, GList L) {// 采用头尾链表存储结构，由广义表L复制得到广义表T。if(!L)  T = NULL;// 复制空表else {if（！（T= （GList） malloc（sizeof（GL.Node））））exit（OVERFLOW）；// 建表结点T -> tag = L -> tag；if (L—> tag == ATOM) T -> atom = L -> atom;// 复制单原子else {CopyGList(T-> ptr. hp, L->ptr. hp) ;// 复制广义表L-＞ptr.hp 的一个副本T->ptr.hpCopyGList(T—> ptr. tp, L->ptr. tp);// 复制广义表L-＞ptr.tp 的一个副本T->ptr.tp} // else} // elsereturn OK;
}// CopyGList

③创建广义表

三种情况：

1. 带括弧的空白串
2. 长度为1的单字符串
3. 长度>1的字符串

显然，前两种情况为递归的终结状态，子表为空表或只含一个原子结点，后一种情况为递归调用

Status CreateGList (GList &L, SString S) {//采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设 emp="（）"if （StrCompare（S, emp））L=NULL； //创建空表else {if (! (L = (GList) malloc (sizeof (GLNode)))) exit (OVERFLOW); //建表结点if （StrLength（S）==1）｛L->tag = ATOM; L->atom =S；｝// 创建单原子广义表else {L->tag = LIST; p = L;SubString (sub, S, 2, Strength(S)—2) ;// 脱外层括号do｛// 重复建n 个子表sever（sub,hsub）；// 从 sub中分离出表头串hsubCreateGList（p->ptr. hp,hsub）；q = p；if （！StrEmpty（sub））｛// 表尾不空if (!(p = (GLode * ) malloc (sizeof (GLNode))))exit (OVERFLOW) ;p->tag = LIST; q->ptr.tp = p；}//if}while (! StrEmpty (sub)) ;q—>ptr. tp = NULL;}//else} // elsereturn OK;
}// CreateGListStatus sever(SString &str, SString &hstr) {// 将非空串 str 分割成两部分：hsub 为第一个‘，’之前的子串，str 为之后的子串n= StrLength（str）； i=0;k=0；//k记尚未配对的左括号个数do {// 搜索最外层的第一个逗号++i;SubString（ch, str,i,1）；if（ch =='（'）  十十k；else if （ch==‘）’）  --k；} while (i<n && (ch! ='，'|| k! =0));if (i<n){SubString (hstr, str, 1, i—1)； SubString(str, str, i+1, n—i)； } else {StrCopy (hstr, str); ClearString(str) }
} // sever