数据结构_串_用链表做存储结构实现KMP算法_C++实现
写这个纠结了很久，老是会有某个环节出问题。先是在处理串的结束标志的问题上，老是会跟其他的判断条件冲突造成提前退出，而且无论主串和模式串情况如何结果总是succeed，尝试了好几种方法，包括将其链接成单循环链表等，效果总是不太理想，后来就想到了临时new一个变量，用完之后再delete掉，结果由于多写了一个delete老是报错，后来才发现在ReMove函数中已经delete掉了。然后就是GetNext()和KMP()处理上有点小问题，有一些细节没有处理好。后来在纸上做了下模拟，也慢慢调过来了，贴出来分享一下，如有错误，欢迎指正。
head.h
#include<iostream>
using namespace std;
class NODE
{
public:
NODE();
char ch;
NODE *succ; //指向下一个节点
NODE *next; //对于主串指向前一个节点；对于模式串指向"失配"下一个要进行比较的节点
};
NODE::NODE()
{
succ = next = NULL;
}
class STRING
{
public:
STRING();
void GetMainString();
void GetSubstring();
void KMP();
void Print();
private:
void GetNext();
void ReMove(NODE*);
void GetLeftString(NODE*);
NODE *head1, *p1, *end1, *head2, *p2, *end2;
//end1标示主串的结尾end2标示模式串的结尾
};
STRING::STRING()
{
end1 = head1 = p1 = end2 = head2 = p2 = NULL;
}
void STRING::GetMainString() //得到主串
{
cout << "GetMainString Called !" << endl << endl;
char ch;
if (head1 != NULL) //释放节点内存
{
ReMove(head1);
head1 = NULL;
// delete end1;
//注意这里不用释放end1的内存，因为在ReMove中结束条件是p==NULL，已经把end1的内存给释放掉了
}
while (cin >> ch)
{
if (head1 == NULL)
{
head1 = new NODE;
head1->ch = ch;
head1->next = head1;
p1 = head1;
}
else
{
p1->succ = new NODE;
p1->succ->ch = ch;
p1->succ->next = p1;
p1 = p1->succ;
}
}
if (head1 != NULL)
{
p1->succ = end1 = new NODE; //给串尾添加结束标志
}
cin.clear();
}
void STRING::GetSubstring() //得到模式串
{
cout << "GetSubString Called !" << endl << endl;
char ch;
if (head2 != NULL)
{
ReMove(head2);
head2 = NULL;
// delete end2;
}
while (cin >> ch)
{
if (head2 == NULL)
{
head2 = new NODE;
head2->ch = ch;
p2 = head2;
}
else
{
p2->succ = new NODE;
p2 = p2->succ;
p2->ch = ch;
}
}
if (head2 != NULL)
{
p2->succ = end2 = new NODE;
}
cin.clear();
}
void STRING::KMP() //KMP算法核心
{
cout << "KMP Called !" << endl << endl;
if (head1 == NULL || head2 == NULL) //空串处理
{
cout << "Failed !" << endl << endl;
}
GetNext(); //得到next"值"
p1 = head1;
p2 = head2;
while (p1 != end1 && p2 != end2)
{
if (p2 == NULL || p1->ch == p2->ch)
{
p1 = p1->succ;
if (p2 == NULL)
p2 = head2;
else
p2 = p2->succ;
}
else
{
p2 = p2->next;
}
}
if (p2 == end2) //判断是否匹配成功
{
cout << "Succeed ! The Left Of The String is = ";
GetLeftString(p1);
}
else
{
cout << "Failed !" << endl << endl;
}
}
void STRING::Print() //输出主串和模式串的内容
{
cout << "Print Called !" << endl << endl;
if (head1 == NULL)
{
cout << "No Data In MainString !" << endl << endl;
}
else
{
cout << "MainString = ";
p1 = head1;
while (p1 != end1)
{
cout << p1->ch;
p1 = p1->succ;
}
cout << endl << endl;
}
if (head2 == NULL)
{
cout << "No Data In SubString !" << endl << endl;
}
else
{
cout << "SubString = ";
p2 = head2;
while (p2 != NULL)
{
cout << p2->ch;
p2 = p2->succ;
}
cout << endl << endl;
}
}
void STRING::GetNext() //得到模式串的next值
{
p1 = head2;
p2 = head2->next = NULL;
while (p1->succ != end2)
{
if (p2 == NULL || p1->ch == p2->ch)
{
p1 = p1->succ;
if (p2 == NULL)
p2 = head2;
else
p2 = p2->succ;
if (p2 != p2->next)
p1->next = p2;
else
p2 = p2->next;
}
else
{
p2 = p2->next;
}
}
}
void STRING::GetLeftString(NODE *p) //输出匹配成功后主串中剩下的部分
{
while (p != end1)
{
cout << p->ch;
p = p->succ;
}
cout << endl << endl;
}
void STRING::ReMove(NODE *p) //销毁字符串所占的内存
{
if (p == NULL)
return;
else
{
ReMove(p->succ);
delete p;
}
}#include<iostream>
using namespace std;
class NODE
{
public:
NODE();
char ch;
NODE *succ; //指向下一个节点
NODE *next; //对于主串指向前一个节点；对于模式串指向"失配"下一个要进行比较的节点
};
NODE::NODE()
{
succ = next = NULL;
}
class STRING
{
public:
STRING();
void GetMainString();
void GetSubstring();
void KMP();
void Print();
private:
void GetNext();
void ReMove(NODE*);
void GetLeftString(NODE*);
NODE *head1, *p1, *end1, *head2, *p2, *end2;
//end1标示主串的结尾end2标示模式串的结尾
};
STRING::STRING()
{
end1 = head1 = p1 = end2 = head2 = p2 = NULL;
}
void STRING::GetMainString() //得到主串
{
cout << "GetMainString Called !" << endl << endl;
char ch;
if (head1 != NULL) //释放节点内存
{
ReMove(head1);
head1 = NULL;
// delete end1;
//注意这里不用释放end1的内存，因为在ReMove中结束条件是p==NULL，已经把end1的内存给释放掉了
}
while (cin >> ch)
{
if (head1 == NULL)
{
head1 = new NODE;
head1->ch = ch;
head1->next = head1;
p1 = head1;
}
else
{
p1->succ = new NODE;
p1->succ->ch = ch;
p1->succ->next = p1;
p1 = p1->succ;
}
}
if (head1 != NULL)
{
p1->succ = end1 = new NODE; //给串尾添加结束标志
}
cin.clear();
}
void STRING::GetSubstring() //得到模式串
{
cout << "GetSubString Called !" << endl << endl;
char ch;
if (head2 != NULL)
{
ReMove(head2);
head2 = NULL;
// delete end2;
}
while (cin >> ch)
{
if (head2 == NULL)
{
head2 = new NODE;
head2->ch = ch;
p2 = head2;
}
else
{
p2->succ = new NODE;
p2 = p2->succ;
p2->ch = ch;
}
}
if (head2 != NULL)
{
p2->succ = end2 = new NODE;
}
cin.clear();
}
void STRING::KMP() //KMP算法核心
{
cout << "KMP Called !" << endl << endl;
if (head1 == NULL || head2 == NULL) //空串处理
{
cout << "Failed !" << endl << endl;
}
GetNext(); //得到next"值"
p1 = head1;
p2 = head2;
while (p1 != end1 && p2 != end2)
{
if (p2 == NULL || p1->ch == p2->ch)
{
p1 = p1->succ;
if (p2 == NULL)
p2 = head2;
else
p2 = p2->succ;
}
else
{
p2 = p2->next;
}
}
if (p2 == end2) //判断是否匹配成功
{
cout << "Succeed ! The Left Of The String is = ";
GetLeftString(p1);
}
else
{
cout << "Failed !" << endl << endl;
}
}
void STRING::Print() //输出主串和模式串的内容
{
cout << "Print Called !" << endl << endl;
if (head1 == NULL)
{
cout << "No Data In MainString !" << endl << endl;
}
else
{
cout << "MainString = ";
p1 = head1;
while (p1 != end1)
{
cout << p1->ch;
p1 = p1->succ;
}
cout << endl << endl;
}
if (head2 == NULL)
{
cout << "No Data In SubString !" << endl << endl;
}
else
{
cout << "SubString = ";
p2 = head2;
while (p2 != NULL)
{
cout << p2->ch;
p2 = p2->succ;
}
cout << endl << endl;
}
}
void STRING::GetNext() //得到模式串的next值
{
p1 = head2;
p2 = head2->next = NULL;
while (p1->succ != end2)
{
if (p2 == NULL || p1->ch == p2->ch)
{
p1 = p1->succ;
if (p2 == NULL)
p2 = head2;
else
p2 = p2->succ;
if (p2 != p2->next)
p1->next = p2;
else
p2 = p2->next;
}
else
{
p2 = p2->next;
}
}
}
void STRING::GetLeftString(NODE *p) //输出匹配成功后主串中剩下的部分
{
while (p != end1)
{
cout << p->ch;
p = p->succ;
}
cout << endl << endl;
}
void STRING::ReMove(NODE *p) //销毁字符串所占的内存
{
if (p == NULL)
return;
else
{
ReMove(p->succ);
delete p;
}
}
main.cpp
#include<iostream>
#include"head.h"
using namespace std;
int main()
{
char choice;
STRING str;
while (1)
{
cout << "Your Choice Please ?" << endl << endl << "1 . SetMainString"
<< endl << "2 . SetSubString" << endl << "3 . KMP" << endl
<< "4 . Print" << endl << "5 . Quit" << endl << endl;
cin >> choice;
system("cls");
switch (choice)
{
case '1':
str.GetMainString();
break;
case '2':
str.GetSubstring();
break;
case '3':
str.KMP();
cin.get();
cin.get();
break;
case '4':
str.Print();
cin.get();
cin.get();
break;
case '5':
return 0;
break;
default:
cout << "No Such Choice !" << endl << endl;
cin.get();
cin.get();
break;
}
system("cls");
}
}