数据结构c语言版第四章串

《数据结构c语言版第四章串》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四章串重点难点理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。典型例题1、简述下列每对术语的区别：　　空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】　（1）空串是指不包含任何字符的串，它的长度为零。　　空白串是指包含一个或多个空格的串，空格也是字符。（2）串常量是指在程序中只可引用但不可改变其值的串。　　串变量是可以在运行中改变其值的。（3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子

2、串的串就称为主串。（4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。2、以HString为存储表示，写一个求子串的算法。【解】　　HString是指以动态分配顺序串为存储表示，其定义为：　　　typedefstruct{　　　　char*ch;　　　　intlength;　　　}HString;　　void*substr

3、(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->lengthlen=s->length-pos

8、;//设置子串的串长　　　　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的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。【解】　　查找过程是这样的，取S

9、中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下：　　链串的结构类型定义:　typedefstructnode{　　　chardata;　　　structnode*next;　　}LinkStrNode;//结点类型　typedefLinkStrNode*LinkString;//LinkString为链串类型　LinkStringS;//S是链串的头指针　charSearchNoin(LinkStringS,LinkStringT)　

10、　{//查找不在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;　　　　}　　　printf("there'snosuchcharacter.");　　　returnNULL

11、;｝习题精选一、.单项选择题1.串是一种特殊的线性表，其特殊性体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若2．串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存3.串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接

12、串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．