[串](3)题集_2
21、假设以结点大小为1(带头结点)的链表结构表示串，试编写实现下列六中串的基本操作StrAssign，Strcopy，StrCompare，StrLength，Concat和SubString的函数
typedef struct String
{
char ch;
int length;
struct String* next;
}String, * StrList;
int main()
{
InitList(&S);
InitList(&T);
char *a = { "abcdefghij" };
char *b = { "lmnopqrstu" };
return 0;
}
void InitList(StrList *L)
{
*L = (StrList)malloc(sizeof(String));
(*L)->length = 0;
if (L == NULL)
{
exit(0);
}
(*L)->next = NULL;
}
void InfoStrList(StrList *L, char e)
{
StrList p;
p = *L;
node = (StrList)malloc(sizeof(String));
node->ch = e;
(*L)->length++;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
node->next = NULL;
}
void StrAssign(StrList* L ,char* e)
{
int i;
for (i = 0; e[i]!= NULL; i++)
{
InfoStrList(L, e[i]);
}
}
int StrLength(StrList *L)
{
return (*L)->length;
}
void StrCopy(StrList *S, StrList* T)
{
if ((*S)->length == 0 || (*S)->ch == NULL)
{
exit(0);
}
InitList(T);
StrList p = (*S)->next;
while (p != NULL)
{
InfoStrList(T, p->ch);
p = p->next;
}
}
int StrCompare(StrList* S, StrList* T)
{
StrList p = (*S)->next, s = (*T)->next;
while (p != NULL && s != NULL)
{
if (p->ch > s->ch)
{
return 1;
}
if (p->ch < s->ch)
{
return -1;
}
p = p->next;
s = s->next;
}
if (p == NULL)
{
return -1;
}
if (s == NULL)
{
return 1;
}
return 0;
}
StrList Concat(StrList* S, StrList* T)
{
StrList V;
InitList(&V);
StrList p,s;
p = (*S)->next;
s = V;
while (p != NULL)
{
s->next=p;
s=s->next;
V->length++;
p = p->next;
}
p= (*T)->next;
while (p != NULL)
{
s->next=p;
s=s->next;
V->length++;
p = p->next;
}
s->next=NULL;
return V;
}
char* SubString(StrList* S,int pos,int len)
{
StrList p = *S;
char* temp = (char*)malloc(sizeof(char) * len);
if (p->next == NULL || pos > p->length || pos < 1 || len < 1 || p->length - pos < len)
{
exit(0);
}
for (int i = 0; i < pos; i++)
{
p = p->next;
}
for (int j = 1; j <= len; j++)
{
temp[j] = p->ch;
p = p->next;
}
return temp;
}22、假设以块链结构表示串，试编写将串s插入到串t中某个字符之后的算法，若串t中不存在此字符，则将串s联接到串t末尾
思路：用这个字符变量遍历整个链表元素，如果有相等的则退出循环，然后判断循环是否走完，指向插入操作
void StrInsert(StrList* S, StrList* T, char e)
{
StrList p,p1;
p = *S;
p1 = *T;
if (p->next == NULL || p1->next == NULL)
{
exit(0);
}
while (p1->next != NULL)
{
p1 = p1->next;
}
while (p->ch != e && p->next != NULL)
{
p = p->next;
}
p1->next = p->next;
p->next = (*T)->next;
}23、假设以块链结构表示串。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S))
利用双向循环链表，双指针开始判断，直到两指针相遇
void SymmetryStr(StrList* S)
{
StrList p, s;
p = (*S)->next;
s = (*S)->prev;
if (p == NULL)
{
exit(0);
}
while (s->next != p && s != p)
{
if (p->ch == s->ch)
{
p = p->next;
s = s->prev;
}
else
{
printf("FALSE");
return 0;
}
}
printf("TRUE");
system("pause");
}
//时间复杂度为O(StrLength(S)/2)24、试写一算法，在串的堆存储结构上实现串的基本操作Concat(&T,s1,s2)
void Concat(String* T, String s1, String s2)
{
T->ch = (char*)malloc(sizeof(char) * (s1.length + s2.length+1));
T->length = 0;
int i, j;
for (i = 1; i <= s1.length; i++)
{
T->ch[i] = s1.ch[i];
T->length++;
}
for (j = 1; j <= s2.length; j++, i++)
{
T->ch[i] = s2.ch[j];
T->length++;
}
}25、试写一算法，实现堆存储结构上的Replace(&S,T,V)
测试代码如下所示：
int Index_KMP(String* S, String* T)
{
int* next = next_arr(T);
int i = 1,j = 1;
while (i <= S->length && j <= T->length)
{
if (j == 0 || S->ch[i] == T->ch[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j > T->length)
{
return i - T->length;
}
else
{
return 0;
}
}
int* next_arr(String* T)
{
int* next = (int*)malloc(sizeof(int) * (T->length+1));
int i = 1, j = 0;
next[i] = 0;
while (i <= T->length)
{
if (j == 0 || T->ch[i] == T->ch[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
return next;
}
void StrInsert(String* S, int pos, String T)
{
if (pos<1 || pos>S->length + 1)
{
exit(0);
}
S->ch = (char*)realloc(S->ch, sizeof(char) * (T.length + S->length + 2));
for (int i = S->length,j=T.length; i >= pos; i--)
{
S->ch[i+j] = S->ch[i];
}
for (int i = pos, j = 1; j <= T.length; i++, j++)
{
S->ch[i] = T.ch[j];
}
S->length += T.length;
}
void StrDelete(String* S, int pos, int len)
{
if (pos<1 || pos>S->length + 1 || len < 0)
{
exit(0);
}
for (int i = pos + len, j = pos; i <= S->length; i++, j++)
{
S->ch[j] = S->ch[i];
}
S->length -= len;
}
void Replace(String* S, String *T, String V)
{
int count = Index_KMP(S, T);
while (count)
{
StrDelete(S, count, T->length);
StrInsert(S, count, V);
count = Index_KMP(S, T);
}
}26、试写一算法，实现堆存储结构串的插入操作StrInsert(&S,pos,T)
void StrInsert(String* S, int pos, String T)
{
if (pos<1 || pos>S->length + 1)
{
exit(0);
}
S->ch = (char*)realloc(S->ch, sizeof(char) * (T.length + S->length + 2));
for (int i = S->length,j=T.length; i >= pos; i--)
{
S->ch[i+j] = S->ch[i];
}
for (int i = pos, j = 1; j <= T.length; i++, j++)
{
S->ch[i] = T.ch[j];
}
S->length += T.length;
}注意：在使用realloc或malloc函数重新分配内存的时候，我们的元素是从1开始存储，则需要分配长度加1的内存！
27、当以定长顺序结构表示串时，可如下所述改进Index：先将模式串t中的第一个字符和最后一个字符与主串s中相应的字符比较，在两次比较都相等之后，再依次从t的第二个字符起逐个比较，这样做可以克服算法IndexBF的弊病，试编写上述改进算法，并比较这两种算法在作Index运算时所需进行的字符间的比较次数
假设S=aaaaaab，T=aaab，的话，利用BF算法需要回溯四次，每次比较3次，因为只有前三个字符与S相等，到第四个字符的时候则需要回溯，则总共需要比较16次才能彻底成功
而改进后，比较首尾是否一样，则总共需要比较十次就可以匹配成功，如下所示：
int Index_newBF(String S, String T)
{
int i = 1, j = 1;
while (i <= S[0] && j <= T[0])
{
if ((j != 1 && S[i] == T[j]) || (j == 1 && S[i] == T[j] && S[i + T[0] - 1] == T[T[0]]))
{
i++;
j++;
}
else
{
i = i - j + 2;
j = 1;
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}当j不等于第一位的时候，就等于匹配成功了，则比较后续的字符，不需要尾端字符相等，if的条件就是改进算法的精髓之处
28、假设以结点大小为1(带头结点)的链表结构表示串，则利用next函数值进行串匹配时，在每个结点中需设三个域：数据域chdata、指针域succ和指针域next，其中数据域中存放一个字符，succ域存放指向同一链表中的后继结点指针，next域在主串中存放指向同一链表中前驱结点的指针，在模式串中，存放指向当该结点的字符与主串中的字符不等时，模式串中的下一个应进行比较的字符结点(即与该结点字符的next函数值相对应的字符结点)的指针，若该结点字符的next函数值为零，则其next域的值应该指向头节点，试按上述定义的结构改写模式串next函数值的算法
29、按照上题结构写出KMP算法
两题测试代码如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct String
{
char ch;
int length;
struct String* succ;
struct String* next;
}String,*StrList;
StrList node;
int Index_KMP(StrList* S, StrList* T, int pos);
void InitString(StrList* L);
void StrAssign(StrList* L, char* a);
void InfoString(StrList* L, char a);
void next_List(StrList* T);
int Index_KMP(StrList* S, StrList* T, int pos);
void visit(StrList S)
{
StrList p;
p = S->succ;
while (p != NULL)
{
printf("%c", p->ch);
p = p->succ;
}
printf("\n");
}
int main()
{
StrList s, t;
InitString(&s);
InitString(&t);
StrAssign(&s, "ACCABBACCABA");
StrAssign(&t, "ABA");
visit(s);
visit(t);
printf("%d",Index_KMP(&s, &t, 1));
system("pause");
return 0;
}
void InitString(StrList* L)
{
*L = (StrList)malloc(sizeof(String));
(*L)->next = NULL;
(*L)->succ = NULL;
(*L)->length = 0;
}
void StrAssign(StrList* L, char* a)
{
int i;
for (i = 0; a[i]; i++);
for (int j = 1; j <= i; j++)
{
InfoString(L, a[j - 1]);
(*L)->length++;
}
}
void InfoString(StrList* L, char a)
{
node = (StrList)malloc(sizeof(String));
node->ch = a;
StrList p = (*L);
while (p->succ != NULL)
{
p = p->succ;
}
node->succ = NULL;
node->next = p;
p->succ = node;
}
void next_List(StrList* T)
{
StrList i, j;
j = (*T);
i = (*T)->succ;
i->next = (*T);
while (i->succ != NULL)
{
if (j == *T || i->ch == j->ch)
{
i = i->succ;
j = j->succ;
i->next = j;
}
else
{
j = j->next;
}
}
}
int Index_KMP(StrList* S, StrList* T, int pos)
{
if (pos<1 || pos>(*T)->length)
{
exit(0);
}
StrList s, p;
int count = 1;
next_List(T);
s = (*S);
p = (*T)->succ;
for (int i = 1; i <= pos; i++)
{
s = s->succ;
}
while (s != NULL && p != NULL)
{
if (p == (*T) || s->ch == p->ch)
{
p = p->succ;
s = s->succ;
count++;
}
else
{
p = p->next;
}
}
if (p == NULL)
{
return count - (*T)->length;
}
else
{
return 0;
}
}30、假设以定长顺序存储结构表示串，试设计一个算法，求串s和串t中出现的第一个最长重复子串及其位置，并分析你的算法的时间复杂度
void Get_LRepSub(String S)
{
int maxlen, i, j, lrs1, lrs2, k;
for (maxlen = 0, i = 1; i < S[0]; i++)
{
for (k = 0, j = 1; j <= S[0] - i; j++)
{
if (S[j] == S[j +i])
{
k++;
}
else
{
k = 0;
}
if (k > maxlen)
{
lrs1 = j - k + 1;
lrs2 = lrs1 + i;
maxlen = k;
}
}
}
printf("%d,%d,%d", lrs1, lrs2, maxlen);
}这是一个枚举暴力算法
把所有可能的子串全部尝试一遍，i控制着错位和j尝试的边界，遍历次数必须是j+i<S[0]。
31、假设以定长顺序存储结构表示串、试设计一个算法，求串s和串t的最长公共子串，并分析你的算法的时间复杂度，若要求第一个出现的最长公共子串(即它在串s和串t的最左边的位置上出现)和所有的最长公共子串，讨论呢的算法能否实现
书本的答案以错位来找寻，对于我来说，很难理解，我采用dp求解，定义一个二维数组作为状态变量。算法如下：时间复杂度为O(n*m)
void Get_LPubSub(String S, String T)
{
int maxlen = 0, i, j, k = 0;
int** f = (int**)malloc(sizeof(int*) * S[0]);
for (int i = 0; i <= S[0]; i++)
{
*(f+i) = (int*)malloc(sizeof(int) * T[0]);
}
for (int i = 0; i <= S[0]; i++)
{
f[i][0] = 0;
}
for (int i = 0; i <= T[0]; i++)
{
f[0][i] = 0;
}
//初始化
struct BOX
{
int lrs1;
int lrs2;
int maxlen;
}BOX[100];
for (i = 1; i <= S[0]; i++)
{
for (j = 1; j <= T[0]; j++)
{
if (S[i] == T[j])
{
f[i][j] = f[i - 1][j - 1] + 1;
}
else
{
f[i][j] = 0;
}
if (f[i][j] >= maxlen)
{
maxlen = f[i][j];
BOX[k].lrs1 = i - maxlen + 1;
BOX[k].lrs2 = j - maxlen + 1;
BOX[k].maxlen = maxlen;
k++;
}
}
}
for (int i = k - 1; i >= 0; i--)
{
printf("%d,%d,%d\n", BOX[i].lrs1, BOX[i].lrs2, BOX[i].maxlen);
if (BOX[i - 1].maxlen < BOX[i].maxlen)
{
break;
}
}
for (int i = 0; i <= S[0]; i++)
{
for (int j = 0; j <= T[0]; j++)
{
printf("%d", f[i][j]);
}
printf("\n");
}
system("pause");
}状态变量如下：
