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

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

2、新建” t对话窗口中“文件” C+ Source File ”宀在“文件名”中输入“Xl.cpp t在“位置”中选择储存路径为“桌面”确定”，（ 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;type

3、def 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);/ 计算成绩pri

4、ntf( 该选手去掉 1 最高分和 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);N

5、ODE *create(int m)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; / 指向首元结点

6、pmin=pmax=p; /设置初始值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.sc

7、oredata.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 该选手的最后得分是： aveendl;return 1;程序运行结果如下 :to icontinuc分和1最低分后的有效评委成赛:76-00:QK.UkSI5目呼邛0话曙入龙雯的姓名:IT炉小胃繭人评娈的姓名: 丰蚣35 丁芬=臼C典评畫的姓名: 4U:

8、 99诒输入评娈的姓名:不韵工46打爵=79y n一 1骯掉： 的去容 选奠養 谟评评评 Ia bcid.B亠巴由亠也比LL3; _二一二-二一二 _二 拜#卑洋拜T加息0 0 0 B a 0 _M 0R0 ?7 日 9 & GO！ 三 娈容容容容容 hl 二.1 _L-F.二 r_r4 详HHHfrtH US 4 4 5 3M5Q- 4 m 一4m 金)133石锁人评炎的姓名: 帀陽33S11JE：+实鲨1 | Z3Debux 1. ext线性表的顺序存储结构【问题描述】用顺序表A记录学生的信息，编写程序：（1 ）将A表分解成两个顺序表B和C,使C表中含原A表中性别为男性的学生， B表中含原

9、表中性别为女性的学生，要求学生的次序与原 A表中相同。（2 ）分别求男生和女生的平均年龄【基本要求】（1）建立学生信息的顺序表A。（2）显示B表和C表中的相关信息。（3）显示计算结果。【实验步骤；】（1）运行 PC 中的 Microsoft Visual C+ 6.0 程序，（2）点击“文件新建” t对话窗口中“文件” C+ Source File”宀在“文件名”中输入“X1.cppt在“位置”中选择储存路径为“桌面”确定”，（3）输入程序代码，程序代码如下：#i nclude #i nclude #in clude #in clude #in clude #include /包含库函数 st

10、rcpy的头文件#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=

11、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,

12、&);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;n O.age=rO.age=O;for( i=1;i=m0.age;i+) if(mi.sex=O)strcpy (n j. name,mi. name);n j.sex=mi.sex; n j.age=mi.age;n O.age+; Mage+=

13、mi.age;j+;elsestrcpy(rk. name,mi. name);rk.sex=mi.sex; rk.age=mi.age;rO.age+;Fage+=mi.age;k+;Mage=Mage/n O.age;Fage=Fage/rO.age;cout女生的平均年龄是：Mage男生的平均年龄是：Fageendl;return 1;void prin t(STD *m)for(i nt i=1;i=m0.age;i+)printf (姓名:%3s，性别(0 女 1 男):%d,年龄:dn,,mi.sex,mi.age); 程序运行结果如下：生的=1,rl=M I 灯:劉

14、12:ddd,性别佃女1；ddd,性另l细女1 m anu key to continueBJQjli.龄：11了入学生信 a = aaa12年年幸辜 年年年 114,5世宅：ddd曹卩畀1名；bhb&世名:aaa,性别 住名:bh*j,生别 左名ACS怪别 住名:ddd,性卿 理胖霸莘器是 乂生名启肮己录如下； 吃纟性界细女：L:bbb.性别W女1：ccc, 1 n ext=q-n ext; q- next=p;尾插法：指针变量q始终指向尾结点，p指针开辟单元，生成结点：q-next=p; q=p; ?插入：p所指向结点的后面插入新结点s所指结点 s-next=p-next; p-next=

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

16、文件新建” t对话窗口中“文件” C+ Source File ”宀在“文件名”中输入“X1 t在“位置”中选择储存路径为“桌面”确定”，( 6) 输入程序代码，程序代码如下 :#include #include #define MaxSize 100typedef char ElemType;typedef structElemType dataMaxSize;int top;/栈顶指针 SeqStack;/ 定义栈typedef structElemType elemMaxSize;int front,rear;/队首和队尾指针 SqQueue;/ 定义队列/-初始栈函数void Init

17、Stack(SeqStack *&s)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),即

