Page 75 - 高中 信息技术 选择性必修1 数据与数据结构

 3.2 用字符串存储数据

（1）串的顺序存储结构。
串的顺序存储结构与一维数组的类似，用一组地址连续的存储单元存储串值的字符
序列，如图3-6所示。字符串的字符依次存放在这些存储单元中。因此，串可以用数组

表示。

串s 2 0 1 8 0 1 0 5

位置 0 1 2 3 4 5 6 7

图3-6 串的顺序存储结构

广东教育出版社
字符串的顺序存储结构，使得字符的查询、访问变得简单。只要知道字符在字符串中
的位置，就可以像访问数组元素一样通过位置访问这个字符。

但是，字符串的顺序存储结构给字符串的插入、删除造成不便。在字符串中插入子串
时，必须将插入点后的元素全部依次后移；删除字符串的一个子串时，必须将删除后的部
分全部前移。

此外，存储串的连续的存储单元一般要求先定义好最大长度，这也使得串的操作受
限。两个字符串连接的结果，很可能超出这个最大长度。
（2）串的动态存储结构。
用顺序存储结构来存储字符串，因为其规模在定义的时候就已定下，容易造成存储空

间的浪费；同时，线性表的插入和删除操作效率很低。因此，有些时候也采用动态存储方
式。动态存储方式包括链式存储结构和堆存储结构。

在串的链式存储结构中，每个结点包含字符域和结点链接指针域，字符域存放字符，
指针域存放指向下一结点的指针，如图3-7所示。因此，串可用单链表表示。

图3-7 串的链式存储结构

字符串的各种运算和串的存储结构有很大的关系，存储结构不同，其运算和操作也会

有所不同。
在各种事务管理系统中，可以通过字符串的操作来实现对事物的自动化管理。例如，
对于超市中商品信息的查询，可以通过商品条形码来获得商品的详细信息，也可以通过提

取商品条形码中的某个子串来实现同类商品的比价功能。

实 践

为了优化系统，提高查询效率，拟升级菜谱自助查询系统的功能：除了通过食材名称

获取菜谱，还可以直接选择某一类别食材的全部菜谱清单供顾客选择。优化升级的主要目
的在于提供对“类别”的查询响应。因此，对数据结构进行以下改造：

67 67

21X2204.indd 67 2019/9/26 13:53:16