数据结构基础讲解（七）——数组和广义表专项练习

本文数据结构讲解参考书目：

通过网盘分享的文件：数据结构  C语言版.pdf
链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码: ze8e

数据结构基础讲解（六）——串的专项练习-CSDN博客

个人主页：樱娆π-CSDN博客​​​​​​

大佬们！！！需要互三的d我！！！！1

目录

数组的类型定义

抽象数据类型数组可形式地定义

基本操作

 数组的顺序存储

特殊矩阵的压缩存储

1.对称矩阵

2.三角矩阵

1)上三角矩阵

2) 下三角矩阵

3.对角矩阵

广 义 表

广义表的运算

广义表的存储结构

1.头尾链表的存储结构

2.扩展线性链表的存储结构

总结

广义表的举例说明

广义表的深度

 广义表的元素访问

广义表的元素插入

 广义表的元素删除

广义表的遍历

---

 

 * 本文中提到的aij表示下标为ij                                                             

数组的类型定义

数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素，每个元素受 n(n>=1) 个线性关系的约束，每个元素在 n 个线性关系中的序号儿 i1, …，in 称为该元素的下标，可 以通过下标访问该数据元素。因为数组中每个元素处千 n(n>=1) 个关系中，故称该数组为 n 维 数组。数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据， 但属于同一数据类型.

抽象数据类型数组可形式地定义

ADT Array{

数据对象： ji=0, ···,bi-1, i=l, 2, …, n,

D = { a• 五j2"·Jn·ln(>O)称为数组的维数，坛是数组第i 维的长度，

ji 是数组元素的第j维下标，aj1j2...jn

数据关系： R = {Rl,R2, …, Rn}

基本操作：

}ADT Array

基本操作

 数组的顺序存储

由千数组一般不做插入或删除操作， 也就是说； 一旦建立了数组， 则结构中的数据元素个数 和元素之间的关系就不再发生变动。 因此， 采用顺序存储结构表示数组比较合适

假设每个数据元素占 L 个存储单元， 则二维数组 A[0.. m-1, 0 .. n-1] (即下标从 0 开始， 共有 m行n列）中任一元素 au的存储位置可由下式确定

LOC(i, j) = LOC(0, 0) + (nx i + j)L

式中， LOC(i,J)是 au的存储位置； LOC(O, 0) 是 aoo的存储位置， 即二维数组 A 的起始存储位置， 也称为基地址或基址.

注：此处没有链式存储。 

特殊矩阵的压缩存储

假若值相同的元素或者零元素在矩阵中的分布有一定规律， 则称此类矩阵为特殊矩阵。

1.对称矩阵

若 n 阶矩阵A中的元满足下述性质

 则称为n阶对称矩阵

        对于对称矩阵，可以为每一对对称元分配一个存储空间，则可将忙个元压缩存储到 n(n + 1)/2 个元的空间中， 不失一般性， 可以行序为主序存储其下三角 （包括对角线）中的元。

2.三角矩阵

以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。上三角矩阵是指矩阵下三角（不 包括对角线）中的元均为常数c或零的n阶矩阵， 下三角矩阵与之相反。 对三角矩阵进行压缩存 储时， 除了和对称矩阵一样， 只存储其上 （下）兰角中的元素之外， 再加一个存储常数c的存储 空间即可

1)上三角矩阵

sa[k]和矩阵元 aij 之间的对应关系为

2) 下三角矩阵

sa[k]和矩阵元 aij 之间的对应关系为

3.对角矩阵

对角矩阵 所有的非零元都集中在以主对角线为中心的带状区域中，即除了主对角线上 和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零.

广 义 表

广义表是线性表的推广，也称为列表,广义表一般记作:

LS = (a1 , a2, · · ·, an )

其中，LS是广义表(a1, a2, …，an )的名称，n是其长度。广义表的定义中，a; 可以是单个元素，也可以是广义表，分别称为广义表 LS 的原子和子表。

1. A = ()—A 是一个空表， 其长度为零
2. B=(e)-B 只有一个原子 e, 其长度为1
3. C= (a, (b, c, d))—C的长度为2, 两个元素分别为原子 a 和子表(b,c, d)
4. D = (A, B, C)—D 的长度为3,3个元素都是广义表。显然，将子表的值代入后，则有 D = ((), (e), (a, (b, c, d)))
5.  E = (a, E)—这是一个递归的表， 其长度为2。E 相当于一个无限的广义表 E=(a, (a, (a, ···)))

广义表的重要结论：

1. 广义表的元素可以是子表，而子表的元素还可以是子表……由此，广义表是一个多层次 的结构，可以用图形象地表示。
2. 广义表可为 其他广义表所共享。例如在上述例子中，广义表 A、 B 和 C 为 D 的子表， 则在 D 中可以不必列出子表的值，而是通过子表的名称来引用
3. 广义表可以是一个递归的表，即广义表也可以是 其本身的一个子表。例如，表 E 就是一 个递归的表

广义表的运算

取表头 GetHead(LS)： 取出的表头为非空广义表的第一个元素，它可以是一个单原子，也 可以是一个子表。

取表尾 GetTail(LS)：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是 一个广义表

注：广义表（）和（（））不同。前者为空表，长度n = 0; 后者长度n = 1, 可分解得到 其表头、 表尾均为空表（）

广义表的存储结构

