国家开放大学电大《数据结构》实验报告.docx
《国家开放大学电大《数据结构》实验报告.docx》由会员分享,可在线阅读,更多相关《国家开放大学电大《数据结构》实验报告.docx(50页珍藏版)》请在冰点文库上搜索。
国家开放大学电大《数据结构》实验报告
数据结构形成性考核册
实验名称:
实验一线性表
线性表的链式存储结构
【问题描述】
某项比赛中,评委们给某参赛者的评分信息存储在一个带头结点的单向链表中,编写程序:
(1)显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)。
(2)在链表中删除一个最高分和一个最低分的结点。
(3)计算该参赛者去掉一个最高分和一个最低分后的平均成绩。
【基本要求】
(1)建立一个评委打分的单向链表;
(2)显示删除相关结点后的链表信息。
(3)显示要求的结果。
【实验步骤】
(1)运行PC中的MicrosoftVisualC++6.0程序,
(2)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”,
(3)输入程序代码,
程序代码如下:
#include
#include
#include
#include
#include
#defineNULL0
#definePWRS5//定义评委人数
structpw//定义评委信息
{charname[6];
floatscore;
intage;
};
typedefstructpwPW;
structnode//定义链表结点
{structpwdata;
structnode*next;
};
typedefstructnodeNODE;
NODE*create(intm);//创建单链表
intcalc(NODE*h);//计算、数据处理
voidprint(NODE*h);//输出所有评委打分数据
voidinput(NODE*s);//输入评委打分数据
voidoutput(NODE*s);//输出评委打分数据
voidmain()
{
NODE*head;
floatave=0;
floatsum=0;
head=create(PWRS);
printf("所有评委打分信息如下:
\n");
print(head);//显示当前评委打分
calc(head);//计算成绩
printf("该选手去掉1最高分和1最低分后的有效评委成绩:
\n");
print(head);//显示去掉极限分后的评委打分
}
voidinput(NODE*s)
{
printf("请输入评委的姓名:
");
scanf("%S",&s->data.name);
printf("年龄:
");
scanf("%d",&s->data.age);
printf("打分:
");
scanf("%f",&s->data.score);
printf("\n");
}
voidoutput(NODE*s)
{
printf("评委姓名:
%8s,年龄:
%d,打分:
%2.2f\n",s->data.name,s->data.age,s->data.score);
}
NODE*create(intm)
{
NODE*head,*p,*q;
inti;
p=(NODE*)malloc(sizeof(NODE));
head=p;
q=p;
p->next=NULL;
for(i=1;i<=m;i++){
p=(NODE*)malloc(sizeof(NODE));
input(p);
p->next=NULL;
q->next=p;
q=p;
}
return(head);
}
voidprint(NODE*h)
{for(inti=1;((i<=PWRS)&&(h->next!
=NULL));i++){
h=h->next;
output(h);}
printf("\n");
}
intcalc(NODE*h)
{
NODE*q,*p,*pmin,*pmax;
floatsum=0;
floatave=0;
p=h->next;//指向首元结点
pmin=pmax=p;//设置初始值
sum+=p->data.score;
p=p->next;
for(;p!
=NULL;p=p->next)
{
if(p->data.score>pmax->data.score)pmax=p;
if(p->data.scoredata.score)pmin=p;
sum+=p->data.score;
}
cout<<"给出最高分的评委姓名:
"<data.name<<"年龄:
"<data.age<<"分值:
"<data.score<cout<<"给出最低分的评委姓名:
"<data.name<<"年龄:
"<data.age<<"分值:
"<data.score<printf("\n");
sum-=pmin->data.score;
sum-=pmax->data.score;
for(q=h,p=h->next;p!
=NULL;q=p,p=p->next)
{
if(p==pmin){q->next=p->next;p=q;}//删除最低分结点
if(p==pmax){q->next=p->next;p=q;}//删除最高分结点
}
ave=sum/(PWRS-2);
cout<<"该选手的最后得分是:
"<return1;
}
程序运行结果如下:
线性表的顺序存储结构
【问题描述】
用顺序表A记录学生的信息,编写程序:
(1)将A表分解成两个顺序表B和C,使C表中含原A表中性别为男性的学生,B表中含原表中性别为女性的学生,要求学生的次序与原A表中相同。
(2)分别求男生和女生的平均年龄
【基本要求】
(1)建立学生信息的顺序表A。
(2)显示B表和C表中的相关信息。
(3)显示计算结果。
【实验步骤;】
(1)运行PC中的MicrosoftVisualC++6.0程序,
(2)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”,
(3)输入程序代码,
程序代码如下:
#include
#include
#include
#include
#include
#include//包含库函数strcpy的头文件
#defineNULL0
structstudent//定义学生信息
{charname[8];
intsex;//0女:
1:
男
intage;
};
typedefstructstudentSTD;
intcreate(STD*m);//创建顺序表
intcalc(STD*m,STD*n,STD*r,float&Fage,float&Mage);//计算、数据处理
voidprint(STD*m);
constintMAX=100;//定义人数
voidmain()
{
STDA[MAX];
STDB[MAX];
STDC[MAX];
floatage1=0,age2=0;//age1男age2女
create(A);
printf("学生总表A记录如下:
\n");
print(A);
calc(A,B,C,age1,age2);
printf("女生名册B记录如下:
\n");
print(B);
printf("男生名册C记录如下:
\n");
print(C);
}
intcreate(STD*m)
{
intn;
printf("请输入班级总人数:
\n");
scanf("%d",&n);
m[0].age=n;//置顺序表长度
printf("请输入学生信息:
\n");
for(inti=1;i<=n;i++)
{
printf("姓名:
");
scanf("%s",&m[i].name);
printf("性别0女1男:
");
scanf("%d",&m[i].sex);
printf("年龄:
");
scanf("%d",&m[i].age);
printf("\n");
}
return1;
}
intcalc(STD*m,STD*n,STD*r,float&Fage,float&Mage)
{inti,j=1,k=1;
n[0].age=r[0].age=0;
for(i=1;i<=m[0].age;i++)
{if(m[i].sex==0)
{
strcpy(n[j].name,m[i].name);
n[j].sex=m[i].sex;n[j].age=m[i].age;
n[0].age++;Mage+=m[i].age;j++;
}
else
{
strcpy(r[k].name,m[i].name);
r[k].sex=m[i].sex;r[k].age=m[i].age;
r[0].age++;Fage+=m[i].age;k++;
}
}
Mage=Mage/n[0].age;Fage=Fage/r[0].age;
cout<<"女生的平均年龄是:
"<"<return1;
}
voidprint(STD*m)
{
for(inti=1;i<=m[0].age;i++)
{
printf("姓名:
%3s,性别(0女1男):
%d,年龄:
%d\n",m[i].name,m[i].sex,m[i].age);
}
}
l程序运行结果如下:
实验结束。
实验结论:
线性表采用链式存储(链表)时:
以结构变量存储结点,动态生成结点,以指针链接结点,能有效利用存储空间,插入删除方便,但不能随机访问.单向链表可从某结点访问到后继结点。
单向链表操作的关键步骤:
建立链表的头插法:
指针变量p开辟单元,生成结点,指针变量q始终指向头结点,操作为:
p->next=q->next;q->next=p;尾插法:
指针变量q始终指向尾结点,p指针开辟单元,生成结点:
q->next=p;q=p;?
插入:
p所指向结点的后面插入新结点s所指结点s->next=p->next;p->next=s;?
删除:
p,q指向相邻结点,q所指结点是p所指结点的后继,删除q所指结点,p->next=q->next;?
遍历:
p=p->next;
实验名称:
实验二栈、列队、递归程序设计
2.1栈和队列的基本操作
【问题描述】
编写一个算法,输出指定栈中的栈底元素,并使得原栈中的元素倒置。
【基本要求】
(1)正确理解栈的先进后出的操作特点,建立初始栈,通过相关操作显示栈底元素。
(2)程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程,按堆栈的操作规则打印结果栈中的元素。
【实验步骤;】
(4)运行PC中的MicrosoftVisualC++6.0程序,
(5)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”,
(6)输入程序代码,
程序代码如下:
#include
#include
#defineMaxSize100
typedefcharElemType;
typedefstruct
{
ElemTypedata[MaxSize];
inttop;//栈顶指针
}SeqStack;//定义栈
typedefstruct
{
ElemTypeelem[MaxSize];
intfront,rear;//队首和队尾指针
}SqQueue;//定义队列
//---初始栈函数
voidInitStack(SeqStack*&s)
{
s=(SeqStack*)malloc(sizeof(SeqStack));
s->top=-1;
}
//----进栈函数
intPush(SeqStack*&s,ElemTypee)
{
if(s->top==MaxSize-1)
return0;
s->top++;
s->data[s->top]=e;
return1;
}
//---显示栈函数
voidDispStack(SeqStack*s)
{
inti;
for(i=s->top;i>=0;i--)
printf("%c",s->data[i]);
printf("\n");
}
//---显示栈底元素
voidDispBottomStack(SeqStack*s)
{
printf("%c",s->data[0]);//先进后出,栈底元素为第一个元素,即data[0]
printf("\n");
}
//---判空栈函数
intStackEmpty(SeqStack*s)
{
return(s->top==-1);
}
//---出栈函数
intPop(SeqStack*&s,ElemType&e)
{
if(s->top==-1)
return0;
e=s->data[s->top];
s->top--;
return1;
}
//---初始队列函数
voidInitQueue(SqQueue*&q)
{
q=(SqQueue*)malloc(sizeof(SqQueue));
q->front=q->rear=0;
}
//---入队列函数
intInQueue(SqQueue*&q,ElemTypee)
{
if((q->rear+1)%MaxSize==q->front)//队满
return0;
q->rear=(q->rear+1)%MaxSize;
q->elem[q->rear]=e;
return1;
}
//---出队列函数
intOutQueue(SqQueue*&q,ElemType&e)
{
if(q->front==q->rear)//队空
return0;
q->front=(q->front+1)%MaxSize;
e=q->elem[q->front];
return1;
}
//---判空队列函数
intQueueEmpty(SqQueue*q)
{
return(q->front==q->rear);
}
//-----主程序
voidmain()
{
ElemTypee;
SeqStack*s;
printf("
(1)初始化栈s\n");
InitStack(s);
printf("
(2)栈为%s\n",(StackEmpty(s)?
"空":
"非空"));
printf("(3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');//入栈元素1
Push(s,'b');//入栈元素2
Push(s,'c');//入栈元素3
Push(s,'d');//入栈元素4
Push(s,'e');//入栈元素5
printf("(4)栈为%s\n",(StackEmpty(s)?
"空":
"非空"));
printf("(5)从栈顶到栈底元素:
");DispStack(s);
printf("(6)栈底元素为:
");DispBottomStack(s);
printf("(7)出栈/入队列序列:
");
SqQueue*q;
InitQueue(q);
while(!
StackEmpty(s))
{
Pop(s,e);//出栈
printf("%c",e);
InQueue(q,e);//入队
}
printf("\n");
printf("(8)栈为%s,",(StackEmpty(s)?
"空":
"非空"));
printf("队列为%s\n",(QueueEmpty(q)?
"空":
"非空"));
printf("(9)出队列/入栈序列:
");
while(!
QueueEmpty(q))
{OutQueue(q,e);//出队
Push(s,e);//入栈
printf("%c",e);
}
printf("\n");
printf("(10)栈为%s,",(StackEmpty(s)?
"空":
"非空"));
printf("队列为%s\n",(QueueEmpty(q)?
"空":
"非空"));
free(q);//释放队列
printf("(11)从栈顶到栈底元素:
");DispStack(s);
free(s);//释放栈
}
程序运行结果如下:
2.2递归程序设计
【问题描述】
给定一个5位的十进制正整数,用递归法分别编制程序:
(1)要求从低位到高位逐次输出各位数字。
(2)要求从高位到低位逐次输出各位数字。
【基本要求】
(1)比较题中两种不同要求的递归程序设计和执行过程差别。
(2)正确理解递归程序的执行过程。
(3)显示计算结果。
【实验步骤】
(1)运行PC中的MicrosoftVisualC++6.0程序,
点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中
(2)输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”,
(3)输入程序代码
程序代码如下:
#include
#include
voidout(intn,inti)//从高位到低位输出函数
{
intx,y;
y=int(pow(10,i));
if(n!
=0)
{
x=n/y;
n=n-x*y;
printf("%d",x);
}
elseprintf("0");
i--;
if(i>=0)out(n,i);
}
voidout1(intm,intj)//从低位到高位输出函数
{
intx,z;
if(m!
=0)
{
x=int(m/10);
z=m-x*10;
m=x;
printf("%d",z);
}
elseprintf("0");
j--;
if(j>=0)out1(m,j);
}
voidmain()
{
intm,n,o,x,i,j;
printf("输入需要排列的数字:
\n");
scanf("%d",&o);
m=n=o;
x=n;
i=-1;
while(x!
=0)
{
x=x/10;
i++;
}//求出i为十进制正整数位数
j=i;
printf("\n");
printf("从高位到低位逐次输出各位数字:
");
out(n,i);
printf("\n");
printf("从低位到高位逐次输出各位数字:
");
out1(m,j);
printf("\n");
}
程序运行结果如下:
实验结论:
栈和队列是运算受限制的线性表
栈:
后进先出(LIFO)
例:
进栈b,c,d,e,f出栈可能为f,e,d,c,b;b,c,d,e,f;c,b,e,d,f•••但不可能是e,d,f,b,c
队列:
先进先出(FIFO)
例:
入队1,2,3,4,5出队1,2,3,4,5
实验名称:
实验三二叉树
3.1二叉树的顺序存储结构和链式存储结构
【问题描述】
设一棵完全二叉树用顺序存储方法存储于数组tree中,编写程序:
(1)根据数组tree,建立与该二叉树对应的链式存储结构。
(2)对该二叉树采用中序遍历法显示遍历结果。
【基本要求】
(1)在主函数中,通过键盘输入建立设定的完全二叉树的顺序存储结构。
(2)设计子函数,其功能为将顺序结构的二叉树转化为链式结构。
(3)设计子函数,其功能为对给定二叉树进行中序遍历,显示遍历结果。
(4)通过实例判断算法和相应程序的正确性。
【实验步骤】
(7)运行PC中的MicrosoftVisualC++6.0程序,
(8)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”,
(9)输入程序代码,
程序代码如下:
#include
#include
#include
#include
#include
#defineMaxSize10
typedefstructnode
{
chardata;
structnode*left,*right;
}NODE;
voidCreab(char*tree,intn,inti,NODE*p);
voidInorder(NODE*p);
voidmain()
{
NODE*p;
chartree[MaxSize];
intn=1;
inti=1;
printf("请输入完全二叉数的节点值(连续输入字符,以回车结束输入。
):
");
while((tree[n]=getchar())!
='\n')n++;
tree[n]='\n';
p=NULL;
Creab(tree,n,i,p);
Inorder(p);
}
voidCreab(char*tree,intn,inti,NODE*p)
{
if(i>=n)p=NULL;
else
{
p=(NODE*)