实验一：顺序表的基本操作

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); } 运行结果如下图：