数据结构-数组（稀疏矩阵转置）和广义表
目录
- 1、数组
- 定义
- 1）数组存储地址计算
- 示例
- ①行优先
- ②列优先
- 2）稀疏矩阵的转置
- 三元组顺序表
- 结构定义
- ①普通矩阵转置
- ②三元组顺序表转置稀疏矩阵
- ③稀疏矩阵的快速转置
- 3）十字链表
- 结构定义
- 2、广义表
- 定义
- 1）基本操作
- ①GetHead
- ②GetTail
- 2）构造存储结构的两种方法
- 表头表尾
- 结构定义
- 3）递归算法
- ①求广义表深度
- ②复制广义表
- ③创建广义表
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的转置矩阵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
③稀疏矩阵的快速转置
如果能预先确定就诊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的转置矩阵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中每一列含非零元个数
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
}//if
return 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；// 空表深度1
if (L—> tag == ATOM) return 0;// 原子深度 0
for (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.hp
CopyGList(T—> ptr. tp, L->ptr. tp);// 复制广义表L-＞ptr.tp 的一个副本T->ptr.tp
} // else
} // else
return OK;
}// CopyGList
③创建广义表
三种情况：
- 带括弧的空白串
- 长度为1的单字符串
- 长度>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中分离出表头串hsub
CreateGList（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
} // else
return OK;
}// CreateGList
Status 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