[数据结构]实验1
实验1: 顺序表的操作实验
一、实验名称和性质
二、实验目的
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 /*线性表的最大长度*/
typedefstruct
{ Elemtypeelem[MAXLEN]; /*顺序表中存放元素的数组,其中elemtype 为抽象数据类型,在程序
具体实现时可以用任意类型代替*/
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,inti,Elemtypex)
/*在顺序表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.elem[j+1]=L.elem[j];/*将第i 个元素及后续元素位置向后移一位*/
L.elem[i-1]=x; /*在第i 个元素位置处插入新元素x*/
L.length++; /*顺序表L 的长度加1*/
return OK;
}
status Sqlist_delete(Sqlist&L,inti,Elemtype&e)
/*在顺序表L 中删除第i 个元素*/
{if (iL.length)return ERROR; /*删除位置不正确则出错*/
for(j=i;j
L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/
L.length--; /*顺序表L 的长度减1*/
return OK;
}
int Sqlist_search(SqlistL,Elemtype x)
/* 在顺序表中查找值为x 的元素,如果找到,则函数返回该元素在顺序表中的位置,否则返回0*/
/*从第一个元素开始依次将每个元素值与给定值x 比较*/
if (i
return i;
else
return o;
}
3.源程序代码参考
#include /*顺序表Sqlist 的定义*/
#define MAXLEN 50
typedefstruct{intelem[MAXLEN];
int length;}Sqlist;
Sqlist Sqlist_insert(SqlistL,inti,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.elem[j+1]=L.elem[j];/*将第i 个元素及后续元素位置向后移一位*/ L.elem[i-1]=x;/*在第i 个元素位置处插入新元素x*/ L.length++;/*顺序表L 的长度加1*/
}
return L;
}
Sqlist Sqlist_delete(SqlistL,int i) /*顺序表删除函数*/
{int j;
if(iL.length) printf("ERROR!");/*删除位置不正确则出错*/
else { for(j=i;j
L.elem[j-1]=L.elem[j];/*将第i+1个元素及后继元素位置向前移一位*/
L.length--;/*顺序表L 的长度减1*/
}
return L;
}
intSqlist_search(SqlistL,int x)
/* 在顺序表中查找值为x 的元素,如果找到,则函数返回该元素在顺序表中的位置,否则返回0*/ { int i;
/*从第一个元素开始依次将每个元素值与给定值x 比较*/
if (i
return i;
else
return 0;
}
void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/
{ int j;
for(j=0;j
printf("%4d ",L.elem[j]);
printf("\n");
}
voidmain() /*主函数 */
{ Sqlist L;
inti,x,j;
printf("\nplease input the length:");/*请求输入顺序表中元素个数*/
scanf("%d",&L.length);
printf("please input the Value:\n");/*请求输入顺序表中各个元素*/
for(j=0;j
scanf("%d",&L.elem[j]);
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 position\n",x,Sqlist_search(L,x));
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)核心算法描述
SqlistdelSqlist(Sqlist L)
{int i=0,j;
while(i
if (L.elem[i]==L.elem[i+1])/*相邻的两个元素比较相等*/
{ for (j=i+1;j
*/
L.elem[j-1]=L.elem[j];
L.length--;/*有序顺序表的表长减1*/ }
else
i++;
return L;
}