📄 第一题.cpp
字号:
}
else
j=next[j];
}
return next;
}//GetNext
int * GetNextval(SqList T){//求模式串的next函数的修正值并存入数组nextval
int i=0,j=-1,*nextval;
nextval=(int *)malloc((T.length)*sizeof(int));
nextval[0]=-1;
while(i<T.length-1)
{
if(j==-1||T.elem[i]==T.elem[j])
{
i++;
j++;
if(T.elem[i]!=T.elem[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
return nextval;
}//GetNextval
int IndexKMP(SqList S,SqList T,int pos){//KPM算法
int i=pos,j=1,*next;
next=GetNextval(T);
while(i<=S.length&&j<=T.length)
{
if(j==0||S.elem[i-1]==T.elem[j-1])
{
i++;
j++;
}
else
j=next[j-1]+1;
}
if(j>T.length)
return i-T.length-1;
else
return 0;
}//IndexKMP
Matrix CreatMatrix(){//建立二维数组存储结构的矩阵M
Matrix M;
int i,j,mu,nu;
printf("\n输入行数和列数(中间用逗号隔开):");
scanf("%d,%d",&mu,&nu);
M.mu=mu;
M.nu=nu;
for(i=0;i<mu;i++)
{
for(j=0;j<nu;j++)
{
printf("输入元素M[%d][%d]=:",i,j);
scanf("%d",&M.data[i][j]);
}
}
return M;
}//CreatMatrix
Matrix TransMatrix(Matrix M){//求二维数组存储结构的矩阵M的转置矩阵
Matrix N;
int i,j;
N.mu=M.nu;
N.nu=M.mu;
for(i=0;i<M.mu;i++)
{
for(j=0;j<M.nu;j++)
N.data[j][i]=M.data[i][j];
}
return N;
}//TransMatrix
Matrix MultSMatrix(Matrix M,Matrix N){//求二维数组存储结构的矩阵M和N的乘积矩阵
Matrix Q;
int i,j,k;
if(M.nu!=N.mu)
{
printf("这两个矩阵不能相乘!");
exit(0);
}
Q.mu=M.mu;
Q.nu=N.nu;
for(i=0;i<M.mu;i++)
for(j=0;j<N.nu;j++)
{
Q.data[i][j]=0;
for(k=0;k<M.nu;k++)
Q.data[i][j]+=M.data[i][k]*N.data[k][j];
}
return Q;
}//MultSMatrix
void PrintMatrix(Matrix M)//输出矩阵
{
int i,j;
printf("矩阵为：");
for(i=0;i<M.mu;i++)
{
printf("\n");
for(j=0;j<M.nu;j++)
printf("%d\t",M.data[i][j]);
}
printf("\n");
}//PrintMatrix
void ShowSqList(){//顺序表演示系统
SqList L,La,Lb,Lc;
int i,loc;
while(1)
{
printf("\n\n\n\n 顺序表演示系统 \n");
printf(" 1.初始化顺序表并给顺序表赋值. \n");
printf(" 2.在顺序表L中位置i前插入新的元素. \n");
printf(" 3.删除顺序表中的第i个元素. \n");
printf(" 4.合并顺序表. \n");
printf(" 5.结束. \n");
printf("*************************************************************\n");
printf(" 请输入你要进行操作的序号: \n");
scanf("%d",&i);
while(!((i>0)&&(i<=5)))
{
printf("输入有误,请重新选择操作:");
scanf("%d",&i);
getchar();
}
switch(i)
{
case 1: L=InitSqList();
PrintSqList(L); break;
case 2: printf("输入位置pos：(0=<pos<=%d)",L.length+1);
scanf("%d",&loc);
getchar();
ListInsert_Sq(&L,loc);
PrintSqList(L); break;
case 3: ListDelete_Sq(&L);
PrintSqList(L); break;
case 4: printf("建立顺序表La,Lb:\n");
La=InitSqList();
PrintSqList(La);
printf("\n");
Lb=InitSqList();
PrintSqList(Lb);
Lc=MergeList_Sq(La,Lb);
PrintSqList(Lc); break;
case 5: return;
}
}
}//ShowSqList
void ShowLinkedList(){//链表演示系统
int i,locate,x;
LinkedList head,La,Lb,p,Lc;
while(1)
{
printf("\n\n\n\n 链表演示系统 \n");
printf(" 1.建立链表. \n");
printf(" 2.遍历链表. \n");
printf(" 3.检查链表是否为空. \n");
printf(" 4.求链表的长度. \n");
printf(" 5.从链表中查找所需位置的元素. \n");
printf(" 6.从链表表中查找与给定元素值相同 \n");
printf(" 的元素在链表中的位置 \n");
printf(" 7.在链表中插入元素. \n");
printf(" 8.删除链表中的元素. \n");
printf(" 9.合并链表. \n");
printf(" 10.结束. \n");
printf("************************************************************\n");
printf(" 请输入你要进行操作的序号: \n");
scanf("%d",&i);
while(!((i>0)&&(i<=10)))
{
printf("\ni值错误");
printf("\n请重新选择你要进行操作的序号(1<=i<=10)：");
scanf("%d",&i);
}
switch(i)
{
case 1: head=LinkedListCreat();
LinkedListTraverse(head); break;
case 2: LinkedListTraverse(head); break;
case 3: if(LinkedListEmpty(head))
printf("链表为空");
else
printf("链表非空"); break;
case 4: printf("链表的长度为%d",LinkedListLength(head)); break;
case 5: printf("请输入所要查找的位置:");
scanf("%d",&locate);
getchar();
p=LinkedListGet(head,locate);
if(!p)
printf("输入非法");
else
printf("您要查找的元素是%d",p->data); break;
case 6: printf("输入元素:");
scanf("%d",&x);
getchar();
if(!LinkedListLocate(head,x))
printf("不存在查找元素");
else
printf("元素的位置是%d",LinkedListLocate(head,x)); break;
case 7: printf("输入位置pos(1<=pos<=%d):",head->data);
scanf("%d",&locate);
getchar();
printf("输入元素:");
scanf("%d",&x);
LinkedListInsert(head,locate,x);
LinkedListTraverse(head); break;
case 8: printf("输入要删除的元素:");
scanf("%d",&x);
getchar();
LinkedListDel(head,x);
LinkedListTraverse(head); break;
case 9:printf("建立链表La:");
La=LinkedListCreat();
LinkedListTraverse(La);
printf("\n建立链表Lb:");
Lb=LinkedListCreat();
LinkedListTraverse(Lb);
Lc=MergeLinkedList(La,Lb);
printf("\n合并链表La、Lb，并排序后得到");
LinkedListTraverse(Lc);
case 10: return;
}
}
}//ShowLinkedList
void ShowKMP(){//串的模式匹配演示系统
SqList S,T;
int pos;
printf("\n\n\n\n串的模式匹配演示. \n");
printf("建立主串:");
S=InitSqList();
printf("建立模式串:");
T=InitSqList();
printf("输入主串开始匹配的位置：");
scanf("%d",&pos);
if(!IndexKMP(S,T,pos))
printf("模式匹配不成功");
else
printf("模式串在主串中的位置为：%d",IndexKMP(S,T,pos));
}//ShowKMP
void ShowArMatrix(){//二维数组存储结构的矩阵演示系统
int i;
Matrix M,N,T,Q;
while(1)
{ printf("\n\n\n\n\n 二维数组存储结构的矩阵演示系统 \n");
printf(" 1.建立二维数组存储结构的矩阵. \n");
printf(" 2.求二维数组的矩阵的转置矩阵. \n");
printf(" 3.求两个二维数组的矩阵的乘积矩阵. \n");
printf(" 4.退出. \n");
printf("*****************************************************************\n");
printf(" 请输入你要进行操作的序号: \n");
scanf("%d",&i);
while(!((i>=0)&&(i<=4)))
{
printf("输入不正确,请重新选择操作:");
scanf("%d",&i);
}
switch(i)
{
case 1: M=CreatMatrix();
PrintMatrix(M); break;
case 2: N=TransMatrix(M);
PrintMatrix(N); break;
case 3: printf("建立要相乘的矩阵M和T:\n");
printf("先建立矩阵M:");
M=CreatMatrix();
PrintMatrix(M);
printf("建立矩阵T:");
T=CreatMatrix();
PrintMatrix(T);
Q=MultSMatrix(M,T);
printf("两矩阵相乘得到矩阵Q ");
PrintMatrix(Q); break;
case 4: return;
}
}
}//ShowArMatrix
void main(){
int i;
while(1)
{
printf("\n\n\n\n\n 数据结构演示系统 \n");
printf(" 1.顺序表演示系统. \n");
printf(" 2.链表演示系统. \n");
printf(" 3.串的模式匹配演示系统. \n");
printf(" 4.矩阵演示系统. \n");
printf(" 5.退出. \n");
printf("******************************************************************\n");
printf(" 请输入你要进入的演示系统: \n");
scanf("%ld",&i);
while(i<1||i>5)
{ printf("输入不正确，请重新输入你要进入的演示系统(0<i<5):");
scanf("%ld",&i);
}
switch(i)
{ case 1:ShowSqList(); break;
case 2:ShowLinkedList(); break;
case 3:ShowKMP(); break;
case 4:ShowArMatrix(); break;
case 5: return;
}
}
}//main
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -