查找排序应用问题实现.doc

实验七、八 查找排序应用问题实现 一、实验目的 1．理解掌握动态查找表在计算机中的各种实现方法。 2．熟练掌握顺序查找、折半查找在顺序表上的实现及解决简单的应用问题。3．熟练掌握常用排序算法在顺序表上的实现，能解决简单的应用问题。 二、实验内容 题目1：从键盘上输入n个学生的基本信息（学号、姓名、班级、年龄等）,建立其顺存储结构,然后执行如下操作： 1、分别按学号、姓名、班级、年龄进行插入排序、交换排序和选择排序并显示排序结果（排序算法任选，但必须保证每种算法至少使用一次）； 2、可按学号、姓名、班级或其组合查找某一学生，若查找成功，则输出其基本信息，否则提示出错。 试设计程序完成上述功能。 提示：上述操作可用菜单方式实现，字符数据类型可用字符串比较函数strcmp (const char *, const char *) ,在string.h 头文件中 测试数据：自定 相关常量及结构定义：#define MAXSIZE 20 typedef struct { int Sno; char Sname[10]; char Sclass[20]; int Sage; }RecordType ; typedef struct { RecordType r[ MAXSIZE+1]; int length ; }SqList; 设计相关函数声明： void InitList(SqList L) 插入排序：void Insert_Sort_Sno(SqList L) void Insert_Sort_Sname(SqList L) void Insert_Sort_Sclass(SqList L) void Insert_Sort_Sage(SqList L) 起泡排序：void SwapSort_Sno(SqList L) void SwapSort_Sname(SqList L) void SwapSort_Sclass(SqList L) void SwapSort_Sage(SqList L) 选择排序：void Select_Sort_Sno(SqList L) void Select_Sort_Sname(SqList L) void Select_Sort_Sclass(SqList L) void Select_Sort_Sage(SqList L) 查找信息：void Search_Sno(SqList L) void Search_Sno(SqList L) void Search_Sno(SqList L) 三、数据结构与核心算法的设计描述 1.初始化链表 void InitList(SqList L) { for(int i=1;i=L.length;i++) { cout第i个学生的信息endl; cout学号:; cinL.r[i].Sno; cout姓名:; cinL.r[i].Sname; cout班级:; cinL.r[i].Sclass ; cout年龄:; cinL.r[i].Sage; } } 2.插入排序 ⑴ 按学号 void Insert_Sort_Sno(SqList L) { int i,j; for(i=2;i=L.length;++i) if(L.r[i].SnoL.r[i-1].Sno) { L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;L.r[0].SnoL.r[j].Sno;--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } for(i=1;i=L.length;i++) cout学号:L.r[i].Sno 姓名:L.r[i].Sname 班级:L.r[i].Sclass 年龄:L.r[i].Sageendl; } ⑵ 按姓名 void Insert_Sort_Sname(SqList L) { int i,j; for(i=2;i=L.length;i++) if(strcmp(L.r[i].Sname,L.r[i-1].Sname)0) { L.r[20]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;strcmp(L.r[20].Sname,L.r[j].Sname)0;j--)