《数据结构--第四章--幻灯片》由会员分享，可在线阅读，更多相关《数据结构--第四章--幻灯片（40页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构,第四章 串,4.1 串的抽象数据类型的定义,4.2 串的表示和实现,4.1 串的抽象数据类型的定义,串：是由零个或多个字符组成的有限序列。 s=a1a2 an 空串：零个字符的串。 长度：串中字符的数目。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 位置：通常称字符在序列中的序号为 该字符在串中的位置。,4.1 串的抽象数据类型的定义如下：,ADT String ,数据对象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,R1 | ai-1, ai D, i=2,.,n ,串是有限长的字符序列，由一对单引号相括，如:
2、a string ,基本操作：,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (&T, S1, S2),SubString (&Sub, S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&S, pos, T),StrDelete (&S, pos, len),ClearString (&S), ADT String,StrEmpty (S) 初始条件：串S
3、存在。 操作结果：若 S 为空串，则返回 true， 否则返回 false。, 表示空串，空串的长度为零。,StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。,例如：StrCompare(data, state) 0,Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。,例如： Concat( T, man , kind ) 求得 T = mankind ,SubString (&Sub, S, pos,
4、len) 初始条件： 操作结果： 用 Sub 返回串 S 的第 pos 个 字符起长度为 len 的子串。,串 S 存在，1posStrLength(S) 且 0lenStrLength(S)-pos+1。,例如： SubString( sub, commander , 4, 3),子串为“串”中的一个字符子序列,求得 sub = man ;,SubString( sub, commander , 1, 9),SubString( sub, commander , 9, 1),求得 sub = r ,求得 sub = commander ,SubString(sub, commander ,
5、4, 7) sub = ?,SubString(sub, beijing , 7, 2) = ? sub = ?,SubString( student , 5, 0) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,Index (S, T, pos) 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos 个字符之后第一次出现的位置;否则 函数值为0。,假设 S = abcaabcaaabc , T = bca ,Index(S, T, 1) = 2;,Inde
6、x(S, T, 3) = 6;,Index(S, T, 8) = 0;,“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。,Replace (&S, T, V) 初始条件：串S, T和 V 均已存在， 且 T 是非空串。 操作结果：用 V 替换主串 S 中出 现的所有与（模式串）T 相等的不重叠的子串。,例如：,假设 S = abcaabcaaabca , T = bca ,若 V = x , 则经置换后得到 S = axaxaax ,若 V = bc , 则经置换后得到 S = abcabcaabc ,bca,bca,bca,StrInsert (&S, pos, T) 初始条件
7、：串S和T存在， 1posStrLength(S)1。 操作结果：在串S的第pos个字符之前 插入串T。,例如：S = chater ，T = rac ， 则执行 StrInsert(S, 4, T) 之后得到 S = character ,StrDelete (&S, pos, len) 初始条件：串S存在 1posStrLength(S)-len+1。 操作结果：从串S中删除第pos个字符 起长度为len的子串。,对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。,gets(str) 输入一个串； puts(str) 输出一个串； str
8、cat(str1, str2) 串联接函数； strcpy(str1, str2) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；,例如：C语言函数库中提供下列串处理函数：,串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。,在上述抽象数据类型定义的13种操作中，,即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最
9、小操作子 集上实现。,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为 输入或输出的常量出现，则只需存储 此串的串值，即字符序列即可。但在 多数非数值处理的程序中，串也以变 量的形式出现。,4.2 串的表示和实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char
10、 Sstring MAXSTRLEN + 1; / 0号单元存放串的长度,一、串的定长顺序存储表示,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”,串的实际长度可在这个预定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”,特点:,Status Concat(SString S1, SString S2, SString / Concat,例如：串的联接算法中需分三种情况处理：,T1S10 = S11S10; TS10+1S10+S20 = S21S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTR
11、LEN) / 未截断,else if (S10 MAXSTRSIZE) / 截断,else / 截断(仅取S1),T1S10 = S11S10; TS10+1MAXSTRLEN = S21MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T0MAXSTRLEN = S10MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; ,typedef struct char *ch; / 若是非空串，则按串长分配 /存储区，否则 ch 为NULL int length; / 串长度 HString;,二、串的堆分配存储
12、表示,通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( ) 和 free( ) 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。,这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制。,三、串的块链存储表示,也可用链表来存储串值，由于串的数据元素是一个字符，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,#define CHUNKSIZE 80 / 可由用户定义的块大小 t
13、ypedef struct Chunk / 结点结构 char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,本章作业,1.两个串相等的充分必要条件是什么？ 2.空串与空格串是相同的吗？为什么？
14、,习题一,1. for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; O（n3） 2. for (i=1; i=n; i=2*i) +x; O（log2n）,3. s=0; for (i=0; i=n; i+) for (j=0; j=n; j+) for (k=0; ki+j; k+) s+; O（n3）,习题一,4.向一个长度为n的顺序表中的第i个元素（0in-1）之前插入一个元素时，需向后移动 n-i 个元素。 5.在一个长度为n的顺序表中删除第i个元素（0in-1）时，需向前移动 n-
15、i-1 个元素。 6.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是： 静态链表 。 7.如果最常用的操作是取第i个结点及其 前驱，则采用 顺序表 存储方式最 节省时间。,习题一,8.在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作： （1）s-next= p-next ; （2）p-next=s; （3）t=p-data; （4）p-data= s-data ; （5）s-data= t ; 9.在一个单链表中删除p所指结点时，应执行以下操作： q=p-next; p-data=p-next-data; p-next= p-next-next ; free(q);,习题一,10.从顺序表中删除所有值为x的元素。 void delall(Sqlist ,习题一,11.某百货公司仓库
