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

课程设计说明书

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

学院（系）：

专业班级：

学号：

学生：

指导教师：

教师职称：

起止时间：

课程设计（论文）任务及评语

院（系）：教研室：软件工程

学号学生专业班级

课程设计

（论文）数据结构与算法课程设计

题目

1•从十个题目中选择一个题目，，要求每个题目用标准的C语言程序实现，另夕卜，

课

完成思考题一题，思考题须写出相应的类C算法即可。

程

设2•每个题目编写源程序时，要求有主菜单，每个子功能定义为相应的子函数，在

计

(

论主函数中调用各子函数，程序结构清晰。

文

)

根据题目选择合适的逻辑结构和存储结构。

任3•，

务

4•输入的数据白键盘输入。

5•分析算法的时间复杂度，要求算法的效率尽可能高。

6•验证排序算法的稳定性。

指

导

教

师

评

语

及

成

绩

：

签字

教师

指导

：

成绩

日

月

2年

201

录

目

第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>

structstud

(

longnum;

charname[20];

doublescore1,score2;

)；

typedefstructstucode

(

structstudstudent;

structstucode*next;

}L;

voidmenuO;

voidcreatelist(structstucode株r);

voidout(structstucoce*r);

voidsearchi(structstucode*r);

voidsearch2(structstucode*r);

voiddel(structstucodeW);

voidinsert(structstucode**r);

voidcliangeCsliuclstucode**i);

voidmain()

(

charchoose;

intflag=l;

structstucode*r=NULL;

whiledlag)

(

systemC'cls");

menu();

choose=getchar();

switch(choose)

(

case'1,：

createlist(&r);

out(r);

printf("Testingfunction1\nPressanykeytocontinue\n");

getcharO;

getcharO;

break;

case'2’:

searchl(r);

printfCTestingfunctionl\nPressanykeytocontinue\n");

getchai();

getcharO;

break;

case'3*:

search2(r);

printfC'Testingfunctionl\nPressanykeytocontinue\n");

getchar();

getchar();

break;

case'4,:

del(&r);

out(r);

printfC'Testingfunctionl\nPressanykeytocontinue\n");

getchar();

getchar();

break;

case'5,:

insert(Sr);

out(r);

printf("Testingfunctionl\nPressanykeytocontinue\n");

getcharO;

getcharC);

break;

case'6’:

out(r);

printf("Testingfunctionl\nPressanykeytocontinue\n");

getcharC);

getcharC);

break;

case'T:

change(&r);

out(r);

printf("Testingfunctionl\nPressanykeytocontinue\n");

getcharC);

getcharC);

break;

case'0':

flag=0;

printfCTheend.\n");

break;

default:printfC*WrongSelection!(选择错误，请重选！)\n");

getcharC);

getcharO;

}

voidcreatelist(sliuclstucude**r)

(

structstucode®;

longn;

chara[20];

doublesi,s2;

if(*r)*r=NULL;

printfC\n请揄入：\n学号分数1分数2(若要结束请输入四个为零)\n");

scanf(,,%ld%s%l&n,a,&sl,&s2);

if(n==0)return;

p=(L*)malloc(sizeof(L));

p->student.num=n;

strcpy(p->student.name,a);

p->student.scorel=sl;

p->student.score2=s2;

p->next=NULL;

*r=p;

scanf(,,%ld%s%lf%lfn,&n,a,&sl,&s2);

while(n)

t=p;

p=(L*)malloc(sizcof(L));

p->student.num=n;

slrcpy(p->sludenl.name,a);

p->student.scorel=sl;

p->student.score2=s2;

p->next=NULL;

t->next=p;

scanf("%1d%s%1f%1fM,&n,a,&sl,&s2);

)

}

voidsearchi(structstucode*r)

(

longx;structstucode*p=r;

if(!r)

(

printf("没有学生信息可查询！\n”)；

return;

)

printfC请输入要查询的学生信息的学生学号：\n”);

scanf("%ld",&x);

while(p&&p->student.num!=x)

p=p->next;

if(p==NULL)

printf("Error!Nosuchstudent!\n");

else

prinlf("%ld%s%.2If%.21f\n",p->sludent.num,p->sludenl.name,p->sludent.score1

,p->student.score2);

}

