当前位置：文档之家 › 数据结构课后练习 - 第4章

数据结构课后练习 - 第4章

  • 格式：ppt
  • 大小：323.00 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

数据结构课后习题答案第四章

数据结构课后习题答案第四章

第四章一、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

答：●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。

●串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用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)的返回值是什么?(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?(5)调用函数stlen(strcat(s1,s2))的返回值是什么?解：(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。

数据结构教程李春葆课后答案第4章串

数据结构教程李春葆课后答案第4章串

8. 采用顺序结构存储串，设计一个实现串通配符匹配的算法 pattern_index()，其中的 通配符只有‘？’ ，它可以和任一个字符匹配成功。例如，pattern_index("？re"，"there are") 返回的结果是 2。 解：采用 BF 算法的穷举法的思路，只需要增加对‘?’字符的处理功能。对应的算法 如下：
void maxsubstr(SqString s,SqString &t) { int maxi=0,maxlen=0,len,i,j,k; i=0; while (i<s.length) //从下标为 i 的字符开始 { j=i+1; //从 i 的下一个位置开始找重复子串 while (j<s.length) { if (s.data[i]==s.data[j]) //找一个子串,其起始下标为 i,长度为 len { len=1; for(k=1;s.data[i+k]==s.data[j+k];k++) len++; if (len>maxlen) //将较大长度者赋给 maxi 与 maxlen { maxi=i; maxlen=len; } j+=len; } else j++; } i++; //继续扫描第 i 字符之后的字符 } t.length=maxlen; //将最长重复子串赋给 t for (i=0;i<maxlen;i++) t.data[i]=s.data[maxi+i]; }
SqString CommChar(SqString s1,SqString s2) { SqString s3; int i,j,k=0; for (i=0;i<s1.length;i++) { for (j=0;j<s2.length;j++) if (s2.data[j]==s1.data[i]) break; if (j<s2.length) //s1.data[i]是公共字符 { s3.data[k]=s1.data[i]; k++; } } s3.length=k; return s3; }

数据结构课后习题及解析第四章

数据结构课后习题及解析第四章

11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。

写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。

写算法，实现顺序串的基本操作 StrCompare(s,t) 。

第四章习题1. 设 s=' I AM A STUDENT , t= ' GOO D,q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,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 个字符。

数据结构(第二版)习题答案第4章

数据结构(第二版)习题答案第4章
printf("input char to s2:\n");
gets(s2.str);
s2.length=strlen(s2.str);
m=strcompare(s1,s2);
if(m==1) printf("s1>s2\n");
else if(m==-1) printf("s2>s1\n");
free(S);
free(T1);
free(T2);
}
【参考程序
2】：
#include<stdio.h>
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
int length;
}seqstring;
for(k=0;k<t2.length;k++)
s->str[c+k]=t2.str[k];
else if(t1.length<t2.length)
{ for(m=s->length-1;m>i-1;m--)
s->str[t2.length-t1.length+m]=s->str[m]; //后移留空
while (i<t->length && j<p->length)
{
if(j==-1||t->str[i]==p->str[j])
{i++; j++;}
else j=next[j];
}
if (j==p->length) return (i-p->length);

数据结构答案第4章

数据结构答案第4章
【解答】设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t<<m×n时，采用三元组顺序表存储可获得较好的时、空性能。
⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。
A 90 B 180 C 240 D 540 E 108 F 114 G 54
⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。
【解答】1140
【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
Head(Tail(Tail(Head(ST))))=奖金
⑵工资表ST的头尾表示法如图4-7所示。7．若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。
⑵因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即：

数据结构与算法课程第4章的习题答案

数据结构与算法课程第4章的习题答案
swich(branch){
case0: bonus=i*0.1;break;
case1: bonus=bonus1+(i-100000)*0.075;break;
case2:
case3:bonus=bonus2+(i-200000)*0.05;break;
case4:
case5:bonus=bonus4+(i-400000)*0.03;break;
第4章
4.1程序阅读题。以下程序运行结果是什么？
#includestdio.h
void main() {
int i1;
while (i15)
if (i3!2)continue;
else printf(d,i);
printf(\n);
}
结果为：2 5 8 11 14
4.2程序填空题。输出右边所示图案(共N行，N为奇数，此时N＝7)。
}
注意：s、t不能定义为int,long型，因为这两种数据类型的范围都不超过21亿，无法容纳最后求的结果。
(6)求s=a+aa+aaa+…+aa...a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加由键盘输入控制。
程序流程图：
程序代码：
#include<stdio.h>
bonus2=bonus1+100000*0.075;
bonus4=bonus2+200000*0.05;
bonus6=bonus4+200000*0.03;
bonus10=bonus6+400000*0.015;

数据结构课后习题与解析第四章

第四章习题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)。

数据结构与算法python语言实现第4章课后习题

数据结构与算法python语⾔实现第4章课后习题R-4.1 对于⼀个含有n个元素的序列S，描述⼀个递归算法查找其最⼤值。

所给出的递归算法时间复杂度和空间复杂度各是多少? python中三⽬运算符的写法x if(x>y)) else ydef max(data,n):if n==1:return data[0]else:m=max(data,n-1)return data[n-1] if(data[n-1]>m) else m共执⾏n次递归调⽤，因为它花费恒定的时间执⾏⾮递归的部分 所以时间复杂度是O(n)空间复杂度也是O(n)R-4.2使⽤在代码段4-11中实现的传统函数，绘制出power(2,5)函数计算的递归跟踪R-4.3如代码段4-12中实现的函数所⽰，使⽤重复平⽅算法,绘制出power(2,18)函数计算的递归跟踪R-4.4 绘制函数reverse(S,0,5)（代码段4-10)执⾏的递归追踪,其中S=[4,3,6,2,6]R-4.6 写⼀个递归函数,⽤于计算第n个调和数，其中 Hn=1+1/2+1/3+…+1/ndef harmonic(n):if n==1:return 1else:return harmonic(n-1)+1/nprint(harmonic(6))R-4.7 写⼀个递归函数,它可以把⼀串数字转换成对应的整数def tonum(data,m,n):if m==len(data)-1:return data[m]else:return data[m]*pow(10,n-1)+tonum(data,m+1,n-1)data=[1,2,3,4,5]print(tonum(data,0,len(data)))R-4.8Isabel⽤⼀种有趣的⽅法来计算⼀个含有n个整数的序列A的所有元素之和，其中n是2的幂.她创建⼀个新的序列B，其⼤⼩是序列A的⼀半并且设置B[i]=A[2i]+A[2i+1] (i=0,1,…,(n/2)-1)。

数据结构第4单元课后练习答案

第四单元 树形结构
对于三个结点A，B和C，可分别组成多少 不同的无序树、有序树和二叉树？
答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵
高度为h的k叉树的特点是：第h层的节点度为 0，其余结点的度均为k。如果按从上到下， 从左到右的次序从1开始编号，则： ①各层的结点是多少？ ②编号为i的结点的双亲的编号是多少？ ③编号为i的结点的第m个孩子的编号是多少？ ④编号为i的结点的有右兄弟的条件是什么？
试证明在哈夫曼算法的实施过程中，二叉树森林中的每 一棵子树都是Huffman树。
证明： 在Huffman算法进行的每一步，都会有一棵新的二叉树产生，它是合并 原来森林中根结点权值最小的两棵子树而得来的。假设此二叉树为T。 取T的根为一棵独立的子树，则它是一棵Huffman树，将此结点向下分 解，仍然得到一棵Huffman树。 此后，按照与T的形成过程相反的顺序依次分解各叶结点。由于在每次 分解时，新产生的两个叶结点在Huffman算法过程中，都是待合并子树根 结点中权值最小的，也就必然在本二叉树中是权值最小的两个叶结点。 根据前面的定理可知，T是一棵Huffman树。
试证明哈夫曼算法的正确性。
定理 分裂一棵Huffman树的某个叶结点，如果产生的两个叶结点的权值 在所有叶结点权值中最小，则将生成一棵新的Huffman树。 证明： 假设二叉树T是字母表C上的一棵Huffman树，z是它的一个叶节点。在 z的下面添加两个子结点x和y，它们的权值分别是f(x)和f(y)，且满足 f(z)=f(x)+f(y)， f(x)和f(y)在字母表C' =C-{z}+{x,y}上的权值最小，可设新 产生的二叉树为T'。 在字母表C'上存在一棵最优二叉树T"，在T"上x和y互为兄弟结点。在 T"中删除结点x和y，将字母z以及权值f(z)=f(x)+f(y)赋予x和y在T"中的父 结点，得到一棵在字母表C上的二叉树Ť。 根据引理三，可知Ť是字母表C上的最优二叉树，由于T也是字母表C上 的最优二叉树，所以WPL(Ť)= WPL(T)。 由于WPL(Ť)= WPL(T")-f(x)-f(y)， WPL(T)= WPL(T')-f(x)-f(y)，所以 WPL(T")=WPL(T')，即，T'是字母表C'上的最优二叉树。证毕。 补充说明：利用Huffman算法构造一棵二叉树T后，单独取出根结点和它 的两个子结点，则该子树必是一棵最优二叉树。以后，按照与T的形成过 程的相反的顺序依次分解各叶结点，直到再次构造出T，则依据上面的定 理可知T是一棵Huffman树。

《数据结构》第四章习题参考答案

《数据结构》第四章习题一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

( √)2、串是一种数据对象和操作都特殊的线性表。

( √)3、只包含空白字符的串称为空串（空白串）。

( ×)4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。

( ×)5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。

( √)6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。

（×）7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。

（×）二、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（ B ）A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串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))的结果串是（ D ）。

