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

1、.中央电大本科数据结构形成性考核册实验报告实验名称：实验一线性表线性表的链式存储结构【问题描述 】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（、年龄、所给分数等）。（2）在链表中删除一个最高分和一个最低分的结点。（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。【基本要求 】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。（3）显示要求的结果。【实验步骤 】（1）运行 PC中的 Microsoft Visual C+ 6.0程序，（2）点击“文件”“新建”对话窗口中“文件”“

2、 c+ Source File” 在“文件名”中输入“X1.cpp ” 在“位置”中选择储存路径为“桌面”“确定”，（ 3） 输入程序代码，程序代码如下 :#include #include #include #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 no

3、de 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最高分和

4、 1最低分后的有效评委成绩:n);print(head);/显示去掉极限分后的评委打分void input(NODE *s)printf(请输入评委的: );scanf(%S,&);printf(年龄 : );scanf(%d,&s-data.age);printf(打分 : );scanf(%f,&s-data.score);printf(n);void output(NODE *s)printf(评委 : %8s ,年龄 : %d, 打分 : %2.2fn,,s-data.age,s-data.score);NODE *create(int m)

5、NODE *head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=p;q=p;p-next=NULL;for(i=1;inext=NULL;q-next=p;q=p;.下载可编辑 .return (head);void print(NODE *h) for(int i=1;(inext!=NULL);i+) h=h-next;output(h); printf(n);int calc(NODE *h)NODE *q,*p,*pmin,*pmax;float sum=0;float ave=0;p=h-next;/指向首元结点pmin=pmax=p

6、; /设置初始值sum+=p-data.score;p=p-next;for(;p!=NULL;p=p-next)if(p-data.scorepmax-data.score) pmax=p;if(p-data.scoredata.score) pmin=p;sum+=p-data.score;cout给 出 最 高 分 的 评 委 ： 年 龄 ：data.age分 值 ：data.scoreendl;cout给 出 最 低 分 的 评 委 ： 年 龄 ：data.age分 值 ：data.scoredata.score;sum-=pmax-data.sco

7、re;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该选手的最后得分是：aveendl;return 1;程序运行结果如下:.下载可编辑 .线性表的顺序存储结构【问题描述】用顺序表A 记录学生的信息，编写程序：（1）将 A 表分解成两个顺序表B 和 C，使 C 表中含原A 表中性别为男性的学生，B 表中含原表中性别为女性的学生，要求学生的次序与原A 表中相同。（2）分别求男

8、生和女生的平均年龄【基本要求】（ 1） 建立学生信息的顺序表 A。（ 2） 显示 B 表和 C 表中的相关信息。（ 3） 显示计算结果。【实验步骤 ; 】（1）运行 PC中的 Microsoft Visual C+ 6.0程序，（ 2）点击“文件” “新建” 对话窗口中 “文件” “c+ Source File ” 在“文件名” 中输入“ X1.cpp ”在“位置”中选择储存路径为“桌面”“确定”，(3) 输入程序代码，程序代码如下:#include #include #include #include #include #include /包含库函数strcpy的头文件.下载可编辑 .#de

9、fine 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

10、女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,&);printf(性别 0女 1男:);scanf(%d,&

11、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.sex=mi.sex; nj.age=mi.age; n0.age+; Mage+=mi.age;j+;elsestrcpy(,);rk.sex

12、=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 所

13、指结点是p所指结点的后继，删除q所指结点，p-next=q-next; ?遍历： p=p-next;.下载可编辑 .实验名称：实验二栈、列队、递归程序设计2.1栈和队列的基本操作【问题描述 】编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。【基本要求 】（ 1）正确理解栈的先进后出的操作特点, 建立初始栈，通过相关操作显示栈底元素。（ 2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。【实验步骤 ; 】（4）运行 PC中的 Microsoft Visual C+ 6.0程序，（5）点击“文件”“新建”对话窗口中“文件”“ c+ Sou

14、rce File” 在“文件名”中输入“X1.cpp ” 在“位置”中选择储存路径为“桌面”“确定”，（ 6） 输入程序代码，程序代码如下 :#include #include #define MaxSize 100typedef char ElemType;typedef structElemType dataMaxSize;int top;/ 栈顶指针 SeqStack;/定义栈typedef structElemType elemMaxSize;int front,rear;/ 队首和队尾指针 SqQueue;/定义队列/-初始栈函数void InitStack(SeqStack *&s

15、)s=(SeqStack *)malloc(sizeof(SeqStack);s-top=-1;/-进栈函数int Push(SeqStack *&s,ElemType e)if (s-top=MaxSize-1).下载可编辑 .return 0;s-top+;s-datas-top=e;return 1;/-显示栈函数void DispStack(SeqStack *s)int i;for (i=s-top;i=0;i-)printf(%c ,s-datai);printf(n);/-显示栈底元素void DispBottomStack(SeqStack *s)printf(%c ,s-da

16、ta0);/先进后出 , 栈底元素为第一个元素, 即 data0printf(n);/-判空栈函数int StackEmpty(SeqStack *s)return(s-top=-1);/-出栈函数int Pop(SeqStack *&s,ElemType &e)if (s-top=-1)return 0;e=s-datas-top;s-top-;return 1;/-初始队列函数void InitQueue(SqQueue *&q)q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0;.下载可编辑 ./-入队列函数int InQueue(

17、SqQueue *&q,ElemType e)if (q-rear+1)%MaxSize=q-front) /队满return 0;q-rear=(q-rear+1)%MaxSize;q-elemq-rear=e;return 1;/-出队列函数int OutQueue(SqQueue *&q,ElemType &e)if (q-front=q-rear) /队空return 0;q-front=(q-front+1)%MaxSize;e=q-elemq-front;return 1;/-判空队列函数int QueueEmpty(SqQueue *q)return(q-front=q-rear

18、);/-主程序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);/入栈元素4.下载可编辑 .Push(s,e);/入栈元素5printf(4)栈为 %sn,(StackEmpty(s)?空 : 非空 );printf(5)从栈顶到栈底元素:);DispStack(s);p

