《数据结构》实验1

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

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

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

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

5、败，函数返回 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 个元素

6、位置处插入新元素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 (Sqlis

7、t 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 50 typedef structint elemMAXLEN; int length;Sqlist;Sqlist Sqlist_insert (S

8、qlist 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*/ re

9、turn 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 的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返

10、回 0*/ int i;for (i=1;i=L.length&L.elemi-1!=x;i+);/* 从第一个元素开始依次将每个元素值与给定值 x 比较 */if (i=L.length)return i;elsereturn 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,&

11、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);/* 调用顺序表插入

12、函数 */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) ) /*如果查找成功，则显示查找成功和找到的元素位置，否则显

13、示查找不成功*/printf( search is success and %d is %d positionn,x,Sqlist_search(L,x);elseprintf( search is unsuccessn);运行结果参考如图1-1所示:图1-1验证性实验运行结果4.七、设计性实验编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。(1)实验要求 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元 素值。删除有序顺序表中所有的 重复元素，并显示删除后的有序顺序表中各元素值。(2)核心算法提示要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12, 15, 15, 15, 35, 56, 56, 78。则删除重复元素后所得的有序 表为：12, 15, 35, 56, 78。下面给出大致的操作步骤：从第1个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等,则继续往下比较，如此重复，直到最后