数据结构c语言版第4章串.ppt

资源描述

《数据结构c语言版第4章串.ppt》由会员分享，可在线阅读，更多相关《数据结构c语言版第4章串.ppt（56页珍藏版）》请在三一文库上搜索。

1、1 串的基本概念,2 串的存储结构,3 串的基本运算及其实现,4,学习导读在计算机应用中，非数值处理的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串进行处理的。在事务处理中，用户的姓名、地址及货物的名称、规格等也是字符串数据。字符串简称为串，它是一种特殊的线性表，这种线性表的数据元素总是字符型的，字符串的数据对象为字符集。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和基本的串操作。,学习目标与重点,理解串的定义；理解串

2、的顺序存储结构和链式存储结构；掌握串的定长顺序存储的基本算法。,4.1 串类型的定义,4.1.1 串的定义串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作： s = c1c2cn (n0) 其中：s为串名，用双引号括起来的字符序列是串的值；ci(1in)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Null string），如：s=，它的长度为零；仅由空格组成的的串称为空格串，如：s=；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=的长度为2 。

3、s=Imastudent的长度为13 ，请读者注意，在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，如s1=a 与s2=a 两者是不同的，s1表示字符，而s2表示字符串。,4.1.2 主串和子串一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。称一个字符在串序列中的序号为该字符在串中的位置，子串在主串中的位置是以子串的第一个字符在主串中的位置来表示的。当一个字符在串中多次出现时，以该字符第一次在主串中出现的位置为该字符在串中的位置。当一个子串在主串中多次出现时，以该子串第一次在主串中出现，子串第一个字符的位置为该子串在主串中的位置。例如：s1、s2

4、、s3为如下的三个串： s1=Im a student; s2=student; s3=teacher。则它们的长度分别为13、7、7；串s2是s1的子串，子串s2在s1中的位置为7，也可以说s1是s2的主串；串s3不是s1的子串，串s2和s3不相等。,4.1.3 串的基本运算串的基本运算有赋值、联接、求串长、求子串、求子串在主串中出现的位置、判断两个串是否相等、删除子串等。在本节中，我们尽可能以C语言的库函数表示其中的一些运算，若没有库函数，则用自定义函数说明。,（1）strcpy(str1,str2) 字符串拷贝（赋值）：把str2指向的字符串拷贝到str1中，返回str1。库函数和形

5、参说明如下： char * strcpy(char * str1, char * str2) （2）strcat(str1,str2) 字符串的联接：把字符串str2接到str1后面，str1最后的结尾符0被取消。返回str1。库函数和形参说明如下： char * strcat(char * str1, char * str2) （3）strlen(str) 求字符串的长度：统计字符串str中字符的个数（不包括0），返回字符的个数，若str为空串，则返回值为0。库函数和形参说明如下： unsigned int strlen(char *str) （4）strstr(str1,str2) 子串的

6、查询：找出子串str2在主串str1第一次出现的位置（不包括子串str2的结尾符），返回该位置的指针，若找不到，返回空指针NULL。库函数和形参说明,如下： char * strstr(char * str1,char * str2) （5）strcmp(str1,str2) 字符串的比较：比较两个字符串str1、str2。若str1str2，则返回负数；若str1str2，则返回正数；若str1str2，则返回0。库函数和形参说明如下： int strcmp(char * str1,char * str2) （6）substr(str1,str2,m,n) 求子串：在字符串str1中，从第m

7、个字符开始，取n个长度的子串str2；若mstrlen(str)或n0，则返回空值NULL。自定义函数和形参说明如下： int substr(char * str1,char *str2,int m,int n) （7）delstr(str,m,n) 字符串的删除：在字符串str中，删除从第m个字符开始的n个长度的子串。自定义函数和形参说明如下： Void delstr(char *str,int m,int n) （8）Insstr(str1,m,str2 ) 字符串的插入：在字符串str1第m个位置之前开始，插入字符串str2。返回str1。自定义函数和形参说明如下： Void inss