18、 data0printf(%c ,s-data0);/ 先进后出 ,栈底元素为第一个元素 printf(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 InQ

19、ueue(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=

20、q-rear);/ 主程序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);pr

21、intf(6)栈底元素为:);DispBottomStack(s);printf(7)出栈/入队列序列：”)；SqQueue *q;In itQueue(q);while (!StackEmpty(s)Pop(s,e);/ 出栈prin tf(%c ,e);In Queue(q,e); 入队prin tf(n);printf(8)栈为 %s,(StackEmpty(s)?空:非空); printf(队列为 %sn,(QueueEmpty(q)?空:非空); printf(9)出队列/入栈序列:);while (!QueueEmpty(q) OutQueue(q,e); 出队Push(s,e);

22、入栈prin tf(%c ,e);prin tf(n);printf(10)栈为 %s,(StackEmpty(s)?空:非空); printf(队列为 %sn,(QueueEmpty(q)?空:非空); free(q);/释放队列printf(11)从栈顶到栈底元素:);DispStack(s); free(s);/ 释放栈程序运行结果如下：播次进栈元素仏乩悅为非主栈底元素为“ 巧岀驚?M列序歹 栈为空,队列崩1S为非空.Mr 险戻栈擴囲糕斥元素= Press amy key to cont inue栈顶到栈底兀素w d c b aU ：e d c b an|：零 d c b aabode2

23、.2 递归程序设计问题描述 】给定一个 5 位的十进制正整数，用递归法分别编制程序： (1)要求从低位到高位逐次输出各位数字。(2)要求从高位到低位逐次输出各位数字。基本要求 】( 1) 比较题中两种不同要求的递归程序设计和执行过程差别。( 2) 正确理解递归程序的执行过程。( 3) 显示计算结果。实验步骤 】( 1)运行 PC 中的 Microsoft Visual C+ 6.0 程序，点击“文件”“新建”t对话窗口中“文件”t “C+ Source File ”宀在“文件名”中(2)输入“Xl.cppt在“位置”中选择储存路径为“桌面”t “确定”，(3) 输入程序代码程序代码如下 :#i

24、nclude#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);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;prin tf(%d ,z);else printf(0 );j-；if(j=0) out1(m,j);void mai n()int m, n, o,x,i,

25、j;printf(”输入需要排列的数字:n); scan f(%d, &o);m=n=o;x=n;i=-1;while(x!=0)x=x/10;i+;求出i为十进制正整数位数j=i;prin tf(n ”);printf(”从高位到低位逐次输出各位数字：”);out( n, i);prin tf(n ”);printf(”从低位到高位逐次输出各位数字：”);out1(m,j);prin tf(n ”);程序运行结果如下：输入需要排列的数字：13579从高位到低位逐次输岀各位数壬泡3579 从袪位罰高位逐次鎰岀卷位数学詔7531Press an key to con tin ueHN入需要排列的

26、数字:3456 25 34 43 SpHPress any ke to continue实验结论:栈和队列是运算受限制的线性表栈：后进先出（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 ，建立与

27、该二叉树对应的链式存储结构。( 2) 对该二叉树采用中序遍历法显示遍历结果。【 基本要求 】( 1) 在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。( 2) 设计子函数，其功能为将顺序结构的二叉树转化为链式结构。( 3) 设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。( 4) 通过实例判断算法和相应程序的正确性。【 实验步骤 】(7) 运行 PC 中的 Microsoft Visual C+ 6.0 程序，(8) 点击“文件新建”t对话窗口中“文件” C+ Source File ”宀在“文件名”中输入“Xl.cppt在“位置”中选择储存路径为“桌面”确定”，( 9

28、)输入程序代码，程序代码如下 :#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 n=1;int i=1;printf( 请输入完全二叉数的节点值(连续输入字符，以回车结束输入。 ) :); while(t

29、reen = getchar( ) != n) n+;treen =n;p=NULL;Creab(tree,n,i,p);Ino rder(p);void Creab(char *tree, int n,i nt i,NODE *p) if(i=n) p=NULL;else p=(NODE *)malloc(sizeof(NODE); p_data=treei;prin tf(%c ,p-data );Creab(tree, n, 2*i,p-left);Creab(tree, n, 2*i+1,p-right);/*中序遍历树*/void In order(NODE *p)if(p!=NUL

30、L) Ino rder(p-left);prin tf(%c ,p-data);Ino rder(p-right);程序运行结果如下：贋输入完全二叉数的节点倩连续输入字符，以回车结東输入。）旳hij abdhiejcfgr Pfcss an ji key to continue3.1二叉树的遍历【问题描述】设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。【基本要求】（1）掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序遍历。（2）能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。【实验步骤】( 1)运行 PC 中的 Microsoft Visu

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

32、ild;p = 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关联的结点，从而求得邻接矩阵中相应与顶点1的矩阵元素。设计程序代码如下#in

33、 clude#defi ne MaxVertexNum 5 #defi ne MaxEdgeNum 20#defi ne MaxValue 1000 typedef 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

34、);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 折半查找【 问题描述 】某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登

35、记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。 【 基本信息 】（6）建立现有学生信息表，平均成绩已有序。（ 7） 输入插入学生的记录信息。（8） 用折半查找找到插入位置，并插入记录。 【 测试数据 】自行设计。【 实验提示 】（10 ） 用结构数组存储成绩信息表。（11 ） 对记录中的平均成绩进行折半查找。5.2 二叉排序树的建立【 问题描述 】 参阅相关资料，阅读建立二叉排序树的程序。【 基本要求 】（1） 掌握建立二叉排序树的原理和方法。（2） 能跟踪程序人工建立二叉排序树。实验报告内容：实验 5.1 折半查找设计程序代码如下#include

36、 #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;else low=mid+1; for(k=0;klow-1;k+)strcpy(,sk+1.name) ; sk.avg =sk+1.avg ; printf(%d,low

37、);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,,stui.avg); printf(n);printf(n);printf(

38、 请输入学生的姓名： );scanf(%s, );printf(n);printf( 请输入平均成绩： );scanf(%f,&stu0.avg );printf(n);in sort(stu,N);printf(折半排序后同学的信息表n ”,MAX);printf(排名姓名平均分数n); for(i=0;i=N;i+)prin tf(%d:%6s%3.2fn,i+1,stui. name,stui.avg);prin tf(n);程序运行结果如下实验5.2二叉排序树的建立设计程序代码如下：#i nclude#i nclude#defi ne MAX 5typedef str

