国开助手《数据结构（本）》形考实验报告答案

1. 请在实验1—实验7中选择其中一个，认真完成并提交实验报告，老师会根据你的实验报告给出成绩，本次实践活动满分100分，占形成性考核成绩的20%，你一定要认真完成哦！
2. 实验7 排序
3. 1 冒泡排序的改进算法
4. 问题描述
5. 某班学生成绩信息表中每个学生的记录包含各门功课的成绩和平均成绩，以及按平均成绩的排名等信息，要求从键盘输入每个学生各门功课的成绩，计算出平均成绩，按平均成绩由高到低对信息表的记录重新排序，并定出每位同学的名次，打印排序后的信息表。
6. 实验要求
7. （1）建立学生成绩信息表，计算平均成绩。
8. （2）用冒泡法对平均成绩排序，程序中要求一旦序列被排好序就结束相应排序操作。
9. 如果对于本实验无从下手，你可以通过查看“设计思路”，帮助你开拓思维。
10. （1）用结构数组存储学生成绩信息表。
11. （2）在某趟冒泡排序中没有发生元素间的交换则说明已排好序。
12. 如果对于自己编写的程序不知道是否正确，你可以通过查看“实验设计”进行核查。
13. 程序代码如下：
14. /*实验6.1 冒泡法排序的改进算法*/
15. #include
16. #define N1 5 /*学生人数*/
17. #define N2 3 /*课程门数*/
18. /*定义学生信息类型*/
19. typedef struct{
20. char name[10]; /*姓名*/
21. int score[N2]; /*N2门课程成绩*/
22. float avg; /*平均成绩*/
23. }Student;
24. void bsort（Student*a,int n）; /*改进的冒泡排序*/
25. void main（）
26. {
27. Student a[N1];
28. int i,j;
29. printf（"请输入 %d 位学生信息（姓名、 %d 门课程成绩）nn",N1,N2）;
30. for（i=0; i
31. {
32. printf（"输入第 %d 位学生信息: ",i+1）;
33. scanf（"%s",a.name）;
34. a.avg=0;
35. for（j=0; j
36. {
37. scanf（"%d",&a.score[j]）;
38. a.avg+=a.score[j];
39. }
40. a.avg/=N2; /*计算平均成绩*/
41. }
42. bsort（a,N1）; /*排序*/
43. /*排序后的学生信息表*/
44. printf（"n名次 姓名 "）;
45. for（i=0; i
46. printf（"课程%d ",i+1）;
47. printf（"平均成绩n"）;
48. for（i=0; i
49. {
50. printf（"%-4d %-4s ",i+1,a.name）;
51. for（j=0; j
52. printf（"%-6d",a.score[j]）;
53. printf（"%-6.1fn",a.avg）;
54. }
55. }
56. /*改进的冒泡排序，按平均成绩从高到低排序*/
57. void bsort（Student *a,int n）
58. {
59. Student temp;
60. int i,j,flag;
61. for（j=0; j
62. {
63. flag=0;
64. for（i=0; i
65. if（a.avg
66. {
67. flag=1; /*本趟有元素交换*/
68. temp=a;
69. a=a[i+1];
70. a[i+1]=temp;
71. }
72. if（flag==0） break; /*没有元素交换，说明已排好序*/
73. }
74. }
75. 如果已运行程序得出实验结果，你可以查看“测试结果”进行检测。
76. 程序运行结果如下：
77. 程序运行结果如下：
78. 通过本实验的学习，有如下收获：
79. （1）学生人数和课程门数分别用常量N1和N2定义，便于程序的修改与测试。
80. （2）N2门课程成绩在结构类型定义中用一维数组存放，提高程序的通用性。
81. 2 堆排序
82. 问题描述
83. 阅读筛选和建堆的程序，针对某一个待排序的序列，通过人工跟踪程序的执行，完成排序的全过程。
84. 实验要求
85. （1）掌握建堆、筛选的基本原理和算法步骤。
86. （2）写出主函数，试运行堆排序的程序。
87. （3）掌握堆排序的算法程序，能针对实例按步骤人工完成建堆和排序的过程。
88. 请认真阅读以上实验的问题描述，按照实验要求认真独立完成实验。如果在实验过程中遇到困难，你可以通过以下辅助方式，顺利完成本实验。
89. 如果对于本实验无从下手，你可以通过查看“设计思路”，帮助你开拓思维。
90. （1）筛选是建堆的基本算法。
91. （2）把要排序序列看成一棵完全二叉树，用循环方式从最后一个非叶结点（设序号为i）开始，逐次对序号为i，i-1，……的结点，直至根结点调用筛选算法，完成建堆。
92. （3）不断通过堆顶元素与堆中最后一个元素的交换并筛选，完成排序。
93. 如果对于自己编写的程序不知道是否正确，你可以通过查看“实验设计”进行核查。
94. 程序代码如下：
95. /*实验6.2 堆排序*/
96. #include
97. #define N 8
98. /*定义待排序记录类型*/
99. typedef struct
100. {
101. int key;
102. }NODE;
103. void heapsift（NODE a[],int i,int n）; /*筛选算法*/
104. void heapsort（NODE a[],int n）; /*堆排序*/
105. void display（NODE a[],int n）; /*输出关键字序列*/
106. void main（）
107. {
108. NODE a[N+1]={0,40,80,65,100,14,30,55,50}; /*定义记录数组*/
109. printf（"初始关键字序列为："）;
110. display（a,N）;
111. heapsort（a,N）;
112. printf（"n堆排序后的关键字序列为："）;
113. display（a,N）;
114. }
115. /*筛选算法*/
116. void heapsift（NODE a[],int i,int n）
117. {
118. NODE temp;
119. int j;
120. temp=a;
121. j=2*i; /*j为i的左孩子*/
122. while（j<=n） /*最多调整到最后一个非叶结点*/
123. {
124. if（j+1<=n && a[j].key > a[j+1].key）
125. j++; /*j指向左右孩子中关键字较小者*/
126. if（temp.key > a[j].key）
127. {
128. a=a[j]; /*较小子结点记录调整到父结点位置*/
129. i=j; /*准备继续对子结点进行筛选*/
130. j=2*i;
131. }
132. else
133. break; /*已满足小根堆，筛选结束*/
134. }
135. a=temp;
136. }
137. /*堆排序，实现按关键字从大到小排序*/
138. void heapsort（NODE a[],int n）
139. {
140. int i;
141. NODE temp;
142. /*利用筛选算法建初始小根堆*/
143. printf（"n建初始小根堆过程如下：n"）;
144. for（i=n/2; i>=1; i--）
145. {
146. printf（"筛选%3d后:",a.key）;
147. heapsift（a,i,n）;
148. display（a,n）;
149. }
150. printf（"n初始小根堆序列为："）;
151. display（a,n）;
152. /*利用小根堆排序*/
153. printf（"n堆排序每趟排序状态如下：n"）;
154. for（i=n; i>1; i--） /*共进行（n-1）趟排序*/
155. {
156. /*将最小值与筛选序列最后一个元素交换*/
157. temp=a[1];
158. a[1]=a;
159. a=temp;
160. heapsift（a,1,i-1）; /*对根元素继续筛选，重新构成小根堆*/
161. printf（"（%d）",n-i+1）;
162. display（a,n）;
163. }
164. }
165. /*输出关键字序列*/
166. void display（NODE a[],int n）
167. {
168. int i;
169. for（i=1; i<=n; i++）
170. printf（"%4d",a.key）;
171. printf（"n"）;
172. }
173. 如果已运行程序得出实验结果，你可以查看“测试结果”进行检测。
174. 程序运行结果如下：
175. 通过本实验的学习，有如下收获：
176. （1）为便于调用堆排序算法，初始化的记录数组中下标1～n中对应存储n个数据。
177. （2）对于待排序的n个数据，筛选的次数为n/2次，堆排序趟数为n-1。
178. （3）可利用小根堆实现按关键字从大到小排序，反之利用大根堆可实现按关键字从小到大排序。
179. 完成这个实验的成绩占形成性考核成绩的20%，你可以在这里提交。