《[精选]中国科大数据结构-中科大继续教育学院》由会员分享，可在线阅读，更多相关《[精选]中国科大数据结构-中科大继续教育学院（29页珍藏版）》请在金锄头文库上搜索。
1、数据结构第四章字符串,本章内容 4.1 串的基本概念 4.2 串的存储结构 4.3 串的基本运算的实现 习题4,4-2,4.1 串的基本概念,串(String)的概念：是由零个或多个字符组成的有限序列。记作： S=a1 a2 an (n0) 其中S是串名，用双引号括起来的字符序列为串值，引号是界限符，ai(1in)是一个任意字符(字母、数字或其他字符)，它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。 将串值括起来的双引号本身不属于串，它的作用是避免串与常数或与标识符混淆。例如，A=123是数字字符串，长度为3，它不同于整常数123。 常将仅由一个
2、或多个空格组成的串称为空白串。注意空串和空白串的不同，例如 和分别表示长度为1的空白串和长度为0的空串。,4-3,4.1 串的基本概念,子串的概念：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符首次出现在主串中的位置来表示。 例如，设有两个字符串C和D： C=This is a string. D=is 则它们的长度分别为17、2；D是C的子串，C为主串。D在C中出现了两次，其中首次出现所对应的主串位置是3。因此，称D在C中的序号(或位置)为3。 若两个串的长度相等且对应字符都相等
3、，则称两个串是相等的。当两个串不相等时，可按“字典顺序”区分大小。,4-4,4.1 串的基本概念,串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。 串的运算： 串赋值 StrAssign( /256个字符依次存储在ch0.chMAXSIZE1中 int len; SString; /SString是顺序串类型，则串的最大长度不能超过255 SString s; /定义串变量s,4-8,4.2 串的存储结构,在直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。例如，C语言中以字符0表示串值的终结。 C
4、语言中串的静态存储结构如下图所示：,C语言中串的静态存储结构,4-9,4.2 串的存储结构,2. 动态存储分配的顺序串(堆串) 这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。 假设以一维数组heapMAXSIZE表示可供字符串进行动态分配的存储空间，并设一整型变量free指向heap中未分配区域的开始地址。在程序执行过程中，当生成一个新串时，就从free指示的位置起为新串分配一个
5、所需大小的存储空间，同时记录该串的相关信息。这种存储结构称为堆结构。动态分配存储空间的顺序串也叫堆串。堆串可定义如下： typedef struct int length; int start; HeapString;,4-10,4.2 串的存储结构,在C语言中，有一个称为“堆”的自由存储空间，并可利用malloc()和free()等动态存储管理函数，根据实际需要动态分配和释放字符数组空间，如下图所示。其类型可描述如下： typedef struct char *ch; /指示串的起始地址，可按实际的串长分配存储区 int len; HString; HString s; /定义一个串变量,顺
6、序串的动态存储结构,4-11,4.2 串的存储结构,在程序中，可根据实际需求为这种类型的串变量动态分配存储空间，这样做非常有效、方便，只是在程序执行过程中要不断地生成新串和销毁旧串。,4-12,4.2 串的存储结构,4.2.2 串的链式存储 顺序串上的插入和删除操作极不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串，如下图所示。,结点大小为1的链串s,4-13,4.2 串的存储结构,链串的类型描述： typedef struct node char ch; struct node *next; /next为指向结点的指针 LString; LStr
7、ing s; /定义一个串变量s 一个链串由头指针惟一确定。 这种结构便于进行插入和删除运算，但存储空间利用率太低。,4-14,4.2 串的存储结构,为了提高存储密度，可使每个结点存放多个字符。如图所示，通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。,结点大小为4的链串,4-15,4.2 串的存储结构,对于结点大小不为1的链串，其类型定义只需对上述的结点类型做简单的修改即可。 #define nodesize 80 typedef struct node char datanode
8、size; struct node *next; LString; 虽然增大结点的数据域使得存储密度增大，但是做插入、删除运算时，需要考虑结点的分拆与合并，可能会引起大量字符的移动，给运算带来不便。,4-16,4.2 串的存储结构,链串的插入,4-17,4.3 串的基本运算的实现,1. 求子串运算(采用静态存储顺序串) int StrSub(SString *sub, SString s, int pos, int len) /用sub返回串s中序号pos开始的长度为len 的子串 int i; if (poss.len | lens.len-pos) sub-len=0; return(0)
9、; /子串起始位置及长度是否合适 else for(i=0;ichi=s.chi+pos; sub-len= 0; /子串结束 sub-len=len; return(1); ,4-18,4.3 串的基本运算的实现,2. 定位运算(采用静态存储顺序串) 串的定位运算也称为串的模式匹配，是一种重要的串运算。 设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回1。t也称为模式。 【算法思想】首先将s0与t0进行比较，若不同，就将s1与t0进行比较，直到s的某一个字符si和t
10、0相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即sij+1，t返回到t0，继续开始下一趟的比较，重复上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是ij，否则，匹配失败。 设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程如下图所示。,4-19,简单模式匹配的匹配过程,4-20,4.3 串的基本运算的实现,模式匹配算法 int StrIndex(SString s,int pos,SString t) /求串t在串s中的位置 int i,j; if(t
11、.len=0) return(0); i=pos;j=0; while(i=t.len) return(i-j); /匹配成功，返回存储位置 else return(-1); ,4-21,4.3 串的基本运算的实现,3插入运算(采用动态存储串) StrInsert(HString *s, int pos, HString t) /在串s的第pos个字符之前插入串t char *temp; int i; if(poss-len) return(0); /pos不合理 if(t.len) /t非空 temp=(char*)malloc(s-len+t.len)*sizeof(char); /临时变
12、量，暂存插入后的结果 if(temp=NULL) return(0); for(i=0;ichi; for(i=0;ilen;i+) tempi+t.len=s-chi; s-len+=t.len; free(s-ch); /释放原串s s-ch=temp; /s获得相加结果 return(1); ,4-22,4.3 串的基本运算的实现,4连接运算(采用动态存储串) StrCat(HString *s,HString t) /将串t连接在串s的后面 char *temp; int i; temp=(char *) malloc(s-len+t.len)*sizeof(char); if(tem
13、p=NULL) return(0); for(i=0;ilen;i+) tempi=s-chi; /复制s串 for(i=s-len;ilen+t.len;i+) /复制t串 tempi=t.chi-s-len; s-len+=t.len; free(s-ch); s-ch=temp; return(1); ,4-23,4.3 串的基本运算的实现,5串定位(采用链串存储) LString *lindex(LString s,LString t) /求串t在串s中的位置，返回指向t串起始位置的指针 LString *loc,*p,*q; loc=s; p=loc;q=t; while(p ,4-
14、24,习 题 4,1. 简述下列每对术语的区别：空串和空白串，串常量和串变量，主串和子串，静态分配的顺序串和动态分配的顺序串。 2. 设s=I am a student，t=good，q=programer。给出下列操作的结果： StrLength(s) SubString(sub1,s,1,7) StrIndex(s, a,4) StrReplace(s, student,q) Strcat(StrCat(sub1,t) 3. 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个
15、位置上。若i大于S的长度，则插入不执行。,4-25,习 题 4,4. 利用C的库函数strlen 和strcpy写一算法void StrDelete(char *S,int i, int m)，删去串S中从位置i开始的连续m个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S),则将S中从位置i开始直至末尾的字符均删去。 5. 以HString为存储表示，写一个求子串的算法。 6. 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： a bcdefghIjklmnopqrstuvwxyz ngzqtcobmuhelkpdawxfyIvrsj 则字符串encrypt被加密为tkzwsdf。试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。,4-26,习 题 4,7. 写一算法void StrReplace(char *T, char *P, char *S)，将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。 8. 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。,4-27,习题,本章习题参见教师网页： http:/,4-28,演讲完毕，谢谢观看！,
