欢迎来到天天文库
浏览记录
ID:50840623
大小:45.45 KB
页数:4页
时间:2020-03-15
《数据结构C语言版第四章串.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、第四章串重点难点理解"串"类型定义中各基本操作的特点,并能正确利用它们进行串的其它操作;掌握串类型的各种存储表示方法;理解串的两种匹配算法。典型例题1、简述下列每对术语的区别: 空串和空白串;串常量和串变量;主串和子串;静态分配的顺序串和动态分配的顺序串;【解】 (1)空串是指不包含任何字符的串,它的长度为零。 空白串是指包含一个或多个空格的串,空格也是字符。(2)串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。(3)主串和子串是相对的,一个串中任意个连续字符组成的串就是这个串
2、的子串,而包含子串的串就称为主串。(4)静态分配的顺序串是指串的存储空间是确定的,即串值空间的大小是静态的,在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间,在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定,也是顺序存储空间)。2、以HString为存储表示,写一个求子串的算法。【解】 HString是指以动态分配顺序串为存储表示,其定义为: typedefstruct{ char*ch; intlength; }HStri
3、ng; void*substr(HString*sub,HString*s,intpos,intlen) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 inti; if(pos<0
4、
5、pos>s->length-1
6、
7、len<=0) Error("parametererror!");//参数不合法,子串为空串 if(s->length8、 sub->len=s->length-pos;//设置子串的串长 elsesub->length=len;//设置子串的串长 sub->ch=(char*)malloc(len*sizeof(char));//为sub->ch申请结点空间 for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中 sub->ch[i]=s->ch[pos+i]; }3、若S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找9、出S中第一个不在T中出现的字符。【解】 查找过程是这样的,取S中的一个字符(结点),然后和T中所有的字符一一比较,直到比完仍没有相同的字符时,查找过程结束,否则再取S中下一个字符,重新进行上述过程。算法如下: 链串的结构类型定义: typedefstructnode{ chardata; structnode*next; }LinkStrNode;//结点类型 typedefLinkStrNode*LinkString;//LinkString为链串类型 LinkStringS;//S是链串的头指针 10、charSearchNoin(LinkStringS,LinkStringT) {//查找不在T中出现的字符 LinkStrNode*p,*q; p=S; q=T; while(p) {//取S中结点字符 while(q&&p->data!=q->data)//进行字符比较 q=q->next; if(q==NULL) returnp->data;//找到并返回字符值 q=T;//指针恢复串T的开始结点 p=p->next; } 11、 printf("there'snosuchcharacter."); returnNULL;}习题精选一、.单项选择题1.串是一种特殊的线性表,其特殊性体现在()。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符若2.串下面关于串的的叙述中,()是不正确的?A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存3.串的长度是指()。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所12、含非空格字符的个数4.设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是:A.BCDEFB.BCDEFGC.BCPQRSTD.
8、 sub->len=s->length-pos;//设置子串的串长 elsesub->length=len;//设置子串的串长 sub->ch=(char*)malloc(len*sizeof(char));//为sub->ch申请结点空间 for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中 sub->ch[i]=s->ch[pos+i]; }3、若S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找
9、出S中第一个不在T中出现的字符。【解】 查找过程是这样的,取S中的一个字符(结点),然后和T中所有的字符一一比较,直到比完仍没有相同的字符时,查找过程结束,否则再取S中下一个字符,重新进行上述过程。算法如下: 链串的结构类型定义: typedefstructnode{ chardata; structnode*next; }LinkStrNode;//结点类型 typedefLinkStrNode*LinkString;//LinkString为链串类型 LinkStringS;//S是链串的头指针
10、charSearchNoin(LinkStringS,LinkStringT) {//查找不在T中出现的字符 LinkStrNode*p,*q; p=S; q=T; while(p) {//取S中结点字符 while(q&&p->data!=q->data)//进行字符比较 q=q->next; if(q==NULL) returnp->data;//找到并返回字符值 q=T;//指针恢复串T的开始结点 p=p->next; }
11、 printf("there'snosuchcharacter."); returnNULL;}习题精选一、.单项选择题1.串是一种特殊的线性表,其特殊性体现在()。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符若2.串下面关于串的的叙述中,()是不正确的?A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存3.串的长度是指()。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所
12、含非空格字符的个数4.设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是:A.BCDEFB.BCDEFGC.BCPQRSTD.
此文档下载收益归作者所有