资源描述
计算机科学与技术学院课程设计成绩单
课程名称:数据结构 指导教师:
姓名
性别
男
学号
班级
综合成绩
成绩等级
程序运行情况
(占总成绩20%)
□能正确运行 □基本能正确运行 □能运行但结果不完善
(20分) (15分) (10分)
程序功能的完善程度
(占总成绩10%)
□完善 □基本完善 □不完善
(10分) (8分) (5分)
程序结构的合理性
(占总成绩10%)
□合理 □基本合理 □不太合理
(10分) (8分) (5分)
对问题的答辩情况
(占总成绩40%)
□概念正确有创新 □能正确回答所有问题 □基本能正确回答
(40分) (35分) (30分)
□部分问题回答概念不清晰
(20分)
学生的工作态度与独立工作能力
(占总成绩10%)
□工作态度认真能独立完成任务 □工作态度认真但独立性较差
(10分) (8分)
□工作态度基本认真但缺乏独立性
(5分)
设计报告的规范性
(占总成绩10%)
□符合规范 □基本符合规范 □规范性较差
(10分) (8分) (5分)
优秀:90分~100分 良好:80分~89分 中等:70~79分 及格:60~69分 不及格0分~59分
计算机科学与技术学院
课 程 设 计 报 告
课程名称: 数 据 结 构
专 业: 计算机科学与技术
班 级:
学 号:
姓 名:
指导老师:
【设计目的】
数据结构是计算机专业的核心课程,是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段,要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C(C++)程序并上机调试的基本方法,还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节,对于学生基本程序设计素养的培养和软件工作者工作作风的训练,将起到显著的促进作用,学以至用,才能真正的培养学生的能力。
【设计要求】
1、课程设计题目共两题,每个学生必须独立完成;
2、课程设计时间为1.5周;
3、设计语言C(C++)不限;
4、课余时间完成源程序和课程设计报告等文档书写工作,上机时间只能做调试工作。上机时带上源程序、数据结构教材、C语言教材。
题目一 火车票务系统的设计与实现
设计一个火车票务系统,并完成如下功能:
列车记录包含6项:车次、始发站、终点站、发车时间、到站时间、票价
Z38、 武昌、 北京西、21:06 、07:01 、272
(1)列车信息录入:输入列车基本信息。
(2)列车信息删除:删除车次信息。(列车线路停运)
(3)列车信息修改:删除车次信息。(列车时间、票价等信息有变动)
(4)列车信息输出:根据格式对齐输出列车信息。
(5)列车信息查询:可根据车次号、始发站、终点站查询满足条件的列车信息。
(6)列车信息排序:可根据票价对列车信息进行排序并输出。
【需求分析】
一 根据题目要求系统主界面应有以下几个功能:
1录入信息
2 显示信息
3 查询信息
4 增加信息
5 修改信息
6 删除信息
7排序
对于各种有关信息操作,必须包括有车次、始发站、终点站、发车时间、到站时间、票价
二 查询包括:由车次,起点站和终点站的分别查询
三 排序::由票价排序
【设计分析】
头文件:
#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 //车次信息类型
{
char 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 *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(CNODE *,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("\n\n\n");
for(i=0;i<15;i++) printf("=");
printf("列车售票信息管理系统");
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("\n请选择您所需要的功能:");
fflush(stdin);
scanf("%d",&func);
switch(func){
case 1:
printf("\n\n车次信息管理>>>>\n");
for(i=0;i<N;i++) printf("=");
printf("\n\t1.增加新的车次");
printf("\n\t2.取消车次");
printf("\n\t3.返回上级菜单\n");
for(i=0;i<N;i++) printf("=");
printf("\n请选择您所需要的功能:");
fflush(stdin);
scanf("%d",&func);
switch(func){
case 1:
create();
printf("\n售票信息更新成功!\n\n");
break;
case 2:del();break;
case 3:main();break;
default:printf("\n[错误]功能号输入有误!请重新输入!");
}
break;
case 2:
printf("\n\n售票记录管理>>>>\n");
for(i=0;i<N;i++) printf("=");
printf("\n\t1.增加新的售票记录");
printf("\n\t2.退票");
printf("\n\t3.返回上级菜单\n");
for(i=0;i<N;i++) printf("=");
printf("\n请选择您所需要的功能:");
fflush(stdin);
scanf("%d",&func);
switch(func){
case 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:
printf("\n\n售票记录查询>>>>\n");
for(i=0;i<N;i++) printf("=");
printf("\n\t1.按票号搜索");
printf("\n\t2.按购票者证件号搜索");
printf("\n\t3.按购票日期搜索");
printf("\n\t4.返回上级菜单\n");
for(i=0;i<N;i++) printf("=");
printf("\n请选择您所需要的功能:");
fflush(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请输入您所要查询的购票者证件号:");
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)
if(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(search()->head,d);
else search_date_all(root,d);
break;
case 4:main();break;
default:printf("\n[错误]功能号输入有误!自动返回上级菜单\n...");
}
break;
case 4:
printf("\n\n售票记录一览>>>>\n");
for(i=0;i<N;i++) printf("=");
printf("\n\t1.仅浏览车次");
printf("\n\t2.指定车次已售票记录");
printf("\n\t3.所有车次已售票记录");
printf("\n\t4.测试:先序遍历车次");
printf("\n\t5.返回上级菜单\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("[错误]无车次纪录!");
else{inorder(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("[错误]无车次纪录!");
else{inorder_all(root);printf("\n");}
break;
case 4:
printf("\n+++测试:先序遍历车次\n");
if(root==NULL) printf("[错误]无车次纪录!");
else{preorder(root);printf("\n");}
break;
case 5:main();break;
default:printf("\n[错误]功能号输入有误!自动返回上级菜单\n...");
}
break;
default:printf("\n[错误]功能号输入有误!请重新输入!");
}
main();
}
void 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("%d\t",ptr->data);
inorder(ptr->rchild);
}
}
void preorder(TNODE *ptr)
{
if(ptr!=NULL)
{
printf("%d\t ",ptr->data);
preorder(ptr->lchild);
preorder(ptr->rchild);
}
}
void print_c(CNODE *tkt){
if(tkt!=NULL) printf("\t%d\t%d\t%d-%d-%d\n",tkt->no,tkt->id,tkt->date.x,tkt->date.y,tkt->date.z);
}
void print_c_all(CNODE *head){
int i=0,j=0;
if(head==NULL){printf("\n记录为空!\n");return;}
for(i=0;i<N;i++) printf("=");
printf("\nNO\t票号\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;
}
printf("\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 k[MAX];
printf("\n您所希望增加车次的数量:");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("新增第%d列车次:",i+1);
scanf("%d",&k[i]);
}
for(i=0;i<n;i++)
insert(k[i]);
}
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->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>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输入您所要查找的车次编号:");
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请输入您想要取消的车次编号:");
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)
{
if(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->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);
printf("车次 %d 已取消!\n\n",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("购票者证件号:");
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);
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 return 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->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车次:%d\n",ptr->data);
search_c_id(ptr->head,id);
search_c_id_all(ptr->rchild,id);
}
}
void search_date(CNODE *head,TIME t){
CNODE *s,*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");
}
void search_date_all(TNODE *ptr,TIME t){
if(ptr!=NULL){
search_date_all(ptr->lchild,t);
printf("\n车次:%d\n",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...");
else if(p==head){head=NULL;free(p);}
else{
temp=p->next;
p->next=temp->next;
free(temp);
}
return(head);
}
题目二 地铁建设问题
城市要在各个辖区之间修建地铁来加快
展开阅读全文