一、实验目的

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;
}