8、tr(char *str1,int m,char *str2) 对字符串的置换可以通过求串长，删除子串，字符串的联接等基本运算来实现。,算法4-1,4.2 串的表示和实现串的存储结构有3种方法：定长顺序存储表示，堆分配存储表示和串的块链存储表示。,4.2.1 定长顺序存储表示类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计算机的存储器地址是采用以字编址，一个字（即一个存储单元）占多个字节，因此顺序存储结构方式有两种：（1）紧缩格式：即一个字节存储一个字符。这种存储方式可以在一个存储单元中存放多个字符，充分地利用了存储空间

9、。但在串的操作运算时，若要分离某一部分字符时，则变得非常麻烦。,图4-1 串值的紧缩格式存储,4.2 串的表示和实现串的存储结构有3种方法：定长顺序存储表示，堆分配存储表示和串的块链存储表示。,图4-1 串值的紧缩格式存储,图4-1所示是以4个字节为一个存储单元的存储结构，每个存储单元可以存放4个字符。对于给定的串s=datastructure，在C语言中采用字符0作串值的结束符。串s的串值连同结束符的长度共15，只需4个存储单元。,用字符数组存放字符串时，其结构用C语言定义如下： #define MAXSTRLEN 255 /用户可在255以内定义最大串长 P73 Typedef un

10、signed char SSTRINGmaxstrlen+1; /0单元存放串的长度由上述讨论可知，串的顺序存储结构有两大不足之处：一是需事先预定义串的最大长度，这在程序运行前是很难估计的。二是由于定义了串的最大长度，使得串的某些操作受限，如串的联接运算等。串的实际长度可在预定义长度的范围内随意，超过预定义长度的串值则被“截断”。C语言以“0”表示串值的终结。,图4-2 串值的非紧缩格式存储,（2）非紧缩格式：这种方式是以一个存储单元为单位，每个存储单元仅存放一个字符。这种存储方式的空间利用率较低，如一个存储单元有4个字节，则空间利用率仅为25%。但这种存储方式中不需要分离字符，因而程序处理

