电大《数据结构》实验报告.pdf
数据结构形成性考核册 实验名称：实验一 线性表 线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。（2）在链表中删除一个最高分和一个最低分的结点。（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。（3）显示要求的结果。【实验步骤】（1）运行 PC中的 Microsoft Visual C+程序，（2）点击“文件”“新建”对话窗口中“文件”“c+Source File”在“文件名”中输入“”在“位置”中选择储存路径为“桌面”“确定”，（3）输入程序代码，程序代码如下:#include#include#include#include#include#define NULL 0#define PWRS 5 2.2fge=n;ame);printf(性别 0 女 1 男:);scanf(%d,&mi.sex);printf(年龄:);scanf(%d,&mi.age);printf(n);return 1;int calc(STD*m,STD*n,STD*r,float&Fage,float&Mage)int i,j=1,k=1;n0.age=r0.age=0;for(i=1;i=m0.age;i+)if(mi.sex=0)strcpy(nj.name,mi.name);nj.sex=mi.sex;nj.age=mi.age;n0.age+;Mage+=mi.age;j+;else strcpy(rk.name,mi.name);rk.sex=mi.sex;rk.age=mi.age;r0.age+;Fage+=mi.age;k+;Mage=Mage/n0.age;Fage=Fage/r0.age;cout女生的平均年龄是：Mage男生的平均年龄是：Fageendl;return 1;void print(STD*m)for(int i=1;inext=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中的 Microsoft Visual C+程序，（5）点击“文件”“新建”对话窗口中“文件”“c+Source File”在“文件名”中输入“”在“位置”中选择储存路径为“桌面”“确定”，（6）输入程序代码，程序代码如下:#include#include#define MaxSize 100 typedef char ElemType;typedef struct ElemType dataMaxSize;int top;ame);x=s0.avg;while(lowsmid.avg)hight=mid-1;else low=mid+1;for(k=0;klow-1;k+)strcpy(sk.name,sk+1.name);sk.avg=sk+1.avg;printf(%d,low);strcpy(slow-1.name,y);slow-1.avg=x;void main()Struct student aN=caozh,96,cheng,95,zhao,93,wang,92,chen,91;struct student stuN;int i;for(i=0;iN;i+)stui+1=ai;printf(初始%d 位同学的信息表n,MAX);1 2 5 4 3 printf(排名 姓名 平均分数n);for(i=1;i=N;i+)printf(%d:%6s%3.2fn,i,stui.name,stui.avg);printf(n);printf(n);printf(请输入学生的姓名：);scanf(%s,stu0.name);printf(n);printf(请输入平均成绩：);scanf(%f,&stu0.avg);printf(n);insort(stu,N);printf(折半排序后同学的信息表n,MAX);printf(排名 姓名 平均分数n);for(i=0;i=N;i+)printf(%d:%6s%3.2fn,i+1,stui.name,stui.avg);printf(n);程序运行结果如下:实验 二叉排序树的建立 设计程序代码如下:#include#include#define MAX 5 typedef struct Bnode int key;struct Bnode*left;struct Bnode*right;Bnode;Bnode*btInsert(int x,Bnode*root);void Inorder(Bnode*root);void main()int i;int aMAX=60,40,70,20,80;Bnode*root=NULL;printf(按关键字序列建立二叉排序树n);for(i=0;iMAX;i+)printf(%d ,ai);printf(n);for(i=0;ikey=x;p-right=p-left=NULL;if(root=NULL)root=p;return p;q=root;while(flag=0)if(q-keyx)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;return root;void Inorder(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#define MAX 3 struct student char name10;float cs;float ms;float es;float avg;void sort(struct student s,int n);void sort(struct student s,int n)struct student temp;int i,j;for(i=1;in;i+)for(j=0;jn-i;j+)if(sj.avgsj+1.avg)temp=sj;sj=sj+1;sj+1=temp;void main()struct student stuMAX;int i;printf(请输入%d 位同学的姓名和各科成绩n,MAX);for(i=0;iMAX;i+)printf(请输入第%d 位学生的姓名:,i+1);scanf(%s,stui.name);printf(n);printf(语文分数:);scanf(%f,&stui.cs);printf(n);printf(数学分数:);scanf(%f,&stui.ms);printf(n);printf(英语分数:);scanf(%f,&stui.es);printf(n);stui.avg=(stui.cs+stui.ms+stui.es)/3;sort(stu,MAX);printf(排名 姓名 语文 数学 外语 平均分数n);for(i=0;iMAX;i+)printf(%d:%6s%3.2f%3.2f%3.2f%3.2fn,i+1,stui.name,stui.cs,stui.ms,stui.es,stui.avg);程序运行结果如下:实验 堆排序 设计程序代码如下:#include#define N 8 struct NODE int date;void heapshift(struct NODE a,int i,int n)struct NODE temp;int j;temp=ai;j=2*i;while(jn)if(j+1aj+1.date)j+;if aj.date)ai=aj;i=j;j=2*i;else break;ai=temp;void heapsort(struct NODE a,int n)int i;struct NODE temp;for(i=n/2;i=1;i-)heapshift(a,i,n);for(i=n;i1;i-)temp=a1;a1=ai;ai=temp;heapshift(a,1,i-1);void main()struct NODE bN=40,80,65,100,14,30,55,50;struct NODE aN;int i;printf(初始数据序列：);for(i=0;iN;i+)ai+1.date=bi.date;for(i=1;i=N;i+)printf(%d ,ai.date);printf(n);printf(n);heapsort(a,N);printf(堆排序后的数据序列：);for(i=1;i=N;i+)printf(%d ,ai.date);printf(n);程序运行结果如下:
