数据结构与算法课程设计学生成绩管理系统.doc

课 程 设 计 说 明 书

题目：数据结构与算法课程设计

学院（系）：
专业班级：
学 号：
学生姓名：
指导教师：
教师职称：
起止时间：

课程设计（论文）任务及评语
院（系）： 教研室： 软件工程
学 号

学生姓名

专业班级

课程设计（论文）题目
数据结构与算法课程设计
课程设计（论文）任务

1．从十个题目中选择一个题目,，规定每个题目用标准的C语言程序实现，此外,完毕思考题一题，思考题须写出相应的类C算法即可。
2．每个题目编写源程序时，规定有主菜单,每个子功能定义为相应的子函数，在主函数中调用各子函数，程序结构清楚。
3． 根据题目,选择合适的逻辑结构和存储结构。
4． 输入的数据由键盘输入。
5． 分析算法的时间复杂度，规定算法的效率尽也许高。
6． 验证排序算法的稳定性。
指导教师评语及成绩

成绩： 指导教师签字：

2023 年 月 日

目 录
第1章 课程设计目的与规定 1
1.1 课程设计目的 1
1.2 课程设计的实验环境 1
1.3 课程设计的预备知识 1
1.4 课程设计规定 1
第2章 课程设计内容 2
2.1题目的选择 2
2.2 题目的具体实现 2
2.3 思考题解析 12
总结： 14
参考文献 错误！未定义书签。

第1章 课程设计目的与规定
1.1 课程设计目的
本课程设计是计算机科学与技术专业、软件工程专业的专业技术实践课。
本实践课的重要目的是：使学生学会运用在课堂中学过的理论知识，解决相应的实际问题，进一步理解和灵活掌握所学的内容，培养学生理论和实践相结合的能力，培养学生分析问题解决问题的能力。同时，在实验环节规范化、程序设计方法等方面受到比较系统和规范的训练。通过实践设计使学生进一步加深对程序设计的规范化及对复杂程序设计环节的理解。通过课程设计，加深对《数据结构》这一课程所学内容的进一步理解与巩固。通过课程设计，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。通过课程设计，提高程序开发功能，能运用合理的控制流程编写清楚高效的程序。通过课程设计，训练C程序调试能力，能将一个中小型各级组织系统联调通过。通过课程设计，开发一个中小型系统，掌握系统研发全过程。通话课程设计，培养分析问题、解决实际问题的能力。

1.2 课程设计的实验环境
PC机，WindowsXP，C++。
1.3 课程设计的预备知识
C语言程序设计、数据结构。
1.4 课程设计规定
（1）认真查找资料，分析每个题目应选择的数据结构（逻辑结构和物理结构）；
（2）准时到实验室调试程序，遵守实验室的规章制度，爱惜设备；
（3）每个题目编写源程序时，每个子功能定义为相应的子函数，在主函数中调用各子函数，程序结构清楚，有必要的注释，可读性强。
（4）程序健壮性强，当数据输入错误时，要进行相应的解决；
（5）分析算法的时间复杂度，规定算法的效率尽也许高；
（6）对于排序算法，要验证排序算法的稳定性。

第2章 课程设计内容
2.1题目的选择
6、学生成绩管理系统
2.2 题目的具体实现
（1）题目应实现的具体功能；
录入学生成绩信息并保存；
可查询显示所有学生的个人信息；
可查询显示所有学生的所学课程信息；
按学号或姓名查询成绩信息;
能添加、删除和修改学生的成绩信息；

