综合实践1数据结构与算法分析Word下载.docx
- 文档编号:1250057
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:21
- 大小:69.95KB
综合实践1数据结构与算法分析Word下载.docx
《综合实践1数据结构与算法分析Word下载.docx》由会员分享,可在线阅读,更多相关《综合实践1数据结构与算法分析Word下载.docx(21页珍藏版)》请在冰点文库上搜索。
指导教师(签字):
注:
介于A和C之间为B级,低于C为D级和E级。
按各项指标打分后,总分在90~100为优,80~89为良,70~79为中,60~69为及格,60分以下为不及格。
航班信息的查询与检索系统设计说明
1、问题描述与分析
排序和查找是数据信息处理中使用频度极高的操作。
为了加快查找的速度,需要先对数据记录按关键字排序。
当今乘飞机旅行的人越来越多,人们需要关心了解各类航班的班次、时间、价格及机型等信息。
在这个飞机航班数据的信息模型中,航班号是关键字,而且是具有结构特点的一类关键字。
因为航班号是字母数字混编的,例如:
CZ1234,这种记录集合是一个适合于多关键字排序的例子。
2、数据结构设计和基本算法设计方法的选择
该设计要求对飞机航班信息进行排序和查找。
可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。
对于本设计,可采用基数排序法对一组具有结构特点的飞机班号进行排序,利用二分查找法对排好序的航班记录按航班号实现快速查找,按其他关键字的查找可采用最简单的顺序查找方法进行,因为它们用的较少。
每个航班记录包括8项,分别是:
航班号、起点站、到达站、班期、起飞时间、到达时间、飞机型号以及票价等,本设计储存的航班信息如下:
航班号
起点站
终点站
班期
起飞时间
到达时间
机型
票价
CA1544
合肥
北京
1.2.4.5
1055
1240
733
960
MU5341
上海
广州
每日
1420
1615
M90
1280
CZ3869
重庆
深圳
2.4.6
0855
1035
1010
MU3682
桂林
南京
2.3.4.6.7
2050
2215
1380
HU1836
0940
1120
738
1250
CZ3528
成都
厦门
1.3.4.5.7
1510
1650
CRJ
1060
MU4594
昆明
西安
1.3.5.6
1015
1140
328
1160
SC7425
青岛
海口
1.3.6
1920
2120
DH4
1630
其中航班号一项的格式为:
k0k1k2k3k4k5
Z
3
8
6
9
其中k0和k1的输入值是航空公司的别称,用两个大写字母表示,后4位为航班编号,这种航班号关键字可分成两段,即字母和数字。
其余七项输入内容因为不涉及本设计的核心,因此除了票价为数值型外,均为字符串即可。
3、软件结构设计
图3-1结构框图
4、算法设计
源程序:
#include<
iostream.h>
string.h>
stdio.h>
#defineN8//航班数
//航班信息
typedefstructflight
{
charflight_number[10];
//航班号
charstart_address[10];
//起飞站
chararrived_address[10];
//终点站
charwork_date[10];
//班期
intstart_time;
//起飞时间
intarrived_time;
//到达时间
charFlightType[4];
//机型
intfare;
//票价
}DataType;
structflightFlight[N];
//———————————按航班号进行基数排序———————————
typedefcharKeyType;
#defineD7//D为排序码的最大位数
#defineR'
a'
//R为基数,这里为小于字母'
代表的整型值
structNode;
//单链表结点类型
typedefstructNodeRadixNode;
structNode
{
KeyTypekey[D];
//关键字
DataTypeinfo;
//数据信息
RadixNode*next;
};
typedefRadixNode*RadixList;
typedefstructQueueNode
RadixNode*f;
//对列的头指针
RadixNode*e;
//对列的尾指针
}Queue;
Queuequeue[R];
voidradixSort(RadixList*plist,intd,intr)
inti,j,k;
RadixNode*p,*head;
head=(*plist)->
next;
for(j=d-1;
j>
=0;
j--)//进行d次分配和收集
{
p=head;
for(i=0;
i<
r;
i++)
{
queue[i].f=NULL;
queue[i].e=NULL;
//清队列
}
while(p!
=NULL)
k=p->
key[j];
//按排序码的第j个分量进行分配
if(queue[k].f==NULL)queue[k].f=p;
//若第k个堆为空,则当前记录为队头
else(queue[k].e)->
next=p;
//否则当前记录链接到第k队的队尾
queue[k].e=p;
p=p->
i=0;
while(queue[i].f==NULL)i++;
//从r个队列中找出第一个非空的队列
p=queue[i].e;
head=queue[i].f;
//head为收集链表的头指针
for(i++;
if(queue[i].f!
{p->
next=queue[i].f;
}//收集非空队列
p->
next=NULL;
(*plist)->
next=head;
}
//初始化航班信息
structNodeelement[N+1]={
"
"
0,0,"
0,NULL,//表头
CA1544"
合肥"
北京"
1245"
1055,1240,"
733"
960,NULL,
MU5341"
上海"
广州"
每日"
1420,1615,"
M90"
1280,NULL,
CZ3869"
重庆"
深圳"
246"
855,1035,"
1010,NULL,
MU3682"
桂林"
南京"
23467"
2050,2215,"
1380,NULL,
HU1836"
940,1120,"
738"
1250,NULL,
CZ3528"
成都"
厦门"
13457"
1510,1650,"
CRJ"
1060,NULL,
MU4594"
MU4594"
昆明"
西安"
1356"
1015,1014,"
328"
1160,NULL,
SC7425"
SC7425"
青岛"
海口"
136"
1920,2120,"
DH4"
1630,NULL,
//————————————信息显示————————————
//按表的格式输出某个航班信息
//显示头部信息
voidCout_info1()
cout<
<
"
****************************************\n"
endl;
*航班信息表*\n"
航班号起飞时间到达时间起飞站终点站班期机型票价\n"
//显示主体信息
voidCout_info2_1(Nodep[])//方式一
p->
info.flight_number;
info.start_time;
info.arrived_time;
info.start_address;
info.arrived_address;
info.work_date;
info.FlightType;
info.fare<
元"
voidCout_info2_2(flightF[],inti)//方式二
F[i].flight_number;
F[i].start_time;
F[i].arrived_time;
F[i].start_address;
F[i].arrived_address;
F[i].work_date;
F[i].FlightType;
F[i].fare<
//显示所有航班信息
voidoutput_ALL_info1(Nodeelement[])//方式一
RadixListp=element;
Cout_info1();
Cout_info2_1(p);
voidoutput_ALL_info2(flightF[])//方式二
for(inti=0;
i<
N;
i++)
Cout_info2_2(F,i);
//——————————————信息复制————————————————
//将排好的序列(链表)转化成顺序表存储形式
voidcopy(flightF[],Nodeelement[])
inti;
N&
&
p!
=NULL;
i++)
strcpy(F[i].flight_number,p->
info.flight_number);
F[i].start_time=p->
F[i].arrived_time=p->
strcpy(F[i].start_address,p->
info.start_address);
strcpy(F[i].arrived_address,p->
info.arrived_address);
strcpy(F[i].work_date,p->
info.work_date);
strcpy(F[i].FlightType,p->
info.FlightType);
F[i].fare=p->
info.fare;
//———————————————服务菜单——————————————
voidF_By_Time(flightF[],int);
voidF_By_Address(flightF[],int);
voidF_By_fare(flightF[]);
voidF_By_FN(flightF[]);
//主菜单
voidmainmenu()
charch;
inty;
主菜单\n"
===========================================================\n"
Pleasechoose:
(inputthenumber)(输入查询/排序命令)\n"
0.showthemainmenu(显示主菜单)\n"
1.Findbyflightnumber(按航班号查询)\n"
2.Findbystarttime(按起飞时间查询)\n"
3.Findbyarrivedtime(按到达时间查询)\n"
4.Findbystartaddress(按起飞地点查询)\n"
5.Findbyarrivedaddress(按目的地点查询)\n"
6.Findbythefare(按票价范围查询)\n"
----其他键退出"
while
(1)
请输入服务命令:
;
cin>
>
y;
switch(y)
case0:
mainmenu();
break;
case1:
F_By_FN(Flight);
case2:
F_By_Time(Flight,1);
case3:
F_By_Time(Flight,2);
case4:
F_By_Address(Flight,1);
case5:
F_By_Address(Flight,2);
case6:
F_By_fare(Flight);
default:
cout<
谢谢惠顾!
是否退出?
(Y/N):
ch;
if(ch=='
Y'
||ch=='
y'
)break;
//——————————————查询系统——————————————
//通过航班号实现二分查找法查找
voidF_By_FN(flightF[])
intlow=0,high=N,mid;
charNum[10];
请输入您要查询的航班号:
Num;
while(low<
=high)
mid=(low+high)/2;
if(strcmp(Num,F[mid].flight_number)==0){Cout_info2_2(F,mid);
elseif(strcmp(Num,F[mid].flight_number)<
0)high=mid-1;
elselow=mid+1;
//通过起飞/到达时间查询
voidF_By_Time(flightF[],intTime)
intT,i;
请输入您要查询的航班的起飞/抵达时间(eg:
16:
45showas1645):
T;
if(Time==1)//按起飞时间查询
if(T==F[i].start_time)Cout_info2_2(F,i);
if(Time==2)//按抵达时间查询
if(T==F[i].arrived_time)Cout_info2_2(F,i);
}
//通过站点查询
voidF_By_Address(flightF[],intAD)
charstr[10];
请输入您要查询的航班的起飞/抵达地址:
str;
if(AD==1)//按起点站查询
if(strcmp(str,F[i].start_address)==0)Cout_info2_2(F,i);
if(AD==2)//按目的站查询
if(strcmp(str,F[i].arrived_address)==0)Cout_info2_2(F,i);
//通过票价范围查询
voidF_By_fare(flightF[])
intT1,T2,i;
请输入您要查询的航班的最低票价(单位:
元):
T1;
请输入您要查询的航班的最高票价(单位:
T2;
if(T1<
=F[i].fare&
T2>
=F[i].fare)Cout_info2_2(F,i);
//——————————————主函数————————————————
intmain()
element[i].next=&
element[i+1];
element[10].next=NULL;
radixSort(&
p,D,R);
//基数排序
output_ALL_info1(element);
//输出排序后的有序序列(航班信息)
copy(Flight,element);
//另存储排序后的航班信息
//给出主菜单
return0;
Radixsort函数
Copy函数
Mainmenu函数
5.调试分析
1.主菜单程序
2.按航班号查询
3.按起飞时间查询
4.按到达时间查询
5.按目的地查询
6.按票价范围
有关于时间和空间复杂度的分析
因为本设计采用的是基数排序算法,时间复杂度的任何情况都为O(d*n),空间复杂度为O(n).
6、综合实践总结
1.综合实践过程的收获.
通过本次综合实践,让我更好的了解和认识了C语言和C++,经过自己编程的锻炼让我巩固了自己在C语言和C++方面的基础知识,现将本次综合实践过程中的学习收获总结如下:
数据说明次序应当规范化,使数据属性容易查找,也有利于测试、排错和维护。
说明的先后次序应固定,应按逻辑功能排序,逻辑功能块内建议采用下列顺序:
整型说明、实型说明、字符说明、逻辑量说明。
如果设计了一个复杂的数据结构,应当通过注释对其变量的含义、用途进行说明。
程序注释是程序员与日后的程序读者之间通信的重要手段之一,注释分为文件注释、函数注释和功能注释。
正规程序的注释应注意:
注释行的数量占到整个源程序的1/3到1/2。
文件注释位于整个源程序的最开始部分,注释后空两行开始程序正文。
它包括:
程序标题。
目的、功能说明。
文件作者、最后修改日期等说明。
函数注释通常置于每函数或过程的开头部分,它应当给出函数或过程的整体说明对于理解程序本身具有引导作用。
功能性注释嵌在源程序体中,用于描述其后的语句或程序段做什么工作,也就是解释下面要做什么,或是执行了下面的语句会怎么样。
而不要解释下面怎么做,因为解释怎么做常常与程序本身是重复的。
2.遇到问题以及解决问题的思路和方法
在编程中,经常会因为一些小毛病导致程序无法调试通过,总结一下经验,还是主要因为自己平时马虎,缺少编程经验造成的,下面总结几个自己在编程中出现的错误和解决的经验:
(1)if语句对出错的处理:
If语句是我最喜欢用的用语句,因为它简单、直观,只有两种选择,但就是这样简单的语句,在本次编程中,让我感觉到它的深奥。
当我们遇到if语句出错的时候,首先先检测输入量的合法性,然后再正常处理。
这样做的好处是突出了错误的条件,让别人在使用你的函数的时候,第一眼就能看到不合法的条件,于是就会更下意识的避免。
另外还要注意——不要使用空的ifelse语句。
如
if(cMychar>
=‘A’)
if(cMychar<
=‘Z’)
printf(“Thisisaletter”);
else
printf(“Thisisnotaletter”);
else到底是否定哪个if容易引起误解。
可通过加{}避免误解。
——尽量减少使用“否定”条件的条件语句。
如:
把if(!
((cMychar<
’0’)||(cMychar>
’9’)))
改为if((cMychar>
=’0’)&
(cMychar
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 综合 实践 数据结构 算法 分析