当前位置：首页 > java >正文

数据结构（五）——串、数组、广义表

java 2025/5/13 7:53:18

一、串的定义与实现

1.串的定义和特点

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

串是内容受限的线性表,它限定了表中的元素为字符
串长:串中字符个数(n20):n=0 时称为空串
空白串:由一个或多个空格符组成的串
子串:串S中任意个连续的字符序列叫S的子串，S叫主串

当两个串的长度相等，并且各个对应位置的字符都相等时，才称这两个串相等

2.串的抽象类型定义

3.串的存储结构：定长顺序存储、堆分配存储、块链存储

（1）定长顺序存储：按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，通常用定长字符数组来实现

①显式存储串长

a.以下标为0的数组分量来存放串的实际长度

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

b.专设一个字段来表示串长

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

②隐式存储串长：在串值后面加一个不计入串长的结束标记字符，如C语言中的"\0"。此时串长为隐含值，不便于实现涉及串长的操作

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

typedef struct{char *data;  //若是非空串，则按串实际长度分配存储区，否则data为NULLint length;  //串长度
}HString;

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

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

二、数组的定义与实现

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

1.一维数组
一维数组可看成是一个线性表或一个向量，存储在一块连续的存储单元中，适合于随机查找。一维数组记为A[n]或A=(a0，a1，….ai，…，an-1)，一维数组中ai的存储地址LOC(ai)可由下式求出:

LOC(ai)=LOC(a0)+i*L (0≤i<n)

2.二维数组

二维数组，又称矩阵。每个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。例如，设A是一个有m行n列的二维数组，A可以看成由m个行向量组成的向量，也可以看成由n个列向量组成的向量。

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

三、广义表的定义与实现

广义表是线性表的推广，也称为列表。

广义表是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对括号。

、

eg: 广义表(a,(a,b),d,e,((i,j),k)) 的长度是（）？深度是（）？

答案：5；3

四、习题

答案：B

解释：串是内容受限的线性表，表中元素只能存字符，这是特殊性的体现

答案：B

解释：以行序为主(横着一个一个存)，则 LOC[5,5] = [(5-1)*100 + (5-1)] *2 + 10 = 818

答案：B

解释：以列序为主(竖着一个一个存)，则 LOC[5,8] = [(8-1) * 8 + (5-1)] * 3 + BA = BA + 180

答案：B

解释：A[8,5] : (8-0) * 10 + (5 - 1) = 84 （按行先存储）

A[8,5] : (5-1) * 9 + (8-0) = 44 （按列先存储）

A[3,10] : (10 - 1) * 9 + (3 - 0 ) = 84 （按列先存储）

A[5,8] : (8-1) * 9 + (5-0) = 68 （按列先存储）

A[0,9] : (9-1) * 9 + (0-0) = 72 （按列先存储）