- 6.数组和广义表
- 6.1 数组
- 6.1.1数组的顺序实现
- 6.1.1.1 例题
- 6.2 特殊矩阵
- 6.2.1 稀疏矩阵
- 6.2.1.1 特殊矩阵
- 6.2.1.2 随机稀疏矩阵
- 6.2.2 稀疏矩阵的转置
- 6.2.2.1 常规算法
- 6.2.2.2 三元组顺序表
- 6.3 广义表
- 6.3.1 例题
- 6.3.2 广义表的实现
- 6.3.2.1 头尾链表存储表示
- 6.3.2.2 子表分析法
- 6.3.2.3 例题
- 6.3.3 广义表的递归操作
介绍数组的抽象数据类型
ADT Array{
数据对象：
D={aj1,j2...ji|ji=0,....bi-1,i=1,2,....n,n(>0)是数组的维数，bi是数组第i维的长度}
数据关系：
R={R1,R2,....,RN}
RI={
6.1.1数组的顺序实现
两种顺序映像方式：
-
以行序为主序（低下标优先）
二维数组A中任一元素ai,j 的存储位置
LOC(i,j) = LOC(0,0) + (b2×i＋j)×L
-
以列序为主序（高下标优先）
推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系。
LOC(j1, j2, …, jn ) = LOC(0,0,…,0) + ∑ ci ji
其中 cn = L，ci-1 = bi ×ci , 1 < i <= n
称为 n 维数组的映象函数, 数组元素的存储位置是其下标的线性函数。
6.1.1.1 例题
- 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( B )。
A．BA+141 B．BA+180
C．BA+222 D．BA+225 - 设有二维数组A[0…9,0…19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为（232）。
- 假设以行序为主序存储二维数组A=array[1…100，1…100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。
A. 808 B. 818 C. 1010 D. 1020
6.2 特殊矩阵
6.2.1 稀疏矩阵
假设 m 行 n 列的矩阵含 t 个非零元素，则称
σ=t/(m*n)
为稀疏因子，通常认为 σ<= 0.05 的矩阵为稀疏矩阵。
以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:
- 零值元素占了很大空间;
- 计算中进行了很多和零值的运算，遇除法还需判别除数是否为零。
6.2.1.1 特殊矩阵
三角矩阵
对称矩阵
对角矩阵
6.2.1.2 随机稀疏矩阵
非零元在矩阵中随机出现。
6.2.2 稀疏矩阵的转置
6.2.2.1 常规算法
//用常规的二维数组表示时的算法
for (col=1; col<=nu; ++col)
for (row=1; row<=mu; ++row)
T[col][row] = M[row][col];
//其时间复杂度为: O(mu×nu)
6.2.2.2 三元组顺序表
#define MAXSIZE 12500
typedef struct {
int i, j; //该非零元的行下标和列下标
ElemType e; // 该非零元的值
} Triple; // 三元组类型
typedef union {
Triple data[MAXSIZE + 1];
int mu, nu, tu;
} TSMatrix; // 稀疏矩阵类型
//快速转置算法
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &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];
cpot[1] = 1;
for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1];
for (p=1; p<=M.tu; ++p) {转置矩阵元素}
} // if
return OK;
} // FastTransposeSMatrix
// O(M.nu+M.tu)
6.3 广义表
广义表是递归定义的线性结构，
LS = ( a1, a2,…, an )
其中：i 或为原子 或为广义表。
例如: A = ( )
F = (d, (e))
D = ((a,(b,c)), F)
C = (A, D, F)
B = (a, B) = (a, (a, (a, … , ) ) )
//广义表的抽象数据类型
ADT Glist {
数据对象：D＝{ei | i=1,2,..,n; n≥0;
ei∈AtomSet 或 ei∈GList,
AtomSet为某个数据对象 }
数据关系：
LR＝{| ei-1 ,ei∈D, 2≤i≤n}
基本操作：
//结构的创建和销毁
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());
} ADT Glist
6.3.1 例题
- 广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。
A. a B.（） C.（a,b,c,d） D.（b,c,d） - 下面说法不正确的是( A )。
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 - 当广义表中的每个元素都是原子时，广义表便成了_______。线性表
- 广义表的表尾是指除第一个元素之外，_______。其余元素组成的表
- 设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
6.3.2 广义表的实现
介绍广义表的头尾链表存储表示以及子表分析法存储表示。
6.3.2.1 头尾链表存储表示
6.3.2.2 子表分析法
6.3.2.3 例题
- 广义表A=((a) , ((b,c),d))，画出头尾链表存储结构，求其长度和深度。
长度2，深度3。
- 已知广义表 LS=((a,b), (c,d,e,f), g)， head 和 tail 分别是求表头和表尾，则tail( tail( head( tail(LS)))) 的运算结果是_____。(e , f）
- 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。(x,y,z)
6.3.3 广义表的递归操作
内容：介绍广义表的递归操作
- 递归函数
一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：
1)在每一次调用自己时，必须是(在某种意义上)更接近于解;
2)必须有一个终止处理或计算的准则。
- 用分治法设计递归函数
对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成k (1
- 对广义表进行分解
广义表从结构上可以分解成
广义表 = 表头 + 表尾
或者
广义表 = 子表1 + 子表2 + ··· + 子表n
因此常利用分治法求解之。
算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。
- 求广义表的深度
将广义表分解成 n 个子表，分别(递归)求得每个子表的深度，
广义表的深度=Max {子表的深度} +1
可以直接求解的两种简单情况为：
空表的深度 = 1
原子的深度 = 0
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0:原子, LIST==1:子表
typedef struct GLNode {
ElemTag tag; // 标志域
union{
AtomType atom; // 原子结点的数据域
struct {struct GLNode *hp, *tp;} ptr;
};
} *GList
int GlistDepth(Glist L) {
// 返回指针L所指的广义表的深度
if (!L) return 1;
if (L->tag == ATOM) return 0;
for (max=0, pp=L; pp; pp=pp->ptr.tp){
dep = GlistDepth(pp->ptr.hp);
if (dep > max) max = dep;
}
return max + 1;
} // GlistDepth
