数据结构基础实验4.docx
《数据结构基础实验4.docx》由会员分享,可在线阅读,更多相关《数据结构基础实验4.docx(11页珍藏版)》请在冰点文库上搜索。
数据结构基础实验4
浙江大学城市学院实验报告
课程名称数据结构基础
实验项目名称实验四线性表的顺序表示和实现
学生姓名专业班级学号
实验成绩指导老师(签名)日期
一.实验目的和要求
1、学会定义线性表的动态分配顺序存储结构。
2、掌握线性表的动态分配顺序存储结构及基本操作实现函数。
3、进一步熟悉C语言函数的基本结构,掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用。
二.实验内容
1、编写应用程序(填空),实现可以在顺序表中插入任意给定数据类型(定义为抽象数据类型)数据的功能。
要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据(正整数),对它们求和并输出。
请使用动态内存分配的方式申请数组空间,并把主函数设计为一个文件test4.cpp,其余函数设计为另一个文件SeqList.h。
请填空完成以下给出的源代码并调试通过。
(1)文件SeqList.h:
typedefstructList{
ElemType*list;
intsize;
intMaxSize;
}SeqList;
voidInitList(SeqList&L)
{//初始化线性表
…………
}
voidClearList(SeqList&L)
{//清除线性表
………………
}
intLengthList(SeqListL)
{//求线性表长度
………..
}
boolInsertList(SeqList&L,ElemTypeitem,intpos)
{//按给定条件pos向线性表插入一个元素
…….
}
ElemTypeGetList(SeqListL,intpos)
{//在线性表L中求序号为pos的元素,该元素作为函数值返回
…………..
}
(2)文件test4.cpp:
#include
#include
typedefElemType;
#defineMAXSize10;
#include"SeqList.h"
voidmain(void)
{
SeqListmyList;
inti=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、选做部分:
编写函数boolDeleteElem(SeqList&L,intmin,intmax)实现从顺序表中删除其值在给定值min和max之间(min3、填写实验报告,实验报告文件取名为report4.doc。
4、上传实验报告文件report4.doc、源程序文件test4.cpp及SeqList.h到Ftp服务器上(ftp:
//10.61.14.240:
5000)自己的文件夹下。
三.函数的功能说明及算法思路
(包括每个函数的功能说明,及一些重要函数的算法实现思路)
1、//初始化线性表
voidInitList(SeqList&L)
{L.MaxSize=10;
L.list=newElemType[L.MaxSize];
if(L.list==NULL){
cout<<"动态可分配的储存空间用完,退出运行!
"<exit
(1);
}
L.size=0;
}
2、//清除线性表
voidClearList(SeqList&L)
{
if(L.list!
=NULL){
delete[]L.list;
L.list=NULL;
}
L.MaxSize=0;
L.size=0;
}
3、//求线性表长度
intLengthList(SeqListL)
{
returnL.size;
}
4、//按给定条件pos向线性表插入一个元素
boolInsertList(SeqList&L,ElemTypeitem,intpos)
{
if(pos<-1||pos>L.size+1){
cout<<"pos值无效!
"<}
inti;
if(pos==0){
for(i=0;iif(itempos=i+1;
}
elseif(pos==-1)pos=L.size+1;
if(L.size==L.MaxSize){
intk=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);
if(L.list==NULL){
cout<<"动态可分配的储存空间用完,退出运行!
"<exit
(1);
}
L.MaxSize=2*L.MaxSize;
}
for(i=L.size-1;i>=pos-1;i--)
L.list[i+1]=L.list[i];
L.list[pos-1]=item;
L.size++;
returntrue;
}
5、//在线性表L中求序号为pos的元素,该元素作为函数值返回
ElemTypeGetList(SeqListL,intpos)
{
if(pos<1||pos>L.size){
cerr<<"posisoutrange!
"<exit
(1);
}
returnL.list[pos-1];
}
四.实验结果与分析
(包括运行结果截图、结果分析等)
五.心得体会
(记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
)
在编写函数时,L.list、L.MaxSize和L.size的赋值和定义易弄混。
【附录----源程序】
SeqList.h
typedefstructList{
ElemType*list;
intsize;
intMaxSize;
}SeqList;
voidInitList(SeqList&L)
{//初始化线性表
L.MaxSize=10;
L.list=newElemType[L.MaxSize];
if(L.list==NULL){
cout<<"动态可分配的储存空间用完,退出运行!
"<exit
(1);
}
L.size=0;
}
voidClearList(SeqList&L)
{//清除线性表
if(L.list!
=NULL){
delete[]L.list;
L.list=NULL;
}
L.MaxSize=0;
L.size=0;
}
intLengthList(SeqListL)
{//求线性表长度
returnL.size;
}
boolInsertList(SeqList&L,ElemTypeitem,intpos)
{//按给定条件pos向线性表插入一个元素
if(pos<-1||pos>L.size+1){
cout<<"pos值无效!
"<}
inti;
if(pos==0){
for(i=0;iif(itempos=i+1;
}
elseif(pos==-1)pos=L.size+1;
if(L.size==L.MaxSize){
intk=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);
if(L.list==NULL){
cout<<"动态可分配的储存空间用完,退出运行!
"<exit
(1);
}
L.MaxSize=2*L.MaxSize;
}
for(i=L.size-1;i>=pos-1;i--)
L.list[i+1]=L.list[i];
L.list[pos-1]=item;
L.size++;
returntrue;
}
ElemTypeGetList(SeqListL,intpos)
{//在线性表L中求序号为pos的元素,该元素作为函数值返回
if(pos<1||pos>L.size){
cerr<<"posisoutrange!
"<exit
(1);
}
returnL.list[pos-1];
}
Test4.cpp
#include
#include
#include
typedefintElemType;
#defineMAXSize10
#include"SeqList.h"
voidmain(void)
{
SeqListmyList;
inti=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);
}
(黑色字为填空部分)