数据结构实验报告（华夏）

for (i=0 ;i< n ; i＋＋ ) /*dist数组初始化*/ ｛

dist[i]=cost[v0][i] ;

if(dist[i]0) }

path[i]=v0 ; /* path数组初始化*/ ｝

for (i=0 ;i< n ; i ＋＋) s[i]=0 ; s[v0]=1 ;

for (i=0 ;i< n ; i ＋＋)

｛ min＝MAX ; /*按最短路径不减原理计算*/ u=v0 ；

for (j=0 ;j< n ; j++ )

if(s[j]= =0 && dist[j]

s[u]=1 ; /* u为求出的最短路径的顶点编号*/ for (j=0;j< n ;j++)

if(s[j]= =0 && dist[u]＋cost[u][j]< dist[j]) /* 调整dist*/ ｛

dist[j]＝dist[u]＋cost[u][j] ；

path[j]=u ; /* path记录了经过的顶点*/ ｝ }

for (i=0 ;i< n ; i ＋＋) /* 打印结果*/ if(s[i]= =1) ｛ u=i ; while(u!=v0) {

printf(“％d<―― “，u+1 ); u=path[u] ; ｝

printf(“％d “，u+1 );

printf(“d＝％d\\n“，dist[i] ); } else

printf(“％d<――％dd＝X\\n “，j+1,v0+1); ｝

三、实验结果分析讨论

1． 输入的数据为

请输入起始顶点的编号：1

请输入顶点数和边数： 5 ，7

请输入第1个顶点的信息：1

请输入第2个顶点的信息：2

请输入第3个顶点的信息：3 请输入第4个顶点的信息：4 请输入第5个顶点的信息：5

请输入第1条边的起始顶点编号和终止顶点编号：1,2 输入此边的权值： 10

请输入第2条边的起始顶点编号和终止顶点编号：1,5 输入此边的权值： 50 ??

2． 输出的结果是：

四、巩固题 根据下面描述的问题及提示的算法，编写一个C程序，调试运行。

[问题描述] 用无向网络图表示N个城市之间通信网络的建设计划，顶点表示城市，边上的

权值表示线路的造价，设计一个方案，使这个通信网的总造价最低。

[算法提示]采用prim方法实现

分析：1. 初始化：建立图的邻接矩阵 ；

2. 设置一个顶点的集合S和边的集合TE，初始时S和TE皆为空集； 3. 选中图中一个顶点K（从K开始生成最小生成树），将K加入集合S中； 3． 重复下列步骤：

A 选取一条权值最小的边〈X，Y〉，其中X在S中，Y不在S中； B 将顶点Y加入集合S，边〈X，Y〉加入集合TE中；

[测试数据]

假设无向网络图为： 5 14 5 7 29 8 6

1 13 6 2 9

实验六 查找算法设计

一、预习报告

实验目的

1、掌握用Turbo C上机调试基本查找算法的程序；

2、熟练掌握顺序表和有序表的查找方法，编制二分查找法的实现方法； 3、了解二叉排序树的构造和查找算法 ； 4、了解散列表的设计及应用

基本原理与方法 二分查找法实现对序列的查找原理用C语言编程实现

实验设备 PC机一台、配置Turbo C软件 二、实验内容

二分查找法的实现

〔问题描述〕 学生成绩查询程序设计

[基本要求] 1. 建立学生成绩表，根据学号查询某学生的成绩；

2. 设学生数为10人，成绩初始化时建立（也可以用循环输入）；

3. 采用二分查找法查找 [算法提示]：

1. 为简单方便，学生信息里只包含学号和一门课程的成绩，按学号递增有序存放。 2. 按学号查询某学生的成绩并输出。 [参考程序] # include “stdio.h” # include “string.h” # include “alloc.h”

#define MAXSIZE 40

typedef struct {

int key ; /*学号*/

int score ; /*成绩*/

}elemtype;

typedef struct /*定义顺序表类型*/ {

elemtype elem[MAXSIZE] ; int length ；

｝stable ；

int search(stable ST，int key) /*二分查找函数*/ {

int low，mid，high； ; low＝1；high＝ST.length ; while（low<=high） ｛

mid＝（low+high）/2 ；

if(key= =ST.elem[mid].key) return mid ；

else if(key

return 0 ； ｝

main() /*主程序*/ {

elemtype stu〔〕＝｛1,68,2,95,3,70,4,80,5,66,6,887,71,8,89,9,74,10,90｝ /*初始化成绩表*/

Stable class； int j，k；

class.elem=stu； class.lengh=10；

printf(“this class has %d students.\\n”，class.length)；

/*输出班级学生数*/

while(1)

printf(“ \\n input num(>0) you want search ：” )； scanf(“%d”,&k)； /*输入学生学号*/ if(!k) break ；

j＝search(class, k) /*查找*/ if(j) ｛

printf(“ \\n output score ：” )； /*输出学生成绩*/ printf(“ ％d\\n ” ，class.elem[j].score ：” )； }

else printf(“ \\n no this student。” )； ｝

三、实验结果分析讨论

1． 输入的数据为

input num(>0) you want search ： 9

输出的结果为：outup score：74

input num(>0) you want search ： 1

输出的结果为：68

input num(>0) you want search ： 6 输出的结果为：88

input num(>0) you want search ： 5 输出的结果为：66

input num(>0) you want search ： 0

2． 试写出第一次输入数据后得到输出的结果系统执行的过程

3．将一门课程改成输入五门课程成绩，要按学号查找某学生的全部成绩的C程序并

调试之。

四、巩固题

设计一个读入一串整数构造一棵二叉排序树的算法

[实现提示] 二叉排序树的构成，可从空的二叉树开始，每输入一个结点，就将其插入到当前已形成的二叉排序树中，所以，它实际是利用了二叉排序树的插入算法。