数据结构第四章课后习题以及解决第一个最长重复子串问题

#include<iostream>
#include<cstring>
#include<string>
#pragma warning(disable:4996)
using namespace std;
/****预定义****/
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef struct StringType {
char *ch;
int length;
int* next;
};
/*****串的基本操作****/
void init_Str(StringType &t,const char *chars)
{
int i = 0; const char *c = chars;
for (; *c; ++i, ++c);
if (!i) { t.ch = NULL; t.length = 0; }
else {
if (!(t.ch = (char*)malloc((i + 1) * sizeof(char))))
exit(OVERFLOW);
strcpy(t.ch, chars);
t.length = i;
t.ch[t.length] = '';
}
}
void show_Str(StringType &s)
{
for (int i = 0; i < s.length; i++)
{
cout << s.ch[i]<<" ";
}
cout << endl;
for (int i = 0; i < s.length; i++)
{
cout << s.next[i]<<" ";
}
cout << endl;
}
void StrAssign(StringType &t, StringType s)//将s的值赋给t
{


if (!s.length) { t.ch = NULL; t.length = 0; }
else {
if (!(t.ch = (char*)malloc(s.length * sizeof(char))))
exit(OVERFLOW);
strcpy(t.ch, s.ch);
t.length = s.length;
}
}
int StrCompare(StringType s, StringType t)//比较s和t
{
for (int i = 0; i < s.length&&i < t.length; ++i)
if (s.ch[i] != t.ch[i])return s.ch[i] - t.ch[i];
return s.length - t.length;
}
int StrLength(StringType s)//返回串的长度
{
return s.length;
}
StringType Concat(StringType s, StringType t)//返回由s和t连接而成的新串
{
StringType k;
if (!(k.ch = (char*)malloc((s.length + t.length+1) * sizeof(char))))
exit(OVERFLOW);
if (s.ch != NULL) 
{
strcpy(k.ch, s.ch);
}
else { 
strcpy(k.ch, "");//当s中的字符不存在值得话，需要一个初始值;
}
strcat(k.ch, t.ch);
k.length = s.length+t.length;
if (k.ch[k.length] != '')
{
k.ch[k.length] = '';
}
return k;
}
StringType SubString(StringType s, int start, int len)//返回第start个字符起长度为len的子串
{
StringType k;
if (!(k.ch = (char*)malloc((len+1) * sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<len;i++)
{
k.ch[i] = s.ch[start - 1 + i];
}
k.ch[len] = '';
k.length = len;
return k;
}
/******4.10******/
StringType Str_invertion(StringType &s)//对串求逆
{
StringType Inver_str,t; init_Str(Inver_str, ""); init_Str(t, "");
for(int i=s.length;i>0;i--)
{
t = SubString(s,i, 1);
Inver_str = Concat(Inver_str, t);
}
return Inver_str;
}
/******4.12******/
StringType Replace(StringType &S, StringType T, StringType V)//实现串的置换操作
{
int num=0;
StringType t,Res;  init_Str(t, ""); init_Str(Res, "");
for (int i = 0; i < S.length; i++)
{
if(!(i+T.length>S.length))
t = SubString(S, i+1, T.length);
if (!(StrCompare(t, T)))
{
i = i + T.length-1;
Res=Concat(Res, V);
}
else { 
t = SubString(S, i+1, 1);
Res = Concat(Res, t);
}
}
StrAssign(S, Res);
return S;
}
/********4.21********/
typedef struct ListStr
{
char word;
ListStr* next;
ListStr* succ;
};
void Show_L(ListStr* &L)
{
ListStr* original = L;
L = L->next;
while (L!=NULL)
{
cout << L->word;
L = L->next;
}
cout << endl;
L = original->next;
while (L != NULL)
{
if (L->succ == original)
{
cout << L->succ->next->word;
}
else { cout << L->succ->word; }
L = L->next;
}
cout << endl;
L = original;
}
void StrAssign(struct ListStr* &L,const char *word1)//串链表初始化并赋值
{
L = (ListStr*)malloc(sizeof(ListStr)); ListStr* original = L;
L->next = NULL;
int num = strlen(word1);
for (int i = 0; i < num; i++)
{
ListStr* tmp = (ListStr*)malloc(sizeof(ListStr));
tmp->word = *word1;
L->next = tmp; L = L->next; word1++;
}
L->next = NULL;
L = original;
}
int StrCompare(ListStr* &s, ListStr* &t)//对串链表构建的两个串进行比较
{
ListStr* original1 = s, *original2 = t;
while (s != NULL && t != NULL)
{
if (s->word != t->word)
{
return s->word - t->word;
}
else {
s = s->next;
t = t->next;
}
}
if (s == NULL && t == NULL) { return 0; }
else if (s != NULL) { return s->word; }
else { return t->word; }
s = original1; t = original2;
}
int StrLength(ListStr* &s)//获得串链表中串的字符长度
{
ListStr* original = s; s = s->next;
int length = 0;
while (s != NULL)
{
length++;
s = s->next;
}
s = original;
return length;
}
ListStr* Concat(ListStr* &s, ListStr* &t)//返回由s和t连接而成的新串
{
ListStr* original = s;
while (s->next != NULL)
{
s = s->next;
}
s->next = t->next;
return original;
}
ListStr* SubString(ListStr* &s, int start, int len)//返回s中第start个字符起长度为len的子串
{
ListStr* original = s,*s1=(ListStr*)malloc(sizeof(ListStr)),*tmp;
s1->next = NULL; ListStr* original1 = s1;
s = s->next; int index = 0, length = 0;
while (s != NULL)
{
index++;
if (index == start)
{
tmp = (ListStr*)malloc(sizeof(ListStr));
tmp->word = s->word;
s1->next = tmp; s1 = s1->next;
length++; start++;
if(length==len)
{
break;
}
}
s = s->next;
}
s1->next = NULL;
return original1;
}
/*****4.28*****/
void get_LNext(ListStr* &s)//求链表表示的串的next函数值
{
ListStr* original = s,*j;
s = s->next; s->succ = original; j = original;
while (s->next != NULL)
{
if ( j == original || s->word == j->word ) 
{
s = s->next;
j = j->next;
s->succ = j;
}
else
{
j = j->succ;
}
}
s = original;
}
/*****4.29*****/
int index_KMP(ListStr* &s, ListStr* &t, int pos)//链表表示串的KMP串匹配算法
{
ListStr* original1 = s, *original2 = t;
int position=pos;
int length = StrLength(t);
t = t->next;
for(int i=0;i<pos;i++)
{
s = s->next;
}
while (s != NULL && t!=NULL)
{
if (s->word == t->word || t ==original2)
{
s = s->next;
t = t->next;
position++;
}
else {
t = t->succ;
}
}
if (s == NULL) { return 0; }
if (t == NULL) { return position - length; }
}
/*****4.30*****/
void get_next(StringType &t)//得到串的next函数值
{
t.next = (int*)malloc(t.length * sizeof(int));
t.next[0] = 0; int i = 0, j = 0;
while (i < t.length)
{
if (j==0||t.ch[i] == t.ch[j-1])
{
i++;
j++;
t.next[i] = j;
}
else {
j = t.next[j-1];
}
}
}
struct max_next
{
int * max;
int* index;
}max_next;
/******此算法在于解决判断第一个最长重复子串的位置，并灵活使用next函数值解决问题。
核心在于next函数值反应的是串中重复的字符个数，故通过next函数将字符串一个个分解开来，
如将banana 分解为“banana”，“anana”，“nana”...
依次求出他们的子串next函数值，最大值即为，最长重复子串，从后往前遍历，出现最后的最大值
即为第一个最长重复子串的位置************/
int judge_str(StringType &t)//判断第一个最长重复子串并返回其位置
{
max_next.max = (int*)malloc(t.length * sizeof(int)); 
max_next.index = (int*)malloc(t.length * sizeof(int));
int real_max=0,index=0;
for (int i = 0; i < t.length; i++)//对记录各个子串的最大next值进行初始化
{
max_next.max[i] = 0;
}
StringType k;
for(int i=1;i<=t.length;i++)//分别求出串中从头开始各子串的最大next值
{
k=SubString(t, i, t.length - i+1);//求各子串
get_next(k);
for (int j = 0; j < k.length; j++)
{
if (k.next[j] > max_next.max[i-1])  max_next.max[i-1] = k.next[j];//确定各子串最大值;
}
for (int j = 0; j < k.length; j++)
{
if (k.next[j] == max_next.max[i - 1])  max_next.index[i-1]=j;//确定最大max值的下标
}
}
for (int i = 0; i < t.length; i++)
{
if (max_next.max[i] > real_max) real_max = max_next.max[i];//得到各子串重复最大值中的最大值
}
for (int i = t.length-1; i >=0; i--)
{
if (max_next.max[i] == real_max) { index = i; }//得到重复最大值子串的头子符所在下标;
}
if (t.ch[max_next.index[index]] != t.ch[real_max-1])
{
real_max--;//由于next函数值无法比较当前字符是否重复，故需人工比较;
}
for (int i =index; i <(index+real_max); i++)
{

cout << t.ch[i];
}
cout << endl;
return index+1;
}
void main() 
{
/*****4.10*****/
/*StringType t, s;
init_Str(t, "abcd"); init_Str(s,"efgh"); 
t = Concat(t, s); show_Str(t);
t = Str_invertion(t); show_Str(t);*/

/*****4.12*****/
/*StringType S, T,V;
init_Str(S, "abcdcdabc"); show_Str(S);
init_Str(T, "abcd"); init_Str(V, "kc");
Replace(S, T, V); show_Str(S);*/

/*****4.21******/
/*ListStr* S; ListStr* t;
StrAssign(S, "abcdefg"); StrAssign(t, "abce");
S = SubString(S,2,4); Show_L(S);*/


/*****4.28******/
/*ListStr* S; StrAssign(S, "abcaabbabcabaacbacba");
ListStr* T; StrAssign(T, "cba");
get_LNext(T);Show_L(T);
int num = index_KMP(S, T, 1); cout << num << endl;*/


/*****4.30*****/
StringType S; init_Str(S, "GEEKSFORGEEKS"); get_next(S);
show_Str(S); 
judge_str(S);
system("pause");
}

最后

以上就是典雅彩虹为你收集整理的数据结构第四章课后习题以及解决第一个最长重复子串问题的全部内容，希望文章能够帮你解决数据结构第四章课后习题以及解决第一个最长重复子串问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。