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

计算机科学与技术学院课程设计成绩单

课程名称：数据结构 指导教师：
姓名

性别
男
学号

班级

综合成绩

成绩等级

程序运行情况
（占总成绩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
#include
#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");
for(i=0;intf("\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;it!=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");
for(i=0;i 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;intf("\n\t2.指定车次已售票记录");
printf("\n\t3.所有车次已售票记录");
printf("\n\t4.测试：先序遍历车次");
printf("\n\t5.返回上级菜单\n");
for(i=0;i
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 for(i=0;inext;
}
printf("\n");
for(i=0;icreate()
{
int n,i;
int k[MAX];
printf("\n您所希望增加车次的数量:");
scanf("%d",&n);
for(i=0;iot->data=m;
root->lchild=root->rchild=NULL;
root->head=NULL;
}
else
{
p1=root;
while(m!=p1->data)
{
if((mdata)&&(p1->lchild!=NULL)) p1=p1->lchild;
else if((m>p1->data)&&(p1->rchild!=NULL)) p1=p1->rchild;
else if((mdata)&&(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(keydata){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(keydata){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;iid!=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);
}

题目二 地铁建设问题
城市要在各个辖区之间修建地铁来加快