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