一、实验目的：
1、复习C语言程序设计中的知识。
2、掌握线性表的顺序存储结构的表示和实现方法。
3、掌握顺序表基本操作的算法实现。
二、实验内容：
1．建立顺序表。
2．在顺序表上实现插入、删除和查找等操作。
三、实验要求：
1、编写实现顺序表的基本算法（初始化、查找、插入、删除等）的函数，并在此基础上设计一个主程序完成如下功能：
⑴初始化一个顺序表L，数据元素类型可任选；
⑵建立顺序表L，要求数据元素至少10个；
⑶输出顺序表L的长度；
⑷按位置查找：输出顺序表L的第i个元素，如第3个元素；
⑸按内容查找：输出给定元素的位置；
⑹在第i个元素前插入给定元素；
⑺删除顺序表L的第i个元素；
⑻遍历顺序表，将表中的元素按序输出。
编写菜单，以便用户可以选择相应的操作。
- 拓展实验（可选做）
利用顺序表的基本操作，求两个集合A和B的交集、并集和差集。
- 实验步骤：
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define msize 100
#define elemtype int
typedef struct
{elemtype elem[msize];
int last;
}seqlist;
1.顺序表的初始化
seqlist *init_seqlist()
{seqlist *L;
L=(seqlist *)malloc(sizeof(seqlist));
if(L!=NULL)
{L->last=-1;
printf("初始化成功\n");
}
return L;
}
2.建立顺序表输入顺序表元素
seqlist *indata_seqlist (seqlist *L )
{elemtype m;
scanf("%d",&m);
while (m!=0)
{L->last+=1;//访问Last
L->elem[L->last]=m;
scanf("%d",&m);
}
return L;
}
3.获取顺序表元素
elemtype Getdata_seqlist (seqlist *L,int i)
{if(i<1||i>L->last+1)
{return 0;
}
else
return (L->elem[i-1]);
}
4.输出顺序表的长度
int seqlist_Long (seqlist *L )
{printf("该顺序表的长度为%d\n",L->last+1);
return 0;
}
5. 查找给定元素的位置
int search_seqlist_1 (seqlist *L,elemtype key)//查找给定元素的位置
{int i;
for(i=0;i<=L->last;i++)
{if(L->elem[i]==key)
{printf("给定元素的位置为%d\n",i+1);
return (i+1);}}
if(key!=L->elem[i]&&i==L->last)
printf("无此元素\n");
return 0;
}
6.按位置查找对应元素
elemtype search_seqlist_2 (seqlist *L,elemtype key )//按位置查找对应元素
{int i;
if(key<=0||key>(L->last))
{printf("输入错误，查找失败\n");
}
for(i=0;i<L->last;i++)
{if(i+1==key)
printf("对应元素的值为%d\n",L->elem[i]);}
return (L->elem[i]);
}
7. 遍历顺序表
int print_seqlist(seqlist *L)
{int i;elemtype t;
if(L->last==-1)
{return 0;
}int j;
printf("顺序表的所有元素为\n");
for(i=0;i<=L->last;i++)
{
printf("a[%d]=%d\t",i,L->elem[i]);}
return 1;
}
8.在顺序表中插入元素
int insert_seqlist(seqlist *L,int i,elemtype x )
{int j;
if(L->last>=msize-1)
{printf("表已满无法插入\n");
return 0;
}
if((i<1)||(i>L->last+2))
{printf("插入位置不合理\n");
return -1;
}
for(j=L->last;j>=i-1;j--)
L->elem[j+1]=L->elem[j];
L->elem[i-1]=x;
L->last++;
print_seqlist(L);
return 1;
}
9.删除顺序表元素
int Delete_seqlist(seqlist *L,int i,elemtype *w)
{int k;
if((i<1)||(i>L->last+1))
{printf("删除位置不合理\n");
return 0;
}
else
{*w=L->elem[i-1];
for(k=i-1;k<L->last;k++)
{L->elem[k]=L->elem[k+1];
}
}
L->last--;
print_seqlist(L);
return 1;}
10菜单
void menu()
{int a;
printf("\n************ 欢迎使用顺序表的基本操作系统 ************\n");
printf("\n************ 1 初始化顺序表L ************\n");
printf("\n************ 2 建立顺序表L ************\n");
printf("\n************ 3 输出顺序表L的长度 ************\n");
printf("\n************ 4 按位置查找输出顺序表L的第i个元素 ************\n");
printf("\n************ 5 按内容查找输出给定元素的位置 ************\n");
printf("\n************ 6 在第i个元素前插入给定元素 ************\n");
printf("\n************ 7 删除顺序表的第i个元素 ************\n");
printf("\n************ 8 输出顺序表的所有元素 ************\n");
printf("\n************ 9 退出系统 ************\n");
printf("\n************ 10 清理屏幕 返回菜单 ************\n");
printf("\n************ 11 求集合AUB ************\n");
printf("\n************ 12 求集合AnB ************\n");
printf("请选择1-12：");}
11.求两个集合A和B的交集
void union_seqlist(seqlist *L1,seqlist *L2 )
{int i,len,k;
elemtype x;
len=seqlist_Long(L1);
for(i=1;i<=L2->last+1;i++)
{x=Getdata_seqlist (L2,i);
k=search_seqlist_1 (L1,x);
if(k==0)
{insert_seqlist(L1,len+1,x);
len=seqlist_Long(L1);
}}}
12.求两个集合A和B的并集
void union_seqlist_2(seqlist *L1,seqlist *L2 )
{int i,len,k;
elemtype x;
len=seqlist_Long(L1);
for(i=1;i<=L2->last+1;i++)
{x=Getdata_seqlist (L2,i);
k=search_seqlist_1 (L1,x);
if(k!=0)
{insert_seqlist(L1,len+1,x);
len=seqlist_Long(L1);
}}}
int main()
{menu();seqlist *L;seqlist *L1;seqlist*L2;int a;
while(1)
{
int t;scanf("%d",&t);
if(t<1||t>12)
{printf("输入错误，请重新输入：\n");
scanf("%d",&t);}
switch(t)
{case 1:{L=init_seqlist();
break;}
case 2:{
printf("请输入元素，按0结束输入\n");
L=indata_seqlist(L);
printf("该操作完成，请继续输入下一步指令\n");
break;}
case 3:{
a=seqlist_Long (L);
printf("该操作完成，请继续输入下一步指令\n");
break;}
case 5:{
int m;
printf("请输入待查找元素值\n");
scanf("%d",&m);
search_seqlist_1(L,m);
printf("该操作完成，请继续输入下一步指令\n");break;}
case 4:
{printf("输入待查找元素位置\n");
int d;
scanf("%d",&d);
search_seqlist_2 (L,d);
printf("该操作完成，请继续输入下一步指令\n");break;
}
case 6:{printf("输入待插入元素位置\n");
int o;
scanf("%d",&o);
printf("输入待插入元素\n");
int u;
scanf("%d",&u);
insert_seqlist(L,o,u);
printf("插入成功\n");
printf("该操作完成，请继续输入下一步指令\n");
break;
}
case 7:{printf("输入待删除元素位置\n");
int y;int h;
scanf("%d",&y);
Delete_seqlist(L,y,&h);
printf("删除成功\n");
printf("该操作完成，请继续输入下一步指令\n");
break;
}
case 8:{print_seqlist(L);
printf("该操作完成，请继续输入下一步指令\n");break;}
case 9:{exit(0);break;}
case 10:{system("cls");menu();
printf("该操作完成，请继续输入下一步指令\n");break;}
case 11:{
printf("请输入顺序表A中数据元素以0结束:\n");
L1=init_seqlist();
L1=indata_seqlist(L1);
printf("请输入顺序表B中数据元素以0结束:\n");
L2=init_seqlist();
L2=indata_seqlist(L2);
union_seqlist(L1,L2);
printf("AUB=");
print_seqlist(L1);
printf("该操作完成，请继续输入下一步指令\n");
break;}
case 12:{
printf("请输入顺序表A中数据元素以0结束:\n");
L1=init_seqlist();
L1=indata_seqlist(L1);
printf("请输入顺序表B中数据元素以0结束:\n");
L2=init_seqlist();
L2=indata_seqlist(L2);
union_seqlist_2(L1,L2);
printf("AnB=");
print_seqlist(L1);
printf("该操作完成，请继续输入下一步指令\n");
break;
}
default:{printf("输入错误，请重新输入\n");
printf("请选择1-12：");break;}
} }}
- 实验结果：
1菜单如下：
2输入数据删除查找遍历结果如下：
3.求AUB结果如下
4.求AnB结果如下
七、附（源代码）
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define msize 100
#define elemtype int
typedef struct
{elemtype elem[msize];
int last;
}seqlist;
seqlist *init_seqlist()
{seqlist *L;
L=(seqlist *)malloc(sizeof(seqlist));
if(L!=NULL)
{L->last=-1;
printf("初始化成功\n");
}
return L;
}
seqlist *indata_seqlist (seqlist *L )
{elemtype m;
scanf("%d",&m);
while (m!=0)
{L->last+=1;//访问Last
L->elem[L->last]=m;
scanf("%d",&m);
}
return L;
}
elemtype Getdata_seqlist (seqlist *L,int i)
{if(i<1||i>L->last+1)
{return 0;
}
else
return (L->elem[i-1]);
}
int seqlist_Long (seqlist *L )
{printf("该顺序表的长度为%d\n",L->last+1);
return 0;
}
int search_seqlist_1 (seqlist *L,elemtype key)//查找给定元素的位置
{int i;
for(i=0;i<=L->last;i++)
{if(L->elem[i]==key)
{printf("给定元素的位置为%d\n",i+1);
return (i+1);}}
if(key!=L->elem[i]&&i==L->last)
printf("无此元素\n");
return 0;
}
elemtype search_seqlist_2 (seqlist *L,elemtype key )//按位置查找对应元素
{int i;
if(key<=0||key>(L->last))
{printf("输入错误，查找失败\n");
}
for(i=0;i<L->last;i++)
{if(i+1==key)
printf("对应元素的值为%d\n",L->elem[i]);}
return (L->elem[i]);
}
int print_seqlist(seqlist *L)
{int i;elemtype t;
if(L->last==-1)
{return 0;
}int j;
printf("顺序表的所有元素为\n");
for(i=0;i<=L->last;i++)
{
printf("a[%d]=%d\t",i,L->elem[i]);}
return 1;
}
int insert_seqlist(seqlist *L,int i,elemtype x )
{int j;
if(L->last>=msize-1)
{printf("表已满无法插入\n");
return 0;
}
if((i<1)||(i>L->last+2))
{printf("插入位置不合理\n");
return -1;
}
for(j=L->last;j>=i-1;j--)
L->elem[j+1]=L->elem[j];
L->elem[i-1]=x;
L->last++;
print_seqlist(L);
return 1;
}
int Delete_seqlist(seqlist *L,int i,elemtype *w)
{int k;
if((i<1)||(i>L->last+1))
{printf("删除位置不合理\n");
return 0;
}
else
{*w=L->elem[i-1];
for(k=i-1;k<L->last;k++)
{L->elem[k]=L->elem[k+1];
}
}
L->last--;
print_seqlist(L);
return 1;}
void menu()
{int a;
printf("\n************ 欢迎使用顺序表的基本操作系统 ************\n");
printf("\n************ 1 初始化顺序表L ************\n");
printf("\n************ 2 建立顺序表L ************\n");
printf("\n************ 3 输出顺序表L的长度 ************\n");
printf("\n************ 4 按位置查找输出顺序表L的第i个元素 ************\n");
printf("\n************ 5 按内容查找输出给定元素的位置 ************\n");
printf("\n************ 6 在第i个元素前插入给定元素 ************\n");
printf("\n************ 7 删除顺序表的第i个元素 ************\n");
printf("\n************ 8 输出顺序表的所有元素 ************\n");
printf("\n************ 9 退出系统 ************\n");
printf("\n************ 10 清理屏幕 返回菜单 ************\n");
printf("\n************ 11 求集合AUB ************\n");
printf("\n************ 12 求集合AnB ************\n");
printf("请选择1-12：");}
void union_seqlist(seqlist *L1,seqlist *L2 )
{int i,len,k;
elemtype x;
len=seqlist_Long(L1);
for(i=1;i<=L2->last+1;i++)
{x=Getdata_seqlist (L2,i);
k=search_seqlist_1 (L1,x);
if(k==0)
{insert_seqlist(L1,len+1,x);
len=seqlist_Long(L1);
}}}
void union_seqlist_2(seqlist *L1,seqlist *L2 )
{int i,len,k;
elemtype x;
len=seqlist_Long(L1);
for(i=1;i<=L2->last+1;i++)
{x=Getdata_seqlist (L2,i);
k=search_seqlist_1 (L1,x);
if(k!=0)
{insert_seqlist(L1,len+1,x);
len=seqlist_Long(L1);
}}}
int main()
{menu();seqlist *L;seqlist *L1;seqlist*L2;int a;
while(1)
{
int t;scanf("%d",&t);
if(t<1||t>12)
{printf("输入错误，请重新输入：\n");
scanf("%d",&t);}
switch(t)
{case 1:{L=init_seqlist();
break;}
case 2:{
printf("请输入元素，按0结束输入\n");
L=indata_seqlist(L);
printf("该操作完成，请继续输入下一步指令\n");
break;}
case 3:{
a=seqlist_Long (L);
printf("该操作完成，请继续输入下一步指令\n");
break;}
case 5:{
int m;
printf("请输入待查找元素值\n");
scanf("%d",&m);
search_seqlist_1(L,m);
printf("该操作完成，请继续输入下一步指令\n");break;}
case 4:
{printf("输入待查找元素位置\n");
int d;
scanf("%d",&d);
search_seqlist_2 (L,d);
printf("该操作完成，请继续输入下一步指令\n");break;
}
case 6:{printf("输入待插入元素位置\n");
int o;
scanf("%d",&o);
printf("输入待插入元素\n");
int u;
scanf("%d",&u);
insert_seqlist(L,o,u);
printf("插入成功\n");
printf("该操作完成，请继续输入下一步指令\n");
break;
}
case 7:{printf("输入待删除元素位置\n");
int y;int h;
scanf("%d",&y);
Delete_seqlist(L,y,&h);
printf("删除成功\n");
printf("该操作完成，请继续输入下一步指令\n");
break;
}
case 8:{print_seqlist(L);
printf("该操作完成，请继续输入下一步指令\n");break;}
case 9:{exit(0);break;}
case 10:{system("cls");menu();
printf("该操作完成，请继续输入下一步指令\n");break;}
case 11:{
printf("请输入顺序表A中数据元素以0结束:\n");
L1=init_seqlist();
L1=indata_seqlist(L1);
printf("请输入顺序表B中数据元素以0结束:\n");
L2=init_seqlist();
L2=indata_seqlist(L2);
union_seqlist(L1,L2);
printf("AUB=");
print_seqlist(L1);
printf("该操作完成，请继续输入下一步指令\n");
break;}
case 12:{
printf("请输入顺序表A中数据元素以0结束:\n");
L1=init_seqlist();
L1=indata_seqlist(L1);
printf("请输入顺序表B中数据元素以0结束:\n");
L2=init_seqlist();
L2=indata_seqlist(L2);
union_seqlist_2(L1,L2);
printf("AnB=");
print_seqlist(L1);
printf("该操作完成，请继续输入下一步指令\n");
break;
}
default:{printf("输入错误，请重新输入\n");
printf("请选择1-12：");break;}
} }}