第四章 串
教学目的与要求
本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。
重点和难点
本章重点是掌握串上实现的模式匹配算法，其也是本章难点。
教学内容
第一节 串的基本概念
４.1.1 基本概念
串：是零个或多个字符组成的有限序列。串中所包含的字符个数称为串的长度。
空串：长度为0的串称为空串，它不包含任何字符。
空白串：仅由一个或多个空格组成的串称为空白串。应注意空串和空白串的区别。
子串、主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身的子串。
子串在主串中的位置：通常，将子串在主串中首次出现时子串首字符对应的主串中的序号定义为子串在主串中的位置。
２．串的基本运算
（１）求串的长度（Length）
（２）串复制 (Copy)：
（３）串联接 (Concat) （４）串比较 (Compare)
（５）字符定位(Index)
除上述基本运算外，串运算还有求子串、子串的定位、子串的置换等操作。这些操作，一般可由这些基本操作实现。
第二节 串的存储结构
4.2.1串的顺序存储
1.静态存储分配的顺序串
顺序串最简单的描述形式是直接使用定长的字符数组来定义。其定义形式为
# define maxstrsize 256
typedef char Seqstring[maxstrsise];
利用类型描述符Seqstrsring可定义数组变量存储串，利用特定字符表示串的结束(Ｃ语言用转义字符’\0’) 。例如Seqstrstring s;
变量s可存储长度不超过255个字符的字符串，以’\0’作为串的结束。
顺序串的类型定义也可以象线性表的顺序存储一样，在定义字符数组的基础上，引入描述长度的成员。其定义形式为
# define maxstrsize 256
typedef struct {
char ch[maxstrsise];
第 4 章 广义线性表——多维数组和广义表
2005-07-14
第 4 章 广义线性表——多维数组和广义表
课后习题讲解
1. 填空
⑴ 数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。
【解答】存取，修改，顺序存储
【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。
⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（ ）。
【解答】1140
【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（ ）。
【解答】d+41
【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。
⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（ ）和（ ）。
【解答】三元组顺序表，十字链表
⑸ 广义表((a), (((b),c)),(d))的长度是（ ），深度是（ ），表头是（ ），表尾是（ ）。
【解答】3，4，(a)，((((b),c)),(d))
⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（ ）。
【解答】Head(Head(Tail(LS)))
2. 选择题
⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（ ）个字节，A的第8列和第5行共占（ ）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。
第四章习题 （P111-113）
一、 复习题
1、试述数据和数据结构的概念及其区别。
数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93）
2、列出算法的五个重要特征并对其进行说明。
算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95）
3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。
时间复杂度 空间复杂度（P97-98）
4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？
线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。 （P99-105）
5、简述树与二叉树的区别；简述树与图的区别。
树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104）
6、请举出遍历算法在实际中使用的例子。
第四章习题（P111-113）
一、 复习题
1、试述数据和数据结构的概念及其区别。
数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93）
2、列出算法的五个重要特征并对其进行说明。
算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95）
3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。
时间复杂度空间复杂度（P97-98）
4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？
线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105）
5、简述树与二叉树的区别；简述树与图的区别。
树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104）
6、请举出遍历算法在实际中使用的例子。
