当前位置：文档之家 › 数据结构第5章 串和广义表

数据结构第5章 串和广义表

  • 格式：ppt
  • 大小：824.50 KB
  • 文档页数：64

下载文档原格式

  / 64

合集下载

数据结构第五章 数组与广义表

数据结构第五章 数组与广义表
an-1,n-1
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组Sa[n(n+1)/2]作为n阶对称矩阵A的存 储结构，且约定以行序为主序存储各个元素，则在Sa[k]和矩
阵元素aij之间存在一一对应关系： （下标变换公式）
i(i+1)/2 + j 当i≥j k = j(j+1)/2 + i 当i<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]; }
分析算法FastTransposeSMatrix的时间 复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … …
//对当前行中每一个非零元
处
brow=M.data[p].j;
理
if (brow < N.nu ) t = N.rpos[brow+1];
M
else { t = N.tu+1 }
的
for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

数据结构递归与广义表

数据结构递归与广义表

第5章递归与广义表一、复习要点本章主要讨论递归过程和广义表。

一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。

因此，递归算法的设计是必须掌握的基本功。

递归算法的一般形式：void p ( 参数表) {if( 递归结束条件)可直接求解步骤；基本项else p( 较小的参数);归纳项}在设计递归算法时，可以先考虑在什么条件下可以直接求解。

如果可以直接求解，考虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设计归纳项，从而给出递归求解的算法。

必须通过多个递归过程的事例，理解递归。

但需要说明的是，递归过程在时间方面是低效的。

广义表是一种表，它的特点是允许表中套表。

因此，它不一定是线性结构。

它可以是复杂的非线性结构，甚至允许递归。

可以用多重链表定义广义表。

在讨论广义表时，特别注意递归在广义表操作实现中的应用。

本章复习的要点：1、基本知识点要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。

理解递归过程的机制与利用递归工作栈实现递归的方法。

通过迷宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。

在广义表方面，要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广义表操作的使用，广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。

2、算法设计求解汉诺塔问题，掌握分治法的解题思路。

求解迷宫问题、八皇后问题，掌握回溯法的解题思路。

对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。

计算广义表结点个数，广义表深度，广义表长度的递归算法。

输出广义表各个原子所在深度的非递归算法。

判断两个广义表相等的递归算法。

广义表的按深度方向遍历和按层次（广度）方向遍历的递归算法。

使用栈的广义表的按深度方向遍历的非递归算法。

递归的广义表的删除算法二、难点与重点1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用递归的分层(树形)表示：递归树递归深度(递归树的深度)与递归工作栈的关系单向递归与尾递归的迭代实现3、广义表：广义表定义、长度、深度、表头、表尾用图形表示广义表的存储结构广义表的递归算法，包括复制、求深度、求长度、删除等算法三、教材中习题的解析5-1 已知A[n]为整数数组，试写出实现下列运算的递归算法：(1) 求数组A中的最大整数。

数据结构第五章习题

数据结构第五章习题

数据结构第五章习题1.名词解释（1）串（2）广义表2.判断题〔以下各题，正确的请在前面的括号内打√，错误的打×〕〔〕〔1〕串中不可以包含空白字符。

〔〕〔2〕两个串相等必有串长度相同。

〔〕〔3〕两个串相等那么各位置上的字符不一定对应相同。

〔〕〔4〕串的长度不能为零。

〔〕〔5〕子串是主串中字符构成的有限序列。

〔〕〔6〕串是一种特殊的线性表。

〔〕〔7〕空格串是由一个或多个空格字符组成的串，其长度为1。

〔〕〔8〕广义表最大子表的深度为广义表的深度。

〔〕〔9〕广义表不能递归定义。

〔〕〔10〕广义表的组成元素可以是不同形式的元素。

3.填空题（1）串中字符的个数称为串的____________。

（2）不含有任何字符的串称为____________，它的长度是____________。

（3）串的___________就是把串所包含的字符序列，依次存入连续的存储单元中去。

（4）串的链式存储结构是将存储区域分成一系列大小相同的节点，每个节点有两个域：____________域和____________域。

其中____________域用于存储数据，____________域用于存储下一个节点的指针。