A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG3、串的长度是指（ B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数三、填空题1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。

2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第一章 绪论
4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例
学习要点
1. 熟悉串的7种基本操作的定义，并能利用这些基本操 作来实现串的其它各种操作。 2. 熟练掌握串的定长顺序存储结构上实现串的各种操作 的方法。
3. 掌握串的堆存储结构以及在其上实现串操作的基本方 法。
四、简答题
1. 简述串的存储结构及各自的特点。 • 堆分配存储表示的特点是，仍以一组地址连续的存储单元 存放串值字符序列，但存储空间是在程序执行过程中动态 分配而得。所以也称为动态存储分配的顺序表。 • 在C语言中，利用动态存储管理函数malloc()和free()，来 根据实际需要动态分配和释放字符数组空间。 • 若分配成功，则返回一个指向起始地址的指针，作为串的 基址，同时，为了以后处理方便，约定串长也作为存储结 构的一部分。
S
S
h
e
n
d
a
# # ^
• 为了提高存储密度，可使每个结点存放多个字符。通常将 结点数据域存放的字符个数定义为结点大小。 • 显然，当结点大小大于1时，串的长度不一定正好是结点 的整数倍，则链表中的最后一个结点不一定全被串值占满， 此时通常补上“#”或其它的非串值字符（一般情况下“#” 不属于串的字符集，是一个特殊的符号）。 • 这种存储形式优点是存储密度高于结点大小为1 的存储形 式。不足之处是做插入、删除字符的操作时，可能会引起 结点之间字符的移动，算法实现起来比较复杂。
取子串：从串S1的第n1个字符 开始连续取n2个字符赋值给给 串T；
此时串T为串S的子串，其再主 串中的位置为n1。
五、程序设计题
1. 设计一个链串上实现串比较操作StringEqual(s, t)的算 法。
typedef struct {
char data; Chunk *next;
typedef struct {
Chunk *head;
int curlen; } LinkString
}Chunk;
int index( LinkString r1, LinkString r2 ) { //链串上的子串定位操作 LinkString p, p1, q, q1; int i=0, pos=0; p=r1->head;
• Substring(s1,4,2): „de‟;
• Substring(s1,14,1): „n‟;
• Substring(s1,20,1): „t‟. • 连接的结果： s2=„student‟.
四、简答题
2. 字符串s1=„abcdefghijklmnopqrstuvw‟，由如下运算分别 得到s2和s3，请给出s2和s3的值。
四、简答题
2. 字符串s1=„abcdefghijklmnopqrstuvw‟，由如下运算分别 得到s2和s3，请给出s2和s3的值。
s 2 StringConcat( Substring( s1,19,3), SubString( s1,4,2), SubString( s1,14,1), Substring( s1,20,1))
}
2. 设计一个链串上实现子串定位操作的算法。 • 比较两个串的大小 int strcmp(hstring s,hstring t){ for(i=0; i<s.length && i<t.length; ++i) if(s.ch[i]!=t.ch[i] //每个字符两两比较 return(s.ch[i]-t.ch[i]);
}
四、简答题
3. 分析下述两个算法的具体功能。
SEQSTRING fun2(SEQSTRING S, int n1, int n2) { //S为顺序存储的串变量 SEQSTRING T; int i; for(i=0;i<n2;i++) T.ch[i]=S.ch[n1+i-1]; T.len=n2; return(T); }
4. 字符串”VARTYPE int”，若采用动态分配的顺序存储方 A 法需要_______个字节（设每种数据均占用2个字节）。
A. 22 B. 11 C. 10 D. 动态产生，视情况而定
三、填空题
顺序存储结构 1. 串的两种最基本的存储方式是____________和 链式存储结构 ____________ 。 2. 串的链式存储结构是将存储区域分成一系列大小相同 数据 的节点，每个节点有两个域：____________域和 指针 ____________域。其中前者用于存储数据，后者用于 存储下一个节点的指针。
一、判断对错题
1. 串中不可以包含有空白字符。（ ×） 2. 子串是主串中字符构成的有限序列。（× ）
二、单项选择题
B 1. 串是一种特殊的线性表，其特殊性体现在_______。 A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以任意
二、单项选择题
C 2. 求字符串T在字符串S中首次出现的位置的操作为_______。 A. 求串的长度 A. 8 B. 37 B. 求子串 D. 9 C. 串的模式匹配 D. 串的连接 B 3. 若串S=”software”，其子串数目是_______。 C. 36
• 在顺序存储结构中，实现串操作的原操作为“字符序 列的复制”，操作的时间复杂度基于复制的字符序列 的长度。 • 在定长顺序存储表示中，如果在操作中出现串值序列 的长度超过上界MAXSTRLEN时，约定用截尾法处理；
• 这种情况不仅在求联接串时可能发生，在串的其它操 作中，如插入、置换等也可能发生。克服这个弊病只 有不限定串长的最大长度，即动态分配串值的存储空 间。
四、简答题
1. 简述串的存储结构及各自的特点。
• 定长顺序存储表示（静态存储分配的顺应表）：是用一组 连续的存储单元来存放串中的字符序列。
• 所谓定长顺序存储结构，是直接使用定长的字符数组来定 义，数组的上界预先给出： #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存串长
typedef struct{ char *ch; int length; }hsring;
• 这种存储结构表示时的串操作仍是基于“字符序列的 复制” 。例如，串复制操作StrCopy(&T, S)的实现算 法是，若串T已存在，则先释放串T所占空间，当串S 不空时，首先为串T分配大小和串S长度相等的存储空 间，然后将串S的值复制到串T中。 • 又如，串插入操作StrInsert(&S,pos,T)的实现算法是， 为串S重新分配大小等于串S和串T长度之和的存储空 间，然后进行串值复制。
s3 SubString( s1, StringLength( s2), StringLength( s2))
• StringLength(s2): 7; • s3=Substring(s1, 7, 7): “ghijklm”.
四、简答题
3. 分析下述两个算法的具体功能。
SEQSTRING fun1(SEQSTRING *S, seqstring *T) { //S和T为顺序存储的串变量 SEQSTRING *R; int i,j; 将串S与串T联接后赋值给R for(i=0;i<S->len;i++) R->ch[i]=S->ch[i]; for(j=0;j<=T->len;j++) R->ch[S->len+j]=T->ch[j]; R->len=i+j; return(R);
s3 SubString( s1, StringLength( s2), StringLength( s2))
四、简答题
2. 字符串s1=„abcdefghijklmnopqrstuvw‟，由如下运算分别得 到s2和s3，请给出s2和s3的值。
s 2 StringConcat( Substring( s1,19,3), SubString( s1,4,2), SubString( s1,14,1), Substring( s1,20,1)) • Substring(s1,19,3): „stu‟;
return(p->data-q->data);
p=p->next; q=q->next; } return s.curlen-t.curlen; //所有字符相同时则比较长度
}
结束
while ( p!=NULL )
{ q=r2-head; while( q!=NULL ) { if ( p->data==q->data ) { p1=p->next; q1=q->next;
while( p1->data==q1->data ) //当前字符相同 { p1=p1->next; q1=q1->next; } if ( q1==NULL ) pos=i+1; //匹配成功返回位置 } else q=q->next; } p=p->next; //从主串的下一个字符开始重新比较 i++; } re的特点。 • 串的块链存储表示：用链表存储串，每个结点存储串的n 个字符，当串长不是n的整数倍时最后一个结点剩余位置 用空字符＃补齐。 • 如串ABCDEFGHI当n=4时： head ABCD EF GH I # # # ^
• 当n=1时： head
A
B
C
I ^
return s.length-t.length; //所有字符相同时则比较长度
} 在此基础上进行修改！
• 比较两个串的大小 int strcmp(LinkString s, LinkString t){ p=s->head; q=t->head; for(i=0; i<s.curlen && i<t.curlen; ){ if(p->data!=q->data //每个字符两两比较