实验目的 1.掌握常用的排序方法,并掌握用高级语言实现排序的算法 2.深刻理解排序的定义和各种排序方法的特点,宾能加以灵活应用。 3.了解各种方法的排序过程以及依据的原则,并掌握各种排序方法的时间复杂度的分 析方法 二实验内容 1统计成绩 为题描述]给出n个学生的考试成绩表,每条信息由姓名和分数组成,试设计一个算法 (1)按分数高低顺序,打印出每个学生在考试中获得的名词,分数相等的为同一名次 (2)安名次列出每一个学生的姓名和成绩。 基本要求]学生的成绩必须通过键盘输入数据建立,同时要对输出进行格式控制。 [算法实现]下面给出的使用直接选择排序算法实现的C语言程序。在此基础上读者可以尝 试用直接插入, shell排序,冒泡排序,快续排序归并排序等算法实现本问题的求解 #define n 30 typedef struct student ichar name[ 8]; student rIn fint num, I, j, max, temp printf(“请输入学生成绩”) for(I=0,lrImax. score) i temp=r max r[]=r[l] r[l=temp f((I>o)&&(r[l]. score<r[I-1] score)) printf(num, r[I] name, r[l]. score);
一. 实验目的 1． 掌握常用的排序方法，并掌握用高级语言实现排序的算法。 2． 深刻理解排序的定义和各种排序方法的特点，宾能加以灵活应用。 3． 了解各种方法的排序过程以及依据的原则，并掌握各种排序方法的时间复杂度的分 析方法。 二 实验内容 1 统计成绩 [为题描述]给出 n 个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： （1） 按分数高低顺序，打印出每个学生在考试中获得的名词，分数相等的为同一名次； （2） 安名次列出每一个学生的姓名和成绩。 [基本要求]学生的成绩必须通过键盘输入数据建立，同时要对输出进行格式控制。 [算法实现]下面给出的使用直接选择排序算法实现的 C 语言程序。在此基础上读者可以尝 试用直接插入，shell 排序，冒泡排序，快续排序归并排序等算法实现本问题的求解 #define n 30 typedef strucr student {char name[8]; int score; } student r[n]; main() {int num,I,j,max,temp; printf(“请输入学生成绩”); for(I=0;Ir[max].score) max=j; if(max!=I) {temp=r[max]; r[max]=r[I]; r[I]=temp; } if((I>0)&&(r[I].score<r[I-1].score)) num=num+1; printf(num,r[I].name,r[I].score);
2.用最小意义关键字优先的基数排序法,实现对数的排序,数列中 的每个数据由d位数字组成,不足d位的高位补0 算法提示]设待排序数序列为rl,r2r3..rn,他们各自的关键字为 k2…kn;其中每个关键字由d个分量组成,k^d,kr^d-1.k1,其中 k^1位最大意义关键字分量,k^d为最小意义关键字分量,从而将 数据按关键字分量k^dk^d-1k^1的顺序对数据排序。 设待排序的数据均由3位数组成,即d=3;显然,每个数据由分量 k^3,k^2,kf^l组成,k∧1表示第一位,k2表示第二位,k3表示 第三位。 由于待排序数据为序列,则每位上的数据由0-9种的某个数组成 故可设置10个队列,用数组f和e的元素fiei分别表示队列的开头 和结尾(I=0-9),只要每一次排序前先将各队列置空,然后按 k^3k^2,k^1的顺序对其排序即可 为了使排序过程尽可能地不进行数列中的数据移动,可设计结点为 包含关键字域key和指针域next的结构体。于是,第I各队列由 f和ei分别存放该队列中的一个数据和最后一个数据在序列中的位 置下标值。数列在进行排序前,之后及排序过程中,各对列中各个 数据的先后顺序通过指针域next的链域来实现,可由变量p来指示 排序后这个有序数列的第一个元素的位置 算法实现] # define d3∥关键字位数为3 # define m10/基数10 { int key[d]∥关键字由d个分量组成 nt next;/静态指针域next datatype other;/其他域 typedef struct {intf;e;/n个队列的首指针,和尾指针 queue b[m]:/用对列表示 )时r到rn-1进行基数排序,返回收集用的链头 指针 recl fint I,j, k, tp: for(l=0;<n,+)/将r0到r[n-1]链成一个静态表 [, next=1+1 r[n-1]next=-1;/将初始链表的终端结点指针置空
} } 2.采用最小意义关键字优先的基数排序法，实现对数的排序，数列中 的每个数据由 d 位数字组成，不足 d 位的高位补 0。 [算法提示]设待排序数序列为 r1,r2,r3…..r n,他们各自的关键字为 k1,k2….kn;其中每个关键字由 d 个分量组成，ki^d,ki^d-1…ki^1,其中 ki^1 位最大意义关键字分量，ki^d 为最小意义关键字分量，从而将 数据按关键字分量 ki^d,ki^d-1…ki^1 的顺序对数据排序。 设待排序的数据均由 3 位数组成，即 d=3;显然，每个数据由分量 ki^3,ki^2,ki^1 组成，ki^1 表示第一位，ki^2 表示第二位， ki^3 表示 第三位。 由于待排序数据为序列，则每位上的数据由 0-9 种的某个数组成， 故可设置 10 个队列，用数组 f 和 e 的元素 fi,ei 分别表示队列的开头 和结尾（I=0-9）,只要每一次排序前先将各队列置空，然后按 ki^3,ki^2,ki^1 的顺序对其排序即可. 为了使排序过程尽可能地不进行数列中的数据移动，可设计结点为 一包含关键字域 key 和指针域 next 的结构体。于是，第 I 各队列由 fi 和 ei 分别存放该队列中的一个数据和最后一个数据在序列中的位 置下标值。数列在进行排序前，之后及排序过程中，各对列中各个 数据的先后顺序通过指针域 next 的链域来实现，可由变量 p 来指示 排序后这个有序数列的第一个元素的位置。 [算法实现] #define d 3//关键字位数为 3 #define m 10//基数 10 typedef struct {int key[d];//关键字由 d 个分量组成 int next;//静态指针域 next datatype other;//其他域 }rectype; typedef struct {int f,e;//n 个队列的首指针，和尾指针 }queue; queue b[m];//用对列表示 //对 r[0]到 r[n-1]进行基数排序，返回收集用的链头 指针 int basesort® rectype r[]; {int I,j,k,t,p; for(I=0;I<n;I++)//将 r[0]到 r[n-1]链成一个静态表 r[I],next=I+1; r[n-1].next=-1;//将初始链表的终端结点指针置空
or(=d-1j>=0j-)∥/进行d趟排序 for(l=0,l<m,1++)∥清空对列 b]f-1 while(p!=-1)∥/按关键字第j个分量进行分配 i kelp] keyi if(b(k].f==-1) b[k]p/付列为空时,将r[p]链到队列头部 r[bkel]next=p/否则对列非空将rp]链到队尾 b[ke=p,∥修改对列的尾指针 p=r[p]next/扫描下一个记录 While(b]f=-1)∥检索第一个非空队列 t=ble p=b[]f/p尾收集链表的头指针 while(<m-1)检索下一个对列 fb]=1y/队列非空时链接 r[t]. next=b[l].f. t=ble r[ t]. next=1∥本唐收集完毕,将链表的终端结 点指针置空 return p 3写出含有n个元素的队中增加一个元素, 且调整为堆的算法 算法提示]由于堆可看成一棵完全二叉 树,所以可以用一个数组r[1至rn+1表示 个堆。其中r倒到rn表示原始堆中的各
p=0; for(j=d-1;j>=0;j--)//进行 d 趟排序 for(I=0;I<m;I++)//清空对列 { b[I].f=-1; b[I].e=-1; } while(p!=-1)//按关键字第 j 个分量进行分配 {k=r[p].key[j]; if(b[k].f==-1) b[k].p;//对列为空时，将 r[p]链到队列头部 else r[b[k].e].next=p;//否则对列非空将 r[p]链到队尾 b[k].e=p;//修改对列的尾指针 p=r[p].next;//扫描下一个记录 } I=0; While(b[I].f==-1)//检索第一个非空队列 I++; t=b[I].e; p=b[I].f//p 尾收集链表的头指针 while(I<m-1)//检索下一个对列 {I++; if(b[I].f!=-1)//队列非空时链接 { r[t].next=b[I].f; t=b[I].e; r[t].next=-1;//本唐收集完毕，将链表的终端结 点指针置空 } return p; } 3 写出含有n 个元素的队中增加一个元素， 且调整为堆的算法 ［算法提示］由于堆可看成一棵完全二叉 树，所以可以用一个数组 r[1]至 r[n+1]表示 一个堆。其中 r[1]到 r[n]表示原始堆中的各
个元素,rn+1j用于存放新插入的元素。由 于原来的n个元素已经构成堆,则当插入 个元素时,有可能破坏堆的结构,所以 需依据情况进行调整,此时仅需要从rn+1 出发, 走一条从叶子结点rn+1到根结点r[1的 路径(设为小根堆)。每次就该结点r和 其双亲结点进行比较,若 r[] key>r[key,此时算法结束,不需要 进行调整,此时r[到rn+1即为堆,否则, 将r{与r进行交换,继续和上一层结点 比较,直到根结点为止 [算法实现] #define n 15 #define datatype int typedef struct Int key;∥关键字域 datatype other/∥其它域 grectlype, ∥堆r[到rn中插入一个新元素 heapinsert(r, x) rectype rl datatype x while(>l)
个元素，r[n+1]用于存放新插入的元素。由 于原来的 n 个元素已经构成堆，则当插入 一个元素时，有可能破坏堆的结构，所以 需依据情况进行调整，此时仅需要从 r[n+1] 出发, 走一条从叶子结点 r[n+1]到根结点 r[1]的 路径（设为小根堆）。每次就该结点 r[j]和 其双亲结点 r[I] 进 行 比 较 ， 若 r[I].key>r[I].key，此时算法结束，不需要 进行调整，此时 r[1]到 r[n+1]即为堆，否则， 将 r[I]与 r[j]进行交换，继续和上一层结点 比较，直到根结点为止。 [算法实现] #define n 15 #define datatype int typedef struct {int key;//关键字域 datatype other;//其它域 }rectlype; rectype r[n]; //在堆 r[1]到 r[n]中插入一个新元素 heapinsert(r,x) rectype r[]; datatype x; { int I,j; j=n+1; while(j>1)
l=j/2,/结点k的双亲结点ki ifr(门key<xkey)j=1∥/若此时为堆跳出循 环 FI }∥不为堆在调整 r[=x;/x插入正确的插入位置 main( datatype for(上=1;<=n,H+) (scanf(r) printf(rl) scanf(&x); heapinsert(r, x); for(l=1I<=n+1;H++) printf(r[); 4输入若干国家名称,请按字典顺序将这 些国家进行排序(设所有的名称钧用大写 或小写表示)。 算法提示]本提实质是对一些字符串进 行排序,可以用直接选择排序或 shell排序 等,这里 shell采用排序。 Shell排序又称 “缩小增量排序”它的做法是:先取一个 小于n的整数d1作为第一个增量,把文
{I=j/2;//求结点 kj 的双亲结点 ki if(r[I].key<x.key)j=1;//若此时为堆跳出循 环 else {r[j]=r[I]; j=I; }//不为堆在调整 } r[I]=x;//x 插入正确的插入位置 } main() {int n,I; datatype x; for(I=1;I<=n;I++) {scanf(r[I]); printf(r[I]); } scanf(&x); heapinsert(r,x); for(I=1;I<=n+1;I++) printf(r[I]); } 4.输入若干国家名称，请按字典顺序将这 些国家进行排序（设所有的名称钧用大写 或小写表示）。 ［算法提示］本提实质是对一些字符串进 行排序，可以用直接选择排序或 shell 排序 等，这里 shell 采用排序。Shell 排序又称 “缩小增量排序”它的做法是：先取一个 小于 n 的整数 d１作为第一个增量，把文
件的全部记录分成d1个组,所有距离为 d1倍数的记录放在同一个组中,再每一个 组织结进行插入排序;然后,取第二个增 量d20) h=h/2;∥取增量h2 change=false for(I=0; K<n-h, 1++) if(r①r+h])∥比较 temp=r[/交换 r[=r[I+h]; r[I+h]= change=true/置已交换标志
件的全部记录分成 d1 个组，所有距离为 d1 倍数的记录放在同一个组中，再每一个 组织结进行插入排序；然后，取第二个增 量 d20) { h=h/2;//取增量 h/2 do { change=false; for(I=0;Ir[I+h])//比较 ｛temp=r[I];//交换 r[I]=r[I+h]; r[I+h]=temp; change=true;//置已交换标志
while(!change); printf( output country namen) for(=0;<n;H++) printf(r[);
} }while(!change); } printf(“output country name\n”); for(I=0;I<n;I++) printf(r[I]); }