39、uct Bnodeint key;struct Bnode *left;struct Bnode *right;Bn ode;Bnode * bt In sert(i nt x,B node *root);void Ino rder(B node *root);void mai n()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(ro

40、ot=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 Ino rder(B node *root)if(root!=NULL) In order(root-left);prin tf(%d ”,root-key);Ino rder(root-right);程序运行结果如下实验名称：实验六 排序6.1 泡沫

41、法排序的改进算法【 问题描述 】 某班学生成绩信息表中每个学生的记录包括各门功课的成绩和平均成绩，以及按平均成绩的排名等信息， 要求从键盘输入每个学生各门功课的成绩，计算出平均成绩，按平均成绩由高到低对信息的记录重新排序， 并定出每位同学的名次，打印排序后的信息表。【 基本要求 】（9） 建立学生成绩信息表，计算平均成绩。（10 ） 用泡沫法对平均成绩排序，程序中要求一旦序列被排好序就结束相应排序操作。【 测试数据 】自行设计【 实验提示 】（1） 用结构数组存放学生成绩信息表。（2） 在某趟泡沫中没有发生元素间的交换则说明已排好序6.2 堆排序【 问题描述 】 阅读筛选和建堆的程序，针对某一

42、个待排序的序列，通过人工跟踪程序的执行，完成排序的全过程【 基本要求 】（1） 掌握建堆、筛选的基本原理和算法步骤。（2） 写出主函数，试运行堆排序的程序。（3）掌握堆排序的算法程序，能针对实例按步骤人工完成建堆和排序的过程。【 测试数据 】自行设计。【 实验提示 】（1） 筛选是建堆的基本算法。（2）把要排序序列看成一棵完全二叉树，用循环方式从最后一个非叶结（设序号为k）开始，逐次对序号为k, k-1,的结点，直至根结点调用筛选算法，完成建堆。（ 3）不断通过堆顶元素与堆中最后一个元素的交换并筛选，完成排序。实验报告内容：实验 6.1 冒泡法排序的改进设计程序代码如下#include#include#define MAX 3 struct studentchar name10;float cs;float ms;float es;float avg;void sort(struct student s,int n);void s