一、实验目的

1．掌握查找的不同方法，并能用高级语言实现查找算法。

2．熟练掌握顺序表和有序表的顺序查找和二分查找方法。

3．掌握排序的不同方法，并能用高级语言实现排序算法。

4．熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。

二、实验内容

1．学生信息如下：

学号 姓名 数据结构 程序设计

1 王立 76 88

2 张秋 88 77

3 刘丽 79 65

4 王通 86 85

5 赵阳 71 90

6 李艳 68 70

7 钱娜 89 95

8 孙胜 60 76

2．创建顺序查找表，输入学生信息。

【选做：也可以将学生信息存入文件，直接从文件读取学生信息】

3．使用顺序查找方法按姓名查找学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

4．使用二分查找方法，查找学生学号信息。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

5．使用直接插入排序方法，对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表，验证排序结果。

6．使用直接选择排序或冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。

7．使用快速排序方法，对学生信息中的程序设计成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。

8．编写一个菜单，来实现各项功能的选择。

*******************学生成绩管理系统*****************

* 1．信息初始化 2．顺序查找 *

* 3．二分查找 4．直接插入排序 *

* 5．冒泡或选择排序 6．快速排序 *

* 0．退出 *

****************************************************

9．利用工程完成本次实验任务，各个功能分别放到一个函数中。

三、实验结果

给出源程序及输入、输出结果。

解决方案：

#include<iostream>#include<string.h>#include<stdlib.h>#include<conio.h>using namespace std;#define MAXSIZE 100typedef struct {int num;char name[20];int score;int score2;}Student;typedef struct{Student elem[MAXSIZE];int last;}Sqlist;int InitList(Sqlist *L);void DirectInsertSort(Sqlist *L, int left, int right);void QuickSort(Sqlist *L, int low, int high);int BinSearch(Sqlist *L, int n, int k);int Locate(Sqlist *L, Student e);int BubbleSort(Sqlist *L, int n);void ShowList(Sqlist *L,int n);void ShowList2(Sqlist *L,int n);void menu();int main(){int i,temp1,temp2,sum,select=1,bin=0;Sqlist L;Student m,e;while(select){menu();cout<<"请选择你要操作的选项:";cin>>select;cout<<endl;switch(select){case 1: //信息初始化sum=InitList(&L);system("pause");system("cls");break;case 2: //顺序查找cout<<"请输入你要查找的姓名"<<endl;cin>>e.name;temp1=Locate(&L,e);ShowList2(&L,temp1);system("pause");system("cls");break;case 3:cout<<"请输入要查找的学生学号:";cin>>bin;temp2=BinSearch(&L,sum,bin);ShowList2(&L,temp2);system("pause");system("cls");break;case 4:cout<<"姓名直接插入排序前："<<endl;ShowList(&L,sum);cout<<"姓名直接插入排序后："<<endl;DirectInsertSort(&L, 0, sum-1);ShowList(&L,sum);system("pause");system("cls");break;case 5:BubbleSort(&L,sum);ShowList(&L,sum);system("pause");system("cls");break;case 6:QuickSort(&L,0,sum-1);ShowList(&L,sum);system("pause");system("cls");break;case 0:exit(0);}}}void menu(){cout<<"*******************学生成绩管理系统*****************"<<endl;cout<<"* 1．信息初始化 2．顺序查找 *"<<endl;cout<<"* 3．二分查找4．直接插入排序*"<<endl;cout<<"* 5．冒泡或选择排序 6．快速排序 *"<<endl;cout<<"* 0．退出 *"<<endl;cout<<"****************************************************"<<endl;}void ShowList(Sqlist *L,int n){for(int i=0;i<n;i++){cout<<"学号\t"<<"姓名\t"<<"数据结构\t"<<"程序设计\t"<<endl;cout<<L->elem[i].num<<"\t"<<L->elem[i].name<<"\t"<<L->elem[i].score<<"\t\t"<<L->elem[i].score2<<endl;}}int InitList(Sqlist *L){int x=0,sum=0;cout<<"请输入学生的数量："<<endl;cin>>x;sum=x;for(int i=0; i<x; i++){cout<<"第"<<i+1<<"位学生信息"<<endl;cout<<"学号:";cin>>L->elem[i].num;cout<<"-----------------------------"<<endl;cout<<"姓名:";cin>>L->elem[i].name;cout<<"-----------------------------"<<endl;cout<<"数据结构:";cin>>L->elem[i].score;cout<<"-----------------------------"<<endl;cout<<"程序设计:";cin>>L->elem[i].score2;cout<<"-----------------------------"<<endl;}L->last=x;return sum;cout<<endl;}int Locate(Sqlist *L, Student e){int i;for(i=0;i<L->last;i++)//比较函数{if(strcmp(L->elem[i].name, e.name)==0)return i+1;}//return 0;}int BinSearch(Sqlist *L, int n, int k){int low = 0, high =n-1,mid;//n-1while(low<=high){mid=(low+high)/2;if(k==L->elem[mid].num)return mid+1;if(k< L->elem[mid].num)high=mid-1;elselow=mid+1;}return 0;}void DirectInsertSort(Sqlist *L, int left, int right){Student t;for (int i = left; i <= right; ++i){for (int j = i - 1; j >= 0 && strcmp(L->elem[j].name,L->elem[j+1].name)>0; --j) {t=L->elem[j];L->elem[j]=L->elem[j+1];L->elem[j+1]=t;}}}int BubbleSort(Sqlist *L, int n){int i,j;Student t;for(i=0;i<n-1;i++){for(j=n-1;j>i;j--){if(L->elem[j-1].score > L->elem[j].score){t=L->elem[j-1];L->elem[j-1]=L->elem[j];L->elem[j]=t;}}}return 0;}void QuickSort(Sqlist *L, int low, int high){int i=low,j=high; Student pivotvalue=L->elem[i]; if(low>=high) return; while(i<j){while(i<j&&L->elem[j].score2>=pivotvalue.score2)j--;L->elem[i]=L->elem[j];while(i<j&&L->elem[i].score2<=pivotvalue.score2)i++;L->elem[j]=L->elem[i];}L->elem[i]=pivotvalue;QuickSort(L,low,i-1);QuickSort(L,i+1,high);}void ShowList2(Sqlist *L,int n){if(n!=0){cout<<"学号\t"<<"姓名\t"<<"数据结构\t"<<"程序设计\t"<<endl;cout<<L->elem[n-1].num<<"\t"<<L->elem[n-1].name<<"\t"<<L->elem[n-1].score<<"\t\t"<<L->elem[n-1].score2<<endl;}elsecout<<"查找失败"<<endl;}