19、rintf(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

20、,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） 比较题中两种不同要求的递

21、归程序设计和执行过程差别。（ 2） 正确理解递归程序的执行过程。（ 3） 显示计算结果。【 实验步骤 】（1）运行 PC中的 Microsoft Visual C+ 6.0程序，点击“文件” “新建” 对话窗口中 “文件”“c+ Source File ” 在“文件名” 中（ 2）输入“ X1.cpp ”在“位置”中选择储存路径为“桌面”“确定”，(3)输入程序代码程序代码如下 :#include#includevoid out(int n,int i)/从高位到低位输出函数int x,y;y=int(pow(10,i);if (n!=0)x=n/y;n=n-x*y;printf(%d ,x)

22、;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=m-x*10;.下载可编辑 .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);prin

23、tf(从高位到低位逐次输出各位数字:);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二叉树的顺序存储结构和链式存储结

24、构【问题描述 】设一棵完全二叉树用顺序存储方法存储于数组tree中，编写程序：（ 1） 根据数组 tree ，建立与该二叉树对应的链式存储结构。（ 2） 对该二叉树采用中序遍历法显示遍历结果。【基本要求 】（ 1） 在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。（ 2） 设计子函数，其功能为将顺序结构的二叉树转化为链式结构。（ 3） 设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。（ 4） 通过实例判断算法和相应程序的正确性。【实验步骤 】（7）运行 PC中的 Microsoft Visual C+ 6.0程序，（8）点击“文件”“新建”对话窗口中“文件”“ c+ S

