《数据结构程序论》word版.doc

学年论文（数据结构 2014-2015 第二学期）题目： 数据结构程序论文 作者： 所在学院： 专业年级： 指导教师： 职称： 2015年 05 月 20日目录1.基本信息32.课程目的和要求32.1课程设计目的32.2课程设计要求和设计33.需求分析和概要设计33.1学籍信息管理33.2链表应用43.3图的部分算法43.4学生成绩管理系统44. 流程图54.1学籍信息管理54.2链表应用54.3图的部分算法64.4学生成绩管理系统65.运行结果85.1学籍信息管理85.2链表应用105.3图的部分算法125.4学生成绩管理系统136.总结207.用户使用说明208.附录（源代码）218.1学生学籍管理系统源代码218.2链式存储的应用-多项式相加源代码298.3图的部分算法源代码348.4学生成绩管理源代码37信息科学与工程学院学生“数据结构课程设计”大作业1.基本信息学生学号班级课程名任课教师学期得分苏晓娜20141401716计算机14-5班数据结构课程设计崔青2014-2015（2）2.课程目的和要求2.1课程设计目的综合应用数据结构课程中所学的数据结构：线性表、栈、队列、数组与稀疏矩阵、树、二叉树、图、检索中的一种或多种数据结构完成一个较大问题的求解（其实这里的问题也并不太大，所用的数据结构可能是其中的多个，也可能是其中的一个两个）。从而培养学生综合应用基本数据结构分析、解决实际问题的能力，并进一步加深对所学知识的理解和掌握。学生成绩管理系统功能的信息量大，数据安全性和保密性要求最高。本功能实现对专业信息、学生信息、情况信息的管理和统计、课程信息和成绩信息查看及维护。2.2课程设计要求和设计1、严格按要求使用计算机等相关实验设备。2、通过实验提高动手操作能力。3、通过实验学会用专业知识分析问题、解决问题的基本方法和步骤。4、能够用理论指导实践。5、通过实验加深对理论知识的理解。6、能够掌握一定软件开发技术，具备一定的软件开发能力。3.需求分析和概要设计3.1学籍信息管理需求分析：综合考察数据存储、以及对各种存储结构的建立、插入、删除、排序、查找等操作。概要设计：（1）数据录入功能：录入每个学生的学号、课程编号、课程名称、学分、平时成绩、实验成绩、卷面成绩共7个数据。实得成绩、实得学分根据条件自动运算。 综合成绩的计算： a.如果本课程的实验成绩为-1，则表无实验成绩，综合成绩=平时成绩*30%+卷面成绩*70% b.如果实验成绩不为-1，表示本课程有实验成绩，综合成绩=平时成绩*15%+实验成绩*15%+卷面成绩*70%实得学分的计算：采用等级学分制。 综合成绩在90100之间，应得学分=学分*100% 综合成绩在8090之间，应得学分=学分*80% 综合成绩在7080之间，应得学分=学分*75% 综合成绩在6070之间，应得学分=学分*60% 综合成绩在60分以下，应得学分=学分*0%查询功能：分为学生基本情况查询和成绩查询两种 （2）删除功能：根据输入的学生姓名或学好删除相应的学生信息。（3）排序功能：能实现选择按综合成绩或实得学分升序或降序排序并显示数据。3.2链表应用试设计一元多项式相加（链式存储）的加法运算。 A（X）=7+3X+9X8+5X9 B（X）=8X+22X7-9X8 1建立一元多项式； 2输出相应的一元多项式； 3相加操作的实现。3.3图的部分算法实现以下两个算法：（1） 深度和广度优先搜索遍历图；（2） 拓扑排序算法；3.4学生成绩管理系统需求分析：用数据结构知识编程一个成绩管理系统。学生成绩的查询和修改提供的学号、姓名完成学生成绩的查询，或者插入，删除学生的信息。能根据输入的学号查找学生，进行信息的修改。能根据输入的学号从结构体数组中学生的记录。实现查询功能，能根据输入的学号或年级在屏幕上显示相应的学生信息。能在屏幕上以列表的方式输出所有学生的信息。概要设计：系统的主要功能系统的主要功能是实现基本的学生成绩的管理和维护。主要包括：(1)学生信息及成绩的录入要求包括的学生信息有：学号、姓名、性别、出生日期、民族及数据结构成绩（具体内容可自行假设，至少录入10名以上学生）所录入的学生按学号散列存储（散列函数为：学号%5 取整，如 1002%5 =2），采用拉链法解决冲突。(2)学生成绩的查询要求根据提供的学号完成学生成绩的查询（必须采用哈希查找）(3)学生成绩的分段统计和排序输出统计出各分数段学生人数（60分以下，6070，7180，.)采用任何一种排序方法，将学生成绩从高到低排序输出4. 流程图4.1学籍信息管理登录界面学籍管理系统添加信息查询信息修改信息删除信息显示信息退出系统图4.1学籍信息管理的流程图4.2链表应用结束开始复制两个多项式合并连接好的多项式的同类项连接两个多项式4.2链表多项式相加流程图4.3图的部分算法图4.3图的部分算法的流程图4.4学生成绩管理系统图4.4.1学生成绩管理的流程图图4.4.2学生成绩统计排序图4.4.3查询学生数据图4.4.4学生成绩管理系统函数即实现功能5.运行结果5.1学籍信息管理5.2链表应用5.3图的部分算法图4.3的运行结果图4.3的运行结果5.4学生成绩管理系统6.总结 做了几个星期的数据结构程序设计终于做完了，在这次小学期程序设计课中不仅让我对一学期的知识内容有了一个总结性的了解，更让我在本次的程序设计过程当中学到了很多东西，比如小组合作，与同学讨论，报告的整理，和对程序编写的新的认识。 在本次小组合作完成设计过程中，我和马涛，孟冬芹三人一组，我们通过选题、设计程序、资料查询、同学讨论、不断地调试和修改代码，共同完成了设计课题。首先我们在选题上根据个人特长和程序使用性选了4个题目，马涛主要负责学籍信息管理，我主要负责学生成绩管理系统，孟冬主要芹负责链表应用和图的部分算法。在这次程序设计完成的过程中，我们都不同程度的提高了对数据结构知识掌握和运用。 由于我对上学期的C语言跟这学期的数据结构都掌握的不够清楚，对于书上的难点的知识也只是稍微懂一些，所以在做课题的时候查了C语言和数据结构的一些资料，通过看书发现原来懂的东西现在看下就很容易记起来，那些不太懂的和不懂的现在看看其实也不是那么难了。通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也对程序产生了很大的兴趣，原来生活中一些常见的应用是这么实现的，其实设计一个程序不难，难的是对于一个程序思想的理解，要掌握一个算法，不仅仅限于读懂，主要的是要理解它的思路，理解它解决问题的方法。所以通过这次试验中，我发现书本上的知识是一个基础，但是我基础都没掌握，更别说写出一个整整的程序了。自己在写程序的时候，也发现自己的知识太少了，特别是基础知识很多都是模模糊糊的一个概念，没有落实到真正的程序。以后要多练习多编辑运行程序。 这次小组合作完成作业中，提高了对数据结构知识的掌握运用和小组合作的能力，非常感谢崔老师的指导，和我的两个小伙伴及班里同学的帮助。7.用户使用说明1.学生信息管理系统 本程序在c+6.0环境下运行通过。运行后,根据提示输入数据即可。综合考察数据存储、以及对各种存储结构的建立、插入、删除、排序、查找等操作。学生成绩的查询和修改提供的学号、姓名完成学生成绩的查询，或者插入，删除学生的信息。2.链表应用 本程序在c+6.0环境下运行通过。运行后,根据提示输入数据即可。3. 图的部分算法 本程序在c+6.0环境下运行通过。运行后,根据提示输入数据即可。先进行图的拓扑排序，最后输出的是深度和广度优先遍历后的结果。4.学生成绩管理系统本程序在c+6.0环境下运行通过。运行后,根据提示输入数据即可。可以进行学生成绩信息的录入，导入，查询，删除，显示，统计，保存，排序。可以很方便的对学生信息进行加工处理。8.附录（源代码）8.1学生学籍管理系统源代码#include #include #include #define BUFLEN 100 #define LEN 15 #define N 100 /学号 课程编号 课程名称 学分平时成绩 实验成绩 卷面成绩 综合成绩 实得学分struct record /*结构体*/ char codeLEN+1; /* 学号 */ char nameLEN+1; /* 姓名 */ int age; /* 年龄 */ char sex3; /* 性别 */ char timeLEN+1; /* 出生年月 */ char add30; /* 家庭地址 */ char telLEN+1; /* 电话号码 */ char mail30; /* 电子邮件地址 */ char CnoLEN+1;/* 课程编号 */ char CnameLEN+1;/* 课程名称 */ char Csd5;/* 学分平时成绩 */ char Cps10;/* 实得学分 */ char Csy10;/* 实验成绩 */ char Cjm10;/* 卷面成绩 */ char Czh20;/* 综合成绩 */ stuN; int k=1,n,m; /* 定义全局变量 */ /* 函数声明 */ void seek(); void modify(); void insert(); void insert1(); void del(); void massage(); void menu(); void course(); void logo(); int main() char name20; int password=1; printf( nn 欢迎登录学籍信息管理 nn); printf( * n); printf( * 制作人:苏晓娜 学号:20141401716 班级:计算机14-5 指导老师：崔青 * n); printf( * n); logo(); system(pause); system(CLS);/*清屏*/ while(k) menu(); system(pause); return 0; void seek() /*查找*/ int i,item,flag; char s121; /* 以姓名和学号最长长度+1为准 */ printf(-n); printf(-1.按序号查询-n); printf(-2.按姓名查询-n); printf(-3.退出本菜单-n); printf(-n); while(1) printf( 请选择子菜单编号:); scanf(%d,&item); flag=0; switch(item) case 1: printf(请输入要查询的同学的序号:n); scanf(%s,s1); for(i=0;in;i+) if(strcmp(stui.code,s1)=0) flag=1; printf( 学号 姓名 年龄 性别 出生年月 地址 电话 E-mailn); printf(-n); printf(%6s %7s %6d %5s %9s %8s %10s %14sn,stui.code,,stui.age, stui.sex,stui.time,stui.add,stui.tel,stui.mail); if(flag=0) printf(该序号不存在！n); break; case 2: printf(请输入要查询的同学的姓名:n); scanf(%s,s1); for(i=0;in;i+) if(strcmp(,s1)=0) flag=1; printf( 学号 姓名 年龄 性别 出生年月 地址 电话 E-mailn); printf(-n); printf(%6s %7s %6d %5s %9s %8s %10s %14sn,stui.code,,stui.age, stui.sex,stui.time,stui.add,stui.tel,stui.mail); if(flag=0) printf(该姓名不存在！n);break; case 3:return; default:printf(请在1-3之间选择n); void modify() /*修改信息*/ int i,item,num; char sex13,s1LEN+1,s2LEN+1; /* 以姓名和学号最长长度+1为准 */ printf(请输入要要修改的同学的序号:n); scanf(%s,s1); for(i=0;in;i+) if(strcmp(stui.code,s1)=0) /*比较字符串是否相等*/ num=i; printf(-n); printf(1.修改姓名n); printf(2.修改年龄n); printf(3.修改性别n); printf(4.修改出生年月n); printf(5.修改地址n); printf(6.修改电话号码n); printf(7.修改E-mail地址n); printf(8.退出本菜单n); printf(-n); while(1) printf(请选择子菜单编号:); scanf(%d,&item); switch(item) case 1: printf(请输入新的姓名:n); scanf(%s,s2); strcpy(,s2); break; case 2: printf(请输入新的年龄:n); scanf(%d,&stunum.age); break; case 3: printf(请输入新的性别:n); scanf(%s,sex1); strcpy(stunum.sex,sex1); break; case 4: printf(请输入新的出生年月:n); scanf(%s,s2); strcpy(stunum.time,s2); break; case 5: printf(请输入新的地址:n); scanf(%s,s2); strcpy(stunum.add,s2); break; case 6: printf(请输入新的电话号码:n); scanf(%s,s2); strcpy(stunum.tel,s2); break; case 7: printf(请输入新的E-mail地址:n); scanf(%s,s2); strcpy(stunum.mail,s2); break; case 8:return; default:printf(请在1-8之间选择n); void logo() /登录 int n=0,k=0;char Name20=苏晓娜,Pass20=20141401716;char mingzi20,mima20;printf(n);retur:if(n3)printf(tt用户名： );scanf(%s,mingzi);if(strcmp(Name,mingzi)=0)printf(tt用户名正确！ n);elseprintf(tt用户名错误！三次输入错误退出程序n);n+;goto retur;else exit(1);retu:if(k3) printf(tt密 码： );scanf(%s,mima);if(strcmp(Pass,mima)=0)printf(tt登陆成功！ n);else printf(ttt密码错误！三次输入错误退出程序n);k+;goto retu; else exit(1);void sort()/*按学号排序*/ int i,j,*p,*q,s; char temp10; for(i=0;ii;j-) if(strcmp(stuj-1.code,stuj.code)0) strcpy(temp,stuj-1.code); strcpy(stuj-1.code,stuj.code); strcpy(stuj.code,temp); strcpy(temp,); strcpy(,); strcpy(,temp); strcpy(temp,stuj-1.sex); strcpy(stuj-1.sex,stuj.sex); strcpy(stuj.sex,temp); strcpy(temp,stuj-1.time); strcpy(stuj-1.time,stuj.time); strcpy(stuj.time,temp); strcpy(temp,stuj-1.add); strcpy(stuj-1.add,stuj.add); strcpy(stuj.add,temp); strcpy(temp,stuj-1.tel); strcpy(stuj-1.tel,stuj.tel); strcpy(stuj.tel,temp); strcpy(temp,stuj-1.mail); strcpy(stuj-1.mail,stuj.mail); strcpy(stuj.mail,temp); p=&stuj-1.age; q=&stuj.age; s=*q; *q=*p; *p=s; void insert() /*插入函数*/ int i=n,j,flag; printf(请输入待增加的人数:n); scanf(%d,&m); do flag=1; while(flag) flag=0; printf(请输入第 %d 个同学的序号:n,i+1); scanf(%s,stui.code); for(j=0;ji;j+) if(strcmp(stui.code,stuj.code)=0) printf(已有该序号,请检查后重新录入!n); flag=1; break; /*如有重复立即退出该层循环,提高判断速度*/ printf(请输入第 %d 个学生的姓名:n,i+1); scanf(%s,); printf(请输入第 %d 个学生的年龄:n,i+1); scanf(%d,&stui.age); printf(请输入第 %d 个学生的性别:n,i+1); scanf(%s,stui.sex); printf(请输入第 %d 个学生的出生年月:(格式:年.月)n,i+1); scanf(%s,stui.time); printf(请输入第 %d 个学生的地址:n,i+1); scanf(%s,stui.add); printf(请输入第 %d 个学生的电话:n,i+1); scanf(%s,stui.tel); printf(请输入第 %d 个学生的E-mail:n,i+1); scanf(%s,stui.mail); if(flag=0) i=i; i+; while(in+m); n+=m; printf(录入完毕！nn); sort(); void insert1() /*插入函数*/ int i=n,j,flag; printf(请输入待增加的人数:n); scanf(%d,&m); do flag=1; while(flag) flag=0; printf(请输入第 %d 个学生的序号:n,i+1); scanf(%s,stui.code); for(j=0;ji;j+) if(strcmp(stui.code,stuj.code)=0) printf(已有该序号,请检查后重新录入!n); flag=1; break; /*如有重复立即退出该层循环,提高判断速度*/ printf(请输入课程编号:n,i+1); scanf(%s,stui.Cno); printf(请输入课程名称:n,i+1); scanf(%s,&stui.Cname); printf(请输入学分平时成绩:n,i+1); scanf(%s,stui.Cps); printf(请输入实验成绩:n,i+1); scanf(%s,stui.Csy); printf(请输入卷面成绩:n,i+1); scanf(%s,stui.Cjm); printf(请输入综合成绩:n,i+1); scanf(%s,stui.Czh); printf(请输入实得学分:n,i+1); scanf(%s,stui.Csd); if(flag=0) i=i; i+; while(in+m); n+=m; printf(录入完毕！nn); sort(); void del() /删除 int i,j,flag=0; char s1LEN+1; printf(请输入要删除同学的序号:n); scanf(%s,s1); for(i=0;in;i+) if(strcmp(stui.code,s1)=0) flag=1; for(j=i;jn-1;j+) stuj=stuj+1; if(flag=0) printf(该序号不存在！n); if(flag=1) printf(删除成功,显示结果请选择菜单5n); n-; void massage() int i; printf( 所有同学的基本信息为:n); printf( 学号 姓名 年龄 性别 出生年月 地址 电话 E-mailn); printf(-n); for(i=0;in;i+) printf(%6s %7s %5d %5s %9s %8s %10s %14sn,stui.code,,stui.age, stui.sex,stui.time,stui.add,stui.tel,stui.mail); void course() int i; printf( 所有同学的成绩信息为:n); printf( 学号 课程编号 课程名称 学分平时成绩 实验成绩 卷面成绩 综合成绩 实得学分); printf(-n); for(i=0;in;i+) printf(%6s %7s %5d %5s %9s %8s %10s %14sn,stui.code,stui.Cno,stui.Cname, stui.Cps,stui.Csy,stui.Cjm,stui.Czh,stui.Csd); void menu()/* 界面 */ int num; printf( n); printf( n); printf( n); printf( *系统功能菜单* n); printf( - - n); printf( * 1.增加学生基本信息 * * 2.查询学生信息 * n); printf( * 3.修改学生信息 * * 4.删除学生信息 * n); printf( * 5.显示当前所有信息 * * 8.增加学生成绩信息 * n); printf( * 7.显示当前成绩信息 * * 6.退出系统 * n); printf( - - n); printf(请选择菜单编号:); scanf(%d,&num); switch(num) case 2:seek();break; case 3:modify();break; case 1:insert();break; case 4:del();break; case 5:massage();break; case 6:k=0;break; case 7:course();break; case 8:insert1();break; default:printf(请在1-6之间选择n); 8.2链式存储的应用-多项式相加源代码#include #include typedef struct pnode int exp; float coef; struct pnode *next; polynode; polynode *A,*B,*C,*D; polynode *creatA() polynode *p1,*r; int i,n; A=(polynode*)malloc(sizeof(polynode); A-next=NULL; r=A; printf(请输入A多项式的项数:); scanf(%d,&n); for(i=1;icoef,&p1-exp); r-next=p1; r=p1; r-next=NULL; return A; polynode *creatB() polynode *p2,*r; int i,n; B=(polynode*)malloc(sizeof(polynode); B-next=NULL; r=B; printf(请输入B多项式的项数:); scanf(%d,&n); for(i=1;icoef,&p2-exp); r-next=p2; r=p2; r-next=NULL; return B; void printA(polynode *A) polynode *p1; p1=A-next; while(p1-next!=NULL) if(p1-next-coef0) printf(%.2fx%d+,p1-coef,p1-exp); elseprintf(%.2fx%d,p1-coef,p1-exp); p1=p1-next; printf(%.2fx%d,p1-coef,p1-exp); void printB(polynode *B) polynode *p2; p2=B-next; while(p2-next!=NULL) if(p2-next-coef0) printf(%.2fx%d+,p2-coef,p2-exp); else printf(%.2fx%d,p2-coef,p2-exp); p2=p2-next; printf(%.2fx%d,p2-coef,p2-exp); void printC(polynode *C) polynode *p=C-next; while(p-next!=NULL) if(p-next-coef0) printf(%.2fx%d+,p-coef,p-exp); else printf(%.2fx%d,p-coef,p-exp); p=p-next; printf(%.2fx%d,p-coef,p-exp); void printD(polynode *D)polynode *p=D-next; while(p-next!=NULL) if(p-next-coef0) printf(%.2fx%d+,p-coef,p-exp); else printf(%.2fx%d,p-coef,p-exp); p=p-next; printf(%.2fx%d,p-coef,p-exp); polynode *polyadd(polynode *A,polynode *B) polynode *p1,*p2,*p,*C; float x; p1=A-next; p2=B-next; p=(polynode*)malloc(sizeof(polynode); p-next=NULL; C=p; while(p1&p2) if(p1-exp=p2-exp) x=p1-coef+p2-coef; if(x!=0) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=x; p-exp=p1-exp; p1=p1-next; p2=p2-next; else p-next=(polynode*)malloc(sizeof(polynode); p=p-next; if(p1-expp2-exp) p-coef=p2-coef; p-exp=p2-exp; p2=p2-next; else p-coef=p1-coef; p-exp=p1-exp; p1=p1-next; while(p1!=NULL) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=p1-coef; p-exp=p1-exp; p1=p1-next; while(p2!=NULL) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=p2-coef; p-exp=p2-exp; p2=p2-next; p-next=NULL; return C; polynode *polyminus(polynode *A,polynode *B) polynode *p1,*p2,*p,*D; float x; p1=A-next; p2=B-next; p=(polynode*)malloc(sizeof(polynode); p-next=NULL; D=p; while(p1&p2) if(p1-exp=p2-exp) x=p1-coef-p2-coef; if(x!=0) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=x; p-exp=p1-exp; p1=p1-next; p2=p2-next; else p-next=(polynode*)malloc(sizeof(polynode); p=p-next; if(p1-expp2-exp) p-coef=p2-coef; p-exp=p2-exp; p2=p2-next; else p-coef=p1-coef; p-exp=p1-exp; p1=p1-next; while(p1!=NULL) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=p1-coef; p-exp=