浙江大学城市学院实验
课程名称 数据结构基础
实验项目名称 实验四 线性
的顺序表示和实现
学生姓名 专业班级 学号
实验成绩 指导老师(签名 ) 日期
1. 实验目的和要求
1、学会定义线性表的动态分配顺序存储结构。
2、掌握线性表的动态分配顺序存储结构及基本操作实现函数。
3、进一步熟悉C语言函数的基本结构,掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用。
2. 实验内容
1、编写应用程序(填空),实现可以在顺序表中插入任意给定数据类型(定义为抽象数据类型)数据的功能。要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据(正整数),对它们求和并输出。请使用动态内存分配的方式申请数组空间,并把主函数
为一个文件test4.cpp,其余函数设计为另一个文件SeqList.h。
请填空完成以下给出的源代码并调试通过。
(1) 文件SeqList.h:
typedef struct List{
ElemType *list;
int size;
int MaxSize;
}SeqList;
void InitList(SeqList &L)
{ //初始化线性表
…………
}
void ClearList(SeqList &L)
{ //清除线性表
………………
}
int LengthList(SeqList L)
{ //求线性表长度
………..
}
bool InsertList(SeqList &L, ElemType item, int pos)
{ //按给定条件pos向线性表插入一个元素
…….
}
ElemType GetList(SeqList L, int pos)
{ //在线性表L中求序号为pos的元素,该元素作为函数值返回
…………..
}
(2)文件test4.cpp:
#include
#include
typedef ElemType;
#define MAXSize 10;
#include "SeqList.h"
void main(void)
{
SeqList myList;
int i=1, x, sum=0, n;
InitList ( );
scanf(“%d”, &x);
while ( x!= -1 )
{
if ( InsertList (myList, , i )==0) {
printf("错误!\n");
return ;
}
i++;
scanf(“%d”, &x);
}
n = LengthList (myList);
for (i=1; i<=n; i++)
{
x=GetList(myList, i);
sum = + x;
}
printf("%d\n ", sum);
ClearList(myList);
}
2、选做部分:编写函数bool DeleteElem(SeqList &L, int min, int max) 实现从顺序表中删除其值在给定值min和max之间(min < max)的所有元素,要求把该函数添加到文件SeqList.h中,并在主函数文件test4.cpp中添加相应语句进行测试。
3、填写实验报告,实验报告文件取名为report4.doc。
4、上传实验报告文件report4.doc 、源程序文件test4.cpp及SeqList.h到Ftp服务器上( ftp://10.61.14.240:5000 )自己的文件夹下。
三. 函数的功能及算法思路
(包括每个函数的功能说明,及一些重要函数的算法实现思路)
1、//初始化线性表
void InitList(SeqList &L)
{
L.MaxSize=10;
L.list=new ElemType[L.MaxSize];
if(L.list==NULL){
cout<<"动态可分配的储存空间用完,退出运行!"<L.size+1){
cout<<"pos值无效!"<=pos-1;i--)
L.list[i+1]=L.list[i];
L.list[pos-1]=item;
L.size++;
return true;
}
5、//在线性表L中求序号为pos的元素,该元素作为函数值返回
ElemType GetList(SeqList L, int pos)
{
if(pos<1 || pos>L.size){
cerr<<"pos is out range!"<题、意见和建议等。)
在编写函数时,L.list、L.MaxSize和L.size的赋值和定义易弄混。
【附录----源程序】
SeqList.h
typedef struct List{
ElemType *list;
int size;
int MaxSize;
}SeqList;
void InitList(SeqList &L)
{ //初始化线性表
L.MaxSize=10;
L.list=new ElemType[L.MaxSize];
if(L.list==NULL){
cout<<"动态可分配的储存空间用完,退出运行!"<
L.size+1){
cout<<"pos值无效!"<=pos-1;i--)
L.list[i+1]=L.list[i];
L.list[pos-1]=item;
L.size++;
return true;
}
ElemType GetList(SeqList L, int pos)
{ //在线性表L中求序号为pos的元素,该元素作为函数值返回
if(pos<1 || pos>L.size){
cerr<<"pos is out range!"<
#include
#include
typedef int ElemType;
#define MAXSize 10
#include "SeqList.h"
void main(void)
{
SeqList myList;
int i=1, x, sum=0, n;
InitList (myList);
scanf("%d", &x);
while ( x!= -1 )
{
if ( InsertList (myList,x, i )==0) {
printf("错误!\n");
return ;
}
i++;
scanf("%d", &x);
}
n = LengthList (myList);
for (i=1; i<=n; i++)
{
x=GetList(myList, i);
sum = sum + x;
}
printf("%d\n ", sum);
ClearList(myList);
}
(黑色字为填空部分)