（2）题目所选择的数据结构及存储结构；
采用线性数据结构及链式存储结构
（3）完整的源程序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct stud
{
long num;
char name[20];
double score1,score2;
};
typedef struct stucode
{
struct stud student ;
struct stucode *next;
}L;
void menu();
void createlist(struct stucode **r);
void out(struct stucode *r);
void search1(struct stucode *r);
void search2(struct stucode *r);
void del(struct stucode **r);
void insert(struct stucode **r);
void change(struct stucode **r);
void main()
{
char choose;
int flag=1;
struct stucode *r=NULL;
while(flag)
{
system("cls");
menu();
choose=getchar();
switch(choose)
{
case '1':
createlist(&r);
out(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '2':
search1(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '3':
search2(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '4':
del(&r);
out(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '5':
insert(&r);
out(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '6':
out(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '7':
change(&r);
out(r);
printf("Testing function 1\nPress any key to continue\n");
getchar();
getchar();
break;
case '0':
flag=0;
printf("The end.\n");
break;
default: printf("\nWrong Selection!(选择错误,请重选!)\n");
getchar();
getchar();
}
}
}
void createlist(struct stucode **r)
{
struct stucode *p,*t;
long n;
char a[20];
double s1,s2;
if(*r) *r=NULL;
printf(" \n请输入：\n 学号 姓名 分数1 分数2（若要结束请输入四个为零）\n");
scanf("%ld%s%lf%lf",&n,a,&s1,&s2);
if(n==0) return;
p=(L *)malloc(sizeof(L));
p->student.num=n;
strcpy(p->student.name,a);
p->student.score1=s1;
p->student.score2=s2;
p->next=NULL;
*r=p;
scanf("%ld%s%lf%lf",&n,a,&s1,&s2);
while(n)
{
t=p;
p=(L *)malloc(sizeof(L));
p->student.num=n;
strcpy(p->student.name,a);
p->student.score1=s1;
p->student.score2=s2;
p->next=NULL;
t->next=p;
scanf("%ld%s%lf%lf",&n,a,&s1,&s2);
}
}
void search1(struct stucode *r)
{
long x; struct stucode *p=r;
if(!r)
{
printf("没有学生信息可查询!\n");
return ;
}
printf(" 请输入要查询的学生信息的学生学号:\n");
scanf("%ld",&x);
while(p&&p->student.num!=x)
p=p->next;
if(p==NULL)
printf("Error! No such student !\n");
else
printf("%ld%s%.2lf%.2lf\n",p->student.num,p->student.name,p->student.score1,p->student.score2);
}
void search2(struct stucode *r)
{
char m[20];
if(!r)
{
printf("没有学生信息可查询!\n");
return ;
}
printf(" 请输入要查询的学生信息的学生姓名:\n");
scanf("%s",m);
while(r&&strcmp(r->student.name,m))
r=r->next;
if(r==NULL)
printf("Error! No such student !\n");
else
printf("%ld%s%.2lf%.2lf\n",r->student.num,r->student.name,r->student.score1,r->student.score2);
}
void del(struct stucode **r)
{
long k;
struct stucode *p=*r,*t;
if(!(*r))
{
printf("没有学生信息可删除 !\n");
return ;
}
printf(" 请输入要删除的学生信息的学生学号:\n");
scanf("%ld",&k);
if(p->student.num==k)
*r=(*r)->next,free(p);
else
{
while(p->next&&p->next->student.num!=k)
p=p->next;
if(p->next==NULL)
printf("Error! No such student !\n");
else
{
t=p->next;
p->next=p->next->next;
free(t);
}
}
}
void insert(struct stucode **r)
{
long n;
char a[20];
double s1,s2;
L *p,*t,*k;
printf(" 请输入要插入的学生信息的学生学号 姓名 分数1 分数2 :\n");
scanf("%ld%s%lf%lf",&n,a,&s1,&s2);
p=(L *)malloc(sizeof(L));
p->student.num=n;
p->student.score1=s1;
p->student.score2=s2;
strcpy(p->student.name,a);
if(!(*r))
{
*r=p;
(*r)->next=NULL;
return ;
}
if(p->student.num<(*r)->student.num)
p->next=(*r),(*r)=p;
else
{
t=*r;
k=t;
while(t->next&&t->next->student.num<=p->student.num)
t=t->next;
p->next=t->next;
t->next=p;
*r=k;
}
}
void out(struct stucode *r)
{
printf("\n\n");
if(!r)
{
printf("没有学生信息可输出!\n");
return ;
}
while(r)
{
printf("%ld%s%.2lf%.2lf\n",r->student.num,r->student.name,r->student.score1,r->student.score2);
r=r->next;
}
printf("\n\n");
}
void change(struct stucode **r)
{struct stucode *p=*r;long x;long n;
char a[20];
double s1,s2;
printf("更改的学生的信息\n");
printf(" 请输入要查询的学生信息的学生学号:\n");
scanf("%ld",&x);
while(p&&p->student.num!=x)
p=p->next;
if(p==NULL)
printf("Error! No such student !\n");
else
printf("%ld%s%.2lf%.2lf\n",p->student.num,p->student.name,p->student.score1,p->student.score2);
printf(" 请输入要修改的学生信息:\n");
scanf("%ld%s%lf%lf",&n,a,&s1,&s2);
p->student.num=n;
strcpy(p->student.name,a);
p->student.score1=s1;
p->student.score2=s2;
}
void menu()
{
printf("\n 学生成绩管理系统\n");
printf("\n 菜单\n\n");
printf("\n 1建立链表\n");
printf("\n 2查找某学号的学生信息\n");
printf("\n 3查找某姓名的学生信息\n");
printf("\n 4删除某学号的学生信息\n");
printf("\n 5插入新的学生信息\n");
printf("\n 6显示所有学生的个人信息\n");
printf("\n 7更改学生个人信息\n");
printf("\n 0退出\n");
printf("\n 请选择您要执行的选项:\n");
}

（4）程序的输入和输出

图1
按学生学号查找结果：

图2

按学生姓名查找：

图3
删除某学生的运营结果：

图4

插入某学生的运营结果：

图5
显示所有学生的信息：

图6

（5）调试程序中碰到的问题及解决方案
在调试search1子函数由于在查找中移动了原指针，导致search1中不能查找，解决方法设一结构体类型的指针，将原指针赋给该指针，将该指针进行移动查找。在调试chance()中，如何对已有的记录进行从新输入更改。解决方案为在chance()子函数中加入一个查找的程序，也就是说先找到要修改的学生信息，用scanf语句对要修改的学生的信息进行重新输入，再将所赋的信息通过赋值语句将修改后的学生信息赋给该学生相应的结构体。如何返回一个结构体中信息，解决方案是采用指针类型，将变量的地址作为实参赋给子函数。数组名代表数组首地址，用scanf语句赋值字符串时，不用加地址操作符。

2.3 思考题解析
所选择的思考题： 编写一个算法，构造一棵哈夫曼树。
程序如下：
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode
void HnffCodeding(HnffmanTree &HT,&HC,int *w,int n)
{
if(n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT;i=1;i<=n;++i,++,++w) *p={ *w,0,0,0};
for(;i<=m;++i,++p) *p={ *w,0,0,0};
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*size(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]=0;
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i;f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]="0";
else cd[--start]="1";
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}

算法分析：
哈夫曼树构造方法如下：
（1） 根据给定的n个权值{W1,W2,…….Wn}构成n课二叉树的集合F={T1,T2……..Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均为空。
（2） 在F中选取两棵节点的权值最小的树为左右之树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左右子树上根结点的权值之和。
（3） 在F中删除这两棵树。同时将得到的二叉树加入F中。
（4） 反复（2）和（3），直到F只含一棵树为止。
哈夫曼树优点：
（1）总平均码长最短;
（2）任一个字符的的编码的前缀都不是另一个字符的编码的前缀。
（3）提高信道运用率，节省发报时间。

总结：
通过本次课程设计，使我学会运用在课堂中学过的理论知识，解决相应的实际问题，进一步理解和灵活掌握所学的内容，培养我们的理论和实践相结合的能力，分析问题解决问题的能力。同时，在实验环节规范化、程序设计方法等方面受到比较系统和规范的训练。
通过实践设计使我们进一步加深对程序设计的规范化及对复杂程序设计环节的理解。通过课程设计，加深对《数据结构》这一课程所学内容的进一步理解与巩固。并通过课程设计，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构，提高程序开发功能，能运用合理的控制流程编写清楚高效的程序，训练C程序调试能力，能将一个查找表调试通过，并掌握系统研发全过程，培养分析问题、解决实际问题的能力。
通过本次课程设计我对结构体，指针有了更深的了解，提高了程序设计的能力。在本次课程设计中，我碰到了很多问题，这不仅使我在专业知识上有了很大的提高，同时也增强了我的逻辑思维能力和动手实践的能力，培养了我面对问题的解决心态，使我在个人素质方面也有了很大的提高。

本人签字：

参考文献
[1]严蔚敏.数据结构.北京.清华大学出版社.2023年8月
[2]谭浩强.C程序设计.北京.清华大学出版社.2023年7月
[3]李春葆著.数据结构教程.清华大学出版社.2023年1月
[4]严蔚敏，吴伟民编著，数据结构，北京.清华大学出版社，1997.4
[5]朱战立，张选平编著.数据结构学习指导和典型例题.西安.西安交通大学出版社，2023.4