（5）子串的定位操作通常称为串的____________。

（6）串的两种最根本的存储方式是____________和____________。

（7）广义表((a), ((b), c), (((d))))的表头是____________，表尾是____________。

（8）广义表的表尾总是一个____________。

4.选择题（1）串是一种特殊的线性表，其特殊性表达在〔〕。

A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以任意（2）串的长度是〔〕。

A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数且大于零D．串中所含字符的个数（3）空串与空格串〔〕。

A．相同B．不相同C．可能相同D．无法确定（4）求字符串T在字符串S中首次出现的位置的操作为〔〕。

《数据结构与算法》第五章-数组和广义表学习指导材料

《数据结构与算法》第五章-数组和广义表学习指导材料

《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

《数据结构——用C语言描述(第二版)》第5章 数组和广义表

《数据结构——用C语言描述(第二版)》第5章 数组和广义表
是指矩阵的下三角（不含对角线）中的元素均为常数C或零的n阶矩阵，下 三角矩阵则与之相反，如图5.3所示。
第五章 数组和广义表
在压缩存储时，矩阵中值相同的元素C可共享一个存储空间，元素 为零则可不必分配空间，而其余的元素有 n(n+1)/2个，因此三角矩阵 可用一维数组M[n×(n+1)/2+1]来存储，其中常数C放在数组的最后一 个下标变量中。
假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以 按以下进行：由于Ｂ的行是Ａ的列，所以可按照b->data三元组表的次序在 a->data中找到相应的三元组进行转置，即可按a->data的列序转置，所得 到的转置矩阵Ｂ的三元组表b->data必定是按行优先存放的。因此，可以对 三元组表a->data从第一行起扫描，找到Ａ的每一列中所有的非零元素，就 可以实现转置。
LOC ( aij ) =LOC ( a00) +(i×n+j) × c 同理可推导出以列为主序优先存储时数据元素a i j 的存储地址，其计算公式 为：
LOC( a i j ) =LOC( a00 ) +( j × n +i ) × c 对于三维数组Am×n×p而言，若以行为主序优先存储时，则其数据元 素aijk的存储地址可为： LOC ( a i j k) =LOC ( a000) +[ i × m×p +j ×p +k] × c 对于一般的二维数组A[c1…d1，c2…d2]而言，此处c1，c2的值不一定是 0，a i j 的地址为： LOC ( a i j ) =LOC ( a c 1 c 2 ) +[ ( i – c 1 )* ( d 2 – c 2 +1) +j – c 2 ] * c

数据结构第5章

数据结构第5章

第5章：数组和广义表 1. 了解数组的定义；填空题：1、假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 。

2、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。

