第四章串
重点难点
理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。
典型例题
1、简述下列每对术语的区别：
空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】
（1）空串是指不包含任何字符的串，它的长度为零。
空白串是指包含一个或多个空格的串，空格也是字符。
（2）串常量是指在程序中只可引用但不可改变其值的串。
串变量是可以在运行中改变其值的。
（3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。
（4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。
动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。
2、以HString为存储表示，写一个求子串的算法。
【解】HString 是指以动态分配顺序串为存储表示，其定义为：
typedef struct {
char *ch;
int length;
}HString;
void *substr( HString *sub,HString *s,int pos,int len)
{//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串
//pos的合法位置为0<=pos<=s->length-1
int i;
if (pos<0||pos>s->length-1||len<=0)
Error("parameter error!");//参数不合法，子串为空串
if (s->length sub->len=s->length-pos;//设置子串的串长 else sub->length=len; //设置子串的串长 sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间 for(i=0;i sub->ch[i]=s->ch[pos+i]; } 3、若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 【解】 查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下： 链串的结构类型定义: typedef struct node{ char data; struct node *next; }LinkStrNode; //结点类型 typedef LinkStrNode *LinkString; //LinkString为链串类型 LinkString S; //S是链串的头指针 char SearchNoin( LinkString S, LinkString T) {//查找不在T中出现的字符 LinkStrNode *p,*q; p=S; q=T; while (p) { //取S中结点字符 while(q&&p->data!=q->data)//进行字符比较 q=q->next; if(q==NULL) return p->data;//找到并返回字符值 q=T; //指针恢复串T的开始结点 p=p->next; } printf("there's no such character."); return NULL;｝ 习题精选 一、.单项选择题 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串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF 二、算法设计 1.编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数） [题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。 对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。 void insert(char *s,char *t,int pos) //将字符串t插入字符串s的第pos个位置。 {int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针 if(pos<1) {printf(“pos参数位置非法\n”);exit(0);} while(*p!=’\0’&&i //若pos小于串s长度，则查到pos位置时，i=pos。 if(*p == '/0') {printf("%d位置大于字符串s的长度",pos);exit(0);} else //查找字符串的尾 while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。 while(*q!= '\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\0'。 for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。 q--; //指针q回退到串t的最后一个字符 for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上 [算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。 2.写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 [题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 void InvertStore(char A[]) //字符串逆序存储的递归算法。 { char ch; static int i = 0;//需要使用静态变量 scanf ("%c",&ch);if (ch!= '.') //规定'.'是字符串输入结束标志 {InvertStore(A); A[i++] = ch;//字符串逆序存储 } A[i] = '\0'; //字符串结尾标记 }//结束算法InvertStore。 3.写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 void Count（） //统计输入字符串中数字字符和字母字符的个数。 ｛int i，num[36]； char ch； for（i＝0；i<36；i++）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示输入字符串结束。 if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符 else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符 for（i=0；i<10；i++） // 输出数字字符的个数 printf（“数字％d的个数＝％d\n”，i，num[i]）； for（i＝10；i<36；i++）// 求出字母字符的个数 printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）； ｝// 算法结束。 第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么? 第四章串 教学目的与要求 本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。 重点和难点 本章重点是掌握串上实现的模式匹配算法，其也是本章难点。 教学内容 第一节串的基本概念 ４.1.1 基本概念 串：是零个或多个字符组成的有限序列。串中所包含的字符个数称为串的长度。 空串：长度为0的串称为空串，它不包含任何字符。 空白串：仅由一个或多个空格组成的串称为空白串。应注意空串和空白串的区别。 子串、主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身的子串。 子串在主串中的位置：通常，将子串在主串中首次出现时子串首字符对应的主串中的序号定义为子串在主串中的位置。 ２．串的基本运算 （１）求串的长度（Length） （２）串复制 (Copy)： （３）串联接 (Concat) （４）串比较 (Compare) （５）字符定位(Index) 除上述基本运算外，串运算还有求子串、子串的定位、子串的置换等操作。这些操作，一般可由这些基本操作实现。 第二节串的存储结构 4.2.1串的顺序存储 1.静态存储分配的顺序串 顺序串最简单的描述形式是直接使用定长的字符数组来定义。其定义形式为 # define maxstrsize 256 typedef char Seqstring[maxstrsise]; 利用类型描述符Seqstrsring可定义数组变量存储串，利用特定字符表示串的结束(Ｃ语言用转义字符’\0’) 。例如Seqstrstring s; 变量s可存储长度不超过255个字符的字符串，以’\0’作为串的结束。 顺序串的类型定义也可以象线性表的顺序存储一样，在定义字符数组的基础上，引入描述长度的成员。其定义形式为 # define maxstrsize 256 typedef struct { char ch[maxstrsise]; int length; }Sqestring; 第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, ‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】 A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长 4．已知串S=‘aaab’,其Next数组值为（）。 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’的nextval 为（） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 《数据结构与算法》第四章串 知识点及例题精选 串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。 4.1 串及其基本运算 4.1.1 串的基本概念 １．串的定义 串是由零个或多个任意字符组成的字符序列。一般记作： s=＂s1 s2 … s n＂＂ 其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。 ２．几个术语 子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 子串的位置：子串的第一个字符在主串中的序号称为子串的位置。 串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。 4.2 串的定长顺序存储及基本运算 因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。 4.2.1 串的定长顺序存储 类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如： #define MAXSIZE 256 char s[MAXSIZE]; 则串的最大长度不能超过256。 如何标识实际长度？ 1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下： typedef struct { char data[MAXSIZE]; int curlen; } SeqString; 定义一个串变量：SeqString s; 这种存储方式可以直接得到串的长度：s.curlen+1。如图4.1所示。 s.data MAXSIZE-1 第四章习题 1. 设s=’I AM A STUDENT’,t=’GOOD’,q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。 7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。 以下算法用定长顺序串： 8．编写下列算法： （1）将顺序串r中所有值为ch1的字符换成ch2的字符。 （2）将顺序串r中所有字符按照相反的次序仍存放在r中。 （3）从顺序串r中删除其值等于ch的所有字符。 （4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5）从顺序串r中删除所有与串r1相同的子串。 9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 10．写算法，实现顺序串的基本操作StrCompare(s,t)。 11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 实习题 1．已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。 （1）利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。 （2）以顺序串作为存储结构来实现。 2．编写一个行编辑程序EDLINE，完成以下功能： （1）显示若干行：list [[n1]-[n2]]：显示第n1行到第n2行，n1缺省时，从第一行开始，n2缺省时，到最后一行， （2）删除若干行。del [[n1]-[n2]]： n1、n2说明同（1）。 （3）编辑第n行。edit n：显示第n行的内容，另输入一行替换该行。 （4）插入一行。ins n：在第n行之前插入一行。 第四章串 重点难点 理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。 典型例题 1、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】 （1）空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 （2）串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 （3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 （4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 2、以HString为存储表示，写一个求子串的算法。 【解】HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString; void *substr( HString *sub,HString *s,int pos,int len) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i; if (pos<0||pos>s->length-1||len<=0) Error("parameter error!");//参数不合法，子串为空串 if (s->length 第3章栈和队列 习题 1．选择题 （1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 （2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。 A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。 A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。 A．x=top->data;top=top->link； B．top=top->link;x=top->link； C．x=top;top=top->link； D．x=top->link； （5）设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（）。 A． n+1 B． n-1 C． n D． n+2 （6）栈在（）中有所应用。 A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 A．队列 B．栈 C．线性表 D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。 A．2 B．3 C．4 D． 6 （9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。 A．top不变 B．top=0 C．top-- D．top++ （10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。 A．线性表的顺序存储结构 B．队列 C. 线性表的链式存储结构 D. 栈 期末复习 第一章 绪论 复习 1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。 2、算法分析的两个主要方面是空间复杂度和时间复杂度。 3、数据元素是数据的基本单位。 4、数据项是数据的最小单位。 5、数据结构是带结构的数据元素的集合。 6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。 数据结构 算 法 数据：计算机处理的信息总称 数据项：最小单位 数据元素：最基本单位 数据对象：元素集合 数据结构：相互之间存在一种或 多种特定关系的数据元素集合。 概念：数据元素之间的关系 线性结构：一对一 非线性结构 树：一对多 图：多对多 顺序存储结构 链表存储结构 索引。。。 散列。。。 算法描述：指令的有限有序序列 有穷性 确定性 可行性 输入 输出 时间复杂度 空间复杂度 第二章 线性表 复习 1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元 3、线性表采用链式存储，便于进行插入和删除操作 4、线性表采用顺序存储和链式存储优缺点比较。 5、简单算法 第三章 栈和队列 复习 定义 逻辑关系：前趋 后继 节省空间 随机存取 插、删效率低 插入 删除 1、 栈和队列的异同点。 2、 栈和队列的基本运算 3、 出栈和出队 4、 基本运算 第四章 串 复习 存储结构 栈的概念：在一端操作的线性表 运算算法 栈的特点：先进后出 LIFO 初始化 进栈push 出栈 pop 顺序队列 循环队列 队列概念：在两端操作的线性表 假溢出 链队列 队列特点：先进先出 FIFO 基本运算 顺序： 链队： 队空：front=rear 队满：front=(rear+1)%MAXSIZE 队空： rear 初始化 判空 进队 出队 取队首元素 《数据结构与算法》第二部分习题精选 一、填空题 1. 称为空串； 称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 3. 子串的定位运算称为串的模式匹配，称为目标串，称为模式。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为。 二、单选题 （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2.设有两个串p和q，求q在p中首次出现的位置的运算称作：Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长（）3.设串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))的结果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF 三、计算题 1.设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求 Replac e(s,’STUDENT’,q)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。 2.已知主串 3.s=’ADBADABBAABADABBADADA’,模式串 pat=’ADABBADADA’。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。 答案 一、填空题 1. 不包含任何字符（长度为0）的串由一个或多个空格（仅由空格符）组成的串 2. 20 3 3.被匹配的主串子串 4. 6 5. (n-m+1)*m 二、单选题 1. B 2. B 3. D 四、计算题 解：①Replace(s,’STUDENT’,q)＝’I AM A WORKER’ ②因为SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘STUDENT’ 《数据结构（C语言版第2版）》（严蔚敏著） 第四章练习题答案 第4章串、数组和广义表 1．选择题 （1）串是一种特殊的线性表，其特殊性体现在（）。 A．可以顺序存储B．数据元素是一个字符 C．可以链式存储D．数据元素可以是多个字符若 答案：B （2）串下面关于串的的叙述中，（）是不正确的？ A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 答案：B 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串， 零个字符的串成为空串，其长度为零。 （3）串“ababaaababaa”的next数组为（）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 答案：C （4）串“ababaabab”的nextval为（）。 A．010104101B．010102101 C．010100011 D．010101011 答案：A （5）串的长度是指（）。 A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 答案：B 解释：串中字符的数目称为串的长度。 （6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单 元，基地址为10，则LOC[5,5]=（）。 A．808 B．818 C．1010 D．1020 答案：B 解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 （7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数 组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 答案：B 解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素， 其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A．13 B．32 C．33 D．40 数据结构(C语言版)习题及答案第四章习题 4.1选择题 1、空串与空格串是（B）。 A、相同 B、不相同Ｃ、不能确定 2、串是一种特殊的线性表，其特殊性体现在（B）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链式存储 D、数据元素可以是多个字符 3、设有两个串p和q，求q在p中首次出现的位置的操作是（B）。 A、连接 B、模式匹配 C、求子串 D、求串长 4、设串1=“ABCDEFG”，2=“PQRST”函数trconcat（，t）返回和t串的连接串，trub（，i，j）返回串中从第i个字符开始的、由连续j 个字符组成的子串。trlength()返回串的长度。则trconcat（trub（1，2，trlength（2）），trub（1，trlength（2）， 2））的结果串是（D）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 5、若串=“oftware”，其子串个数是（B）。 A、8 B、37 C、36 D、9 4.2简答题 1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？ 答：空串是指长度为0的串，即没有任何字符的串。 空格串是指由一个或多个空格组成的串，长度不为0。 子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。串名是串的一个名称，不指组成串的字符序列。 串值是指组成串的若干个字符序列，即双引号中的内容。 2、两个字符串相等的充要条件是什么？ 答：条件一是两个串的长度必须相等 条件二是串中各个对应位置上的字符都相等。 3、串有哪几种存储结构？ 答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。 4、已知两个串：1=”fgcdbcabcadr”,2=”abc”,试求两个串的长度，判断串2是否是串1的子串，并指出串2在串1中的位置。 答：（1）串1的长度为14，串2的长度为3。 （2）串2是串1的子串，在串2中的位置为9。 5、已知：1=〃I’matudent〃，2=〃tudent〃，3=〃teacher〃，试 求下列各操作的结果： trlength(1)；答：13 trconcat(2,3)；答：”tudentteachar” trdelub(1,4,10)；答：I’m 数据结构练习第四章串 一、选择题 1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 A. “STRUCTURE” B.“DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE” 2．字符串的长度是指（）。 A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 3．两个字符串相等的充要条件是（）。 A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 4．关于串的叙述中，正确的是（） A．空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 5．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( ) A．求子串 B.判断是否相等 C．模型匹配 D.连接 7．若串S=’software’,其子串的数目是( )。 A．8 B．37 C．36 D．9 8．串的长度是指（） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 9．串是一种特殊的线性表，其特殊性体现在( )。 A．数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 10．下面关于串的的叙述中，哪一个是不正确的（B） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 9 12．串是一种特殊的线性表，其特殊性体现在（B） A. 可以顺序存储 B. 数组元素是一个字符 C. 可以连续存储 D. 数据元素可以是多个字符 13. 下面关于串的的叙述中，哪一个是不正确的？（B） 第4～5章串和数组自测卷答案 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 （对应严题集4.1①，简答题：简述空串和空格串的区别） 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 8. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。 答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ; （4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）; 二、单选题（每小题1分，共15分） （ B ）1. 〖李〗串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2. 〖李〗设有两个串p和q，求q在p中首次出现的位置的运算称作： Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长 （ D ）3. 〖李〗设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j) 第四章串 习题4 一、选择题 1.串是一种特殊的线性表，其特殊性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的不同，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和固定分配 6.设串S=“abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。 A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的不同，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为： 第四章串 串又称字符串，是一种特殊的线性表，它的每个元素仅由一个字符组成。计算机上非数值处理的对象基本上是字符串数据。在较早的程序设计语言中，字符串仅作为输入和输出的常量出现。随着计算机应用的发展，在越来越多的程序设计语言中，字符串也可作为一种变量类型出现，并产生了一系列字符串的操作。在信息检索系统、文字编辑程序、自然语言翻译系统等等应用中，都是以字符串数据作为处理对象的。本章将讨论串的存储结构和基本操作。 4.1 串的基本概念 4.1.1 串的自然语言定义 串(string)(或字符串)是由零个或多个字符组成的有限序列，一般记为： S="a1 a2 …… a n" (n≥0) 其中，S是串名，用双引号括起来的字符串序列是串的值；a i(1≤i≤n)可以是字母、数字或其他字符；串中字符的个数n称为串的长度。长度为0的串称为空串。 需要注意的是，串值必须用一对双引号括起来，但双引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆。如"tempt"是个串,tempt则是变量名；"23"是串,而23则是一个常量. 串中任意个连续的字符组成的子序列称为该串的子串，如：串S＝"This is a string"，其中"This"是一个子串，"string"也是一个子串。求子串在串中的起始位置称为子串定位或模式匹配。 例如，设A，B，C为如下三个串：A＝"data"，B="structure"，C＝"data structure"，则它们的长度分别是4,9，14，A和B都是C的子串，A在C中的位置是1，而B在C中的位置是6。 下面注意区别空格串与空串的概念。在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其他字符中间。由一个或多个空格组成的串称为空格串，也就是说空格串中只有空格字符，空格串的长度不为零。而空串的长度为零，通常用 来表示，在C程序中表示成"",它是任意串的子串。为了清楚起见，以后我们用“└┙”表示空格字符。 若称两个串是相等的，一定是这两个串的值相等。即：只有当两个串的长度相等，并 第四章串 任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题 三．填空题 1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串 9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等 10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’ 13．（1）char s[ ] (2) j++ (3) i >= j 14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。 程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len) AND(s[i+k]=t[j+k]) //如果在s和t的长度内，对应字符相等，则指针k 后移（加1）。 （2）con:=false //s和t对应字符不等时置标记退出 （3）j:=j+k //在t串中，从第j+k字符再与s[i]比较 （4）j:=j+1 //t串取下一字符 （5）i：=i+1 //s串指针i后移（加1）。 程序（b）：(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同上（a） (2) con=0 (3) j+=k (4) j++ (5) i++ 15．（1）0 （2）next[k] 16．（1）i：=i+1 （2）j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)0 17.程序中递归调用 （1）ch1<>midch //当读入不是分隔符&和输入结束符$时，继续读入字符 （2）ch1=ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch 第四章串 一．单项选择题 1．串的连接运算不满足。 A. 分配律 B. 交换律 C. 结合律 D. 都不满足 2．串是一种特殊的线性表，其特殊性体现在。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 3．设有两个串p和q，求q在p中首次出现的位置的运算称作。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 4．串是一个的序列。 A. 不少于一个字母 B. 有限个字符 C. 不少于一个字符 D. 空格或字母 5．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为。 A. 8 B. 9 C. 36 D. 37 6. 设串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. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 二．填空题 1．两个串相等的充分必要条件是。 2．空格串是①,其长度等于②。3．模式串‘abaabade’的next函数值为。4．在串S=’tuition’中，以t为首字符且值不相同的子串有个。 5. 使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为。 6. 已知字符串p=’abcabcabbac’，则next(3)和next(6)分别为①、②。 7. 设对主串’bcdbcddabcdbcdbac’和模式串’bcdbcdb’进行KMP模式匹配。第1趟匹配失败后，若使用非改进的Next函数，则下一趟匹配将由主串的第①个字符与模式串的第__②___字符开始比较。若采用改进的Next函数，则下一趟匹配将由主串的第③个字符与模式串的第___④__字符开始比较。字符串中字符从1开始编号。 第二部分习题精选 一、填空题 1. 称为空串； 称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 3. 子串的定位运算称为串的模式匹配，称为目标串，称为模式。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为。 二、单选题 （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2.设有两个串p和q，求q在p中首次出现的位置的运算称作：Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长（）3.设串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))的结果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF 三、计算题 1.设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求 Replace(s,’STUDENT’,q)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。 2.已知主串 3.s=’ADBADABBAABADABBADADA’,模式串 pat=’ADABBADADA’。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。 答案 一、填空题 1. 不包含任何字符（长度为0）的串由一个或多个空格（仅由空格符）组成的串 2. 20 3 3.被匹配的主串子串 4. 6 5. (n-m+1)*m 二、单选题 1. B 2. B 3. D 四、计算题 解：①Replace(s,’STUDENT’,q)＝’I AM A WORKER’ ②因为SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘STUDENT’数据结构课后习题答案第四章
数据结构第04章 串
第四章：串
《数据结构与算法》第四章-学习指导材料
数据结构课后习题及解析第四章
数据结构c语言版第四章串
数据结构(C语言版)第三四章习题答案解析
数据结构 (严蔚敏C语言版) 学习、复习提纲
《数据结构与算法》第四章-串习题
《数据结构(C语言版 第2版)》(严蔚敏 著)第四章练习题答案
数据结构(C语言版)习题及答案第四章
数据结构练习第四章 串
数据结构(C语言版)第4-5章习题答案
数据结构课后习题第四章
数据结构 第四章 串
数据结构 习题 第四章 串 答案
数据结构-4 串
数据结构与算法习题：第四章 串
相关主题
文本预览