11、字符的速度高。图4-2为串值的非紧缩格式存储。,图4-2 串值的非紧缩格式存储,字符串上的运算 1）字符串的联接Concat( /若是非空串，则按串长分配存储区，否则ch为NULL int length; /串长度 HString,串的插入算法串的插入算法是为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行复制。串的插入算法描述如下： Status StrInsret( Hstring / StrInsret 该算法的时间复杂性为O（m+n）。即S串与T串串长之和。,赋值运算在内存生成一个值等于串常量chars的串T。赋值运算的描述如下： Status StrAssign(H

12、string / StrAssign,定位运算又称定位函数 Index( S,T,pos)。其功能是在主串S中查找T串子串。如果查找成功，返回值为T子串中的第一个字符在S串中的位置序号。如找不到返回值为0。若存在多个T串，则以第一个为准。T 一般被称为模式串，所以，定位函数又称为模式匹配。 int Index (SString S, SString T, int pos) /返回T在S中第pos个字符之后的位置。若不存在，则函数值为0。 P79 /其中，T非空，1posStrlength(S). i = pos ; j =1 ; while (i T0) return i - T0;（

13、匹配成功返回第一个匹配字符位置 else return 0;（失败返回） / Index 注意：一般的模式匹配仅返回结果是匹配与不匹配。动画,求串长： P77 Int Strlength(Hstring S) return S.length; / Strlength 比较两个串： Int StrCompare(Hstring S, Hstring T) /若ST，则返回值0；若S T ，则返回值 0；若ST，则返回值 0 for (i=0;iS.length / StrCompare,将串清空： Status ClearString(HString /Concat,求子串运算substri

14、ng( s,i,j) P77 该种运算的功能是在串S中求从起始位置i开始长度为j的子串。源串S不发生任何变化。注意在实际应用中该种运算存在下面几种形式； substring( s,i,j )；substring( s,i )；substring( s,i,0)；例如，S = aabcacbbcaabc; i = 6; * substring( s,i ) =cbbcaabc； *substring( s,i，0 ) = ； S = aabcacbbcaabc; i = 6; j = 4; * substring( s,i,j) = cbbc; 注意：1i s.length + 1; 0

15、j; 若 i+j s.length + 1; 则，j = s.length - i+ 1; 如i = 6; j = 14;则 substring( s,i,j) = cbbcaabc；,Status SubString(HString ,4.2.3 串的块链存储表示串属于线性表，所以也可以用链表存储，但是由于串中的每个数据元素是一个字符，因而，用链表存储串值时，就存在每个结点存放一个字符，或每个结点存放多个字符的情况。当每个结点存放多个字符时，如果链表中最后一个结点中存在空字段，则用“#”来填充。如图示： head head 为了便于进行串的操作，以链表存储字符串值时，除了设置头指针外，还

16、设置一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称串的这种存储结构为块链结构。 #define CHUNKSIZE 80 typedef struct Chunk char chCHUNKSIZE; struct Chunk *next; Chunk,A B C D E F G H I # # # ,A B C I ,typedef struct Chunk *head, *tail;/头尾指针 int curlen; /串的当前长度 LString;,在链式存储方式中结点大小的选择直接影响串的处理效率。因而要考虑串值的存储密度。存储密度显然存储密度小，运算处理方便 4.4

17、串的应用 1）文本编辑输入到计算机内存中等待加工与修改的源程序通称文本。现在，文本编辑程序的种类有多种，功能强弱不同，但基本操作如串的查找、插入和删除都是相同的。,总的存储位数,串值所占的存储位,例如一段源程序为： main () float a,b,max; scanf (“%f,%f”, 上述源程序按顺序存储如图4-7。为了管理文本串的页和行，在进行文本编辑时，编辑程序先为文本串建立相应的页表和行表。页表的每一项给出页号和该页的起始行号。而行表的每一项则指示每一行的行号、起始地址和该行子串的长度。假设上图所示文本只占一页，且起始行号为201，则该文本串的行表如图4-8。,201,209

18、,226,250,267,282,行号起始地址长度 100 201 8 101 209 17 102 226 24 103 250 17 104 267 15 105 282 2,图 4-7 文本格式示例,图 4-8 图4-7所示文本串的行表,main () float a,b,max; scanf (“%f,%f”, ,下面我们就来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。若插入行145，则行表中从150开始的各行信息必须向下平移一行。（2）删除一行时，则只要在行表中删除该行的行

19、号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述，有兴趣的同学可设计其中的算法。,作业： 1、利用学过的字符串上的操作运算，设计检查用户输入的程序编号是否正确的算法。（编号若是四位数字组成为正确） 2、假设S、T分别为两个字符串，设计用在S 串中与T串中都存在的所

20、有字符构成新串R且打印该字符在S 串中第一次出现时的位置的算法。 3、已知 S=“aabbbccaabccaabc”, v =xxyy; m=ASSIGN( m,substr(s,LEN(v); i=INDEX( m,SUBSTR(S,6,LEN(v); Replace( m, SUBSTR(S,i,LEN(v),v) = ?;,4、已知字符串1234+-*/5678试编写删除串中+-*/子串的算法。 5、已知字符串S，若在其中能检索到子串“ON”，则用单引号将它括起来，试编写完成该功能的算法。 6、已知字符串S=JION，X= FRANG，试编写将字符串S和X联接成一个字符串的算法。 7、假

21、设S、T分别为两个字符串，设计用在S 串中存在而T串中不存在的所有字符构成新串R且打印字符串S 最后长度的算法。 8、已知字符串S，若在其中能检索到子串IHG，则在其后插入子串=，试编写完成该功能的算法。 9、求出子串NG在字符串JIAOTONG中的位置序号。,学习目标与重点,理解串的定义；理解串的顺序存储结构和链式存储结构；掌握串的定长顺序存储的基本算法。,本章小结本章主要介绍了如下一些基本概念：串：串（或字符串）（String）是由零个或多个字符组成的有限序列。主串和子串：一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。串的定长顺序存储结构：类似于线

22、性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构。堆分配存储结构：用一组空间足够大的、地址连续的存储单元存放串值字符序列，但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。,串的链式存储结构：类似于线性表的链式存储结构，采用链表方式存储串值字符序列的存储方式称为串的链式存储结构。除上述基本概念以外，学生还应该了解串的基本运算（字符串拷贝即赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的定长顺序存储结构的表示、串的链式存储结构的表示、串的堆分配存储结构的表示，能在各种存储结构方式中求字符串的长度、能在各种存储结构方

23、式中利用C语言提供的串函数进行操作。,习题四 1简述空串与空格串、串变量与串常量、主串与子串、串名与串值每对术语的区别？ 2两个字符串相等的充要条件是什么？ 3串有哪几种存储结构？ 4已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 5已知：s1=Im a student，s2=student，s3=teacher，试求下列各运算的结果： strstr(s1,s2)； strlen(s1)； strcat(s2,s3)； delstr(s1,4,10)；,*6设s1=”AB”，s2=”A

24、BCD”，s3=”EFGHIJK，试画出堆存储结构下的存储映象图。 7试写出将字符串s2中的全部字符拷贝到字符串s1中的算法，不允许利用库函数strcpy()。 8设s1和s2是用结点大小为1的单链表表示的串，试写出找出s2中第一个不在s1中出现的字符的算法。 9设字符串采用块链存储结构，块链中每个结点存放m（m=4）个字符，试写出实现字符串删除的算法。,试题库题第四章串,串单选题,1、设字符串s1=abcdefg,s2=pqrst，则运算s=concat(sub(s1,2,len(s2),sub(s1,len(s2),2)后串值为_。 2、空串与空白串是相同的,这种说法_。 3、串是一种

26、s2),subs(s1,len(s2),2)的结果串是_。 6、经过以下队列运算后,队头的元素是_。InitQueue(qu);enQueue(qu,a);enQueue(qu,b);enQueue(qu,c);deQueue(qu); 7、经过以下队列运算后,QueueEmpty(q)的值是_。InitQueue(qu);enQueue(qu,a);enQueue(qu,b),deQueue(qu,x);deQueue(qu,y); 5、BCDEF| BCDEFG| BCPQRST| CDEFGFG D 6、a| b| 1 | 0 B 7、a| b| 1 | 0 C,串单选题,8、元素A、

27、B、C、D顺序连续进入队列qu后,队头元素是_,队尾元素是_。 9、一个队列的入列序列为1234,则队列可能的输出序列是_。 10、环形队列qu的队满条件是_。 8、A| B| C| D A|D 9、4321| 1234| 1432| 3241 B 10、(qu.rear+1)%MaxSize=(qu.front+1)%MaxSize| (qu.rear+1)%MaxSize=qu.front+1| (qu.rear+1)%MaxSize=qu.front| qu.rear=qu.front C,串单选题,11、环形队列qu的队空条件是_。 12、设环形队列中数组的下标是0N-1,其头、尾指

31、nt=(Q.rear+1)%QueueSize| Q.rear=(Q.front+1)%QueueSize C 21、栈顶| 栈底| 任意位置| 指定位置 A,串单选题,22、当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行_语句修改top指针。 23、假定利用数组aN顺序存储一个栈，用top表示栈顶指针,top=-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为_. 24、利用数组aN顺序存储一个栈，用top表示栈顶指针，top=-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为_。 22、top+| top-| to

33、op;| p-next=top-next;top-next=p;| p-next=top;top=p; D 26、top-next=top;| top=top-data;| top=top-next;| top-next=top-next-next C 27、3，2，1| 2，1，3| 3，1，2| 1，2，3 C 28、前一个| 后一个| 当前| 后面 C,串单选题,29、当利用大小为N的数组顺序存储一个队列时，若没有队列长度的变量，则该队列的最大长度为_。 30、当利用大小为N的数组顺序存储一个队列时，若不设有队列长度的变量，则该队列的最大长度为_。 31、从一个顺序队列删除元素时，首先

34、需要_。 32、一个不设队列长度变量的顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为_。 29、N-2| N-1| N| N+1 B 30、N-2| N-1| N| N+1 B 31、队首指针循环加| 队首指针循环减| 取出队首指针所指位置上的元素| 取出队尾指针所指位置上的元素 A 32、f+1=r| r+1=f| f=0| f=r D,串单选题,33、假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为_。 34、假定利用数组aN循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元素x进队时所执行的操作为_。 35、在一个长度为N的数组

36、少元素，可以根据队首指针的值和队尾指针的值来计算。 5、队列的输入序列为1234n,输出序列为a1a2an，则aiai+1(1=i=n-1)。 1、True 2、False 3、True 4、True 5、True,串填空题,1、串的两种最基本的存储方式是_。 2、两个串相等的充分必要条件是_。 3、空串是_，其长度等于_。 4、空白串是_，其长度等于_。 1、顺序存储方式和链式存储方式 2、两个串的长度相等且对应位置的字符相同 3、零个字符的串|零 4、由一个或多个空格字符组成的串|其包含的空格个数,串填空题,5、设s=I_AM_A_TEACHER，(其中,_表示一个空格字符)，其长度是

37、_。 6、设s1=GOOD，s2= ，s3=BYE!，则s1,s2和s3连接后的结果是_。 7、队列是一种具有_特性的线性表。 8、顺序队和链队的区别仅在于_的不同。 5、14 6、GOOD BYE! 7、先进先出 8、存储结构,串填空题,9、如果队列的最大长度难以估计，则最好使用_。 10、在队列中，新插入的元素只能插入到_。 11、环形队列的优点是_。 12、设有数组A0.m作为环形队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队的操作是_。 9、链队 10、队尾 11、解决了假溢出问题 12、 Arear=x; rear=(rear+1)%(m+1);,串

38、填空题,13、设有数组A0.m作为环形队列的存储空间,front为队头指针，rear为队尾指针，假设队列不空，则元素出队并保存到x中的操作是_。 14、若用带头结点的单链表来表示链队，则队列空的标志是_。 15、若用不带头结点的单链表来表示链队，则创建一个空队列所要执行的操作是_。 16、若用带头结点的单链表来表示链队，则创建一个空队列所要执行的操作是_。 13、 x=Afront; front=(front+1)%(m+1); 14、头结点的指针域为空 15、将单链表的首结点指针赋空值 16、将单链表头结点的指针域赋空值,串填空题,17、己知链队的头、尾指针分别是f和r,则将值x入队的操作

39、序列是_。 18、在顺序队列实现的时候,通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生_现象。 19、环形队列用数组A0.m-1存放其元素值，己知其头尾指针分别是front和rear，则当前队列中的元素个数是_。 20、队列的插入操作在_进行，删除操作在_进行。 17、p=(QNode *)malloc(sizeof(QNode); p-data=x; p-next=r-next; r-next=p; r=p; 18、假溢出 19、(rear-front+m)%m 20、队尾| 队首,串填空题,21、栈又称为_表，队列又称为_表。 22、向一个顺序栈插入一个元素时，首先使_后移一

40、个位置，然后把待插入元素_到这个位置上。 23、从一个顺序栈删除元素时，首先取出_的值，然后再使栈顶指针_。 21、后进行出| 先进先出 22、写入| 栈顶指针 23、减1| 栈顶元素,串填空题,24、在一个不设队列长度变量的顺序队列中，判断队空的条件为_，判断队满的条件为_。 25、在一个链队中，若队首指针与队尾指针的值相同，则表示该队为_或该队_。 26、向一个链栈插入一个新结点时，首先把栈顶指针的值赋给_，然后把新结点的存储位置赋给_。 27、从一个链栈中删除一个结点时，需要把栈顶结点_的值赋给_。 24、Q.front=Q.rear| (Q.rear+1)%MaxSize=Q.fro

41、nt 25、空| 只含有一个结点 26、新结点的指针域| 栈顶指针 27、指针域 | 栈顶指针,串填空题,28、当用长度为的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件为_。 29、向一个栈顶指针为HS的链栈中插入一个新结点*p时，应执行_和_操作。 30、中缀表达式3*(x+2)-5所对应的后缀表达式为_。 31、设元素a,b,c,d依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为push(S,a)，push(S,b)， push(S,c)，_，_，_，pop(S)，pop(S)。 28、top=0 29、P-next=HS| HS=p 30、3x2+*5- 31、pop(S)| pop(S)| push(S,d),串问答题,1、设栈s和队列q的初始状态都为空，元素a,b,c,d,e和f依次通过栈s，一个元素出栈后立即进入队列q，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存多少个元素? 答：栈s的容量至少应该存3个元素。,

展开阅读全文

数据结构c语言版 第4章串.ppt

数据结构c语言版第4章串.ppt