数据结构——串、数组、广义表的操作实现
??这一部分是数据结构线性结构的最后一部分，在本章中，主要涉及以下的知识点：字符串模式匹配（BF算法和KMP算法）、数组元素存储位置的计算、特殊矩阵的压缩存储、广义表相关概念等。在这篇博客中，我主要实现字符串和数组压缩的算法，其余内容均用文字描述。如果该博客的内容有不妥的地方，还请各位大神指出。
一、字符串模式匹配
1.字符串的类型定义
??在数据结构中，我们尽量避免使用string容器去解决字符串问题（应急的情况下除外）。对于一个字符串而言，以顺序存储的方式进行存储最为常见，那么这个时候就需要定义字符串的长度。
#define MAXLEN 255
typedef struct
{
char ch[MAXLEN+1];
int length;
}SString;
2.BF算法
??BF算法是字符串匹配的最基本的算法，其时间复杂度为O(n*n)，也是最耗时的算法，不过相较于KMP算法理解起来更加容易一些。下面的代码主要描述了该算法的实现。
int Index_BF(SString S,SString T,int pos)
{
int i=pos,j=1;
while (i<=S.length&&j<=T.length)
{
if (S.ch[i]==T.ch[j])
{
i++;
j++;
}
else
{
i=i-j+2;
j=1;
}
}
if (j>T.length)
return i-T.length;
else
return -1;
}
3.KMP算法
??KMP算法相较于BF算法而言，更加的高效，它省去了子串从头回溯的麻烦，利用一个next[]数组进行维护，其算法的时间复杂度为O(n+m)。其中，对于next[]数组而言，有两种求取方式，读者可根据自身需求来选择合适的算法。
void get_next(SString T,int next[])
{
int i=1,j=0;
next[1]=0;
while (i<T.length)
{
if (j==0||T.ch[i]==T.ch[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
void get_nextval(SString T,int nextval[])
{
int i=1,j=0;
nextval[1]=0;
while (i<T.length)
{
if (j==0||T.ch[i]==T.ch[j])
{
i++;
j++;
if (T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
int Index_KMP(SString S,SString T,int pos)
{
int i=pos,j=1;
int nextval[255];
memset(nextval,0,sizeof(nextval));
get_nextval(T,nextval);
while (i<=S.length&&j<=T.length)
{
if (j==0||S.ch[i]==T.ch[j])
{
i++;
j++;
}
else
j=nextval[j];
}
if (j>T.length)
return i-T.length;
else
return -1;
}
4.完整代码的实现：
#include <bits/stdc++.h>
#define MAXLEN 255
using namespace std;
typedef struct
{
char ch[MAXLEN+1];
int length;
}SString;
void Menu()
{
cout<<"串的操作实现"<<endl;
cout<<"1.串的模式匹配（BF算法）"<<endl;
cout<<"2.串的模式匹配（KMP算法）"<<endl;
cout<<"0.退出"<<endl;
cout<<"请选择服务：";
}
int Index_BF(SString S,SString T,int pos)
{
int i=pos,j=1;
while (i<=S.length&&j<=T.length)
{
if (S.ch[i]==T.ch[j])
{
i++;
j++;
}
else
{
i=i-j+2;
j=1;
}
}
if (j>T.length)
return i-T.length;
else
return -1;
}
void get_next(SString T,int next[])
{
int i=1,j=0;
next[1]=0;
while (i<T.length)
{
if (j==0||T.ch[i]==T.ch[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
void get_nextval(SString T,int nextval[])
{
int i=1,j=0;
nextval[1]=0;
while (i<T.length)
{
if (j==0||T.ch[i]==T.ch[j])
{
i++;
j++;
if (T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
int Index_KMP(SString S,SString T,int pos)
{
int i=pos,j=1;
int nextval[255];
memset(nextval,0,sizeof(nextval));
get_nextval(T,nextval);
while (i<=S.length&&j<=T.length)
{
if (j==0||S.ch[i]==T.ch[j])
{
i++;
j++;
}
else
j=nextval[j];
}
if (j>T.length)
return i-T.length;
else
return -1;
}
int main()
{
while (true)
{
system("cls");
Menu();
SString S,T;
int x;
cin>>x;
switch(x)
{
case 1:
int s1,t1;
cout<<"\n请输入字符串S的长度：";
cin>>s1;
S.length=s1;
cout<<"\n请输入字符串S：";
for (int i=1;i<=s1;i++)
cin>>S.ch[i];
cout<<"\n请输入字符串T的长度：";
cin>>t1;
T.length=t1;
cout<<"\n请输入字符串T：";
for (int i=1;i<=t1;i++)
cin>>T.ch[i];
if (Index_BF(S,T,0)!=-1)
cout<<"\n字符串T第一次在第"<<Index_BF(S,T,0)<<"位与字符串S匹配！\n"<<endl;
else
cout<<"\n字符串T不与字符串S匹配！\n"<<endl;
break;
case 2:
int s2,t2;
cout<<"\n请输入字符串S的长度：";
cin>>s2;
S.length=s2;
cout<<"\n请输入字符串S：";
for (int i=1;i<=s2;i++)
cin>>S.ch[i];
cout<<"\n请输入字符串T的长度：";
cin>>t2;
T.length=t2;
cout<<"\n请输入字符串T：";
for (int i=1;i<=t2;i++)
cin>>T.ch[i];
if (Index_KMP(S,T,0)!=-1)
cout<<"\n字符串T第一次在第"<<Index_KMP(S,T,0)<<"位与字符串S匹配！\n"<<endl;
else
cout<<"\n字符串T不与字符串S匹配！\n"<<endl;
break;
case 0:
exit(0);
}
system("pause");
}
return 0;
}
二、特殊矩阵的压缩存储
??这一部分知识里，代码很少，只需掌握其通项公式即可，在这里的代码，我用一个一维数组进行存储，实现了这项功能。
#include <bits/stdc++.h>
using namespace std;
void Menu()
{
cout<<"特殊矩阵压缩存储的操作实现"<<endl;
cout<<"1.对称矩阵"<<endl;
cout<<"2.上三角矩阵"<<endl;
cout<<"3.下三角矩阵"<<endl;
cout<<"0.退出"<<endl;
cout<<"请选择服务：";
}
int main()
{
while (true)
{
system("cls");
Menu();
int x;
cin>>x;
switch (x)
{
case 1:
{
int a1[50][50];
int sa1[2500];
int n1;
cout<<"\n请输入矩阵阶数：";
cin>>n1;
cout<<"\n请输入矩阵元素：\n";
for (int i=0;i<n1;i++)
{
for (int j=0;j<n1;j++)
cin>>a1[i][j];
}
int k1=0;
for (int i=0;i<n1;i++)
{
for (int j=0;j<n1;j++)
{
if (i>=j)
sa1[k1++]=a1[i][j];
}
}
cout<<"\n压缩存储后的数组为："<<endl;
for (int i=0;i<k1;i++)
cout<<sa1[i]<<" ";
cout<<endl;
break;
}
case 2:
{
int a2[50][50];
int sa2[2500];
int n2;
cout<<"\n请输入矩阵阶数：";
cin>>n2;
cout<<"\n请输入矩阵元素：\n";
for (int i=0;i<n2;i++)
{
for (int j=0;j<n2;j++)
cin>>a2[i][j];
}
int k2=0;
for (int i=0;i<n2;i++)
{
for (int j=0;j<n2;j++)
{
if (i<=j)
sa2[k2++]=a2[i][j];
}
}
sa2[k2++]=a2[n2-1][0];
cout<<"\n压缩存储后的数组为："<<endl;
for (int i=0;i<k2;i++)
cout<<sa2[i]<<" ";
cout<<endl;
break;
}
case 3:
{
int a3[50][50];
int sa3[2500];
int n3;
cout<<"\n请输入矩阵阶数：";
cin>>n3;
cout<<"\n请输入矩阵元素：\n";
for (int i=0;i<n3;i++)
{
for (int j=0;j<n3;j++)
cin>>a3[i][j];
}
int k3=0;
for (int i=0;i<n3;i++)
{
for (int j=0;j<n3;j++)
{
if (i>=j)
sa3[k3++]=a3[i][j];
}
}
sa3[k3++]=a3[0][n3-1];
cout<<"\n压缩存储后的数组为："<<endl;
for (int i=0;i<k3;i++)
cout<<sa3[i]<<" ";
cout<<endl;
break;
}
case 0:
exit(0);
}
system("pause");
}
return 0;
}
??就此，关于线性结构的所有数据结构全部实现完毕，基于线性结构的“一对一”的特点，以线性表为基础，逐渐增加了一些常用的算法和常用的操作。而到了接下来的非线性结构部分，算法设计是一方面，更重要的是算法的实现与概念的理解，可以说接下来的知识才是重点。
下面附上前面几个数据结构的链接，方便读者进行查阅：
?[ ] 线性表的操作实现
?[ ] 栈和队列的操作实现
|