《數(shù)據(jù)結構教程習題答案 李蓉蓉 安楊等編著第三版 第四章練習題答案》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構教程習題答案 李蓉蓉 安楊等編著第三版 第四章練習題答案（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、4.1
/*********************************************
題目：采用順序結構存儲串，編寫一個實現(xiàn)串通配符匹配的算法，pattern_index()其中的通配符只有“?”它可以和任意一字符匹配成功，例如pattern_index("?re", "there are")返回的結果是2
實踐;狼影
時間：2012.9.23
************************************************************/
/*********************************************
2、*
若發(fā)現(xiàn)源碼有錯或高人有更好的方式，請留言本人的空間，你的留言將是對我學習的最大幫助，感激不盡
******************************************************/
# include
# include
# include
# define size 256
typedef struct
{
char string[size];
int length;
}STRING;
//函數(shù)的聲明
STRING *init_string(void);
3、
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
4、(0 == n)
printf("沒有匹配的字符串\n");
else
printf("匹配的有%d個\n", n);
}
//初始化字符串
STRING *init_string(void)
{
STRING *st;
st = (STRING *)malloc(sizeof(STRING));
if(NULL == st)
{
printf("內(nèi)存分配錯誤\n");
exit(-1);
}
st->length = 0;
return st;
}
//輸入字符串
void creat_string(STRI
5、NG *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->string[i] == t->string[j] || '?' == t->string[j])
{
i++;
j++;
}
else
{
i = i-j+1
6、;
j = 0;
}
//計算符合要求字串的個數(shù)
if(j>=t->length)
{
n++;
j = 0;
}
}
return n;
}
/*********************************
輸入主串,
there are many boy are are
輸入模式串
?re
匹配的有4個
Press any key to continue
***********************************************/
4.2
/*****************
7、*******************
題目：有兩個串s1和s2，設計一個算法求一個這樣的串，該串的字符是s1和s2中公共字符
設計;狼影
時間：2012.9.23
*****************************************/
/*****************************************************************************************
若發(fā)現(xiàn)源碼有錯，或高人有更好的方法，請在本人百度空間留言，感激不盡，，你的留言將是對我學習的最大幫助?。?
******************
8、*******************************************************************/
# include
# include
# include
# define size 256
typedef struct
{
char string[size];
int length;
}STRING;
//函數(shù)的聲明
STRING *init_string(void);
void creat_string(STRING *st);
int
9、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)
{
10、 printf("相同的字符是\n");
printf("%s\n", s3->string);
}
else
printf("沒有相同的字符\n");
}
//初始化字符串
STRING *init_string(void)
{
STRING *st;
st = (STRING *)malloc(sizeof(STRING));
if(NULL == st)
{
printf("內(nèi)存分配錯誤\n");
exit(-1);
}
st->length = 0;
return st;
}
//創(chuàng)建字符串
voi
11、d creat_string(STRING *st)
{
printf("輸入字符串\n");
gets(st->string);
st->length = strlen(st->string);
}
//發(fā)現(xiàn)相同的字符
int find_same(STRING *s1, STRING *s2, STRING *s3)
{
int i, j, k = 0, d;
int find = 0;
//下面的三重循環(huán)尋找相同的字符，并保證輸入的字符不重復有些麻煩，若有好的方法，希望告知！
for(i = 0; ilength; i++)
{
12、
for(j = 0; jlength; j++)
{
if(s1->string[i] == s2->string[j])
{
for(d = 0; d<=k; d++)
if(s3->string[d] == s1->string[i])
{
find = 1;
goto end;
}
s3->string[k++] = s1->string[i];
}
end: if(1 == find)
{
find = 0;
break;
13、 }
}
}
s3->string[k] = '\0';
return k;
}
/***********************************
輸入字符串
asdfghdffsafg
輸入字符串
asfd
相同的字符是
asdf
Press any key to continue
*****************************************************/
4.3
/***************************************
題目：設目標串為t = 'abcaabbab
14、cabaacbacba' 模式p = 'abcabaa'
(1):計算p的nextval函數(shù)值
(2):不寫算法，只畫出KMP算法進行模式匹配時，每一趟的匹配過程（??！此題，讀者自己去畫，下面只是KMP算法的代碼實現(xiàn)）
(課本上喲相關的畫法，大可參照課本111頁來畫)
實踐;狼影
時間：2012.9.23
*****************************************/
/*************************************************
若發(fā)現(xiàn)源碼錯誤，請在本人百度空間留言，你的留言將是對我學習的最大幫助
15、，感激不盡!!
*******************************************************************************/
# include
# include
# include
# define size 256
typedef struct
{
char string[size];
int length;
}STRING;
//函數(shù)的聲明
STRING *init_string(char *p);
int KMP(STRING
16、*s1, STRING *s2);
void call_nextval(STRING *s, int *nextval);
main()
{
STRING *s1, *s2;
int n;
char *t = "abcaabbabcabaacbacba";
char *p = "abcabaa";
//初始化字符數(shù)組
s1 = init_string(t);
s2 = init_string(p);
n = KMP(s1, s2);
if(-1 == n)
printf("沒有匹配的字串\n");
else
printf("
17、匹配字串起始的下標是%d\n", n);
}
//初始化字符數(shù)組
STRING *init_string(char *p)
{
int i = 0;
STRING *st = (STRING *)malloc(sizeof(STRING));
if(NULL == st)
{
printf("內(nèi)存分配錯誤\n");
exit(-1);
}
while(p[i] != '\0')
{
st->string[i] = p[i];
i++;
}
st->string[i] = '\0';
st->length = i;
18、return st;
}
//KMP算法的實現(xiàn)
int KMP(STRING *s1, STRING *s2)
{
int nextval[size];
int differ = 0;
int i = -1, j = -1;
call_nextval(s2, nextval);
while(ilength && jlength)
{
if(j == -1 || s1->string[i]==s2->string[j])
{
i++;
j++;
}
else
j = nextval[j
19、];
}
if(j>=s2->length)
return (i-s2->length);
else
return -1;
}
//求nextval數(shù)組
void call_nextval(STRING *s, int *nextval)
{
int i = 0, j = -1;
nextval[0] = -1;
//求nextval的值
while(ilength)
{
if(-1==j || s->string[i] == s->string[j])
{
i++; j++;
if(s->stri
20、ng[i] != s->string[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
}
//輸出nextval的值
printf("nextval的值是\n");
for(i = 0; ilength; i++)
{
printf("%d ", nextval[i]);
}
printf("\n");
}
/**********************************
nextval的值是
-1 0 0 -1 0 2 1
匹配字串起始的下標是7
Press any key to continue
*************************************************/
數(shù)據(jù)結構教程習題答案 李蓉蓉 安楊等編著第三版 第四章練習題答案
