数据结构教程习题答案 李蓉蓉 安杨等编著第三版 第四章练习题答案.doc

4.1/*题目：采用顺序结构存储串，编写一个实现串通配符匹配的算法，pattern_index()其中的通配符只有“?”它可以和任意一字符匹配成功，例如pattern_index(?re, there are)返回的结果是2实践;狼影时间：2012.9.23*/*若发现源码有错或高人有更好的方式，请留言本人的空间，你的留言将是对我学习的最大帮助，感激不尽*/# include # include # include # define size 256typedef struct char stringsize;int length;STRING;/函数的声明STRING *init_string(void);void creat_string(STRING *st);int pattern_index(STRING *t, STRING *s);main()STRING *s, *t;int n;s = init_string();t = init_string();/输入字符串printf(输入主串,n);creat_string(s);fflush(stdin);printf(输入模式串n);creat_string(t);n = pattern_index(t, s);if(0 = n)printf(没有匹配的字符串n);elseprintf(匹配的有%d个n, n);/初始化字符串STRING *init_string(void)STRING *st;st = (STRING *)malloc(sizeof(STRING);if(NULL = st)printf(内存分配错误n);exit(-1);st-length = 0;return st;/输入字符串void creat_string(STRING *st)gets(st-string);st-length = strlen(st-string);/字符串匹配int pattern_index(STRING *t, STRING *s)int i = 0, j = 0;int n = 0;while(ilength)if(s-stringi = t-stringj | ? = t-stringj)i+;j+;elsei = i-j+1;j = 0;/计算符合要求字串的个数if(j=t-length)n+;j = 0;return n;/*输入主串,there are many boy are are输入模式串?re匹配的有4个Press any key to continue*/4.2/*题目：有两个串s1和s2，设计一个算法求一个这样的串，该串的字符是s1和s2中公共字符设计;狼影时间：2012.9.23*/*若发现源码有错，或高人有更好的方法，请在本人百度空间留言，感激不尽，你的留言将是对我学习的最大帮助！*/# include # include # include # define size 256typedef struct char stringsize;int length;STRING;/函数的声明STRING *init_string(void);void creat_string(STRING *st);int find_same(STRING *s1, STRING *s2, STRING *s3);main()STRING *s1, *s2, *s3;int n;/申请空间s1 = init_string();s2 = init_string();s3 = init_string();/输入字符串creat_string(s1);fflush(stdin);creat_string(s2);/寻找相同的字符n = find_same(s1, s2, s3);if(0 != n)printf(相同的字符是n);printf(%sn, s3-string);elseprintf(没有相同的字符n);/初始化字符串STRING *init_string(void)STRING *st;st = (STRING *)malloc(sizeof(STRING);if(NULL = st)printf(内存分配错误n);exit(-1);st-length = 0;return st;/创建字符串void creat_string(STRING *st)printf(输入字符串n);gets(st-string);st-length = strlen(st-string);/发现相同的字符int find_same(STRING *s1, STRING *s2, STRING *s3)int i, j, k = 0, d;int find = 0;/下面的三重循环寻找相同的字符，并保证输入的字符不重复有些麻烦，若有好的方法，希望告知！for(i = 0; ilength; i+)for(j = 0; jlength; j+)if(s1-stringi = s2-stringj)for(d = 0; dstringd = s1-stringi)find = 1;goto end;s3-stringk+ = s1-stringi;end:if(1 = find)find = 0;break;s3-stringk = 0;return k;/*输入字符串asdfghdffsafg输入字符串asfd相同的字符是asdfPress any key to continue*/4.3/*题目：设目标串为t = abcaabbabcabaacbacba 模式p = abcabaa(1):计算p的nextval函数值(2):不写算法，只画出KMP算法进行模式匹配时，每一趟的匹配过程（！此题，读者自己去画，下面只是KMP算法的代码实现）(课本上哟相关的画法，大可参照课本111页来画)实践;狼影时间：2012.9.23*/*若发现源码错误，请在本人百度空间留言，你的留言将是对我学习的最大帮助，感激不尽!*/# include # include # include # define size 256typedef structchar stringsize;int length;STRING;/函数的声明STRING *init_string(char *p);int KMP(STRING *s1, STRING *s2);void call_nextval(STRING *s, int *nextval);main()STRING *s1, *s2;int n;char *t = abcaabbabcabaacbacba;char *p = abcabaa;/初始化字符数组s1 = init_string(t);s2 = init_string(p);n = KMP(s1, s2);if(-1 = n)printf(没有匹配的字串n);elseprintf(匹配字串起始的下标是%dn, n);/初始化字符数组STRING *init_string(char *p)int i = 0;STRING *st = (STRING *)malloc(sizeof(STRING);if(NULL = st)printf(内存分配错误n);exit(-1);while(pi != 0)st-stringi = pi;i+;st-stringi = 0;st-length = i;return st;/KMP算法的实现int KMP(STRING *s1, STRING *s2)int nextvalsize;int differ = 0;int i = -1, j = -1;call_nextval(s2, nextval);while(ilength & jlength)if(j = -1 | s1-stringi=s2-stringj)i+;j+;elsej = nextvalj;if(j=s2-length)return (i-s2-length);elsereturn -1;/求nextval数组void call_nextval(STRING *s, int *nextval)int i = 0, j = -1;nextval0 = -1;/求nextval的值while(ilength)if(-1=j | s-stringi = s-stringj)i+; j+;if(s-stringi != s-stringj)nextvali = j;elsene