发布时间 : 星期日 文章数据结构实验报告（华夏）更新完毕开始阅读3b8bbc00ccbff121dd368354
for (i=0 ;i< n ; i＋＋ ) /*dist数组初始化*/ ｛
dist[i]=cost[v0][i] ;
if(dist[i]
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程序并 调试之。 四、巩固题 设计一个读入一串整数构造一棵二叉排序树的算法 [实现提示] 二叉排序树的构成，可从空的二叉树开始，每输入一个结点，就将其插入到当前已形成的二叉排序树中，所以，它实际是利用了二叉排序树的插入算法。