实验一：顺序表的基本操作
1、实验目的
(1)掌握顺序表的基本运算，熟悉对顺序表的一些基本操作和具体函数的定义。
(2)掌握顺序存储的概念，学会定义线性表的顺序存储类型。
(3)熟悉c语言程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
(4)熟悉c语言环境的使用及程序的输入、编辑、调试和运行的全过程。
(5)加深对顺序存储结构的理解，逐步培养解决实际问题的编程能力。
2、实验要求
(1)熟练掌握线性表的存储结构及其基本操作。
(2)理解所给出的算法，掌握线性表在实际中的应用。
(3)将上机程序调试通过，并能独立完成一至两个拓展题目。
3、实验内容
实现顺序表上的插入、删除等操作。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对有关算法的理解。
4、试验方法
第一步:定义顺序表的存储结构。
第二步：编写顺序表操作的具体函数定义。
第三步：使用定义的顺序表并调用顺序表的一些操作，实现具体运算。
具体函数的定义有：
(1)insert(L,i,x)在顺序表的第i个元素之前插入一个新元素x.
(2)delete (L,i) 删除顺序表的第i个元素。
(3)listprint(L) 输出顺序表。
5、验证程序
#define MAXSIZE 100//宏定义
#include//函数头文件
typedef int elemtype;//定义顺序表的结构
typedef struct//数据表成员所占储存空间
{
elemtype vec[MAXSIZE];
int last;//顺序表中最后一个元素在数组中的下标，从0开始
}sequenlist;
int insert(sequenlist *L,int i,elemtype x)//插入函数
{
int j;
if(((*L).last)>=MAXSIZE-1)
{
printf("the list is overflow!
");
return 0;//溢出判断
}
else
if((i<1)||(i>(*L).last+2))
{
printf("position is not correct!
");
return 0;//插入位置不对
}
else
{
for(j=(*L).last;j>=i-1;j--)
(*L).vec[j+1]=(*L).vec[j];
(*L).vec [i-1]=x;
(*L).last++;
}
return 1;
}
void delete(sequenlist *L,int i)//删除第i个元素
{
int j;
if((i<1)||(i>(*L).last+1))
printf("delete fail
");
else
{
for(j=i;j<=(*L).last;j++)
(*L).vec[j-1]=(*L).vec[j];
(*L).last--;
}
}
void listprint(sequenlist *L)//输出函数
{
int i;
for(i=0;i<=(*L).last;i++)
printf("i,e=%d,%d
",i,L->vec[i]);
}
main()//主函数
{
sequenlist s1={{1,2,3,4,5,6,7,8,9,10},9};//定义一个变量
sequenlist *L;
int i,j,x;
L=&s1;
printf("please input the insert position and insert value
");
scanf("%d%d",&i,&x);
printf("the insert position :%d
insert value :%d
",i,x);
insert(L,i,x);
listprint(L);
printf("please input the delete position:");
scanf("%d",&j);
delete(L,j);
listprint(L);
}
验证程序结果如下图：
6、预习思考题
调试好上述程序后，试着完成以下拓展内容：
(1)定义一个定位函数locate(L,x)，具有元素检索的功能。当顺序表中存在一个值为x的数据元素时，返回第一次找到的数据元素的位序，否则，给出一个值，表示值为x的元素不存在。在主程序中调用该函数，分析操作结果。
(2)定义一个逆置函数diverse(L),把顺序表进行逆置。在主程序中调用该函数，分析操作结果。
(3)定义一个函数delsame(L),把顺序表中重复的元素删除掉，只保留一个。在主程序中调用该函数，分析操作结果。
思考一：在做思考题1的时候返回值的返回有一定的难度，由于循环的作用返回值可能返回不同的结果，导致返回值被覆盖，不能有效返回。
int locate(sequenlist *L,int x)//定位函数
{
int i,a=-1;
for(i=0;i<=(*L).last;i++)
{if(x==(*L).vec[i]){a=i;break;}}
return a;
}
main()//主函数
{
sequenlist s1={{1,2,3,4,5,6,7,8,9,10},9};//定义一个变量
sequenlist *L;
int i,j,x,k,y;
L=&s1;
printf("please input the insert position and insert value
");
scanf("%d%d",&i,&x);
printf("the insert position :%d
insert value :%d
",i,x);
insert(L,i,x);
listprint(L);
printf("please input the delete position:");
scanf("%d",&j);
delete(L,j);
listprint(L);
printf("输入定位数值");
scanf("%d",&k);
y=locate(L,k);
if(y==-1)
printf("查找不出来
");
else printf("该数值的位置是%d
",y);
}
程序运行结果如下图：
思考二：根据前后位置调换直接互换数值，要求是ivoid diverse(sequenlist *L)//换序函数
{
int i,j,t;
for(i=0,j=L->last;i运行结果如下图：
思考三：先确定第一个值，然后用后面的值进行比较，如果相等直接调用删除函数，不相等进行下一个比较，然后用第二个数值与后面的数值进行比较。最后比计较结束。
void delsame(sequenlist *L)//删除函数
{
int i,j;
for(i=0;ilast;i++)
for(j=i+1;j<=L->last;)
{
if(L->vec[i]==L->vec[j])
delete(L,j+1);
else j++;
}
}
main()
{
..........
.........
printf("删除重复的数值:
");
delsame(L);
listprint(L);
}
运行结果如下图：
