课程设计

哈夫曼编码/译码器
教室数据管理
电网建设造价计算
计算机竞赛管理系统
航班信息查询和检索系统
车票管理系统

一、设计任务及要求

设计并实现一个学生管理系统，即定义一个包含学生信息（学号，姓名，成绩）的顺序表，可以不考虑重名的情况，系统至少包含以下功能：

1. 根据指定学生个数，逐个输入学生信息；
2. 逐个显示学生表中所有学生的相关信息；
3. 给定一个学生信息，插入到表中指定的位置；
4. 删除指定位置的学生记录；
5. 统计表中学生个数；
6. 利用直接插入排序或者折半插入排序按照姓名进行排序；
7. 利用快速排序按照学号进行排序；
8. 根据姓名进行折半查找，成功返回此学生的学号和成绩；

二、设计导向

1. 设计目的

1. 巩固和加深对数据结构课程所学知识的理解，了解并掌握数据结构与算法的设计方法；
2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3. 提高综合运用所学的理论知识和方法，独立分析和解决问题的能力；
4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；
5. 培养查阅资料，独立思考问题的能力。

2. 总体设计方案

如图所示，首先确定你要输入学生的数量，将学生的信息存储在表中，按照位置逐个输出学生的信息，删除一个位置的学生信息就是将该位置之后的元素往前移一个位置，插入一个就是将该位置之后的元素往后移一个位置；快速排序：就是选择一个元素作为中心轴，比它小的放前面，比它大的放后面；然后对其它子表也采用中心轴进行排序，直到子表只有一个元素时结束，利用了递归算法。

3. 详细设计

为了实现对学生信息管理系统的各个功能，定义了以下函数:

1. int InsList(SeqList *L,int i,Student e) //插入学生信息 、输入学生的学号，成绩和姓名

2. int DelList(SeqList *L,int i) //删除指定位置学生记录
   该位置前面的元素不变，后面的元素依次前移

3. int Binary_Search(SeqList *L) //根据成绩进行折半查找，成功返回此学生的学号和姓名
   首先输入该学生的成绩，若key等于mid则查找成功，若/key小于mid则high=mid-1，若key大于mid则low=mid+1。

4. int Patition(SeqList *L,int low,int high) //快速排序（学号）
   （1）第一个记录作枢轴记录
   （2）枢轴记录关键字
   （3）从表的两端向中间扫描
   （4）将比枢轴小的记录移动到低端
   （5）将比枢轴大的记录移动到高端
   （6）枢轴记录到位
   （7）.返回枢轴位置

5. int InsertSort(SeqList* L) // 直接插入排序
   在elem[1:i-1]中查找插入elem[i]的位置，将elem[j+1…i-1]中的所有记录均后移一个位置elem[1…j].key<=elem[i].key<elem[j+1…i-1].key将elem[i]插入到elem[j+1]的位置上。

6. int BInsert_price(SeqList*L) //折半插入排序（成绩）
   首先取无序区间第一个元素，若key等于mid则查找成功，若/key小于mid则high=mid-1，若key大于mid则low=mid+1;直到low等于或大于high时插入该元素，依次重复该方法直到无序区间无元素。

7. 学生信息系统实现功能如图2所示：
   

4. 系统测试与结果分析

结果分析：
学生信息系统正常运行，能够实现学生各信息的存储功能，以及信息的展示。测试发现，输入3个学生的信息，能够进行快速排序，折半查找，插入排序和折半插入排序等功能，同时也能够对学生的信息进行删除和插入。

三、课程设计总结

这次课程设计我收获很多，加固了我对顺序表的建立及应用方面的知识，通过对学生信息管理系统的编程，开阔了我的一些思路，不懂的一些知识也得到了解决。如我对直接插入排序和折半插入排序的应用就得到了加强。快速排序的一部分思路出现了错误，导致浪费了许多时间。还有就是在敲代码上还是不够熟练，经常出现一些小错误。数据结构是软件开发中最基础最重要的理论基础，数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。总之，这门课程非常重要。

四、附录：源程序清单

#include<stdio.h> 
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 100

