《《数据结构》实验1.doc》由会员分享，可在线阅读，更多相关《《数据结构》实验1.doc（6页珍藏版）》请在三一文库上搜索。
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 MAXLEN30/* 线性表的最大长度*/
3、typedef structElemtype elemMAXLEN;/*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/int length;/*顺序表的长度，即元素个数*/Sqlist;/*顺序表的类型 */【核心算法提示】1顺序表插入操作的基本步骤：要在顺序表中的第i 个数据元素之前插入一个数据元素 x,首先要判断插入位置i 是否合法，假设线性表的表长为n，则 i 的合法值范围：1 i n+1，若是合法位置， 就再判断顺序表是否满，如果满， 则增加空间或结束操作，如果不满，则将第i 个数据元素及其之后的所有数据元素都后移一个位置，此时第i
4、个位置已经腾空，再将待插入的数据元素x 插入到该位置上，最后将线性表的表长增加1。2顺序表删除操作的基本步骤：要删除顺序表中的第i 个数据元素，首先仍然要判断i的合法性， i 的合法范围是1 i n，若是合法位置，则将第i 个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。3顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e 的数据元素，则可以采用顺序查找的方法，从顺序表中第1 个数据元素开始依次将数据元素值与给定值e 进行比较， 若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e 不相片，则查找失败，函数返回0 值。【核心算法描述】s
5、tatusSqlist_insert(Sqlist &L,int i,Elemtype x)/*在顺序表 L 中第 i 个元素前插入新元素x*/ if (i<1|i>L.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 个元素位置处插入
6、新元素x*/L.length+;/*顺序表 L 的长度加 1*/return OK;statusSqlist_delete(Sqlist &L,int i,Elemtype &e)/*在顺序表 L 中删除第 i 个元素 */ if (i<1|i>L.length) return ERROR; /*删除位置不正确则出错*/for(j=i;j<=L.length-1;j+)L.elemj-1=L.elemj; /*将第 i+1 个元素及后继元素位置向前移一位*/L.length-;/*顺序表 L 的长度减 1*/return OK；intSqlist_search
7、(Sqlist L,Elemtype x)/*在顺序表中查找值为x 的元素，如果找到， 则函数返回该元素在顺序表中的位置，否则返回 0*/ for (i=1;i<=L.length&&L.elemi-1!=x;i+);/* 从第一个元素开始依次将每个元素值与给定值x 比较 */if (i<=L.length)return i;elsereturn o;3源程序代码参考#include <stdio.h>/*顺序表Sqlist的定义 */#define MAXLEN 50typedef structint elemMAXLEN;int length;Sql
8、ist;SqlistSqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/int j;if(i<1|i>L.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
9、=x; /*在第i个元素位置处插入新元素x*/L.length+; /*顺序表L 的长度加1*/return L;SqlistSqlist_delete(Sqlist L,int i)/*顺序表删除函数*/int j;if(i<1|i>L.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(
10、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;elsereturn 0;voidSqlist_display(Sqlist L) /*顺序表元素输出函数*/ int j;for(j=0;j<=L.length-1;j+)printf("%4d ",L.elemj);p
11、rintf("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("plea
12、se 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:"
13、); /*请求输入删除操作位置*/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 a
14、nd %d is %d positionn",x,Sqlist_search(L,x); elseprintf(" search is unsuccessn");4运行结果参考如图1-1 所示：图 1-1 验证性实验运行结果七、设计性实验编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。（ 1）实验要求 根据输入的 n 个非递减 的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。 删除 有序顺序表中所有的 重复元素 ，并显示删除后的有序顺序表中各元素值。（ 2）核心算法提示要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表
15、的特性： 重复的元素总是在相邻的位置上，如： 12，15， 15， 15，35，56，56， 78。则删除重复元素后所得的有序表为： 12，15， 35，56， 78。下面给出大致的操作步骤：从第1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。（ 3）核心算法描述Sqlist delSqlist(Sqlist L)int i=0,j;while(i<L.length - 1)if (L.elemi=L.elemi+1)/* 相邻的两个元素比较相等*/ for (j=i+1;j<L.length;j+)/* 删除相等的两个元素中前面那个元素*/L.elemj -1=L.elemj;L.length - ;/* 有序顺序表的表长减1*/elsei+;return L;