电大《数据结构》实验报告.docx

该【电大《数据结构》实验报告 】是由【森林书屋】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【电大《数据结构》实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构形成性考核册
实验名称:实验一 线性表
线性表的链式存储结构
【问题描述】
某项比赛中,评委们给某参赛者的评分信息存储在一个带头结点的单向链表中,编写程序:
(1)
显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)
。
(2)
在链表中删除一个最高分和一个最低分的结点。
(3)
计算该参赛者去掉一个最高分和一个最低分后的平均成绩。
【基本要求】
(1)
建立一个评委打分的单向链表;
(2)
显示删除相关结点后的链表信息。
(3)
显示要求的结果。
【实验步骤】
(1)
运行PC中的MicrosoftVisualC++程序,
2)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“”
→在“位置”中选择储存路径为“桌面”→“确定”,
3)输入程序代码,
程序代码如下 :
#include<>
#include<>
#include<>
#include<>
#include<>
#defineNULL0
# ge=n;ame);
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<<"女生的平均年龄是:"<<Mage<<"男生的平均年龄是:"<<Fage<<endl;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);}
}
程序运行结果如下 :
实验结束。
实验结论: 线性表采用链式存储(链表)时:以结构变量存储结点,动态生成结点,以指针链接结点,能
有效利用存储空间,插入删除方便,但不能随机访问 .单向链表可从某结点访问到后 继结点。 单向链表操
作的关键步骤:建立链表的头插法:指针变量 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;
实验名称:实验二栈、列队、递归程序设计栈和队列的基本操作
【问题描述】
编写一个算法,输出指定栈中的栈底元素,并使得原栈中的元素倒置。
【基本要求】
(1)正确理解栈的先进后出的操作特点 ,建立初始栈,通过相关操作显示栈底元素。
(2)程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程, 按堆栈的操作规则打印结果栈中的元素。
【实验步骤;】
(4) 运行PC中的MicrosoftVisualC++ 程序,
5)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“”
→在“位置”中选择储存路径为“桌面”→“确定”,
6)输入程序代码,
程序代码如下 :
#include<>
#include<>
#defineMaxSize100
typedefcharElemType;
typedefstruct
{
ElemTypedata[MaxSize];
inttop;
1 3
x=s[0].avg;
while(low<=hight)
{
mid=(low+hight)/2;
if(x>s[mid].avg)
hight=mid-1;
else
low=mid+1;
}
for(k=0;k<low-1;k++){strcpy(s[k].name,s[k+1].name);s[k].avg=s[k+1].avg;
}
printf("%d",low);
strcpy(s[low-1].name,y);
s[low-1].avg=x;
}
voidmain()
{

2 4 5
ame);
Structstudenta[N]=
{{"caozh",96},{"cheng",95},{"zhao",93},{"wang",92},{"chen",91}};
structstudentstu[N];
inti;
for(i=0;i<N;i++)
stu[i+1]=a[i];
printf("初始%d位同学的信息表 \n",MAX);
printf("排名 姓名 平均分数\n");
for(i=1;i<=N;i++)
printf("%d: %6s %\n",i,stu[i].name,stu[i].avg);
printf("\n");
printf("\n");
printf("请输入学生的姓名: ");
scanf("%s",stu[0].name);
printf("\n");
printf("请输入平均成绩: ");
scanf("%f",&stu[0].avg);
printf("\n");
insort(stu,N);
printf("折半排序后同学的信息表 \n",MAX);
printf("排名 姓名 平均分数\n");
for(i=0;i<=N;i++)
{
printf("%d: %6s %\n",i+1,stu[i].name,stu[i].avg);
}
printf("\n");
}
程序运行结果如下 :
实验二叉排序树的建立
设计程序代码如下 :
#include<>
#include<>
#defineMAX5
typedefstructBnode
{
intkey;
structBnode*left;
structBnode*right;
}Bnode;
Bnode*btInsert(intx,Bnode*root);
voidInorder(Bnode*root);
voidmain()
{
inti;
inta[MAX]={60,40,70,20,80};
Bnode*root=NULL;
printf("按关键字序列建立二叉排序树 \n");
for(i=0;i<MAX;i++) printf("%d ",a[i]);
printf("\n");
for(i=0;i<MAX;i++) root=btInsert(a[i],root);
printf("中序遍历的二叉排序树 \n");
Inorder(root);
printf("\n");
}
Bnode*btInsert(intx,Bnode*root)
{
Bnode*p,*q;
intflag=0;
p=(Bnode*)malloc(sizeof(Bnode));
p->key=x;
p->right=p->left=NULL;
if(root==NULL)
{ root=p; returnp;}
q=root;
while(flag==0)
{
if(q->key>x)
{
if(q->left!=NULL)
q=q->left;
else
{
q->left=p;
flag=1;
}
}
else
{
if(q->right!=NULL)
q=q->right;
else
{
q->right=p;
flag=1;
}
}
}
returnroot;
}
voidInorder(Bnode*root)
{
if(root!=NULL){
Inorder(root->left);
printf("%d",root->key);
Inorder(root->right);
}
}
程序运行结果如下 :
实验名称:实验六 排序
泡沫法排序的改进算法
【描述】
某班学生成信息表中每个学生的包括各功的成和平均成,以及按平均成的排名等信息,要求从入每个学生各功的成,算出平均成,按平均成由高到低信息的重新排序,并定出每位同学的名次,打印排序后的信息表。
【基本要求】
4)建立学生成信息表,算平均成。
5)用泡沫法平均成排序,程序中要求一旦序列被排好序就束相排序操作。
数据】
自行
【提示】
1)用构数存放学生成信息表。
2)在某趟泡沫中没有生元素的交明已排好序
堆排序
【描述】
和建堆的程序,某一个待排序的序列,通人工跟踪程序的行,完成排序的全程【基本要求】
1)掌握建堆、的基本原理和算法步。
2)写出主函数,运行堆排序的程序。
3)掌握堆排序的算法程序,能例按步人工完成建堆和排序的程。
数据】
自行。
【提示】
(1)
是建堆的基本算法。
(2)
把要排序序列看成一棵完全二叉,用循方式从最后一个非叶(序号
k)开始,逐次序
号k,k-1,⋯的点,直至根点用算法,完成建堆。
(3)
不断通堆元素与堆中最后一个元素的交并,完成排序。
实验报告内容:
实验冒泡法排序的改进
设计程序代码如下 :
#include<>
#include<>
#defineMAX3
structstudent{
charname[10];
floatcs;
floatms;
floates;
floatavg;
};
voidsort(structstudents[],intn);
voidsort(structstudents[],intn)
{
structstudenttemp;
inti,j;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if(s[j].avg<s[j+1].avg){
temp=s[j];
s[j]=s[j+1];
s[j+1]=temp;
}
}
voidmain()
{
structstudentstu[MAX];
inti;
printf("请输入 %d位同学的姓名和各科成绩 \n",MAX);
for(i=0;i<MAX;i++)
{
printf("请输入第 %d位学生的姓名 :",i+1);
scanf("%s",stu[i].name);
printf("\n");