typedef struct{
	int no;       // 学号 
	char name[20];    // 姓名 
	int price;        // 成绩 
}Student;

typedef struct{
	Student elem[MAXSIZE]; //线性表占用的数组空间 
	int last;    //最后一个元素的下标
}SeqList;
int InsList(SeqList *L,int i,Student e)   //插入学生信息 
{    /*在L中第i个位置之前插入新的数据元素e，L的长度加1*/ 
	int k;
	if(i<1||(i>L->last+2))
	{
		return 0;
	}
	for(k=L->last;k>=i;k--) //元素向后移动位置
	L->elem[k+1]=L->elem[k];
	L->elem[i]=e;
	L->last++;
	return 1;
}

int DelList(SeqList *L,int i) //删除指定位置学生记录 
{      
	int k;
	if(i<1||i>L->last+1)
	return 0;
	for(k=i;k<=L->last;k++) 
	{
		L->elem[k-1]=L->elem[k]; //将后面元素依次前移 
	}
	L->last--;
	return 1;
}
//根据成绩进行折半查找，成功返回此学生的学号和姓名
int Binary_Search(SeqList *L)
{
    int key;
    printf("输入要查找的学生成绩:");
    scanf("%d",&key);
    int low=1,high=L->last;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(L->elem[mid].price==key)
        {
            printf("学号：%d 姓名:%s  成绩：%d\n",L->elem[mid].no,L->elem[mid].name,L->elem[mid].price);
 
            return 0;
        }
        else if(L->elem[mid].price<key)
            low=mid+1;
        else if(L->elem[mid].price>key)
            high=mid-1;
    }
    printf("错误!!!没有此学生信息!\n");
}
//快速排序（学号）
int Patition(SeqList *L,int low,int high)
{
	L->elem[0]=L->elem[low];                //用第一个记录作枢轴记录
	double pivotkey=L->elem[low].no;      //枢轴记录关键字
	while(low<high)
    {              //从表的两端向中间扫描
		while(low<high&&L->elem[high].no>=pivotkey)
			--high;
		L->elem[low]=L->elem[high];         //将比枢轴小的记录移动到低端
		while(low<high&&L->elem[low].no<=pivotkey)
			++low;
		L->elem[high]=L->elem[low];         //将比枢轴大的记录移动到高端
	}
	L->elem[low]=L->elem[0];                //枢轴记录到位
	return low;                       //返回枢轴位置
}
int QSort(SeqList *L,int low,int high) 
{
	//对表L中的子序列L.r[low...high]做快速排序
	if (low<high){                          
		int pivotloc=Patition(L,low,high); //一分为二
		QSort(L,low,pivotloc-1);           //对低子表递归排序
		QSort(L,pivotloc+1,high);          //对高子表递归排序
	}
}
int QuickSort(SeqList *L)
{
	//对表L做快速排序
	QSort(L,1,L->last);
	int i;
	for(i=1;i<=L->last;i++)
	{
	printf(	"学号：%d 姓名 ：成绩：
	           %d\n\n",L.elem[i].no,L.elem[i].name,L.elem[i].price);
	}
}
//直接插入排序
int InsertSort(SeqList* L)
{
	int i, j;
	for(i=2;i<=L->last;i++)
		if (L->elem[i].price < L->elem[i - 1].price)//待比较数值小于前一个数
		{
			L->elem[0] = L->elem[i];
			L->elem[i] = L->elem[i-1];
			for (j =i-2;L->elem[0].price < L->elem[j].price; --j)
				L->elem[j + 1] = L->elem[j];
			L->elem[j + 1] = L->elem[0];
		}
	printf("按成绩进行直接插入排序为：\n");
 
    for(i=1;i<=L->last;i++)
    {
     printf(	"学号：%d 姓名 ：成绩：
	           %d\n\n",L.elem[i].no,L.elem[i].name,L.elem[i].price);
    }
    printf("\n");
}
//折半插入排序（成绩）
int BInsert_price(SeqList*L)
{
	int low,j;int high;
    if(L->last<1)
	{
		printf("空表");
		return 0;
	}
	int i;
	Student a[MAXSIZE];
	
	for(i=2;i<=L->last;i++)
	{
		L->elem[0]=L->elem[i];
		
		low=1;high=i;
		while(low<=high)
			{
            int m=(low+high)/2;
            if(L->elem[0].price<L->elem[m].price)high=m-1;
            else low=m+1;//否则，选择m+1—high
        }
        for(j=i-1;j>=high+1;--j) L->elem[j+1]=L->elem[j];//元素后移
        L->elem[low]=L->elem[0];//将新元素插入a[high-1]
    }
	printf("按成绩进行折半插入排序为：\n");
	for(i=1;i<=L->last;i++)
    {
printf(	"学号：%d 姓名 ：成绩：
	           %d\n\n",L.elem[i].no,L.elem[i].name,L.elem[i].price);
    }
    printf("\n");
}

int main()
{
	int i,x,a,temp,select=1,sum=0,c;
	SeqList L;
	Student m,e;
	printf("********************************************************************\n"); 
	printf("*      1. 根据指定学生个数，逐个输入学生信息;                      *\n");
	printf("*      2. 逐个显示学生表中所有学生的相关信息；                     *\n");
	printf("*      5. 给定一个学生信息，插入到表中指定的位置；                 *\n");
	printf("*      6. 删除指定位置的学生记录；                                 *\n");
	printf("*      7. 统计表中学生个数；                                       *\n");
	printf("*      8. 利用快速排序按照学号进行排序                             *\n");
	printf("*      9.利用直接插入排序和折半插入排序按照成绩进行排序            *\n");
	printf("*      10. 根据成绩进行折半查找，成功返回此学生的学号和成绩；      *\n");
	printf("********************************************************************\n");
	printf("\n"); 
	while(select)
	{
		printf("请选择你要操作的选项:");
		scanf("%d",&select);
		printf("\n");
		switch(select)
		{
			case 1:
				
			    printf("请输入学生的数量："); 
			    scanf("%d",&x);
			    printf("\n");
			    sum=x; 
			    for(i=0;i<x;i++)
			    {
			    	printf("第%d位学生信息\n",i+1);
			    	printf("\n");
				    printf("学号：");
				    scanf("%d",&L.elem[i+1].no);
				    printf("-----------------------------\n");
				    printf("姓名：");
				    scanf("%s",&L.elem[i+1].name);
				    printf("-----------------------------\n");
				    printf("成绩：");
				    scanf("%d",&L.elem[i+1].price);
				    printf("-----------------------------\n");
			    } 
			    L.last=x;
			    printf("\n");
			    break;
			    
			case 2:
				
			    printf("所有学生的相关信息为：\n\n");
			    for(i=1;i<=L.last;i++)
			    {
printf(	"学号：%d 姓名 ：成绩：
	           %d\n\n",L.elem[i].no,L.elem[i].name,L.elem[i].price);
				}
				printf("\n");
				break;
			case 5:
				int p;
				printf("请输入你要插入的位置：");
				scanf("%d",&p);
				printf("请输入插入学生信息：\n");
				printf("学号：");
				scanf("%d",&m.no);
				printf("姓名：");
				scanf("%s",&m.name);
				printf("成绩：");                                                                                
				scanf("%d",&m.price);
				if(InsList(&L,p,m))
				{
					sum++;
					printf("插入成功！\n\n"); 
				}
				else
				    printf("插入失败！\n\n");
				break;
			case 6:
				printf("请输入要删除学生的位置：");
			    scanf("%d",&c);
			    if(DelList(&L,c))
			    {
			    	sum--;
			    	printf("删除成功!\n\n");
				}
			    else
			        printf("删除失败！\n\n");
			    break;
			case 7:
				{
					printf("总学生个数为：%d\n\n",sum);
				}
				break;
			case 8:
				printf("按学号进行快速排序为\n");
			    QuickSort(&L); 
                break;
			case 9:
			InsertSort(&L);
				   BInsert_price(&L);
				break;	
			case 10:
			Binary_Search(&L);
			break;
		} 
	}
	return 0;
	}