《数据结构》实验1.doc

1、1实验 1: 顺序表的操作实验一、实验名称和性质所属课程 数据结构实验名称 顺序表的操作实验学时 2实验性质 验证 综合 设计必做/选做 必做 选做二、实验目的1掌握线性表的顺序存储结构的表示和实现方法。2掌握顺序表基本操作的算法实现。3了解顺序表的应用。三、实验内容1建立顺序表。2在顺序表上实现插入、删除和查找操作（验证性内容） 。3删除有序顺序表中的重复元素（设计性内容） 。4完成一个简单学生成绩管理系统的设计（应用性设计内容） 。四、实验的软硬件环境要求硬件环境要求：PC 机（单机）使用的软件名称、版本号以及模块：Windows 环境下的 VC+6.0五、知识准备前期要求熟练掌握了 C

2、语言的编程规则、方法和顺序表的基本操作算法。六、验证性实验1实验要求编程实现如下功能：（1）根据输入顺序表的长度 n 和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。（2）在顺序表的第 i 个元素之前插入一个值为 x 的元素，并输出插入后的顺序表中各元素值。（3）删除顺序表中第 i 个元素，并输出删除后的顺序表中各元素值。（4）在顺序表中查找值为 e 的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败” 。2. 实验相关原理：线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：#define MAXLEN 3

3、0 /*线性表的最大长度*/typedef struct Elemtype elemMAXLEN; /*顺序表中存放元素的数组，其中 elemtype 为抽象数据类型，在2程序具体实现时可以用任意类型代替*/int length; /*顺序表的长度，即元素个数*/Sqlist; /*顺序表的类型*/【核心算法提示】1顺序表插入操作的基本步骤：要在顺序表中的第 i 个数据元素之前插入一个数据元素 x,首先要判断插入位置 i 是否合法，假设线性表的表长为 n，则 i 的合法值范围：1i n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第 i 个数据元素及其之

4、后的所有数据元素都后移一个位置，此时第 i 个位置已经腾空，再将待插入的数据元素 x 插入到该位置上，最后将线性表的表长增加 1。2顺序表删除操作的基本步骤：要删除顺序表中的第 i 个数据元素，首先仍然要判断i 的合法性，i 的合法范围是 1i n，若是合法位置，则将第 i 个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减 1。3顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为 e 的数据元素，则可以采用顺序查找的方法，从顺序表中第 1 个数据元素开始依次将数据元素值与给定值 e 进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值

5、 e 不相片，则查找失败，函数返回 0 值。【核心算法描述】status Sqlist_insert(Sqlist /*插入位置不正确则出错*/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(Sql

6、ist /*删除位置不正确则出错*/for(j=i;j /*顺序表 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=

7、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 个元素及后继元素位

8、置向前移一位*/L.length-; /*顺序表 L 的长度减 1*/return L;int Sqlist_search(Sqlist L,int x)/* 在顺序表中查找值为 x 的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回 0*/4 int i;for (i=1;i=L.lengthi+); /*从第一个元素开始依次将每个元素值与给定值 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+)

9、printf(“%4d “,L.elemj);printf(“n“); void main() /*主函数 */ Sqlist L;int i,x,j;printf(“nplease input the length:“);/*请求输入顺序表中元素个数*/scanf(“%d“,printf(“please input the Value:n“);/*请求输入顺序表中各个元素*/for(j=0;j=L.length-1;j+)scanf(“%d“, printf(“please input the insert position:“); /*请求输入插入操作位置*/scanf(“%d“,prin

10、tf(“please input the insert node:“);/*请求输入需要插入的新元素*/scanf(“%d“,L=Sqlist_insert(L,i,x); /*调用顺序表插入函数*/Sqlist_display(L); /*调用顺序表元素输出函数*/printf(“please input the delete position:“); /*请求输入删除操作位置*/scanf(“%d“,L=Sqlist_delete(L,i); /*调用顺序表删除函数*/Sqlist_display(L); /*调用顺序表元素输出函数*/5printf(“please input the s

11、earch node:“); /*请求输入查找的结点值*/scanf(“%d“,if (Sqlist_search(L,x) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查找不成功*/printf(“ search is success and %d is %d positionn“,x,Sqlist_search(L,x);elseprintf(“ search is unsuccessn“);4运行结果参考如图 1-1 所示：图 1-1 验证性实验运行结果七、设计性实验编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。（1）实验要求 根据输入的 n

12、 个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。（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)6if (L.elemi=L.elemi+1) /*相邻的两个元素比较相等*/ for (j=i+1;jL.length;j+) /*删除相等的两个元素中前面那个元素 */L.elemj-1=L.elemj;L.length-; /*有序顺序表的表长减 1*/elsei+;return L;