2. 理解数组的顺序表示方法会计算数组元素顺序存储的地址；填空题：1、已知A 的起始存储位置（基地址）为1000，若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A 57可知，是从0行0列开始！) 2、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1，c 2)+[(j-c 2)*(d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950选择题：（ A ）1、假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

（无第0行第0列元素）A ．16902B ．16904C ．14454D ．答案A, B, C 均不对 答：此题（57列×60行＋31行）×2字节＋10000=16902( B )2、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：A ．i(i-1)/2+j-1B ．i(i-1)/2+jC ．i(i+1)/2+j-1D ．i(i+1)/2+j3、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

中南大学数据结构与算法第5章数组和广义表课后作业答案

中南大学数据结构与算法第5章数组和广义表课后作业答案

第5章数组与广义表习题练习答案5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002a0010a0011a0012a0100a0101a0102a0110a0111a0112a0200a0201a0202a0210a0211a0212a1000a1001a1002a1010a1011a1012a1100a1101a1102a1110a1111a1112a1200a1201a1202a1210a1211a1212按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：a0000a1000a0100a1100a0200a1200a0010a1010a0110a1110a0210a1210a0001a1001a0101a1101a0201a1201a0011a1011a0111a1111a0211a1211a0002a1002a0102a1102a0202a1202a0012a1012a0112a1112a0212a02125.2 给出C语言的三维数组地址计算公式。

解：因为C语言的数组下标下界是0，所以Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d其中Amnp表示三维数组。

Loc(A000)表示数组起始位置。

i、j、k表示当前元素的下标,d表示每个元素所占单元数。

5.3设有三对角矩阵A n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a ij,求：(1)用i , j 表示k的下标变换公式。

(2)用k 表示i,j 的下标变换公式。

《数据结构(Python语言描述)》第5章 广义表

《数据结构(Python语言描述)》第5章 广义表
数据结构 (Python3
广义表是由n个类型相同的数据元素(a1、a2、……、an)组成的有限序列。广义表的元素可以是单个 元素，也可以是一个广义表。通常广义表记作：
GL=(a1,a2,…,an) 广义表有两种数据元素，分别是原子和子表，因此需要两种结构的节点，一种是表节点，用来表 示子表，如图5-1所示；一种是原子节点，用来表示原子，如图5-2所示。
OPTION
在广义表GL中，如果ai也是一个 广义表表，则称ai为广义表GL的 子表。
03 表头
OPTION
在广义表中GL中，a1如果不为空， 则称a1为广义表的表头。
04 表尾
OPTION
在广义表GL中，除了表头a1的其余 元素组成的表称为表尾。
05 深度
OPTION
广义表GL中括号嵌套的最大层数。
图5-3 广义表表节点
表节点由三个域组成：标志域tag，指向表头节点的指针域ph，指向表尾节 点的指针域pt。表节点的标志域tag=1。
5.3 存储结构
7
图5-4 广义表原子节点
原子节点由两个域组成：标志域tag，值域atom。原子节点的标志域tag=0。
节点的定义：
class Node:
def __init__(self, ph, pt, tag, atom):
表节点由三个域组成，即标志域tag、指向表头节点的指针域ph、指向表尾节点的指针域pt。表节点 的标志域tag=1。
原子节点由两个域组成，即标志域tag、值域atom。原子节点的标志域tag=0。
5.2 基本用语
4
01 原子
OPTION
在广义表GL中，如果ai为单个元 素，则称ai称为原子
02 子表

数据结构第五章

数据结构第五章

5.3.1 特殊矩阵
是指非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 0≦i,j≦n-1 则称A为对称矩阵。
对称矩阵中的元素关于主对角线对称，故只 要存储矩阵中上三角或下三角中的元素，这样， 能节约近一半的存储空间。

2013-7-25 第4章 18
5.3 矩阵的压缩存储

在科学与工程计算问题中，矩阵是一种常用 的数学对象，在高级语言编制程序时，常将 一个矩阵描述为一个二维数组。 当矩阵中的非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下，会占用许 多单元去存储重复的非零元素或零元素，这 对高阶矩阵会造成极大的浪费。 为了节省存储空间，我们可以对这类矩阵进 行压缩存储：
5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的， 因此用一维内存来表示多维数组，就必 须按某种次序将数组元素排成一列序列 ，然后将这个线性序列存放在存储器中 。 又由于对数组一般不做插入和删除 操作，也就是说，数组一旦建立，结构 中的元素个数和元素间的关系就不再发 生变化。因此，一般都是采用顺序存储 的方法来表示数组。
即为多个相同的非零元素只分配一个存储空间； 对零元素不分配空间。


课堂讨论： 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的 存储空间，且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵， 稀疏矩阵等。 4. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%）
通常有两种顺序存储方式：
⑴行优先顺序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1 个列向量紧接在第j个列向量之后，A的m*n个元素按 列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。

数据结构习题及答案与实验指导(数组和广义表)5

数据结构习题及答案与实验指导(数组和广义表)5

第5章数组和广义表本章所讨论的多维数组和广义表是对线性表的推广，其特点是数据元素仍可被视为一个表。

要求熟悉多维数组的逻辑结构、存储结构，广义表的逻辑结构、表示形式，以及矩阵的压缩存储的有关内容。

重点提示：●多维数组的存储方式和存取特点●特殊矩阵的存储●稀疏矩阵的存储●广义表的表示形式5-1 重点难点指导5-1-1 相关术语1．特殊矩阵要点：矩阵中非零元素或零元素的分布有一定规律的矩阵。

2．对称矩阵要点：一种特殊矩阵；n阶方阵的元素满足性质：a ij=a ji（0≤i，j≤n-1）。

3．三角矩阵要点：以主对角线划分，有上三角矩阵和下三角矩阵两种；主对角线以下，不包括主对角线中的元素，均为常数c，称为上三角矩阵；主对角线以上，不包括主对角线中的元素，均为常数c，称为下三角矩阵。

4．对角矩阵要点：非零元素集中在以主对角线为中心的带状区域中，也称带状矩阵。

5．稀疏矩阵要点：矩阵中非零元素的个数远小于矩阵元素总数的矩阵。

6．三元组表要点：是稀疏矩阵的一种存储结构；将稀疏矩阵的非零元素的三元组（行、列和值）按行优先的顺序排列；得到结点均是三元组的线性表。

7．广义表要点：是线性表的推广；是n个元素a1,a2,…,a n的有限序列；其中a i或者是原子或者是广义表；通常记为LS=(a1,a2,…,a n)，LS为广义表的名字。

5-1-2 多维数组1．对n维数组逻辑结构的理解n维数组可视为由n-1维数组为元素的线性结构。

举例：一个m行n列的二维数组可视为由m个一维数组为元素组成的线性结构，其中每个一维数组又由n 个单元素组成。

]a ,,a ,[a A A A A a a a a a a a a a Amn in i2i1i m 21mnv m2m12n 22211n 1211 =⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=其中2．数组的顺序存储方式（1）行优先顺序——将数组元素按行向量排列，即第i ＋1行紧接在第i 行后面。

数据结构第五章数组和广义表

数据结构第五章数组和广义表

数据结构第五章数组和广义表(总6页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。

A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。

供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。

A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。

A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。

数据结构第五章数组和广义表

数据结构第五章数组和广义表

第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。

A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。

供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。

A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。

A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。

A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。

大学数据结构课件--第5章 数组和广义表

大学数据结构课件--第5章 数组和广义表

a 32 a 33 a 34 0 0
a 43 a 44 a 45 0
a 54 a 55 a 56 a 65 a 66
5.3.2 稀疏矩阵
稀疏矩阵的存储：如何表示非零元素的位置信息 1. 三元组表：每个元素用一个三元组（i，j，v）来表示。 i j v
0 1 6 1 1 6 2 3 8 12 9
2
3 4 5 6 7 8
2
5.2 数组的顺序表示和实现
a00 a00 a10 a01 存储单元是一维结构，而数组是个多维结构 , …… …… 则用一组连续存储单元存放数组的数据元素就有 am-1,0 a0,n-1 个次序约定问题。 a01 a10
a11
……
a11
……
二维数组可有两种存储方式： am-1,1 a1,n-1
……
K=
i*n-i(i-1)/2+j-i n(n+1)/2
当 i≤j 当i>j
0 a11 ... a1n-1 ... ... ... ... 0 0 0 an-1n-1
当i ≤ j时,a[i][j]是非零元素, a[i][j]前面有i行,共有n+(n-1)+(n-2)+…(n-(i-1))
=i(n+[n-(i-1)])/2=i*n-i(i-1)/2个元素，a[i][j]前面有j列，共j-i个非零元素，
A m× n
( a10 a11 … a1,n-1 )
=
注：
( … … …… ) ( am-1,0 am-1,2 … am-1,n-1 ) ( ( ( (
① 数组中的元素都具有统一的类型; ② 数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变； ③ 数组的基本操作简单：初始化、销毁、存取元素和修改元素值

数据结构课后习题答案第五章数组与广义表

数据结构课后习题答案第五章数组与广义表

第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000。

计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。

试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。

答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。

（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

数据结构第五章 数组和广义表

数据结构第五章 数组和广义表

5.3.1
特殊矩阵
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 1≤i,j≤n 则称A为对称矩阵。 a11 1 5 1 3 7 a21 a 22 5 0 8 0 0 a31 a32 a33 1 8 9 2 6 ……………….. 3 0 2 5 1 an 1 a n 2 a n 3 …a n n 7 0 6 1 3
第5章
数组和广义表
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.1 数组的定义
数组-----线性表的扩展 A =(a0,a1,a2,…，an-1)
a00 a10 ┇ Am×n= ai0 ┇ am-1,0 a01 … a0j … a11 … a1j … ┇ ai2 … aij … ┇ am-1,2 … am-1,j … a0,n-1 a1,n-1 ai,n-1 am-1,n-1 α0 α1 ┇ Am×n= α i ┇ α m-1
Assign( &A, e, index1, ..., indexn) 赋值操作 初始条件：A是n维数组,e为元素变量,随后是n个下标值。 操作结果：若下标不超界,则将e的值赋给所指定的A的元 素,并返回OK。 对于数组来说一旦维数确定了，每个元素的下标确定了, 那么整个数组就确定了，这样的一个数组结构除了能改变 某元素的值，其他的不能再改变。
5.2 数组的顺序表示和实现
数组类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。 有两种顺序映象的方式。
有两种顺序映像方法： 1）以行序为主序(行优先，先行后列)：先存储行号较小 的元素，行号相同者先存储列号较小的元素；

数据结构讲义第5章-数组和广义表

数据结构讲义第5章-数组和广义表
对于一个矩阵结构,显然用一个二维数组来表示是非常 恰当的.但有时会遇到这样一类矩阵:在这种矩阵中有 许多值相同的元素或者是零元素,为了节省存储空间, 可以对这类矩阵进行压缩存储. 压缩存储是:为多个值相同的元素只分配一个存储空间: 对零元素不分配存储空间. 特殊矩阵:值相同的元素或者零元素在矩阵中的分布有 一定规律,则称此类矩阵为特殊矩阵,反之,称为稀疏 矩阵.
5.4 广义表
5)若广义表不空,则可分成表头和表尾,反之,一对表头和表尾 可唯一确定广义表 对非空广义表:称第一个元素为L的表头,其余元素组成的表称 为LS的表尾; B = (a,(b,c,d)) 表头:a 表尾 ((b,c,d)) 即 HEAD(B)=a, C = (e) D = (A,B,C,f ) 表头:e 表尾 ( ) TAIL(B)=((b,c,d)),
5.4 广义表
4)下面是一些广义表的例子; A = ( ) 空表,表长为0; B = (a,(b,c,d)) B的表长为2,两个元素分别为 a 和子表(b,c,d); C = (e) C中只有一个元素e,表长为1; D = (A,B,C,f ) D 的表长为4,它的前三个元素 A B C 广义表, 4 A,B,C , 第四个是单元素; E=( a ,E ) 递归表.
以二维数组为例:二维数组中的每个元素都受两个线性关 系的约束即行关系和列关系,在每个关系中,每个元素aij 都有且仅有一个直接前趋,都有且仅有一个直接后继. 在行关系中 aij直接前趋是 aij直接后继是 在列关系中 aij直接前趋是 aij直接后继是
a00 a01 a10 a11
a0 n-1 a1 n-1
a11 a21 ┇ a12 a22 ┇ ai2 ┇ … amj … amn … aij … ain … … a1j a2j … … a1n a2n β1 β2 ┇ βi ┇ βm
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

5.1 串的定义和基本运算
• （4）串的连接StrCat(S,T)。 • 初始条件：串S和T存在。 • 操作结果：将串T的值连接在串S的后面。 • （5）求子串SubString(Sub,S,pos,len)。 • 初始条件：串S存在，1≤pos≤StrLength(S)且
1≤len≤StrLength(S)-pos+1。 • 操作结果：用Sub返回串S的第pos个字符起长度为len的
1≤len≤StrLength(S)-pos+1。 • 操作结果：从串S中删除第pos个字符起长度为len的子串。 • （9）串的替换StrReplace(S,T,V)。 • 初始条件：串S，T和V存在，且T是非空串。 • 操作结果：用V替换串S中出现的所有与T相等的不重叠子
串。 • （10）判断串空StrEmpty(S)。 • 初始条件：串S存在。 • 操作结果：若串S为空串，则返回1；否则返回0。
• （1）非紧凑存储。设串S="Hello boy"，计算机字长为32 位（4个Byte），用非紧凑格式一个地址只能存一个字符， 如图5-2所示。其优点是运算处理简单，但缺点是存储空 间十分浪费。
• （2）紧凑存储。同样存储S="Hello boy"，用紧凑格式一 个地址能存四个字符，如图5-3所示。紧凑存储的优点是 空间利用率高，缺点是对串中字符处理的效率低。
•}
5.3 串的基本运算的实现
• （3）求子串操作。求串S从第pos位置开始，长度为len的 子串，并将其存入到串Sub中。操作成功返回1，不成功 返回0。其算法描述如下：
• int SubString(String *S,String *Sub,int pos,int len)
• { /*求子串函数*/
• （1）求串的长度操作。求得一个字符串S的长度值并返回 该值。其算法描述如下：
• int StrLength(String *S) • { /*求串长度函数*/ • int i=0; • while(S->ch[i]!='\0') • i++; • S->Len=i; • return(S->Len); •}
5.2 串的存储结构
• 2．索引存储的例子
• 设字符串：S1="boy"
•
S2="girl"
•
S3="man"
•
S4="woman"
• 用指针free指向堆中未使用空间的首地址。
• 索引表如图5-5所示。
• 考虑到对字符串的插入和删除操作，可能引起串的长度变 化，在“堆”中为串值分配空间时，可预留适当的空间。
图5-4 带头结点的非空单链表
5.2 串的存储结构
• 2．串的存储密度 • 在各种串的处理系统中，所处理的串往往很长或很多。例
如一本书的几百万个字符，情报资料的几千万个条目，这 就必须考虑字符串的存储密度。
存储密度 = 串值所占的存储位 / 实际分配的存储位
• 串链接存储的存储密度小，存储量比较浪费，但运算处理， 特别是对串的连接等操作的实现比较方便。
图5-1 串S的顺序存放示意图
5.2 串的存储结构
• 2．存储方式
• 当计算机按字节（Byte）为单位编址时，一个存储单元刚 好存放一个字符，串中相邻的字符顺序地存储在地址相邻 的存储单元中。
• 当计算机按字（例如1个字为32位）为单位编址时，一个 存储单元可以由4个字节组成。此时顺序存储结构又有非 紧凑格式和紧凑格式两种存储方式。
• （3）子串。串中任意个连续的字符组成的子序列称为该 串的子串。另外，空串是任意串的子串，任意串是自身的 子串。
• （4）主串。包含子串的串称为该子串的主串。 • （5）模式匹配。子串的定位运算又称为串的模式匹配，
是一种求子串在主串中第一次出现的第一个字符的位置。 • （6）两个串相等。两个串的长度相等且各个位置上对应
的字符也都相同。
5.1 串的定义和基本运算
• 【例5-1】 有以下4个串： • S1="Welcome to Beijing!" • S2= "Welcome to" • S3= "Welcometo " • S4="Beijing" • 则各串长度及其之间的关系如何？ • 解： • （1）S1的长度为19，S2的长度为10，S3的长度为10，
5.3 串的基本运算的实现
• （2）串的建立操作。从键盘读入一个字符串并赋给S，并 调用求字符id CreatStr(String *S)
• { /*建立一个新串函数*/
•
gets(S->ch);
•
S->Len=StrLength(S); /*调用求串长度子函数*/
• { char name[MAXLEN];
/*串名*/
• int length;
/*串长*/
• char *start;
/*起始地址*/
• }LNode;
• 4．“堆”的管理
• C语言中用动态分配函数malloc和free来管理“堆”。 利 用函数malloc为每个新串分配一块实际串长所需要的存储 空间，分配成功则返回一个指向起始地址的指针，作为串 的基址，同时，约定的串长也作为存储结构的一部分。函 数free则用来释放用malloc分配的存储空间。
5.1 串的定义和基本运算
• （11）串的比较StrCompare(S,T)。 • 初始条件：串S和T存在。 • 操作结果：若S>T，则返回值>0；若S=T，则返回值等于
0；若S<T，则返回值<0。 • （12）串的清空StrClear(S)。 • 初始条件：串S存在。 • 操作结果：将S清为空串。 • （13）输出串DispStr(S)。 • 初始条件：串S存在。 • 操作结果：显示串S的所有字符。
5.2 串的存储结构
• 5.2.1 定长顺序串存储
• 1．顺序存储的类型定义
• 顺序串的类型定义与顺序表的定义相似，可以用一个字符 型数组和一个整型变量表示，其中字符数组存储串，整型 变量表示串的长度。具体C语言定义格式见5.3节。
• 如串S="Beijing"，字符串从S.ch[0]单元开始存放，用'\0' 来表示串的结束，则串S的存储示意图如图5-1所示。
该存储空间称为“堆”（也称为自由存储区）。 • （2）另外建立一个索引表，用来存储串的名字（name）、
长度（length）和该串在“堆”中存储的起始地址 （start）。 • （3）程序执行过程中，每产生一个串，系统就从“堆” 中分配一块大小与串的长度相同的连续空间，用于存储该 串的值，并且在索引表中增加一个索引项，用于登记该串 的名字、长度、和该串的起始地址。
界符，引号括起来的字符序列为串值，ai（1≤i≤n） 可以是字母、数字或其他字符，n为串的长度。
5.1 串的定义和基本运算
• 2．串的相关术语
• （1）空串。不含任何字符的串称为空串，即串的长度n=0 时的串为空串。
• （2）空格串。由一个或多个称为空格的特殊字符组成的 串称为空格串，它的长度是串中空格字符的个数。
• 5.1.2 串的基本操作
• 串的基本操作有很多，下面介绍部分基本运算。 • （1）串的赋值StrAsign(S,chars)。 • 初始条件：chars是字符串常量。 • 操作结果：生成一个值等于chars的串S。 • （2）串的复制StrCopy(S,T)。 • 初始条件：串S存在。 • 操作结果：由串T复制得串S。 • （3）求串长度StrLength(S)。 • 初始条件：串S存在。 • 操作结果：返回串S的长度，即串S中的元素个数。
• 由于字符串的特殊性，用链表作为字符串的存储方式也不 太实用，因此使用较少。
5.2 串的存储结构
• 5.2.3 串的堆分配存储结构
• 在实际应用中，往往要定义很多字符串，并且各字符串长 度在定义之前又无法确定。在这种情况下，可以采用堆分 配存储（也称为索引存储），这是一种动态存储结构。
• 1．堆分配存储的方法 • （1）开辟一块地址连续的存储空间，用于存储各串的值，
5.1 串的定义和基本运算
• 3．串的应用
• 在汇编语言和高级语言的编译程序中，源程序和目标程序 都是以字符串表示的。在事务处理程序中，如客户的姓名、 地址、邮政编码、货物名称等，一般也是作为字符串数据 处理的。另外，信息检索系统、文字编辑系统、语言翻译 系统等，也都是以字符串数据作为处理对象的。
5.3 串的基本运算的实现
• 本节主要讨论定长顺序存储的各种算法的实现。定长顺序 串的结构定义如下：
• #define MAXSIZE 100 /*顺序串存储空间的总分配量 */
• typedef struct
•{
• char ch[MAXSIZE]; /*存储串的字符数组*/
• int Len;
• 对照串的定义和线性表的定义可知，串是一种其数据元素 固定为字符的线性表。但是，串的基本操作对象和线性表 的操作对象却有很大的不同。线性表上的操作是针对其某 个元素进行的，而串上的操作主要是针对串的整体或串的 一部分子串进行的。这也是数据结构中把串单独作为一章 的原因。
5.1 串的定义和基本运算
5.2 串的存储结构
5.2 串的存储结构
• 5.2.2 链式存储
• 1．链接存储的描述
• 用链表存储字符串，每个结点有两个域：一个数据域（data）和一个 指针域（next）。在串的链式存储结构中，有如下结构：
• 数据域（data）—— 存放串中的字符； • 指针域（next）—— 存放后继结点的地址。 • 仍然以存储S="Hello boy"为例，链接存储结构如图5-4所示。 • （1）链接存储的优点——插入、删除运算方便； • （2）链接存储的缺点——存储、检索效率较低。