voidsearch2(structstucode*r)

(

charm[20];

if(!r)

(

printf("没有学生信息可查询！\n");

return;

)

printfC请输入要查询的学生信息的学生：\n”)；

scanf("%s",m);

whi1e(r&&strcmp(r->student.name,m))

r=r->next;

if(r==NULL)

printf("Error!Nosuchstudent!\n");

else

printf("%ld%s%.2If%.21f\n\r->student.num,r->student.name,r->student.score1

,r->student.score2);

voiddel(structstucoce米米r)

(

longk;

structstucode*p=*r,*t;

if(!(知))

{

printf("没有学生信息可删除!\n");

return;

)

printf("请输入要删除的学生信息的学生学号:\n");

scanf("%ld",&k);

if(p->student.num==k)

*r=(*r)->next,free(p);

else

(

whi1e(p->next&&p->next->student.num!=k)

p=p->next;

if(p->next==NULL)

printf("Error!Nosuchstudent!\n");

else

t=p->next;

p->ncxt=p->next->next;

free(t);

}

)

)

voidinsert(structstucode**r)

(

longn;

chara[20];

doublesi,s2;

L*p,*t,*k;

printf(”请输入要插入的学生信息的学生学号分数1分数2:\n");

scanf(n%ld%s%lf%lf",&n,a,&sl,&s2);

p=(L*)malloc(sizeof(L));

p->student.num=n;

p->studcnt.scorel=sl;

p->student.score2=s2;

strcpy(p->student.name,a);

if(!(*r))

(

*r=p;

(*r)->next=NULL;

return;

if(p->studcnt.num<(*r>>studcnt.num)

p->next=(*r),(*r)=p;

else

(

t=*r;

k=t;

whi1e(t->next&&t->next->student.num<=p->student.num)

t=t->next;

p->next=t->next;

t->next=p;

*r=k;

}

)

voidout(structstuccde米r)

(

printfC\n\n");

if(!r)

(

printfC没有学生信息可输出！\n”)；

return;

while(r)

printf("%ld%s%.2If%.21f\n",r->studcnt.num,r->student.name,r->student.score1

,r->student.score2);

r=r->next;

)

printf("\n\nu);

)

voidchange(structstucode

{structstucode*p=*r;longx;longn;

chara[20];

doublesi,s2;

printf("更改的学生的信息\n”);

printf("请输入要查询的学生信息的学生学号：\n”)；

scanf("%ld",&x);

while(p&&p->student.num!=x)

p=p->next;

if(p==NULL)

printf("Error!Nosuchstudent!\n")；

else

printf("%ld%s%.21f%.21f\n\p->student.num,p->student.name,p->student.score1

,p->student.score2);

printfC请输入要修改的学生信息：\n”);

scanf("%1d%s%1f%1f",&n,a,&sl,&s2);

p->studcnt.num=n;

strcpy(p->studcnt.name,a);

p->student.scorel=sl;

p->sludent.scoie2=s2;

)

voidmenu()

{

printfC'\n学生成绩管理系统\n”)；

printf("\n菜单\n\n");

printf("\n1建立链表\d);

printf("\n2查找某学号的学生信息\n”)；

printf("\n3查找某的学生信息\n”)；

printfC\n4删除某学号的学生信息\n”)；

printfC\n5插入新的学生信息\n");

printfC'\n6显示所有学生的个人信息\n");

printfC\n7更改学生个人信息\n");

printfC\n0退出\n");

printfC\n请选择您要执行的选项：\n");

(4)程序的输入和输出

学生成绩管理系统

菜单

1建立链表

2查找某学号的学生信息

3查找某姓名的学生信息

4删除某学号的学生信息

5插入新的学生信息

6显示所有学生的个人信息

7更改学生个人信息

0退出

请选择您要执行的选项：

图1

按学生学号查找结果：

1建立链表

2查找某学号的学生信息

3查找某姓名的学生信息

4删除某学号的学生信息

5插入新的学生信息

6显示所有学生的个人信息

7更改学生个人信息

。退出

请选择您要执行的选项：

2

请输入要查询的学生信息的学生学号:

101002

101002li39.0092.00

Testingfunction1

Pressanykeytocontinue

图2

按学生查找：

1建立链表

2查找某学号的学生信息

3查找某姓名的学生信息

4删除某学号的学生信息

5插入新的学生信息

6显示所有学生的个人信息

7更改学生个人信息

。退出

请选择您要执行的选项：

3请输入要查询的学生信息的学生姓名:

li

1010021i39.0092.00

Testingfunction1

Pressanykeytocontinue

图3

删除某学生的运行结果：

1建立链表

2查找某学号的学生信息

3查找某姓名的学生信息

4删除某学号的学生信息

5插入新的学生信息

6显示所有学生的个人信息

7更改学生个人信息

0退出

请选择您要执行的选项：

请输入要删除的学生信息的学生学号:

101002

101001sun48.0083.00

101003v/ang85.0064.00

图4

插入某学生的运行结果：

［建立链表

2查找某学号的学生信息

3查找某姓名的学生信息

4删除某学号的学生信息

5插入新的学生信息

6显示所有学生的个人信息

7更改学生个人信息

0退出

请选择您要执行的选项：

S请输入要插入的学生信息、的学生学号姓名分数1分数2：

101002li3992

I101001sun48.0083.00

101002li39.0092.00

I1.01.003“ang85.0064.00

图5

显示所有学生的信息：

1建立槌表

2查找某学号的学生信息

3查找某姓名的学生信息

4删除某学号的学生信息

5插入新的学生信息

6显示所有学生的个人信息

7更改学生个人信息

。退出

请选择您要执行的选项：

101001sun48.0083.00

1010021139.0092.00

101003wang85.0064.00

图6

(5)调试程序中遇到的问题及解决方案

在调试searchl子函数由亍在查找中移动了原指针，导致seaichl中不能查找，解

决方法设一结构体类型的指针，将原指针赋给该指针，将该指针进行移动查找。在调试

chanceO中，如何对已有的记录进行从新输入更改。解决方案为在chance。子函数中

加入一个查找的程序，也就是说先找到要修改的学生信息，用scanf语句对要修改的学

生的信息进行重新输入，再将所赋的信息通过赋值语句将修改后的学生信息赋洽该学生

对应的结构体。如何返回一个结构体息，解决方案是采用指针类型，将变量的地址作为

实参赋给子函数。数组名代表数组首地址，用scanf语句赋值字符串时，不用加地址操

作符。

2.3思考题解析

所选择的思考题：编写一个算法，构造一棵哈夫曼树。

程序如下：

typedefstruct{

unsignedintweight;

unsignedintparent,IchiId,rchiId;

(HTNode,*HuffmanTree;

typcdcfchar**HuffmanCode

voidHnffCodeding(HnffmanTree&HT,&HC,int*w,intn)

(

if(n<=l)return;

m=2*n-l;

HT=(HuffmanTree)malloc((m+l)*sizeof(HTNode));

for(p=HT;i=l;i<=n;++i,++,Hw)*p={米w,0,0,0};

for(;i<=m;++i,++p)*p={*w,0,0,0};

for(i=n+l;i<=m;++i)

(

Select(HT,i-1,si,s2);

HT[sl].parent=i;HT[s2].parent=i;

HT[i].lchild=sl;HT[i].rchild=s2;

HT[i].weight=HT[sl].weight+HT[s2].weight;

}

HC=(HuffmanCode)malloc((n+l)*size(char*)〕;

cd=(char*)malloc(n*sizeof(char));

cd[n-l]=0;

for(i=l;i<=n;++i)

{

start=n-l;

for(c=i;f=HT[i].parent;f!=0;c=f,f=HT[f].parent)

if(HT[f].lchild==c)cd[—start]="O";

elsecd[—start]="1";

IIC[i]=(char^)malloc((n-start)^sizcof(char));

strcpy(IIC[i],&cd[start]);

}

free(cd);

算法分析：

哈夫曼树构造方法如下：

(I)根据给定的n个权值｛Wl,W2,…….Wn)构成n课二叉树的集合

F=｛T1,T2……..Tn｝，其中每棵二叉树Ti中只有一个带权为Wi的根节点，其左

右子树均为空。

(2)在F中选取两棵节点的权值最小的树为左右之树构造一棵新的二叉树，且置新的

二叉树的根结点的权值为左右子树上根结点的权值之和。

(3)在F中删除这两棵树。同时将得