数据结构Chapter4.ppt

1、第四章串,数 据 结 构(Data Structures),2020年8月8日星期六,My Email：,2,现今使用的硬件结构主要是反映数值计算的，因此，在处理字符串数据时比处理整数和浮点数要复杂得多。,串实际上就是数据对象为字符的特殊的线性表。同时也导致串的基本操作和线性表有很大的差别。,4.1串类型的定义 4.2串的表示和实现,目 录,2020年8月8日星期六,My Email：,3,1. 串的定义 串(String)是由零个或多个字符组成的有限序列，记作s=a1a2an，其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串值，不包含在串中。 ai(1in)可以

2、是字母、数字或其它字符。n为串中字符的个数，称为串的长度。,4.1串类型的定义,2020年8月8日星期六,My Email：,4,2. 子串、主串 若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。 通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在串中的位置。例如，设A和B分别为 A=This is a string B=is则B是A的子串，A为主串。B在A中出现了2次，其中首次出现所对应的主串位置是3。因此称B在A中的位置为3。,4.1串类型的定义（续）,2020年8月8日星期六,My Email：,5,3. 空串 不含任何

3、字符的串称为空串，它的长度n=0，记为s=。 空串是任意串的子串，任意串是自身的子串。 4. 空格串 在各种应用中，空格常常是串的字符集合中的元素，因而可出现在其它字符中间。 由一个或多个空格组成串，称为空格串，它的长度n为空格的个数。,4.1串类型的定义（续）,2020年8月8日星期六,My Email：,6,5. 串的抽象数据类型描述 串的抽象数据类型可描述为： ADT String 数据对象：Dai|aiCharacterSet, i=1,2,.,n, n0 数据关系：R1| ai-1, ai D, i=2,.,n 基本操作： 1、StringAssign(m=strlen(t);i=p

4、os; while(in-m+1) substr(sub,s,i,m); if(strcmp(sub,t)!=0)+i; else return i; /返回子串在主串中的位置 /while /if return 0; /S中不存在与T相等的子串 ,4.1串类型的定义（续）,2020年8月8日星期六,My Email：,13,因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过组成串的结点是单个字符。 1. 定长顺序存储表示 在定长顺序存储表示，也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。 #define maxstrlen 256 typedef c

5、har SStringmaxstrlen; SString s; /一个可容纳255个字符的顺序串,4.2串的表示与实现,2020年8月8日星期六,My Email：,14,串的实际长度可在预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。 对串长有两种表示方法： 1. 放在下标为0的数组分量中(PASCAL)； 2. 设置一个字符串结束标志(C语言)。 定长顺序存储可能带来的问题：如果在操作中出现串值序列的长度超过上界MAXSTRLEN时，约定用截尾法处理。这种情况在求联接、插入、置换等操作时可能发生。,4.2串的表示与实现（续）,2020年8月8日星期六,My Emai

6、l：,15,2. 堆分配存储表示 仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数malloc()和free()，来根据实际需要动态分配和释放字符数组空间。 类型的定义如下： typedef struct char *ch; int length; HString;,4.2串的表示与实现（续）,2020年8月8日星期六,My Email：,16, 串插入 Status StrInsert(Hstring ,4.2串的表示与实现（续）,2020年8月8日星期六,My Email：,17,4

7、.2串的表示与实现（续）, 求串长度 int StrLength(HString S) return S.length; 清空串 Status ClearString(HString ,2020年8月8日星期六,My Email：,18,4.2串的表示与实现（续）, 赋值 Status StrAssign(HString ,2020年8月8日星期六,My Email：,19,4.2串的表示与实现（续）, 串比较 int StrCmpare(HString S,HString T) for(i=0;iS.length ,2020年8月8日星期六,My Email：,20,4.2串的表示与实现（续

8、）, 串联接 Status Concat(HString ,2020年8月8日星期六,My Email：,21,4.2串的表示与实现（续）, 求子串 Status Substring(HString ,2020年8月8日星期六,My Email：,22,3. 串的链式存储结构 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。 typedef struct node char data; struct node *next; LString; 一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。,4.2串的表示与实现（续）,2020年8月8日星期六,My Email：,23,为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小。当结点大小大于1时，串的度不一定正好是结点的整数倍，需要要用特殊字符来填充最后一个结点，以表示串的终结。 #define NODESIZE 80type