串、数组、广义表

串的定义与实现

串的定义和特点

串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。

串是内容受限的线性表,它限定了表中的元素为字符
串长:串中字符个数(n20):n=0 时称为空串
空白串:由一个或多个空格符组成的串
子串:串S中任意个连续的字符序列叫S的子串;S叫主串
当两个串的长度相等，并且各个对应位置的字符都相等时，才称这两个串相等

串的存储结构

1.定长顺序存储:按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，通常用定长字符数
组来实现。
a. 显式存储串长
(1)以下标为0的数组分量来存放串的实际长度,

#define MAXSTRLEN 255 //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度

(2)专设一个字段来表示串长

#define MAXSTRLEN 1000 //最大串长
typedef struct
{char data[MAXSTRLEN]; //存放串字符
int length; //存放串的实际长度
}SqString; //顺序串类型

b. 隐式存储串长

(1)在串的最后一个字符后面添加一个结束符’\0’，表示串的结束。
(2)在串的最后一个字符后面添加一个长度字段，表示串的实际长度。

2.堆分配存储:仍以一组地址连续的存储单元存放串值，但存储空间是在程序执行过程中动态分配而得。

3.串的块链存储:串采用链式存储结构存储时称为链串。链串中的一个结点可以存储多个字符。通常将链串
中每个结点所存储的字符个数称为结点大小。

#define CHUNKSIZE 80 //可由用户定义的结点大小
typedef struct Chunk{
char data[CHUNKSIZE]; //存放字符
struct Chunk *next; //指针域
}Chunk; //链串结点类型
typedef struct {
Chunk *head,*tail; //串的头和尾指针
int length; //串的当前长度
}LString;

数组的定义与实现

数组是线性表的推广，特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。

一个二维数组可以看作是每个数据元素类型相都同的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。

广义表的定义与实现

广义表是线性表的推广，也称为列表。
广义表是n(n>=0)个元素的一个序列，表中的元素可以是称为原子的单个元素，也可以是一个子表
若n=0时则称为空表。设ai为广义表的第i个元素，则广义表的一般表示与线性表相同

LS =(a1,a2,…ai,.,an);

其中n表示广义表的长度，n>=0。ai可以是单个元素，也可以是广义表。

如果ai是单个数据元素，则ai是广义表LS的原子;如果ai是一个广义表，则ai是广义表LS的子表.
习惯上，用大写字母表示广义表的名称，用小写字母表示原子。

概念

广义表的**长度(广度)**指:广义表中所包含的数据元素的个数
例如，在广义表(a,(b,c,d))中，它包含一个原子和一个子表，因此该广义表的长度为 2。
再比如，广义表((a,b,c))中只有一个子表(a,b,c)，因此它的长度为 1。

广义表的深度，可以通过观察该表中所包含括号的层数间接得到。这里需要注意，数左括号(或右括号)时，同一层次的多个括号只计算一次。
比如:广义表***((1,2),(3,(4,5)))***中，此广义表中包含 3 层括号，因此深度为 3。
广义表深度=匹配最多括号的元素所匹配的括号对数，如上例子中的4和5都匹配了3对括号。

广义表的运算

由于广义表的结构比较复杂，其各种运算的实现也不如线性表简单,其中，最重要的两个运算如下：
(1)取表头 GetHead(LS):取出的表头为非空广义表的第一个元素，它可以是一个单原子，也可以是一个子表。
(2)取表尾 GetTail(LS):取出的表尾为除共表头之外，由其余元素构成的表。即表尾一定是一个广义表。

总结

1.串是内容受限的线性表，它限定了表中的元素为字符。
2.多维数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。
3.广义表是另一种线性表的推广形式，表中的元素可以是称为原子的单个元素，也可以是一个子表，所以线性表可以看成广义表的特例。

注意

对称矩阵压缩存储默认下三角