计算机学院数据结构课程设计

1、计算机科学与技术学院课程设计成绩单课程名称：数据结构 指导教师： 姓名性别男学号班级综合成绩成绩等级程序运行情况（占总成绩20%）能正确运行 基本能正确运行 能运行但结果不完善（20分） （15分） （10分）程序功能的完善程度（占总成绩10%）完善 基本完善 不完善（10分） （8分） （5分）程序结构的合理性（占总成绩10%）合理 基本合理 不太合理（10分） （8分） （5分）对问题的答辩情况（占总成绩40%）概念正确有创新 能正确回答所有问题 基本能正确回答（40分） （35分） （30分）部分问题回答概念不清晰（20分）学生的工作态度与独立工作能力（占总成绩10%）工作态度认真能独立

2、完成任务 工作态度认真但独立性较差（10分） （8分）工作态度基本认真但缺乏独立性（5分）设计报告的规范性（占总成绩10%）符合规范 基本符合规范 规范性较差（10分） （8分） （5分）优秀：90分100分 良好：80分89分 中等：7079分 及格：6069分 不及格0分59分 计算机科学与技术学院 课 程 设 计 报 告课程名称： 数 据 结 构 专 业: 计算机科学与技术 班 级: 学 号: 姓 名: 指导老师： 【设计目的】数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C

3、（C+）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用，学以至用，才能真正的培养学生的能力。【设计要求】1、课程设计题目共两题，每个学生必须独立完成；2、课程设计时间为1.5周；3、设计语言C（C+）不限；4、课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。上机时带上源程序、数据结构教材、C语言教材。题目一 火车票务系统的设计与实现设计一个火车票务系统，并完成如下功能：列车记录包含6项：车次、始发站、终点站、发车时间、到站时间、票

4、价Z38、 武昌、 北京西、21:06 、07:01 、272（1）列车信息录入：输入列车基本信息。（2）列车信息删除：删除车次信息。(列车线路停运)（3）列车信息修改：删除车次信息。（列车时间、票价等信息有变动）（4）列车信息输出：根据格式对齐输出列车信息。（5）列车信息查询：可根据车次号、始发站、终点站查询满足条件的列车信息。（6）列车信息排序：可根据票价对列车信息进行排序并输出。【需求分析】一根据题目要求系统主界面应有以下几个功能：1录入信息2 显示信息3 查询信息4 增加信息5 修改信息6 删除信息7排序对于各种有关信息操作，必须包括有车次、始发站、终点站、发车时间、到站时间、票价二

5、查询包括：由车次，起点站和终点站的分别查询三 排序:：由票价排序【设计分析】头文件：#include<stdio.h>#include<malloc.h>#define MAX 100#define N 50 typedef struct time /时间类型 int x,y,z; /分别对应年，月，日TIME; typedef struct cnode /票信息类型 int no; /票号 int id; /购票人证件号 TIME date; /购票日期 struct cnode *next;CNODE; typedef struct tnode /车次信息类型 ch

6、ar data; /车次编号 struct tnode *lchild,*rchild; CNODE *head;TNODE; void create(); /按车次建立二叉排序树void insert(int ); /增加新的车次（二叉排序树的插入）void del(); /取消车次（二叉排序树节点删除）void inorder(TNODE *); /中序遍历车次二叉排序树（仅显示车次信息）void inorder_all(TNODE *); /中序遍历车次二叉排序树（显示车次及售票信息）void preorder(TNODE *); /先序遍历车次二叉排序树（仅显示车次信息）TNODE *

7、search(); /按车次编号搜索CNODE *insert_c(CNODE *); /插入新的售票信息（单张）CNODE *insert_c_more(CNODE *); /插入新的售票信息（批量）CNODE *del_c(CNODE *,CNODE *); /退票处理（删除售票信息）CNODE *search_c(CNODE *,int); /按票号查询void search_c_id(CNODE *,int); /按购票人证件号搜索（限定某车次）void search_c_id_all(TNODE *,int); /按购票人证件号搜索（所有车次）void search_date(CNO

8、DE *,TIME); /按购票日期搜索（限定某车次）void search_date_all(TNODE *,TIME); /按购票日期搜索（所有车次）void print_c(CNODE *); /输出售票纪录（单张）void print_c_all(CNODE *); /输出售票纪录（批量） TNODE *root=NULL; void main() int i,func,no,ok; TNODE *t; CNODE *c; TIME d; printf("nnn"); for(i=0;i<15;i+) printf("="); printf

