数据结构实验七、八 查找排序及其应用

1、实验七、八查找排序应用问题实现一、实验目的理解掌握动态查找表在计算机中的各种实现方法。熟练掌握顺序查找、折半查找在顺序表上的实现及解决简单的应用问题。熟练掌握常用排序算法在顺序表上的实现，能解决简单的应用问题。二、实验内容 题目：从键盘上输入n个学生的基本信息（学号、姓名、班级、年龄等）， 建立其顺存储结构，然后执行如下操作：1、分别按学号、姓名、班级、年龄进行插入排序、交换排序和选择排序并显 示排序结果（排序算法任选，但必须保证每种算法至少使用一次）；2、可按学号、姓名、班级或其组合查找某一学生，若查找成功，则输出其基 本信息，否则提示出错。试设计程序完成上述功能。提示：上述操作可用菜单方式

2、实现，字符数据类型可用字符串比较函数 strcmp （const char *, const char *）,在 string.h 头文件中 测试数据：自定设计要求：1、上机前，认真学习教材，理解掌握各种查找算法、排序算法的特点及在 计算机中的实现方法2、上机前，认真独立地写出本次程序清单，流程图，该程序包括数据类型 以及每一种操作的具体的函数定义和主函数。有关算法分别参阅讲义和 参考教材事例。头文件中数据结构设计及相关函数声明：#include#include#define MAXSIZE 20/设记录不超过20个typedefstruct /学生数据结构体定义intSnumber;/学号c

3、harName10;姓名charClass20;班级intAge;年龄charSex10;RecordType;性别typedef struct /定义顺序表的结构RecordType r MAXSIZE +1 ;/存储顺序表的向量int length ;顺序表的长度SqList ;void DataInput(SqList &L);/数据输入void DataPrint(SqList &L);数据输出void InsertSort(SqList &L);/直接插入排序void QuickSort(SqList &L);/快速排序void SelectSort（SqList &L）;/直接选择

4、排序三、实验步骤（一）、数据结构与核心算法的设计描述根据实验题目及要求，宜采用顺序表的线性结构，实验中最重要的是三种 排序算法的理解和实现，只有真正理解算法的内涵，才能熟练地应用，并解决 相应的问题。（二）、函数调用及主函数设计 void main（）SqList L;Datalnput（L）;/学生信息输入/功能变量以下五种排序算法：endl1直接插入排序”endl2交换排序（冒泡排序）endl3选择排序（直接选择排序）endl请输入排序算法前面的序号!endlint k; cout” k;switch(k)break;break;break;case 1: InsertSort(L);ca

5、se 2: QuickSort(L);case 3: SelectSort(L);default: break;DataPrint(L);/学生信息输出四、实验总结从刚开始做实验到实验结束，实验中遇到了很多不能预料到的问题，比如 说关键字的选取，由于刚开始没有详细理解实验题目中的意思，之把学生的学 号作为关键字，之后在它的基础上稍作修改，就成了按照不同关键字进行查找 或比较的算法。五、主要算法流程图及程序清单1、主要算法流程图:一趟快速排序算法流程图2、程序清单：信息输入模块：void DataInput(SqList &L)L.length=0;int i=1;cout您好！欢迎进入数据输入

6、模块!_!endl;cout请输入学生的基本信息！ endl; char ch;do(cout输入第i个学生的基本信息!L.ri.Snumber;cinL.ri.Name;cinL.ri.Class;cinL.ri.Sex;cinL.ri.Age;cout请输入学号cout请输入姓名cout请输入班级cout请输入性别cout请输入年龄i+; L.length+;cout是否继续输入?按Y或y继续!按其他键退出！ch;while(ch=Y|ch=y);直接插入模块：void InsertSort(SqList &L)/直接插入排序，并把班级为关键字 int i,j;for(i=2;i=L.le

7、ngth;+i)if(strcmp(L.ri.Class,L.ri-1.Class)0)(L.r0=L.ri;for(j=i-1;strcmp(L.r0.Class,L.rj.Class)0; -j)L.rj+1=L.rj;L.rj+1=L.r0;快速排序模块:、int Partition(SqList &L,int low,int high)RecordType pivotkey;L.r0=L.rlow;pivotkey=L.rlow;while(lowhigh)(while(low=pivotkey.Snumber)-high;L.rlow=L.rhigh;while(lowhigh&L.

8、rlow.Snumber=pivotkey.Snumber)+low;L.rhigh=L.rlow;L.rlow=L.r0;return (low);void Qsort(SqList &L,int low,int high)int pivotloc;if(lowhigh)(pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);void QuickSort(SqList &L) /快速排序，并把学号为关键字 Qsort(L,1,L.length);直接选择排序模块：void SelectSort(SqList &L) /直接选择排序，并把名字作为关键字int i,j,k;RecordType temp;for(i=1;iL.length;+i)(k=i;for(j=i+1;j=L.length;+j)if(strcmp(L.rj.Name,L.rk.Name)0)k=j;if(i!=k)(temp=L.ri;L.ri=L.rk;L.rk=temp;信息输出：void Da