《数据结构》实验1.doc

实验1: 顺序表得操作实验一、实验名称与性质所属课程数据结构实验名称顺序表得操作实验学时2实验性质验证 综合 设计必做/选做必做 选做二、实验目得1.掌握线性表得顺序存储结构得表示与实现方法。2.掌握顺序表基本操作得算法实现。3.了解顺序表得应用。三、实验内容1.建立顺序表。2.在顺序表上实现插入、删除与查找操作(验证性内容)。3.删除有序顺序表中得重复元素(设计性内容)。4.完成一个简单学生成绩管理系统得设计(应用性设计内容)。四、实验得软硬件环境要求硬件环境要求:PC机(单机)使用得软件名称、版本号以及模块:Windows环境下得VC+6、0五、知识准备前期要求熟练掌握了C语言得编程规则、方法与顺序表得基本操作算法。六、验证性实验1.实验要求编程实现如下功能:(1)根据输入顺序表得长度n与各个数据元素值建立一个顺序表,并输出顺序表中各元素值,观察输入得内容与输出得内容就是否一致。(2)在顺序表得第i个元素之前插入一个值为x得元素,并输出插入后得顺序表中各元素值。(3)删除顺序表中第i个元素,并输出删除后得顺序表中各元素值。(4)在顺序表中查找值为e得数据元素,如果查找成功,则显示“查找成功”与该元素在顺序表中得位置,否则显示“查找失败”。2、 实验相关原理:线性表得顺序存储结构称为顺序表,顺序表得存储结构描述为:#define MAXLEN 30 /*线性表得最大长度*/typedef struct Elemtype elemMAXLEN; /*顺序表中存放元素得数组,其中elemtype为抽象数据类型,在程序具体实现时可以用任意类型代替*/ int length; /*顺序表得长度,即元素个数*/ Sqlist; /*顺序表得类型*/【核心算法提示】1.顺序表插入操作得基本步骤:要在顺序表中得第i个数据元素之前插入一个数据元素x,首先要判断插入位置i就是否合法,假设线性表得表长为n,则i得合法值范围:1in+1,若就是合法位置,就再判断顺序表就是否满,如果满,则增加空间或结束操作,如果不满,则将第i个数据元素及其之后得所有数据元素都后移一个位置,此时第i个位置已经腾空,再将待插入得数据元素x插入到该位置上,最后将线性表得表长增加1。2.顺序表删除操作得基本步骤:要删除顺序表中得第i个数据元素,首先仍然要判断i得合法性,i 得合法范围就是1in,若就是合法位置,则将第i个数据元素之后得所有数据元素都前移一个位置,最后将线性表得表长减1。3.顺序表查找操作得基本步骤:要在顺序表中查找一个给定值为e得数据元素,则可以采用顺序查找得方法,从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较,若相等则查找成功,函数返回该数据元素在顺序表中得位置,若顺序表中所有元素都与给定值e不相片,则查找失败,函数返回0值。【核心算法描述】status Sqlist_insert(Sqlist &L,int i,Elemtype x) /*在顺序表L中第i个元素前插入新元素x*/ if (iL、length+1) return ERROR; /*插入位置不正确则出错*/ if (L、length=MAXLEN) return OVERFLOW; /*顺序表L中已放满元素,再做插入操作则溢出*/ for(j=L、length-1;j=i-1;j-) L、elemj+1=L、elemj;/*将第i个元素及后续元素位置向后移一位*/ L、elemi-1=x; /*在第i个元素位置处插入新元素x*/ L、length+; /*顺序表L得长度加1*/ return OK; status Sqlist_delete(Sqlist &L,int i,Elemtype &e) /*在顺序表L中删除第i个元素*/ if (iL、length) return ERROR; /*删除位置不正确则出错*/for(j=i;j=L、length-1;j+) L、elemj-1=L、elemj; /*将第i+1个元素及后继元素位置向前移一位*/ L、length-; /*顺序表L得长度减1*/ return OK; int Sqlist_search(Sqlist L,Elemtype x) /* 在顺序表中查找值为x得元素,如果找到,则函数返回该元素在顺序表中得位置,否则返回0*/ for (i=1;i=L、length&L、elemi-1!=x;i+);/*从第一个元素开始依次将每个元素值与给定值x比较*/ if (i=L、length) return i; else return o;3.源程序代码参考 #include /*顺序表Sqlist得定义*/#define MAXLEN 50typedef structint elemMAXLEN;int length;Sqlist;Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/int j;if(iL、length+1) /*插入位置不正确则出错*/ printf(ERROR!);else if(L、length=MAXLEN) printf(OVERFLOW!); /*顺序表L中已放满元素,再做插入操作则溢出*/ else for(j=L、length-1;j=i-1;j-) L、elemj+1=L、elemj; /*将第i个元素及后续元素位置向后移一位*/ L、elemi-1=x; /*在第i个元素位置处插入新元素x*/ L、length+; /*顺序表L得长度加1*/ return L;Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/int j; if(iL、length) printf(ERROR!); /*删除位置不正确则出错*/ else for(j=i;j=L、length-1;j+) L、elemj-1=L、elemj; /*将第i+1个元素及后继元素位置向前移一位*/L、length-; /*顺序表L得长度减1*/ return L;int Sqlist_search(Sqlist L,int x)/* 在顺序表中查找值为x得元素,如果找到,则函数返回该元素在顺序表中得位置,否则返回0*/ int i;for (i=1;i=L、length&L、elemi-1!=x;i+); /*从第一个元素开始依次将每个元素值与给定值x比较*/ if (i=L、length) return i; else return 0;void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ int j; for(j=0;j=L、length-1;j+) printf(%4d ,L、elemj); printf(n); void main() /*主函数 */ Sqlist L; int i,x,j; printf(nplease input the length:);/*请求输入顺序表中元素个数*/ scanf(%d,&L、length); printf(please input the Value:n);/*请求输入顺序表中各个元素*/ for(j=0;j=L、length-1;j+)scanf(%d,&L、elemj); printf(please input the insert position:); /*请求输入插入操作位置*/ scanf(%d,&i); printf(please input the insert node:);/*请求输入需要插入得新元素*/ scanf(%d,&x); L=Sqlist_insert(L,i,x); /*调用顺序表插入函数*/ Sqlist_display(L); /*调用顺序表元素输出函数*/ printf(please input the delete position:); /*请求输入删除操作位置*/ scanf(%d,&i); L=Sqlist_delete(L,i); /*调用顺序表删除函数*/ Sqlist_display(L); /*调用顺序表元素输出函数*/ printf(please input the search node:); /*请求输入查找得结点值*/ scanf(%d,&x); if (Sqlist_search(L,x) /*如果查找成功,则显示查找成功与找到得元素位置,否则显示查找不成功*/ printf( search is success and %d is %d positionn,x,Sqlist_search(L,x); else printf( search is unsuccessn); 4.运行结果参考如图1-1所示: 图1-1 验证性实验运行结果七、设计性实验编程实现删除有序顺序表中得所有重复元素,即使有序顺序表中相同得元素只保留一个。(1)实验要求 根据输入得n个非递减得有序数据建立一个有序顺序表,并输出有序顺序表中各元素值。 删除有序顺序表中所有得重复元素,并显示删除后得有序顺序表中各元素值。(2)核心算法提示要在有序顺序表中删除重复得元素,首先就要抓住有序顺序表得特性:重复得元素总就是在相邻得位置上,如:12,15,15,15,35,56,56,78。则删除重复元素后所得得有序表为:12,15,35,56,78。下面给出大致得操作步骤:从第1 个元素开始,依次将它与后面相邻得元素进行比较,如果相等则将前面那个相等得元素从顺序表中删除;如果不相等,则继续往下比较,如此重复,直到最后一个元素为止。(3)核心算法描述 Sqlist delSqlist(Sqlist L)int i=0,j; while(iL、length-1) if (L、elemi=L、elemi+1) /*相邻得两个元素比较相等*/ for (j=i+1;jL、length;j+) /*删除相等得两个元素中前面那个元素*/ L、elemj-1=L、elemj; L、length-; /*有序顺序表得表长减1*/ else i+; return L;