求数据结构（c语言版）程序源代码

Question

给定两个字串X和Y①求子串Z在主串中的所有位置，并记录②找出X和Y的一个最长公共子串③置换①所定位的所有子串

Answer 1

1 #include <string.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 #define MAX_POS_NUM 100
6 #define MAX_STR_LEN 1024
7
8
9 //1. get all position of str_z in str_x
10 int get_sub_str_pos(const char * str_x, const char * str_z, int sub_str_pos[])
11 {
12 if (NULL == str_x || NULL == str_z)
13 {
14 printf("in error!\n");
15 return -1;
16 }
17
18 const char * pos_ptr = NULL;
19
20 pos_ptr = strstr(str_x,str_z);
21
22 int i=0;
23 while(pos_ptr)
24 {
25 printf("substring positon:%d\n",pos_ptr-str_x+1);
26 sub_str_pos[i] = pos_ptr - str_x + 1;
27 pos_ptr = strstr(pos_ptr+strlen(str_z),str_z);
28 i++;
29 }
30
31 return 0;
32 }
33
34 //2. get max length common string of str_x and str_y
35 char * get_max_com_str(const char * str_x, const char * str_y)
36 {

37 int x_len = strlen(str_x);
38 int y_len = strlen(str_y);
39
40 char * tmp_str = new char[y_len+1];
41
42 for(int i=y_len; i>0; i--) // i is substring length
43 {
44 if (i>x_len)
45 continue;
46 for(int j=0;j<=y_len-i; j++) // j is substring start postion
47 {
48 snprintf(tmp_str,i+1,"%s",str_y);
49 if (strstr(str_x,tmp_str))
50 {
51 printf("%s\n",tmp_str);
52 printf("max common substring length:%d\n",i);
53 return tmp_str;
54 }
55 }
56 }
57
58 return NULL;
59 }
60
61 //3. replace all substring in question 1
62 char * replace_sub_str(const char * str_x, char * max_com_str, int sub_str_pos[], int sub_str_len)
63 {
64 char * replaced_str = new char[MAX_STR_LEN];
65
66 int sub_pos = sub_str_pos[0];
67 int l=0; // l is sub_str_pos index
68 int i=0,j=0; //i is str_x pos, j is replaced_str pos
69
70 while(*str_x)

71 {
72 if (i==sub_pos-1) // replace from this position
73 {
74 // printf ("i:%d,\n",i);
75 for (int k=0; k<strlen(max_com_str); k++)
76 {
77 *(replaced_str + j) = * (max_com_str + k);
78 j++;
79 }
80 i += sub_str_len;
81 str_x += sub_str_len;
82 l++;
83 sub_pos = sub_str_pos[l];
84 continue;
85 }
86 *(replaced_str+j) = *str_x++;
87 i++;
88 j++;
89 }
90
91 * (replaced_str + j) = '\0';
92
93 return replaced_str;
94 }
95
96 int main()
97 {
98 const char * str_x = "abcabcabc";
99 const char * str_y = "cabcd";
100 const char * str_z = "abc";
101
102 int sub_str_pos [MAX_POS_NUM] = {0};
103
104 char * max_com_str = NULL;

105
106 char * replaced_str = NULL;
107
108 get_sub_str_pos(str_x,str_z,sub_str_pos);
109 max_com_str = get_max_com_str(str_x,str_y);
110
111 printf("max common str: %s\n",max_com_str);
112
113 replaced_str = replace_sub_str(str_x, max_com_str, sub_str_pos, strlen(str_z));
114 printf("repalced str: %s\n",replaced_str);
115
116 return 0;
117 }

Answer 2

#include<stdio.h>
#include<string.h>

char str_host[100];//主串
char str_x[100];//字符串X
char str_y[100];//字符串Y
char str_z[100];//字符串Z

void subpos(char *str_host,char *str_z,int *pos)
{//求串Z在主串中的所有位置，记录在pos[]数组中
//pos[0]用来记录，位置的个数；从pos[1]开始记录位置
int i,j;
int len_host,len_z;//表示长度
len_host=strlen(str_host);
len_z=strlen(str_z);

for(i=0;i<=len_host-len_z;i++)
{//对主串中，每个位置开始匹配，看能否构成子串
for(j=0;j<len_z;j++)
{
if(str_host[i+j]!=str_z[j])
break;
}
if(j==len_z)
{
pos[0]++;
pos[pos[0]]=i+1;
}
}
}

void subxy(char *str_x,char *str_y,char *str_sub_xy)
{//对X中的所有子串，按长度从长到短，判断是否同时是Y的子串；
//取长度最长的子串，为题目要求
//str_sub_xy记录公共子串
int len_x,len_y,len,curlen;
int i,j,k;
len_x=strlen(str_x);
len_y=strlen(str_y);
len=len_x>len_y?len_x:len_y;//len为x,y中短串的长度；

curlen=len;//表示当前用于匹配的子串长度；
while(curlen--)
{
for(i=0;i+curlen<=len_x;i++)
{//按长度，从长到短，取子串
for(j=i;j<i+curlen;j++)
str_sub_xy[j-i]=str_x[j];
str_sub_xy[j-i]='\0';

if(strstr(str_y,str_sub_xy)!=NULL)
{//如果该子串同时是Y子串
curlen=-1;//用于退出while
break;
}
}
}
if(curlen==-1)
{//则表明没找到匹配子串
str_sub_xy[0]='\0';
}
}

void replace(char *str_host,char *str_rep,int len,int *pos)
{//len表示转换的子串长度，即Z串长度；
int i,j,num;//num表示要转换的个数，即pos[0]
int len_host,len_rep;
len_host=strlen(str_host);
len_rep=strlen(str_rep);

num=pos[0];

for(i=0;i<num;i++)
{
for(j=pos[i]-1;j<len_rep;j++)
{
str_host[j]=str_rep[j-(pos[i]-1)];
}
}

}

void main()
{
int pos[100];//Z在主串中位置
char str_sub_xy[100];//公共子串
char str_rep[100];//用于转换Z的子串，其实际长度应该与Z同；
int len;

memset(pos,0,100*sizeof(int));//初始化为0

scanf("%s%s%s%s%s",str_host,str_x,str_y,str_z,str_rep);
len=strlen(str_z);

subpos(str_host,str_z,pos);
subxy(str_x,str_y,str_sub_xy);
replace(str_host,str_rep,len,pos);

}