9、("列车售票信息管理系统"); for(i=0;i<15;i+) printf("="); printf("n"); printf("t1.车次信息管理n"); printf("t2.售票记录管理n"); printf("t3.售票记录查询n"); printf("t4.售票记录一览n"); printf("t5.退出系统n"); for(i=0;i<N;i+) printf("="); printf(&

10、quot;n请选择您所需要的功能:"); fflush(stdin); scanf("%d",&func); switch(func) case 1: printf("nn车次信息管理>>>>n"); for(i=0;i<N;i+) printf("="); printf("nt1.增加新的车次"); printf("nt2.取消车次"); printf("nt3.返回上级菜单n"); for(i=0;i<N;i+) pr

11、intf("="); printf("n请选择您所需要的功能:"); fflush(stdin); scanf("%d",&func); switch(func) case 1: create(); printf("n售票信息更新成功!nn"); break; case 2:del();break; case 3:main();break; default:printf("n错误功能号输入有误!请重新输入!"); break; case 2: printf("nn售票记录管理&

12、gt;>>>n"); for(i=0;i<N;i+) printf("="); printf("nt1.增加新的售票记录"); printf("nt2.退票"); printf("nt3.返回上级菜单n"); for(i=0;i<N;i+) printf("="); printf("n请选择您所需要的功能:"); fflush(stdin); scanf("%d",&func); switch(func) c

13、ase 1: t=search(); if(t!=NULL) t->head=insert_c_more(t->head); break; case 2: t=search(); printf("需要退票的票号:"); scanf("%d",&no); t->head=del_c(t->head,search_c(t->head,no); break; case 3:main();break; default:printf("n错误功能号输入有误!请重新输入!"); break; case 3:

14、printf("nn售票记录查询>>>>n"); for(i=0;i<N;i+) printf("="); printf("nt1.按票号搜索"); printf("nt2.按购票者证件号搜索"); printf("nt3.按购票日期搜索"); printf("nt4.返回上级菜单n"); for(i=0;i<N;i+) printf("="); printf("n请选择您所需要的功能:"); ffl

15、ush(stdin); scanf("%d",&func); switch(func) case 1: t=search(); if(t!=NULL) printf("n请输入您所要查询的票号:"); scanf("%d",&no); c=search_c(t->head,no); if(c=NULL) printf("错误没有该票号的纪录!该票还未售出或为废票!自动返回上级菜单n."); break; case 2: printf("n请输入您所要查询的购票者证件号:")

16、; scanf("%d",&no); search_c_id_all(root,no); printf("搜索完毕!自动返回上级菜单n."); break; case 3: do printf("n请输入您所要查询的日期(格式: yy-mm-dd):"); scanf("%d-%d-%d",&d.x,&d.y,&d.z); if(d.y<13&&d.y>0) if(d.y=1|d.y=3|d.y=5|d.y=7|d.y=8|d.y=10|d.y=12) i

17、f(d.z<32&&d.z>0) ok=1; else if(d.z=2) if(d.z<30&&d.z>0) ok=1; else if(d.z<31&&d.z>0) ok=1; else ok=0; if(!ok) printf("n错误日期输入有误!请重新输入!"); while(!ok); printf("n指定车次吗?(1->是,0->否):"); scanf("%d",&ok); if(ok) search_date(s

18、earch()->head,d); else search_date_all(root,d); break; case 4:main();break; default:printf("n错误功能号输入有误!自动返回上级菜单n."); break; case 4: printf("nn售票记录一览>>>>n"); for(i=0;i<N;i+) printf("="); printf("nt1.仅浏览车次"); printf("nt2.指定车次已售票记录");

19、printf("nt3.所有车次已售票记录"); printf("nt4.测试：先序遍历车次"); printf("nt5.返回上级菜单n"); for(i=0;i<N;i+) printf("="); printf("n请选择您所需要的功能:"); fflush(stdin); scanf("%d",&func); switch(func) case 1: printf("n+仅浏览车次n"); if(root=NULL) printf(&

20、quot;错误无车次纪录!"); elseinorder(root);printf("n"); break; case 2: printf("n+指定车次已售票记录n"); t=search(); if(t!=NULL) print_c_all(t->head); printf("n"); break; case 3: printf("n+所有车次已售票记录n"); if(root=NULL) printf("错误无车次纪录!"); elseinorder_all(root);p

21、rintf("n"); break; case 4: printf("n+测试：先序遍历车次n"); if(root=NULL) printf("错误无车次纪录!"); elsepreorder(root);printf("n"); break; case 5:main();break; default:printf("n错误功能号输入有误!自动返回上级菜单n."); break; default:printf("n错误功能号输入有误!请重新输入!"); main(); vo

22、id inorder_all(TNODE *ptr)if(ptr!=NULL) inorder_all(ptr->lchild); printf("%d:n",ptr->data); print_c_all(ptr->head); printf("n"); inorder_all(ptr->rchild); void inorder(TNODE *ptr)if(ptr!=NULL) inorder(ptr->lchild); printf("%dt",ptr->data); inorder(ptr-

23、>rchild); void preorder(TNODE *ptr)if(ptr!=NULL) printf("%dt ",ptr->data); preorder(ptr->lchild); preorder(ptr->rchild); void print_c(CNODE *tkt) if(tkt!=NULL) printf("t%dt%dt%d-%d-%dn",tkt->no,tkt->id,tkt->date.x,tkt->date.y,tkt->date.z); void print_c_

24、all(CNODE *head) int i=0,j=0; if(head=NULL)printf("n记录为空!n");return; for(i=0;i<N;i+) printf("="); printf("nNOt票号t购票者证件号t购票日期(年-月-日)n"); for(i=0;i<N;i+) printf("-"); for(j=0;head!=NULL;j+) printf("n%d",j); print_c(head); head=head->next; prin

25、tf("n"); for(i=0;i<N;i+) printf("-"); printf("n总计 %d 条记录n",j); for(i=0;i<N;i+) printf("="); printf("n"); void create()int n,i;int kMAX;printf("n您所希望增加车次的数量:");scanf("%d",&n);for(i=0;i<n;i+) printf("新增第%d列车次:"

26、;,i+1); scanf("%d",&ki);for(i=0;i<n;i+) insert(ki); void insert(int m)TNODE *p1,*p2;if(root=NULL) root=(TNODE *)malloc(sizeof(TNODE); root->data=m; root->lchild=root->rchild=NULL; root->head=NULL; else p1=root; while(m!=p1->data) if(m<p1->data)&&(p1->

27、lchild!=NULL) p1=p1->lchild; else if(m>p1->data)&&(p1->rchild!=NULL) p1=p1->rchild; else if(m<p1->data)&&(p1->lchild=NULL) p2=(TNODE *)malloc(sizeof(TNODE); p2->data=m; p2->lchild=p2->rchild=NULL; p2->head=NULL; p1->lchild=p2; return; else if(m&

28、gt;p1->data)&&(p1->rchild=NULL) p2=(TNODE *)malloc(sizeof(TNODE); p2->data=m; p2->lchild=p2->rchild=NULL; p2->head=NULL; p1->rchild=p2; return; printf("n错误未能成功增加车次%d,车次号 %d 已存在!",m,m); TNODE *search() int key; TNODE *p; p=root; printf("n输入您所要查找的车次编号:"

29、); scanf("%d",&key); while(p!=NULL&&p->data!=key) if(key<p->data)p=p->lchild; else if(key>p->data)p=p->rchild; if(p=NULL) printf("n该车次不存在!"); return(p); void del() int key; TNODE *p1,*p2,*p3,*temp; p1=p2=root; p3=temp=NULL; printf("n请输入您想要取消的

30、车次编号："); scanf("%d",&key); while(p2!=NULL&&p2->data!=key) if(key<p2->data)p1=p2;p2=p2->lchild; else if(key>p2->data)p1=p2;p2=p1->rchild; if(p2=NULL)printf("n错误该车次不存在!返回上级菜单n.");return; else if(p2->lchild=NULL&&p2->rchild=NULL) i

31、f(p1->lchild=p2) p1->lchild=NULL; if(p1->rchild=p2) p1->rchild=NULL; temp=p2; if(root=p2) temp=root;root=NULL; else if(p2->rchild=NULL) temp=p2->lchild; p2->data=temp->data; p2->lchild=temp->lchild; p2->rchild=temp->rchild; else if(p2->lchild=NULL) temp=p2->

32、rchild; p2->data=temp->data; p2->lchild=temp->lchild; p2->rchild=temp->rchild; else p3=p2; temp=p2->lchild; while(temp->rchild!=NULL)p3=temp;temp=temp->rchild; p2->data=temp->data; if(p3=p2) p3->lchild=temp->lchild; else p3->rchild=temp->lchild; free(temp

33、); printf("车次 %d 已取消!nn",key); CNODE *insert_c(CNODE *head) CNODE *k,*p; k=(CNODE *)malloc(sizeof(CNODE); do printf("n车票编号:"); scanf("%d",&k->no); p=search_c(head,k->no); if(p!=NULL) printf("n错误该票已被购买!请重新选择!n"); while(p!=NULL); printf("购票者证件号:&q

34、uot;); scanf("%d",&k->id); printf("购票日期(格式:yy-mm-dd):"); scanf("%d-%d-%d",&k->date.x,&k->date.y,&k->date.z); k->next=head; head=k; return(head); CNODE *insert_c_more(CNODE *head) int n,i; printf("n请输入批量新增售票记录数:"); fflush(stdin);

35、scanf("%d",&n); for(i=0;i<n;i+) head=insert_c(head); printf("n售票记录更新成功!n"); return(head); CNODE *search_c(CNODE *head,int id) CNODE *temp,*s; s=temp=head; while(temp!=NULL&&temp->id!=id)s=temp;temp=temp->next; print_c(temp); if(temp!=NULL) return(s); else ret

36、urn NULL; void search_c_id(CNODE *head,int id) CNODE *s,*head_s; s=head_s=NULL; if(head=NULL) printf("无该证件号纪录!n"); while(head!=NULL) if(head->id=id) s=(CNODE *)malloc(sizeof(CNODE); s->no=head->no;s->id=head->id;s->date=head->date; s->next=head_s;head_s=s; head=head

37、->next; print_c_all(head_s); printf("n"); void search_c_id_all(TNODE *ptr,int id) if(ptr!=NULL) search_c_id_all(ptr->lchild,id); printf("n车次:%dn",ptr->data); search_c_id(ptr->head,id); search_c_id_all(ptr->rchild,id); void search_date(CNODE *head,TIME t) CNODE *s,*

38、head_s; s=head_s=NULL; while(head!=NULL) if(t.x=head->date.x) if(t.y=head->date.y) if(t.z=head->date.z) s=(CNODE *)malloc(sizeof(CNODE); s->no=head->no;s->id=head->id;s->date=head->date; s->next=head_s;head_s=s; head=head->next; print_c_all(head_s); printf("n&qu

39、ot;); void search_date_all(TNODE *ptr,TIME t) if(ptr!=NULL) search_date_all(ptr->lchild,t); printf("n车次:%dn",ptr->data); search_date(ptr->head,t); search_date_all(ptr->rchild,t); CNODE *del_c(CNODE *head,CNODE *p) CNODE *temp; if(p=NULL) printf("错误该票未售出或为废票!返回上级菜单n.")

40、; else if(p=head)head=NULL;free(p); else temp=p->next; p->next=temp->next; free(temp); return(head);题目二 地铁建设问题城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。（1）使用恰当的数据结构存储辖区名称和距离信息。（2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线。（3）输出应该建设的路线，以及所需建设的总里程信息。【需求分析】根据题目要求可知，本设计需要运用

41、图，邻接矩阵，最小树等知识要求：能连通所有城市选择最小路径，即建立最小树；输出最终路径和。【设计分析】头文件#include<iostream>#include<string>using namespace std;#define MAX_VERTEX_NUM 20typedef char VERTYPE;数据定义：typedef struct VERTYPE vexsMAX_VERTEX_NUM; /顶点向量 int visitedMAX_VERTEX_NUM; double arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵 int ve

42、xnum,arcnum; /图的当前顶点数和边数string nameMAX_VERTEX_NUM; mgraph,* MGraph;【编码调试】void init_mgraph(MGraph &g)； /初始化图 for( i=0;i<MAX_VERTEX_NUM;i+) g->vexsi=0; for(i=0;i<MAX_VERTEX_NUM;i+) g->visitedi=0; for(i=0;i<MAX_VERTEX_NUM;i+) for(int j=0;j<MAX_VERTEX_NUM;j+) g->arcsij=0;void ad

43、d_vexs(MGraph &g) ； /增加顶点 for(int i=0;i<g->vexnum;i+) cout<<"请依次输入顶点的代号和名称："<<endl; cin>>g->vexsi>>g->namei; void add_arcs(MGraph &g)； /增加边 for(int i=0;i<g->arcnum;i+) cout<<"请输入边连接的顶点："<<endl; cin>>ch1>>ch2; for(int j=0;j<g->vexnum;j+) if(g->vexsj=ch1) row=j; if(