数据结构实验指导书及答案（徐州工程学院）(8)

int lowcost=32767; for(j=0;j

{if(flag[j]!=1&&mark[j].lowcost

lowcost=mark[j].lowcost;}} flag[nearestv]=1; return nearestv;}

void markothervex_hc(graph_hc*g,markedg_hc*mark,int nearestv,int num,int*flag) {int j;

for(j=0;jarcs[nearestv][j]>0) {if(flag[j]!=1)

{if(mark[j].lowcost>(mark[nearestv].lowcost+g->arcs[nearestv][j])) {mark[j].lowcost= mark[nearestv].lowcost+g->arcs[nearestv][j]; mark[j].adjvex=nearestv;}}}}}

void shortestpath_hc(graph_hc*g,markedg_hc*mark,int start) {int i,num; int *flag; int nearestv; num=g->vexnum;

flag=(int *)malloc((num)*sizeof(int)); flag[start]=1;

for(i=0;ivexnum;i++) {mark[i].adjvex=start; if( g->arcs[start][i]>0)

{mark[i].lowcost=g->arcs[start][i];} else

{mark[i].lowcost=32767;}} for(i=1;ivexnum;i++)

{nearestv=selectnearvex_hc(mark,flag,num); markothervex_hc(g,mark,nearestv,num,flag);}}

void printshortpath_hc(graph_hc*g,markedg_hc*mark,int start) {int i,j,k,path[25]; for(i=0;ivexnum;i++) {if(i!=start)

{printf(\从%d到%d最短路径为:%d; \printf(\途经:\k=0;path[k]=i; j=mark[i].adjvex; while(j!=start) {path[++k]=j;

j=mark[j].adjvex;} printf(\

for(j=k;j>=0;j--)printf(\printf(\ main() {int city;

graph_hc*g;markedg_hc*mark; g=initgraph_hc(); creategraph_hc(g); printf(\城市名称/代号:\

printf(\乌鲁木齐/0, 哈尔滨/1, 呼和浩特/2, 长春/3, 北京/4, \printf(\沈阳/5, 天津/6, 大连/7, 西宁/8, 兰州/9, 西安/10, 郑州/11, \printf(\徐州/12, 成都/13, 武汉/14, 上海/15, 昆明/16, 贵阳/17, 株州/18,\printf(\南昌/19, 福州/20, 柳州/21, 南宁/22, 广州/23, 深圳/24.\\n\printgraph_hc(g);

mark=(markedg_hc*)malloc(g->vexnum*sizeof(markedg_hc)); printf(\输入起始城市:\shortestpath_hc(g,mark,city); printshortpath_hc(g,mark,city);

}

实验十一 顺序表查找算法的实现

实验预备知识：

1．理解记录、关键字和查找的相关概念。 2．熟练掌握顺序表的存储结构。

一、实验目的

1．掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法；理解排序在数据处理中的重要性；

2．学会比较各种排序方法的稳定性分析以及在最好、最坏和平均情况的时间性能分析。 3．掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。 4．熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。

2．如果输入数据较为繁琐，可减低每个班的人数。 3．输入输出数据要有提示，方便用户操作。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验11”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某个学院有20名同学分属于2个班级（Class1 和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。

3．以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。

4．完成如下函数（其中查找函数用顺序查询和折半查询两种方式实现），注意折半查询只适合有序的顺序表：

3．思考两种查找的效率分析和适用场合。 #include \#include \#include \

typedef struct {int cla; int num;

char name[20]; char sex;

long phonenum; }student;

typedef struct

{student *elem; int length; int sum; }ST;

ST *initlist() {ST *l;

l=(ST*)malloc(sizeof(ST)); if(!l)printf(\没有创建ST!\\n\

l->length=0;l->sum=3;

l->elem=(student*)malloc(3*sizeof(student)); if(!l->elem)printf(\没有创建elem!\\n\return(l); }

int place(ST *l,int c,int num) {int low,high,mid,j=-1,i; low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].num>num)high=mid-1; else {j=mid;low=mid+1;}} i=j;

for(j=mid;j>=i;j--)

{if(j==-1||num>l->elem[j].num)break;

else if(num==l->elem[j].num&&c>l->elem[j].cla)break;} return(++j);}

void move(ST *l,int j) {int i;

for(i=l->length-1;i>=j;i--)

{l->elem[i+1].cla=l->elem[i].cla;

strcpy(l->elem[i+1].name,l->elem[i].name); l->elem[i+1].num=l->elem[i].num; l->elem[i+1].sex=l->elem[i].sex;

l->elem[i+1].phonenum=l->elem[i].phonenum;}}

void createlist(ST *l) {int i,j,c,num;

char nam[20],s;long p;

printf(\输入学生信息(class name num sex phonenum):\\n\for(i=0;isum;i++) {flushall();

scanf(\j=!(l->length)?0:place(l,c,num); move(l,j);

l->elem[j].cla=c;

strcpy(l->elem[j].name,nam); l->elem[j].num=num; l->elem[j].sex=s;

l->elem[j].phonenum=p; l->length++;}}

void searchban(ST *l) {int low,high,mid,num,c;

printf(\输入查找人的学号和班级号:\scanf(\if(num!=-1||c!=-1)

{low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].numelem[mid].num>num)high=mid-1; else {if(l->elem[mid].claelem[mid].cla>c)mid--; break;}}

printf(\>elem[mid].name,l->elem[mid].num,l->elem[mid].sex,l->elem[mid].phonenum); } }

void searchshun(ST *l) {int num,c,i;

printf(\输入查找人的学号和班级号:\scanf(\for(i=0;i<=l->length;i++)

if(l->elem[i].num==num)break; if(i!=l->length)

printf(\>elem[i].num,l->elem[i].sex,l->elem[i].phonenum); else

printf(\无此人！\ }

void printlist(ST *l)