实验五 查找与排序
实验课程名： 数据结构与算法
专业班级： 15软件工程1班 学号： 201540550119 姓名： 李志强 实验时间： 3.17-3.24 实验地点： K4-207 指导教师： 祁文青
一、实验目的和要求 1、掌握查找的不同方法，并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。 3、掌握常用的排序方法，并能用高级语言实现排序算法。 4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。 5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的 二、实验内容 任务一：顺序表的顺序查找 完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。 各科成绩 准考证号 姓名 总分 政治 语文 外语 数学 物理 化学 生物 179328 179325 179326 179327 179324 何芳芳 陈红 陆华 张平 赵小怡 85 85 78 82 76 89 86 75 80 85 98 88 90 78 94 100 100 80 98 57 93 92 95 84 77 80 90 88 96 69 47 45 37 40 44 592 586 543 558 502 （1）源代码如下： #include #include #include using namespace std; #define N 5 #define EQ(a, b) ((a) == (b)) #define LT(a, b) ((a) < (b)) #define LQ(a, b) ((a) <= (b)) typedef long KeyType; #define key number typedef struct { long number; char name[10]; int politics; int Chinese; int English; int Math; int Physics; int Chemistry; int Biology; int total; }ElemType; typedef struct { ElemType *elem; int length; }SSTable; void Creat_Seq(SSTable &ST, ElemType *r, int n) { int i, j; ST.elem = new ElemType[n + 1]; if (!ST.elem) exit(0); for (i = 1, j = 0; i <= n; ++i, ++j) { ST.elem[i].number = r[j].number; strcpy(ST.elem[i].name, r[j].name); ST.elem[i].politics = r[j].politics; ST.elem[i].Chinese = r[j].Chinese; ST.elem[i].English = r[j].English; ST.elem[i].Math = r[j].Math; ST.elem[i].Physics = r[j].Physics; ST.elem[i].Chemistry = ST.elem[j].Chemistry; ST.elem[i].Biology = r[j].Biology; ST.elem[i].total = r[j].total; } ST.length = n; } void Ascend(SSTable &ST) { int i, j, k; for (i = 1; i < ST.length; ++i) { k = 1; ST.elem[0] = ST.elem[k]; for (j = i + 1; j <= ST.length; ++j) { if (LT(ST.elem[j].key, ST.elem[0].key)) { k = j; ST.elem[0] = ST.elem[j]; } } if (k != i) { ST.elem[k] = ST.elem[i]; ST.elem[i] = ST.elem[0]; } } } void Creat_Ord(SSTable &ST, ElemType *r, int n) { Creat_Seq(ST, r, n); Ascend(ST); } int Destory(SSTable &ST) { delete []ST.elem; ST.elem = NULL; ST.length = 0; return 1; } int Search_Seq(SSTable ST, KeyType key) { int i; ST.elem[0].key = key; for (i = ST.length; !EQ(ST.elem[i].key, key); --i); return i; } void Visit(ElemType c) { printf(\c.English, c.Math, c.Physics, c.Chemistry, c.Biology, c.total); }