一、实验目的
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 100
typedef 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-1
while(low<=high)
{
mid=(low+high)/2;
if(k==L->elem[mid].num)
return mid+1;
if(k< L->elem[mid].num)
high=mid-1;
else
low=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;
}
else
cout<<"查找失败"<<endl;
}
|