数据结构--最短路径.doc

江南大学物联网工程学院上机报告课程名称 数据结构 上机名称 排序 上机日期 2013- - 班 级 计科1203 姓 名 汪俊 学号 1030412314上机报告要求 1上机名称 2上机要求 3上机环境 4程序清单(写明运行结果) 5上机体会 1. 上机名称排序，实验52. 上机要求 调试实验一，补充实验2主函数，完成实验3 3. 上机环境 Visual C+ 6.04.程序清单(写明运行结果) 一、#include#define N 10#define FALSE 0#define TRUE 1typedef int KeyType;typedef char InfoType;typedef struct KeyType key;InfoType otherinfo;RecType;typedef RecType SeqlistN+1;int m,num; /全局变量m存储输出的是第几趟结果，num存储递归调用的次数Seqlist R;void Insertsort();void Bubblesort();void Selectsort();void main()Seqlist S;int i;char ch1,ch2;printf(请输入10个待排序的数据：(每两个数据间用空格隔开)n);for(i=1;i=N;i+)scanf(%d,&Si.key);ch1=y;while(ch1=y|ch1=Y)printf(*菜单*n);printf(请选择下列操作:n);printf(1-更新待排序数据-n);printf(2-直接插入排序-n);printf(3-冒泡排序-n);printf(4-直接选择排序-n);printf(5-退出-n);printf(请选择操作类别:n);scanf(n%c,&ch2);switch(ch2)case 1:printf(请输入更新待排序数据:n);for(i=1;i=N;i+)scanf(%d,&Si.key);break;case 2:printf(请输入要输出第几趟排序结果:n);scanf(%d,&m);for(i=1;i=N;i+)Ri.key=Si.key;Insertsort();break;case 3:printf(请输入要输出第几趟排序结果:n);scanf(%d,&m);for(i=1;i=N;i+)Ri.key=Si.key;Bubblesort();break;case 4:printf(请输入要输出第几趟排序结果:n);scanf(%d,&m);for(i=1;i=N;i+)Ri.key=Si.key;Selectsort();break;case 5:ch1=n;break;default:ch1=n;void Insertsort()int i,j,k;for(i=2;i=N;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key) /*从右向左在有序区R1.i-1中查找Ri的插入位置*/Rj+1=Rj;j-;Rj+1=R0;if(i-1=m)printf(第%d趟的结果是:n,m);for(k=1;k=N;k+)printf(%5d,Rk.key);printf(n);printf(请输入还想输出第几趟结果,不想输出时请输入0:n);scanf(%d,&m);if(m!=0)printf(最终排序结果是:n);for(k=1;k=N;k+)printf(%5d,Rk.key);printf(n);void Bubblesort()/自下向上 int i,j,k;int exchange;for(i=1;i=i;j-)if(Rj+1.keyRj.key)R0=Rj+1;Rj+1=Rj;Rj=R0;exchange=TRUE;if(i=m)printf(第%d趟的结果是:n,m);for(k=1;k=N;k+)printf(%5d,Rk.key);printf(n);printf(请输入还想输出第几趟结果,不想输出时请输入0:n);scanf(%d,&m);if(!exchange)|(m=0)break;if(m!=0)printf(最终排序结果是:n);for(k=1;k=N;k+)printf(%5d,Rk.key);printf(n);void Selectsort()int i,j,k,h;for(i=1;iN;i+)h=i;for(j=i+1;j=N;j+)if(Rj.keyRh.key)h=j;if(h!=i)R0=Ri;Ri=Rh;Rh=R0;if(i=m)printf(第%d趟的结果是:n,m);for(k=1;k=N;k+)printf(%5d,Rk.key);printf(n);printf(请输入还想输出第几趟结果,不想输出时请输入0:n);scanf(%d,&m);if(m!=0)printf(最终排序结果是:n);for(k=1;k=N;k+)printf(%5d,Rk.key);printf(n);二、#include#define N 4#define false 0#define ture 1typedef int keytype;typedef char infotype;typedef struct keytype key;infotype otherinfo;rectype;typedef rectype seqlistN+1;int m,num;seqlist R;void quicksort(seqlist &R ,int s,int t)int i=s,j=t;if(ij)R0=Ri;dowhile(i=R0.key)j-;if(ij)Ri=Rj;i+;while(ij&Ri.key=R0.key)i+;if(ij)Rj=Ri;j-;while(i0)for(i=gap;i=1&R0.keyRj.key)Rj+gap=Rj;j=j-gap;Rj+gap=R0;j=j-gap;gap=gap/2;void sift(seqlist &R ,int v,int n)int i,j;i=v;j=2*i;R0=Ri;while(j=n)if(jn&Rj.keyRj+1.key)j+;if(R0.key=1;i-)sift(R,i,n);for(i=n;i=2;i-)R0=Ri;Ri=R1;R1=R0;sift(R,1,i-1);void show(seqlist &R,int n)int i;for(i=1;i=n;i+)printf(%d,Ri.key);void main()seqlist S;int i;char ch1,ch2;printf(请输入4个待排元素：（每两个数据间用空格隔开）n);for(i=1;i=N;i+)scanf(%d,&Si.key);ch1=y;while(ch1=y|ch1=Y)printf(*菜单*n);printf(请选择下列操作：n);printf(1-更新待排数据-n);printf(2-快速排序-n);printf(3-希尔排序-n);printf(4-堆排序-n);printf(5-退出-n);printf(请选择操作类型：n);scanf(n%c,&ch2);switch(ch2)case1:printf(请输出更新待排数据：n);for(i=1;i=N;i+)scanf(%d,&Si.key);break;case2:quicksort(S,1,4);show(S,4);break;case3:shellsort(S,4);show(S,4);break;case4:heapsort(S,4);show(S,4);break;case5:ch1=n;break;default:ch1=n;三、#include#include#includeusing namespace std;#define N 6#define false 0#define ture 1typedef int keytype;typedef string infotype;typedef struct keytype paim;keytype key;infotype otherinfo;rectype;typedef rectype seqlistN+1;int m,num;seqlist R;void quicksort(seqlist &R ,int s,int t)int i=s,j=t;if(ij)R0=Ri;dowhile(i=R0.key)j-;if(ij)Ri=Rj;i+;while(ij&Ri.key=R0.key)i+;if(ij)Rj=Ri;j-;while(i0)for(i=gap;i=1&R0.keyRj.key)Rj+gap=Rj;j=j-gap;Rj+gap=R0;j=j-gap;gap=gap/2;void sift(seqlist &R ,int v,int n)int i,j;i=v;j=2*i;R0=Ri;while(j=n)if(jn&Rj.keyRj+1.key)j+;if(R0.key=1;i-)sift(R,i,n);for(i=n;i=2;i-)R0=Ri;Ri=R1;R1=R0;sift(R,1,i-1);void show(seqlist &R,int n)int i,j,m;for(i=6;i=1;i-)Ri.paim=7-i;if(Ri.key=Ri+1.key)Ri.paim=Ri+1.paim;cout姓名为： Ri.otherinfo;cout 成绩为： Ri.key;cout 名次为： Ri.paimendl;void main()seqlist S;int i;char ch1,ch2;printf(请输入6个成绩：n);for(i=1;i=N;i+)scanf(%d,&Si.key);printf(请输入6个学生姓名：n);for(i=1;iSi.otherinfo;ch1=y;while(ch1=y|ch1=Y)printf(*菜单*n);printf(请选择下列操作：n);printf(1-更新成绩-n);printf(2-快速排序-n);printf(3-希尔排序-n);printf(4-堆排序-n);printf(5-退出-n);printf(请选择操作类型：n);scanf(n%c,&ch2);switch(ch2)case1:printf(请输出更新的成绩：n);for(i=1;i=N;i+)scanf(%d,&Si