中央电大数据结构形成性考核册实验报告.doc

中央电大本科数据结构形成性考核册实验报告实验名称：实验一 线性表线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序:（1） 显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。（2） 在链表中删除一个最高分和一个最低分的结点.（3） 计算该参赛者去掉一个最高分和一个最低分后的平均成绩。【基本要求】（1） 建立一个评委打分的单向链表；（2） 显示删除相关结点后的链表信息.（3） 显示要求的结果.【实验步骤】（1） 运行PC中的Microsoft Visual C+ 6.0程序,（2） 点击“文件”“新建” 对话窗口中“文件” “c+ Source File” 在“文件名”中输入“X1。cpp” 在“位置”中选择储存路径为“桌面” “确定,（3） 输入程序代码，程序代码如下：#include stdio。h include stdlib。h include include #define NULL 0 #define PWRS 5 /定义评委人数struct pw /定义评委信息 char name6； float score； int age; ; typedef struct pw PW; struct node /定义链表结点 struct pw data； struct node next; ；typedef struct node NODE； NODE *create（int m)； /创建单链表 int calc（NODE h）； /计算、数据处理 void print(NODE h）; /输出所有评委打分数据 void input(NODE *s);/输入评委打分数据 void output（NODE s);/输出评委打分数据 void main（) NODE *head； float ave=0； float sum=0； head=create（PWRS）; printf（”所有评委打分信息如下：n）； print（head）；/显示当前评委打分 calc（head）；/计算成绩 printf（该选手去掉 1 最高分和 1 最低分后的有效评委成绩:n）； print(head）;/显示去掉极限分后的评委打分 void input（NODE *s） printf(”请输入评委的姓名： ”)； scanf(S”，s-data。name）; printf(年龄: ”)； scanf（”d,&sdata.age）; printf(”打分： ”); scanf（”f”，sdata。score); printf（n”）; void output（NODE *s) printf（”评委姓名: %8s ,年龄: %d,打分： 2。2fn”,s-data.name,sdata.age，sdata.score）； NODE create(int m） NODE head，*p，q； int i; p=（NODE)malloc(sizeof(NODE）； head=p； q=p； pnext=NULL; for（i=1；i=m；i+） p=（NODE）malloc(sizeof（NODE）； input(p); pnext=NULL； qnext=p; q=p； return (head）; void print（NODE h) for(int i=1；(（idata。score； p=pnext; for（;p！=NULL；p=pnext） if（pdata.scorepmax-data.score) pmax=p； if（pdata。scorepmin-data.score） pmin=p; sum+=pdata.score； coutdata.name年龄： ”data。scoreendl; cout给出最低分的评委姓名：pmindata。namedata。scoreendl； printf(”n); sum=pmin-data.score; sum=pmaxdata。score； for （q=h，p=h-next；p！=NULL;q=p,p=pnext) if（p=pmin）qnext=pnext； p=q;/删除最低分结点 if（p=pmax） qnext=p-next； p=q;/删除最高分结点 ave=sum/（PWRS2）; cout”该选手的最后得分是:”aveendl； return 1; 程序运行结果如下：线性表的顺序存储结构【问题描述】用顺序表A记录学生的信息，编写程序：（1）将A表分解成两个顺序表B和C，使C表中含原A表中性别为男性的学生，B表中含原表中性别为女性的学生，要求学生的次序与原A表中相同。(2）分别求男生和女生的平均年龄【基本要求】（1） 建立学生信息的顺序表A。（2） 显示B表和C表中的相关信息.（3） 显示计算结果。【实验步骤;】（1）运行PC中的Microsoft Visual C+ 6。0程序，(2）点击“文件”“新建” 对话窗口中“文件” “c+ Source File” 在“文件名中输入“X1。cpp” 在“位置中选择储存路径为“桌面” “确定，（3） 输入程序代码，程序代码如下:include stdio。hinclude #include malloc.hinclude iostream.h#include include string。h /包含库函数strcpy的头文件#define NULL 0struct student /定义学生信息 char name8； int sex； /0 女： 1：男 int age；;typedef struct student STD；int create(STD *m）; /创建顺序表int calc（STD m，STD n，STD r，float Fage，float &Mage）； /计算、数据处理void print（STD *m）;const int MAX=100; /定义人数void main(） STD AMAX; STD BMAX； STD CMAX； float age1=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）；int create（STD *m)int n;printf (”请输入班级总人数:n ”）;scanf （”d”,&n）；m0.age=n； /置顺序表 长度printf（”请输入学生信息：n）； for（int i=1;i=n；i+） printf（”姓名： ”)； scanf(%s”，mi。name)； 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女生的平均年龄是：”Magenext; q-next=p; 尾插法：指针变量 q 始终指向尾结点，p 指针开辟单元，生成结 点： qnext=p; q=p； ?插入：p 所指向结点的后面插入新结点 s 所指结点 s-next=pnext; p-next=s； ?删除:p,q 指向相邻结点,q 所指结点是 p 所指结点的后继，删除 q 所指结点， pnext=q-next； ？遍历：p=pnext；实验名称:实验二 栈、列队、递归程序设计2。1 栈和队列的基本操作【问题描述】编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。【基本要求】（1）正确理解栈的先进后出的操作特点,建立初始栈,通过相关操作显示栈底元素。(2)程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。【实验步骤；】（4） 运行PC中的Microsoft Visual C+ 6。0程序，（5） 点击“文件”“新建” 对话窗口中“文件” “c+ Source File” 在“文件名”中输入“X1。cpp” 在“位置中选择储存路径为“桌面” “确定，（6） 输入程序代码，程序代码如下:include stdio。h#include malloc。hdefine MaxSize 100typedef char ElemType；typedef struct ElemType dataMaxSize；int top；/栈顶指针 SeqStack；/定义栈typedef struct ElemType elemMaxSize；int front，rear；/队首和队尾指针 SqQueue;/定义队列/初始栈函数void InitStack（SeqStack *s）s=（SeqStack )malloc（sizeof（SeqStack)；stop=-1;/-进栈函数int Push（SeqStack &s，ElemType e)if （stop=MaxSize-1）return 0；s-top+；sdatas-top=e；return 1；/-显示栈函数void DispStack(SeqStack *s）int i；for （i=stop；i=0;i-)printf（”%c ,s-datai）;printf（”n”);/-显示栈底元素void DispBottomStack(SeqStack s)printf（”c ,sdata0）；/先进后出,栈底元素为第一个元素，即data0printf(”n”）；/-判空栈函数int StackEmpty（SeqStack s)return（s-top=1);/-出栈函数int Pop（SeqStack &s,ElemType e）if （s-top=1）return 0；e=sdatastop；stop-；return 1;/初始队列函数void InitQueue（SqQueue *q）q=(SqQueue ）malloc (sizeof（SqQueue）；q-front=q-rear=0;/-入队列函数int InQueue（SqQueue q,ElemType e）if (q-rear+1）MaxSize=qfront） /队满return 0；qrear=（qrear+1）MaxSize;qelemqrear=e；return 1；/-出队列函数int OutQueue（SqQueue &q，ElemType e）if （q-front=q-rear） /队空return 0;q-front=（qfront+1）MaxSize；e=qelemq-front;return 1；/-判空队列函数int QueueEmpty（SqQueue q)return(qfront=qrear）；/-主程序void main（）ElemType e;SeqStack *s；printf（(1）初始化栈sn”);InitStack（s)；printf(”(2)栈为sn”,（StackEmpty（s）?”空”：”非空”)；printf(”（3）依次进栈元素a,b,c,d，en）;Push（s，a)；/入栈元素1Push(s，b)；/入栈元素2Push(s,c）；/入栈元素3Push（s，d）;/入栈元素4Push（s，e）;/入栈元素5printf(”(4)栈为sn”,(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(”队列为sn”，(QueueEmpty(q)?”空”:非空）；printf（(9）出队列/入栈序列：”）；while （！QueueEmpty（q)）OutQueue(q，e）；/出队Push（s,e);/入栈printf（c ”，e)；printf(”n)；printf（10）栈为%s，(StackEmpty（s）?”空”：非空”）；printf（队列为sn，（QueueEmpty(q)？”空：非空）;free(q);/释放队列printf(”(11)从栈顶到栈底元素：）;DispStack(s）;free（s);/释放栈程序运行结果如下：2.2 递归程序设计【问题描述】给定一个5位的十进制正整数，用递归法分别编制程序：（1)要求从低位到高位逐次输出各位数字。（2）要求从高位到低位逐次输出各位数字。【基本要求】（1） 比较题中两种不同要求的递归程序设计和执行过程差别。（2） 正确理解递归程序的执行过程.（3） 显示计算结果。【实验步骤】（1）运行PC中的Microsoft Visual C+ 6。0程序,点击“文件”“新建” 对话窗口中“文件 “c+ Source File 在“文件名”中（2）输入“X1.cpp” 在“位置”中选择储存路径为“桌面” “确定”,（3） 输入程序代码程序代码如下:includestdio。hincludevoid out(int n，int i）/从高位到低位输出函数int x，y；y=int（pow（10,i）;if （n！=0）x=n/y；n=n-xy;printf（”d ”,x);else printf（”0 ”）;i;if(i=0） out（n,i）;void out1（int m，int j）/从低位到高位输出函数int x，z；if (m！=0)x=int（m/10);z=mx10；m=x；printf（%d ，z)；else printf(0 ”）；j-；if（j=0） out1(m，j）;void main（）int m,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”）；l程序运行结果如下:实验结论：栈和队列是运算受限制的线性表l栈：后进先出（LIFO）n例:进栈b， c， d， e， f 出栈可能为 f， e, d， c， b； b, c, d, e， f ； c， b， e, d, f 但不可能是e， d， f， b, cl队列:先进先出（FIFO)n例：入队1，2，3,4，5 出队1，2,3，4，5实验名称:实验三 二叉树3.1 二叉树的顺序存储结构和链式存储结构【问题描述】设一棵完全二叉树用顺序存储方法存储于数组tree中,编写程序:（1） 根据数组tree,建立与该二叉树对应的链式存储结构。（2） 对该二叉树采用中序遍历法显示遍历结果。【基本要求】（1） 在主函数中,通过键盘输入建立设定的完全二叉树的顺序存储结构.（2） 设计子函数,其功能为将顺序结构的二叉树转化为链式结构。（3） 设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。（4） 通过实例判断算法和相应程序的正确性。【实验步骤】（7） 运行PC中的Microsoft Visual C+ 6.0程序，（8） 点击“文件“新建” 对话窗口中“文件 “c+ Source File” 在“文件名”中输入“X1。cpp” 在“位置”中选择储存路径为“桌面 “确定，（9） 输入程序代码，程序代码如下:includestdio。hincludemalloc。hincludestring。hincludestdlib.hincludedata=treei；printf（”c ”，p-data ）;Creab（tree，n，2*i，pleft)；Creab(tree，n,2*i+1，p-right)；/中序遍历树/void Inorder(NODE p)if（p！=NULL） Inorder（p-left）；printf（c ”，pdata）;Inorder（pright); 程序运行结果如下:3。1 二叉树的遍历【问题描述】设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。【基本要求】（1） 掌握前序遍历二叉树的步骤,针对任意一棵二叉树能人工完成对二叉树的前序遍历。（2） 能掌握栈的工作特点,并能正确应用这一特点实现对二叉树的遍历.【实验步骤】（1）运行PC中的Microsoft Visual C+ 6。0程序，点击“文件”“新建 对话窗口中“文件 “c+ Source File 在“文件名”中(2）输入“X1。cpp 在“位置中选择储存路径为“桌面 “确定，（3) 输入程序代码程序代码如下：void FirstOrderAccess1（BTree * header)BTree stackMAX_NODE；BTree *p;int top；top = 0；p = header；do while(p！=NULL） printf（BTreed = c“t”，porder，pdata）； if（p-rchild!=NULL) stack+top = prchild; p = plchild； if(top!=0） p = stacktop；while(（top0）|(p!=NULL）);实验名称：实验四 图的存储方式和应用4。1建立图的邻接矩阵【问题描述】根据图中顶点和边的信息编制程序建立图的邻接矩阵。【基本要求】（4） 程序要有一定的通用性.（5） 直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵【测试用例】【实现提示】（1） 对图的顶点编号。（2） 在上图中，以顶点1为例，因为顶点2,3，4与顶点1关联,可以输入信息1 2 3 4,然后设法求出与顶点1关联的结点,从而求得邻接矩阵中相应与顶点1的矩阵元素.21534实验 图4-1 l 设计程序代码如下：#includestdio。h#define MaxVertexNum 5define MaxEdgeNum 20define MaxValue 1000typedef int VertexType；typedef VertexType vexlist MaxVertexNum；typedef int adjmatrix MaxVertexNum MaxVertexNum;void Createl(vexlist Gv，adjmatrix GA，int n，int e)int i,j，k，w;printf（输入d个顶点数据n”,n）;for(i=0；in；i+） scanf（d”,Gvi）;for（i=0；in；i+)for（j=0；jn;j+)if（i=j) GAij=0；else GAij=MaxValue；Printf（“输入一条边的两端点序号i和j及边上的权wn”）;printf（输入d条无向带权边n，e）；for（k=1；ksmid.avg ）hight=mid-1；else low=mid+1；for（k=0；klow1;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);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”);l 程序运行结果如下：实验5.2 二叉排序树的建立l 设计程序代码如下：include#define MAX 5typedef struct Bnodeint 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；iMAX;i+）root=btInsert（ai，root）;printf（”中序遍历的二叉排序树n”）；Inorder(root）；printf（”n）;Bnode btInsert（int x，Bnode root)Bnode p,q；int flag=0;p=（Bnode ）malloc（sizeof（Bnode)；pkey=x；p-right=pleft=NULL；if(root=NULL）root=p；return p;q=root；while（flag=0）if(qkeyx）if(q-left！=NULL）q=qleft;elseqleft=p；flag=1；elseif（qright！=NULL)q=q-right；elseq-right=p；flag=1；return root;void Inorder(Bnode *root） if（root！=NULL） Inorder(root-left)； printf（%d ”，root-key)； Inorder（root-right）； l 程序运行结果如下：实验名称：实验六 排序6。1 泡沫法排序的改进算法【问题描述】某班学生成绩信息表中每个学