25、ource File ” 在“文件名”中输入“X1.cpp ” 在“位置”中选择储存路径为“桌面”“确定”，（ 9） 输入程序代码，程序代码如下 : #include #include #include #include #include#define MaxSize 10typedef struct nodechar data;struct node *left,*right;NODE;void Creab(char *tree,int n,int i,NODE *p);void Inorder(NODE *p);void main()NODE *p;char treeMaxSize;int

26、 n=1;int i=1;printf(请输入完全二叉数的节点值（连续输入字符，以回车结束输入。）:);while(treen = getchar( ) != n) n+;treen =n;p=NULL;.下载可编辑 .Creab(tree,n,i,p);Inorder(p);void Creab(char *tree,int n,int i,NODE *p)if(i=n) p=NULL;elsep=(NODE *)malloc(sizeof(NODE);p-data=treei;printf(%c ,p-data );Creab(tree,n,2*i,p-left);Creab(tree,n

27、,2*i+1,p-right);/* 中序遍历树 */void Inorder(NODE *p)if(p!=NULL) Inorder(p-left);printf(%c ,p-data);Inorder(p-right);程序运行结果如下:3.1二叉树的遍历【问题描述 】设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。【基本要求 】（ 1） 掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序遍历。（ 2） 能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。.下载可编辑 .【实验步骤 】（1）运行 PC中的 Microsoft Visual C+

28、 6.0程序，点击“文件” “新建” 对话窗口中 “文件”“c+ Source File ” 在“文件名” 中（ 2）输入“ X1.cpp ”在“位置”中选择储存路径为“桌面”“确定”，(3)输入程序代码程序代码如下 :void FirstOrderAccess1(BTree * header)BTree * stackMAX_NODE;BTree *p;int top;top = 0;p = header;dowhile(p!=NULL)printf(BTree%d = %c“t,p-order,p-data);if(p-rchild!=NULL)stack+top = p-rchild;p

29、 = p-lchild;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 关联的结点，从而求得邻接矩阵中

30、相应与顶点1 的矩阵元素。21534实验 图 4-1设计程序代码如下:#include#define MaxVertexNum 5#define MaxEdgeNum 20#define 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个

31、顶点数据 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;k=e;k+)scanf(%d%d%d,&i,&j,&w);GAij=GAji=w;void main().下载可编辑 .vexlist vl;adjmatrix a;Createl(vl,a,5,8);.下载可编辑 .实验名称：实验五查找5.1折半查找【问

32、题描述 】某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。【基本信息 】（ 6） 建立现有学生信息表，平均成绩已有序。（ 7） 输入插入学生的记录信息。（ 8） 用折半查找找到插入位置，并插入记录。【 测试数据 】自行设计。【实验提示 】（ 10） 用结构数组存储成绩信息表。（ 11） 对记录中的平均成绩进行折半查找。5.2二叉排序树的建立【问题描述 】参阅相关资料，阅读建立二叉排序树的程序。【基本要求 】（ 1） 掌握建立二叉排序树的原理和方法。（ 2） 能

33、跟踪程序人工建立二叉排序树。实验报告容：实验 5.1折半查找设计程序代码如下:#include#include#define N 5struct studentchar name10;float avg;void insort(struct student s,int n).下载可编辑 .int low,hight,mid,k;char y10;float x;low=1;hight=n;strcpy(y, );x=s0.avg ;while(lowsmid.avg )hight=mid-1;elselow=mid+1;for(k=0;klow-1;k+)strcpy(sk.na

34、me,sk+1.name) ;sk.avg =sk+1.avg ;printf(%d,low);strcpy( ,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,,s

35、tui.avg);printf(n);printf(n);printf(请输入学生的：);scanf(%s, );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.avg);printf(n);程序运行结果如下:实验 5.2二叉排序树的建立设计程序代码如下:#include#i

36、nclude#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;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;elseq-left=p;flag=1;elseif(q-right!=NULL)q=q-right;elseq-right=p;flag=1;return root;.下载可编辑 .void Inorder(Bnode *root)if