由于广义表中的数据元素可以有不同的结构（或是原子，或是列表），因此难以用顺序存储结 构表示，通常采用链式存储结构。常用的链式存储结构有两种，头尾链表的存储结构和扩展线性 链表的存储结构。

1.头尾链表的存储结构

由千广义表中的数据元素可能为原子或广义表，由此需要两种结构的结点：一种是表结 点， 用以表示广义表； 一种是原子结点， 用以表示原子。从上节得知：若广义表不空， 则可 分解成表头和表尾， 因此， 一对确定的表头和表尾可唯一确定广义表。 一个表结点可由3个 域组成：标志域、 指示表头 的指针域和指示表尾的指针域。而原子结点只需两个域 ：标志域 和值域。

具体操作：

//－－－－－广义表的头尾链表存储表示 －－－－－typedef enum{ATOM, LIST } ElemTag; 
typedef struct GLNode 
｛ 
ElemTag tag; 
union
{ 
AtomType atom; 
struct{struct GLNode*hp, *tp; }ptr; 
}; 
}*GList;

1.  除空表的表头指针为空外， 对任何非空广义表， 其表头指针均指向一个表结点， 且该结点中的 hp 域指示广义表表头（或为原子结点 ， 或为表结点）， tp 域指向广义表表尾（除非表尾为 空， 则指针为空， 否则必为表结点）
2. 容易分清列表中原子和子表所在层次。 如在广义表 D 中， 原子 a 和 e 在同一层次上， 而 b 、 c 和 d 在同一层次且比 a 和 e 低一层， B 和 C 是同一层的子表
3. 最高层的表结点个数即为广义表的长度

2.扩展线性链表的存储结构

这种结构中， 无论是原子结点还是表结点均由三个域组成

总结

(1)串是内容受限的线性表，它限定了表中的元素为字符。串有两种基本存储结构：顺序存 储和链式存储，但多采用顺序存储结构。串的常用算法是模式匹配算法，主要有BF算法和KMP 算法。BF算法实现简单 ，但存在回溯，效率低，时1 、 郎 司复杂度为O(m x n)0 KMP算法对BF算法 进行改进，消除回溯，提高了效率，时间复杂度为O(m + n)。

(2)多维数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结 构的数据，但属千同一数据类型。 一个n维数组实质上是n个线性表的组合， 其每一维都 是一个线性表。数组一般采用顺序存储结构，故存储多维数组时，应先将 其确定转换为 一 维结构，有按 “行 “ 转换和按 “列 “ 转换两种。科学与工程计算中的矩阵通常用二维数组 来表示，为了节省存储空间，对于几种常见形式的特殊矩阵，比如对称矩阵、 三 角矩阵和 对角矩阵，在存储时可进行压缩存储，即为 多个值相同的元只分配一个存储空间，对零元 不分配空间。

(3)广义表是另外一种线性表的推广形式，表中的元素可以是 称为原子的单个元素，也 可以是一个子表，所以线性表可以看成广义表的特例。广义表的结构相当灵活，在某种前提 下 ，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。广义表的常用操作有取 表头和取表尾。广义表通常采用链式存储结构：头尾链表的存储结构和扩展线性链表的存储 结构。

广义表的举例说明

串和数组大家应该都很清楚，但广义表应该是比较对新手而言比较陌生，那么我将用代码加深大家的印象。

广义表是一种递归的数据结构，它可以表示线性表、树形结构甚至图结构。它允许元素是原子或其他广义表，因此可以用来表示复杂的数据结构。

广义表的深度

给定一个广义表 L = (a, (b, c), d)，请计算该广义表的深度

广义表的深度是指从根节点到最深节点的路径长度。

def depth(L):  if isinstance(L, list):  max_depth = 0  for sublist in L:  max_depth = max(max_depth, depth(sublist))  return max_depth + 1  else:  return 0  L = ['a', ['b', 'c'], 'd']  
print(f"广义表 L 的深度为：{depth(L)}")  # 输出：广义表 L 的深度为：2

 广义表的元素访问

给定一个广义表 L = (a, (b, c), d)，请访问该广义表的第 2 个元素

L = ['a', ['b', 'c'], 'd']  
print(f"广义表 L 的第 2 个元素为：{L[1]}")  # 输出：广义表 L 的第 2 个元素为：['b', 'c']

广义表的元素插入

给定一个广义表 L = (a, (b, c), d)，请在该广义表的第 2 个元素的开头插入元素 'e'

L = ['a', ['b', 'c'], 'd']  
L[1].insert(0, 'e')  
print(f"插入元素 'e' 后，广义表 L 为：{L}")  # 输出：插入元素 'e' 后，广义表 L 为：['a', ['e', 'b', 'c'], 'd']

 广义表的元素删除

给定一个广义表 L = (a, (b, c), d)，请删除该广义表的第 2 个元素的第 2 个元素

L = ['a', ['b', 'c'], 'd']  
del L[1][1]  
print(f"删除元素后，广义表 L 为：{L}")  # 输出：删除元素后，广义表 L 为：['a', ['b'], 'd']

广义表的遍历

给定一个广义表 L = (a, (b, c), d)，请遍历该广义表的所有元素

def traverse(L):  for element in L:  if isinstance(element, list):  traverse(element)  else:  print(element)  L = ['a', ['b', 'c'], 'd']  
traverse(L)  # 输出：a b c d

————由于博主还是大三的在读生，时间有限，每天会不定时更新一些学习经验和一些32的项目，如果喜欢就点点关注吧，大佬们！！！！————