数据结构课程设计新版

数据结构课程设计新版（共6篇）

1.数据结构课程设计新版 篇一

第五单元 数据处理

课题:扇形统计图

学情分析：学生之前已经认识了条形统计图和折线统计图，能够利用这些统计图表示数据及变化态势；初步了解了平均数的意义，会求一组数据的平均数，能够应用平均数对数据进行分析、比较。教学目标：

1、通过实例，认识扇形统计图，了解扇形统计图的特点与作用。

2、能读懂扇形统计图，从中获得有效的信息，体会统计在现实生活中的作用。

3、让学生体会统计在现实生活中的作用，渗透健康饮食的教育。教学重点难点：了解扇形统计图的特点与作用。教学方法：自主探究、合作交流、教师引导 教学准备：各种扇形统计图、多媒体课件。教学过程：

一、导入新课。

谁知道我们以前学过哪些统计图？并且说出它们的特点？ 那么，我们今天学习新的一种统计图《扇形统计图》。

二、教学扇形统计图的特点

1、用投影仪出示笑笑一家三口一天各类食物的摄入量统计表。

2、先让学生通过计算独立填上表中的数据。

3、独立制作条形统计图。

4、出示扇形统计图。

5、组织学生交流两种统计图，你能从中获得哪些信息。

6、全班交流。

7、教师小结：条形统计图能清楚地看到哪个量多，哪个量少。而扇形统计图反映的是整体和部分的关系。

三、说一说。

用投影仪出示四幅扇形统计图，先让学生每幅图中各百分数的意义。再让学生说一说每幅统计图获得信息。

四、试一试。

1、出示每幅图。

2、交流这三个问题。

3、教师小结。板书设计：

扇形统计图 各占整体的百分之几 整体与部分的关系

教学反思：

课题：统计图的选择

学情分析：本节内容没有新的概念，也没有新的思路，所有学生具备相对独立学习本课知识的能力，可以放手让学生自主学习，再展示交流。教师进行针对性的指导。教学目标：

1、能读懂条形统计图、折线统计图、扇形统计图，从中获取有效信息，体会统计在现实生活中的作用。

2、了解三种统计图的不同特点，能根据需要选择适当的统计图，直观、有效的表示信息。

3、让学生体会统计在现实生活中的作用，愿意合作与交流。教学重难点：了解并会运用三种统计图的特点与作用。教学方法：自主探究、合作交流、教师引导 教学准备：多媒体课件 教学过程：

一、导入新课。

我们前一课认识了扇形统计图，谁能说出它特点？

指名回答。那么这一节课就学习在什么情况下要用什么样的统计图。

二、学习新课。

1、出示我国从第23届奥运会开始获得金牌，第24——30届奥运会我国获奖牌情况统计表。

2、让学生说一说从统计表中获得信息。

3、用投影仪出示折线统计图、条形统计图、扇形统计图。

4、分别提出教材中的三个问题，让学生们交流。

5、教师小结：折线统计图能明显的看出第24——30届奥运会我国获得奖牌数的变化情况，条形统计图能更明显的看出第28届奥运会我国获得的金牌数。扇形统计图能看出第28届奥运会我国奖牌的分布情况。

三、说一说。让学生用自己的话说一说三种统计图的各有什么特点。指名回答。其他同学补充、评议。教师评价。

四、练一练。

在小组内交流分别用哪种统计图合适？并说出自己的理由。

五、实践活动。

交流课前收集到的各种统计图，体会三种统计图的特点和作用。板书设计：

教学反思：

课题：身高的情况

学情分析：分组整理数据对于学生来说有一定难度，以前从未接触过。分类和分组是整理数据的开始，当调查了一大堆原始数据以后，看起来很杂乱，很自然的想法是把它们分开，但学生不容易想到这一点。教学目标：

1、让学生经历统计的过程，使其掌握分段整理数据的方法。

2、在互相合作中找到解决问题的最佳策略。

3、理解统计的实际意义，使学生进一步增强用统计的方法 解决实际问题的意识，发展统计思想，培养学习的兴趣和与人合作的态度。

教学重难点：经历统计的过程，寻求解决问题的策略和策略的比较与选择。教学方法：自主探究、合作交流、教师引导 教学准备：多媒体课件 教学过程：

一、收集数据，导入新课

1、同学们，每周一的升旗仪式我们穿什么（校服）

像我们参加比较重要的会议或者活动时都要穿校服，它是我们学校学生的一个重要标志。

2、今年学校计划为淘气的班级添置一套新校服，做校服需要收集哪些信息？（课件出示）板书

二、合作探究，分段整理

1、从记录单上，你知道了什么？

学生观察记录单，说发现的信息

2、凌乱无序的数据不方便找到我们需要的信息，所以要讲数据进行整理。

3、服装厂按身高5cm一段确定服装型号，我们一起来整理吧（板书：分段整理）

三、制统计图，分析数据

1、根据身高统计表，完成统计图。

2、提问：从这张表上可以知道什么

3、回顾，刚才都干了哪些工作，经历了哪几个流程？

4、找生活中的例子，举例说明它们也用到了“数据的分段整理”

四、综合运用，深化新知。

五、小结 板书设计：

教学反思：

课题：身高的变化

学情分析：平均数是刻画一组数据集中趋势的统计量，学生学习了平均数，会进行计算，但是当遇到真正的数据需要分析时，却很少想到用平均数。因此，要发展学生的数据分析概念，使他们想到数据，能从数据中提取一些信息。教学目标：

1、通过对淘气身高和全市男生平均身高的研究，认识复式折线统计图，了解复式折线统计图的特点。

2、对数据进行简单分析，并能做出合理推测，体会数据的作用。

3、使学生进一步感受到统计带给人们的帮助，从而提高学生参与统计的兴趣。教学重难点：能根据统计图里的信息制作复式折线统计图，并能根据统计图作出合理分析和推测。

教学方法：自主探究、合作交流、教师引导 教学准备：多媒体课件 教学过程：

一、导入新课

1、谈话：昨天老师要求同学们收集自己一到六年级每个学年第一学期期末的身高数据，请大家拿出自己收集的数据，与同学交流。

2、指名交流后，提问：你是怎样收集这些数据的？

3、这节课，我们就共同来研究“身高的变化”

二、探究新知

1、引导：要把几年的身高数据都展示出来，用什么方法比较合适？为什么？

2、提问：能看图说一说自己这几年身高变化的特点吗？

3、提出要求：学生各自按要求完成统计图

4、展示学生作品，提问：图中哪条折线表示的是你的身高变化情况？为了让别人看清楚，应该怎么做？

5、分析数据。

6、预测：你能估计自己三年后的身高吗？

7。讨论：与单式折线统计图相比，你觉得复式折线统计图有什么特点？

三、深化巩固

四、课堂小结

五、课堂延伸 板书设计：

教学反思：

2.数据结构课程设计新版 篇二

《义务教育数学课程标准(2011年版)》中,在数的运算方面,第一学段(1~3年级)的教学目标有:能熟练地口算20以内的加减法和表内乘除法,会口算百以内的加减法,这是整数四则运算的基础。在此基础上,才能进一步学习计算三位数加减法,一位数乘三位数、两位数乘两位数的乘法,三位数除以一位数除法;会计算同分母分数(分母小于10)的加减运算以及一位小数的加减运算。到了第二学段(4~6年级),在数的运算方面又有了更高的要求:会口算百以内一位数乘、除两位数;能笔算三位数乘两位数的乘法,三位数除以两位数的除法;会分别进行简单的整数、小数、分数(不含带分数)四则混合物运算(以两步为主,不超过三步)。

可见,每一学段都有明确的教学目标,小学阶段运算基本要点有:低年级——百以内的加减法,简单的乘除法,侧重儿童的思维特点;中年级———整数与小数的四则运算,侧重算法与算理;高年级———分数的四则运算,侧重问题解决的心理过程。所以说运算贯穿于小学阶段始终。

一、教师要把握儿童学习数学的心理过程

(一)根据儿童学习数学的心理过程,渗透数形结合的思想

儿童学习数学的过程大致是这样的:(1)操作实物,通过自己或者他人对具体实物的玩弄,借助具体的动作直接认识数学对象的初始形态;(2)形象表象,通过脑袋里想动作操作或者画出图像直观形象地认识和理解数学对象。如,我们进行29+8这样的两位数加一位数加法算式,求结果是怎么得出的?对学生提出这样的要求:把你的计算过程摆一摆、画一画、写一写。生1:先给8找伙伴2,再用27+10=37;生2:用摆小棒操作;生3:画图操作,原来2捆+1捆+7根=37根;生4:计数器上十位上是2,个位上是9,在个位上拨8个是17,满十向十位拨1个,个位是7个。

再如,在教学24+196=(),教师可为学生提供操作实物或画图的学习机会,让学生将自己的想法画出来。教师可提示学生将加法竖式与计数器联系起来,竖摆小棒演示出24+196的计算过程:

(二)根据儿童学习数学的心理过程,渗透数学模型思想

儿童学习数学要经历两个过程:(1)抽象符号,利用数学语言(比如文字、算式、符号、公式等),抽象地描述和刻画数学对象和生活事物;(2)逻辑关系,从数学的角度,深层次揭示数学对象背后的含义,将相关对象联系在一起。再如,29+8=(),预设学生有两种方法:A:29+1=30 30+7=37;B:9+8=17 20+17=37。教师需要提问:A与B两种算法哪一种更接近竖式?再如,通过29+8=37可以产生变式:37-8=29,37-29=8或通过算式之间的联系便于学生进行一式四题的运算,从而寻找到简便方法。

二、培养和提高学生运算能力的具体措施

(一)坚持课前三分钟口算训练,提高学生的口算能力

口算是培养学生计算能力的基础,每个学生都应具备较强的口算能力。因此,在数学课堂教学中,我每天利用课前三分钟的时间训练学生的口算能力,有针对性地设计不同类型的口算题目,并将个人表现与小组评价挂钩,学生的积极性很高,口算能力也得到了一定的提升。

(二)笔算是关键,重视提高学生的计算正确率

小学阶段大部分数学题都要求学生通过列竖式的方法进行笔算。究其原因:在计算时,有的学生特别粗心,有的学生容易将运算符号看错,有的学生对于20以内的进、退位加减法不熟、九九乘法口诀表运用不熟,导致学生运算速度慢、正确率低,针对上述情况,教师在进行算理教学时一定要让学生多体验,寻找合适的方法,积累错题,找出错误的原因,提高计算正确率。

(三)增强简算意识,提高计算的灵活性

简算是依据算式、数据的不同特点,利用运算定律、性质及数与数之间的特殊关系,使计算的过程简化、简洁的计算方法。教师要经常带领学生总结一些常用的简便计算方法,并经常组织学生进行不同形式的简算练习,让学生在计算实践中体验简算的意义、作用与必要性,强化学生自觉运用简算方法的意识,提高学生计算的灵活性和正确率。

总之,教师最终的目标是落实培养运算能力,帮助学生理解运算的算理,寻求合理简洁的运算途径解决问题的方法。教学中,师生共同努力才会收到学生运算能力真正提高的效果。

参考文献

[1]曾信民.小学数学计算能力的培养和提高[J].课程教育研究,2016(19).

3.数据结构课程设计报告 篇三

数据结构课程设计报告

课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级

专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师

数据结构课程设计

迷宫

题目一

1.设计内容 1.1问题描述

求迷宫从入口到出口的所有路径。1.2设计要求

1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。

1.3开发环境

Visual C++6.0的集成化环境 1.4研究思路

对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。

经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。

2.设计步骤

2.1 需求分析

（1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和

1-1数据结构课程设计

迷宫

在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。

2.3 详细设计（1）主菜单伪代码：

while(flag1){

}

{shuru();//输入行列数

printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;i<=m;i++)

for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宫输出 churukou();//迷宫出入口的输入 x=Mazepath(mg);// 判断路径函数

数据结构课程设计

迷宫

和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。

（2）算法的时空分析：

由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。

链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。

3.用户使用说明

运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。

图数据结构课程设计

迷宫

图1-2

图1-3 退出

5.总结与心得体会

本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。

{ }

mg[i][j]=1;//初始化

矩阵,将最外围置为1

printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2);

}mlink;mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量

}

void showplay(int mg[][M+2])//迷宫输出

{

n“);

for(i=1;i<=m;i++){

printf(”n“);for(j=1;j<=n;j++)

printf(”%d “,mg[i][j]);

int i,j;

printf(”迷宫矩阵如下(0可通)：printf(“输入行数：n”);scanf(“%d”,&m);printf(“输入列数：n”);scanf(“%d”,&n);数据结构课程设计

迷宫

} } printf(“n迷宫图形如下(白色for(i=1;i<=m;i++){

}

printf(”n“);for(j=1;j<=n;j++){

} if(mg[i][j]==0)printf(”

if(mg[i][j]==1)printf(“

if(mg[stack->row][stack->col+1]==

p->next=stack;

stack=p;{

p=(mlink 可通)：n”);0)//下面位置可通

*)malloc(sizeof(mlink));

p->row=stack->row;p->col=stack->col+1;□“);//为0的输出□ ■”);//为1的输出■

//入栈

mg[stack->row][stack->col]=1;//将

} else

访问过的标记为1 int Mazepath(int mg[][N+2]){

mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p;

//将入口

mg[stack->row][stack->col]=1;/while((!(stack->row==NULL&

if(mg[stack->row][stack->col-1]==0)//上面可通

//入栈

stack=p;

p->next=stack;

{

p=(mlink *)malloc(sizeof(mlink));

*)malloc(sizeof(mlink));

p->row=stack->row;p->col=stack->col-1;放入堆栈 /标志入口已访问

&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口

{

mg[stack->row][stack->col]=1;//将

访问过的标记为1

数据结构课程设计

迷宫

void tonglu()//将坐标的顶点输出 {

始化

printf(“(%d%3d)n”,q->row,q->col);

情况

else printf(“□”);//0的 } q=stack;{

} for(i=0;i

for(j=0;jrow-1][q->col-1] q=q->next;

=

while(q!=NULL)//循环条件 q=q->next;for(j=0;j

情况

}

void create(int mg[][N+2])//创建和菜单

{

int i,j,x,choice,flag1=1;chushi();while(flag1){ }

printf(“n”);printf(“所有通道为（由下而q=stack;{ 上）：n”);while(q!=NULL)//循环条件

printf(“

##

printf(”#

n“);

*********选择菜单**********

#n”);

printf(“

##

printf(”输入选项：“);scanf(”%d“,&choice);switch(choice){ case 1://手动建立迷宫

{

shuru();

printf(”手动建立for(i=1;i<=m;i++)

n“);

printf(”# 1-手动生成迷

宫

2-自动生成迷宫

3-退出

#n“);0;//将路径中的点赋给辅助数组a 形的界面输出

迷宫矩阵(0表示可通1表示障碍):n”);

for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);

数据结构课程设计

航班信息查询与检索系统

题目二

1.设计内容 1.1问题描述

设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。

1.2设计要求

（1）原始信息存储在文件中，记录不少于50条。（2）用户界面至少包括以下功能：  创建

 修改（插入、添加、删除、更新） 查询  浏览  退出管理系统（3）航班信息包括：

 航班号：字符序列，具体字符表达的意思上网查询  起点站和终点站：字符串  班期：指一周中哪些天有航班

 起飞时间：可将时间定义成一个时、分组成的序列  到达时间：可将时间定义成一个时、分组成的序列  机型：字符序列，具体字符表达的意思上网查询  票价：整型数，具体值可上网查询

（4）创建是指从文件中读取数据，并存入所定义的顺序表中。

（5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。

（6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。

（7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。

数据结构课程设计

航班信息查询与检索系统

typedef struct node { Time rh;Time lv;}Pnode;（2）飞机结构体： struct Plane {

};（3）静态链表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 详细设计（1）主函数：

do{printf(“* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *n”);

printf(“*

1.创建

2.修改

3.查询

4.浏览

5.表长

6.文件

0.退出

*n”);

printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”);

scanf(“%d”,&opt);switch(opt){

case 1:Initlist(L);break;

case 2:handle(L);break;

case 3:search(L);break;

case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break;

数据结构课程设计

航班信息查询与检索系统

} }while(opt!=0);}

（4）文件操作： void File(Sqlist &L){

int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”);

printf(“*

*n”);

printf(“* 1.保存信息到文件

2.从文件读取信息

0 退出 *n”);

printf(“*

*n”);

printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”);

printf(“请输入选项n”);

scanf(“%d”,&ch);

switch(ch)

{

case 1:SaveList(L);break;

} }while(ch!=0);case 2:ReadList(L);break;

case 0:printf(“退出！n”);break;}

（5）浏览信息：就是循环使用输出函数，在此就不必多说了

2.4 调试分析

（1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。

（2）算法中有许多不是很优化的地方。3.用户使用说明

程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打

数据结构课程设计

航班信息查询与检索系统

图2-2 查询信息

图2-3插入

图2-4删除

数据结构课程设计

航班信息查询与检索系统

时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。

6.附录

#include #include #include typedef struct time { int hour;int min;

{ }

void search_key(Sqlist L)//按航班号查找

{ 号：“);

Time rh;Time lv;

scanf(”%s“,n);int i;

printf(”此航班的航班号，起点char n[20];

printf(“请输入要查找的航班

printf(”%dn“,L.length);//表长

}Time;typedef struct node {

}Pnode;struct Plane {

};typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;

终点，班期，起飞时间，到达时间，票价：n”);

if(strcmp(L.plane[i].key,n)==0)

ted，L.plane[i].sche,L.plane[i].lv.hour,L.{

for(i=L.length-1;i>=0;i--){

printf(“%s %s %s %d:%d %

d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length;

plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

[i].price);

0数据结构课程设计

航班信息查询与检索系统

printf(“此航班的航班号，起点

ted，{ 终点，班期，起飞时间，到达时间，票价：n”);

if(L.plane[i].lv.hour<=hour)

ted，L.plane[i].sche,L.plane[i].lv.hour,L.{

for(i=L.length-1;i>=0;i--){

printf(“%s %s %s %d:%d %

d:%d %dn”,L.plane[i].key,L.plane[i].s

L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

}

void search(Sqlist L){

int i;do {

printf(“* * * * * * * * * * * }

} printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane

} void search_rh(Sqlist L){

int hour;printf(”请输入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班号，起点 } } [i].price);

* * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”);

printf(“* 1.航班号查询

2.起点终点查询

3.班期查询 4.起飞时间查询

5.到达时间查询

0.退出

*n”);

printf(“* * * * * * * * * *

* * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”);

scanf(“%d”,&i);

switch(i)

{

case 晚时间：“);终点，班期，起飞时间，到达时间，票价：n”);

if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){

1:search_key(L);break;

2数据结构课程设计

航班信息查询与检索系统

n“);

} else { } printf(”查找不成功。

i--;if(i==0)

{

char c[20];

printf(“输入修改后的scanf(”%s“,c);

内容：”);

strcpy(L.plane[i].sche,c);

printf(“修改成功！n”);}break;{

int a,b;

printf(“输入修改后的int opt;printf(”选择修改对象：“);scanf(”%d“,&opt);switch(opt){ case 1:

printf(”修改成功！n“);printf(”修改成功！n“);{

char a[10];printf(”输入修改后的scanf(“%s”,a);

case 4:

内容：“);

char b[20];printf(”请输入修改后scanf(“%s”,b);

scanf(“%d:%d”,&a,&b);

L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班号：“);

}break;{

int a,b;

printf(”输入修改后的strcpy(L.plane[i].key,a);}break;{

case 5: case 2:

内容：“);

scanf(”%d:%d“,&a,&b);

L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的内容：”);strcpy(L.plane[i].sted,b);}break;

}break;{

int a;

case 6: case 3:

4数据结构课程设计

航班信息查询与检索系统

*n“);

printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“);

printf(”请输入选项n“);

scanf(”%d“,&ch);

switch(ch)

{

case 1:SaveList(L);break;case 2:ReadList(L);break;

L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane

[i].rh.hour,&L.plane[i].rh.min,&L.pl

}

void delet_Sq1(Sqlist &L){

char n[10];int i,j;

printf(”请输入您要删除的航scanf(“%s”,n);if(L.length==0){

printf(“没有选项！n”);for(i=0;i

L.length++;

ane[i].price);

case 0:printf(“退出！n”);break;

}

void Initlist(Sqlist &L)//插入存储 {

“);

容：”);价n“);

scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i

班期

起飞时间

到达时间

票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”请输入顺序表中的内

int i,n;printf(“输入表中航班的数量：

} }while(ch!=0);

班号：”);

if(strcmp(L.plane[i].key,n)==0)

{

printf(“所删除的班机*)malloc((n+10000)*sizeof(Plane));的信息：n”);

printf(“n航班号

起点终点

printf(”%s %s %s %d:%d %d:%

d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

[i].price);

6数据结构课程设计

航班信息查询与检索系统

n”);} printf(“无法打开文件！}

}while(opt!=0);

void insert_Sq(Sqlist &L){ 数量

价n”);

for(i=0;i

printf(“* * * * * * * * * * *

scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[

{

int a=get_Sq(L);

printf(”请输入要添加班机的scanf(“%d”,&n);

printf(“请输入要添加的班机printf(”n航班号

起点终点

int i,n;

//n表示添加的fprintf(fp,“航班号：%sn起点站：%s

终点站：%sn班期：%dn起飞时间：%d:%d

到达时间：%d:%dn价格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi

n“);} void delet_Sq(Sqlist &L){

int opt;do { fclose(fp);printf(”保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price);

数量：“);

信息：n”);

班期

起飞时间

到达时间

票* * * * * * * * * *n“);

printf(”* 1.航班号删除

printf(“* * * * * * * * * * printf(”输入你的选择：“);2.路线删除

0.退出

*n”);* * * * * * * * * * *n“);

scanf(”%d“,&opt);

switch(opt){

case 1:delet_Sq1(L);break;

case 2:delet_Sq2(L);break;

case 0:printf(”退出。}

L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan

e[L.length].rh.min,&L.plane[L.length].price);

}

void handle(Sqlist &L){

}

L.length++;

4.数据结构课程设计正文 篇四

比较与实现

摘 要：本次课程设计主要研究几种常用查找算法的比较与实现，查找的算法有很多种：静态查找表的顺序表、有序表、索引顺序表等查找结构；动态查找表的二叉排序树、哈希查找等查找结构。本次的课程设计主要研究两种常见的查找算法：顺序查找和折半查找，分析比较它们的时间复杂度，并且在此基础上用C语言对它们进行算法编程、调试和运行。

关键词：C语言；顺序查找；折半查找;时间复杂度。

１ 引 言

“数据结构”在计算机科学中是一门综合性的专业基础课，“数据结构”的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，一遍查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

课程设计是我们专业课程知识综合应用的实践训练，是实践性教学的一个重要环节。而数据结构的课程设计，更要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码薄中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读音和含义等等。而同样地，在各种系统软件和应用软件中，也存在“查找”：如编译程序中符号表、信息处理表中相关信息的查找。所以，“查找”就是在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录）。

【1】在计算机中进行查找的方法也会随数据结构不同而不同。在此，引入“查找表”的概念：同类数据元素构成的集合。所以，这次的课程设计就可以从静态查找表的几种典型的算法来实现对数据元素的查找的算法和操作的实现和比较。

1.1课程设计背景

《数据结构》课程设计作为独立的教学环节，是计算机相关专业集中实践环节系列之一，是学习完《数据结构》课程后进行的一次全面的综合练习。所以需要我们了解并掌握数据结构与算法的设计方法，并且具备初步的独立分析和设计能力，同时要掌握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。所以这次课程设计的目的在于：加强学生对C语言的基本知识和技能；加深对数据结构基础理论和基本知识的理解，提高解决实际问题的实践能力；同时帮助调动学生的积极性和能动性，培养学生的自学、动手能力。

２

1.2课程设计目标

本次课程设计，我准备用不同的两种常见的查找方法：针对顺序查找表中查找方法，如顺序查找、折半查找等。并且通过用这些算法实现对某个“特定的”数据元素（关键字）的查找，分析这些操作的性能：它们各自的时间复杂度、空间复杂度和其它的一些性能，同时记录每种查找方法的优缺点，比较得出它们的查找效率和查找范围。

３ 设计概要

2.1 问题描述

对于不同的查找算法，它们各自的时间复杂度和空间复杂度不同，查找的思想和算法也明显不同，所以要分析它们的特点和效率，我们要多方面比较：要比较时间复杂度，我们可以从它们的查找长度侧面比较出来；而它们算法的实现就要熟悉它们的查找思想，熟练应用C语言编写合适的程序。

2.2 设计思路

静态查找表有顺序表和链式表两种表示方法，在这次的课程设计里，我用顺序存储表来表示这两种查找算法的程序。我的设计思路及步骤如下：

（1）熟悉两种算法的编程思想,画出流程图。

（2）先编写两种算法的子程序，再遍写主程序调用它们。

（3）分步调试子程序和主程序，直到不再出现错误，然后运行程序，检查是否和 自己当初的设想一样，一直到结果能让自己满意。（4）比较得出两种查找算法的优缺。

2.3 相关的知识点

（1）C语言表示静态查找表的顺序存储结构 typedef struct { ElemType *elem;

//数据元素存储空间基址，建表时按实际长度分配，0号单元留空

int length;

//表的长度

} SSTable;

４（2）查找算法的衡量指标

查找可能产生“成功”与“不成功”两种结果，但在实际应用的大多数情况下，查找成功的可能性比不成功的可能性大得多，特别是在记录数中n很大时，查找不成功的概率可以忽略不计。当查找不成功的情况不能忽视时，查找算法的平均长度应该是查找成功时的平均查找长度与查找不成功时的平均查找长度之和，平均查找长度为： ASL= picii1n

其中，n为元素的个数； ci是查找第i 个记录需进行的比较次数；pi是查找第i个记录的概率，一般可认为查找每个记录的概率是相等的，即p1=p2=„=pn=1/n。【2】

５ 算法分析及程序编写

3.1.顺序表的查找

（1）基本思想

从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。（2）顺序查找算法流程图

算法流程图如图3-1所示：

图3-1：顺序查找算法流程图

６（3）顺序查找算法代码如下

int Search_Seq(SSTable *table, ElemType key){

/*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/

table->elem[0]=key;

//设置哨兵 int result=0;

// 找不到时，返回0 int i;for(i=table->length;i>=1;i--)

{

//从后往前找

if(table->elem[i]==key)

{

} result=i;

//找到关键字的时候，该元素的位置 break;

}

return result;

//找不到时返回 } <4>顺序查找算法性能分析

对于顺序查找，不论给定值key为何值，查找不成功时和给定值进行比较的关键字个数均为n+1.假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则Pi=1/（2n）,此时顺序查找的平均查找长度为[3]：

ASL= (ni1ni1)+(1/2)(n+1)

=(3/4)(n+1)

<5>结论

顺序查找的优点是算法简单，且对表的结构没有任何要求。它的缺点是查找效率低，因此，当表中元素个数比较多时，不宜采用顺序查找。

７

3.2.折半查找

（1）使用折半查找必须具备两个前提条件

a：要求查找表中的记录按关键字有序(假设：从小到大有序)b：只能适用于顺序存储结构

（2）基本思想

先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找，直到查找成功，或者查找失败。

(3）查找流程图

流程图如图3-2所示：

８

图3-2：折半查找算法流程图

(4）折半查找算法的代码

int Search_Bin(SSTable *table, ElemType key){

/*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0.*/

int low=1;

int high=table->length;

//置区间初值

int result=0;// 找不到时，返回0 while(low <= high)

９

{

} return result;int mid=(low+high)/2;

//中间的数据元素 if(table->elem[mid]==key){ result=mid;break;}

//找到待查元素 else if(keyelem[mid]){ high=mid-1;}

//继续在前半区间进行查找 else { low=mid+1;}

//继续在后半区间进行查找

}[5]

（5）折半查找算法性能分析

在折半查找的过程中，每经过一次比较，查找范围都要缩小一半，所以折半查找的最大查找长度为

MSL=[log2 n]+1 当n足够大时，可近似的表示为log2(n)。（6）结论

折半查找要求查找表按关键字有序，而排序是一种很费时的运算；另外，折半查找要求表是顺序存储的，为保持表的有序性，在进行插入和删除操作时，都必须移动大量记录。因此，折半查找的高查找效率是以牺牲排序为代价的，它特别适合于一经建立就很少移动、而又经常需要查找的线性表。

可见在查找速度上，折半查找比顺序查找速度要快的多，这是它的主要优点[4]。

１０ 测试分析

1.输入元素有误

（1）：若输入的元素个数不合理，元素个数少于n，这种输入造成的的结果是系统一直等待元素的输入，即得不到结果。如图4-1所示：

图4-1：输入元素个数少时的运行情况

（2）若输入元素个数大于n时，系统将从第一个元素起，自动选取前n个元素作为有效元素，进行程序的后续运行。这种情况下的结果如图4-2所示：

图4-2：输入元素个数多时的运行情况

１１

2.查找失败

这种情况是指在n个元素中没有与关键字相同的元素存在，所以程序运行的结果是查找失败。运行结果如图4-3所示：

图4-3：查找失败时的运行情况

3.查找成功

若查找成功，即元素输入无误，且有关键字存在的情况，这个时候的运行结果如图4-4所示[5]：

图4-4：查找成功时的运行情况

１２ 总结和体会

5.1 课程设计总结

“书到用时方恨少”。在这次课程设计，我感触最深的当属查阅大量的设计资料了，为了让自己的设计更加完善，查阅这方面的设计资料是十分必要的，看着那么大叠的书籍、资料摆在自己的面前，有些时候还要上网查阅相关知识点，并且还要整理出有用的知识点，这对于我来说，是在是个不小的挑战。所以，以后一定要多看自己专业方面的书籍，增长自己的知识。而且，写程序是一件十分需要耐心的活，一个不小心，后果就可能是几个小时的思考和调试，幸好这次的课题我并不陌生，所以，并没有自己想象中的艰难。但是，用的时间和精力却绝对也不少。

5.2 心得与体会

这次课程设计，使我对《数据结构》这门课程有了更深入的了解。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。一个人的力量是有限的，要想把课程设计做的更好，就要学会参考一定的资料，吸取别人的经验，让自己和别人的思想有机的结合起来，得出属于你自己的灵感。

在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。程序的编写需要有耐心，有些事情看起来很复杂，但问题需要一点一点去解决，分析问题，把问题一个一个划分，划分成小块以后就逐个去解决。再总体解决大的问题。这样做起来不仅有条理也使问题得到了轻松的解决。

通过这两周的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。

１３

参考文献：

[1]严蔚敏，吴伟民.《数据结构:C语言版》 清华大学出版社，2012.5 [2]Mark Allen Weiss.数据结构与算法分析——C语言描述（英文版第二版）.北京：人民邮电出版社，2005 [3]李峰，谢中科.C语言程序设计.上海：复旦大学出版社，2011 [4]Baloukas, C., Risco-Martin, J.L., Atienza, D., et al.Optimization methodology of dynamic data structures based on genetic algorithms for multimedia embedded systems[J].Journal of Systems and Software, 2009, 82(4): 590-602.[5]李春葆，尹为民.数据结构教程上机指导（第三版）.北京：清华大学出版社,2008

１４

附录：程序源代码：

#include #include #include

using namespace std;typedef int ElemType;

//用C语言定义顺序存储结构

typedef struct {

ElemType *elem;

//数据元素存储空间基址，建表时按实际长度分配，0号单元留空

int length;

//表的长度 } SSTable;

void Create(SSTable *table, int length);

// 构建顺序表

void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);

void Traverse(SSTable *table, void(*visit)(ElemType elem));

void Create(SSTable **table, int length){

// 构建顺序表

SSTable *t =(SSTable*)malloc(sizeof(SSTable));

１５ t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));t->length=length;*table=t;} void FillTable(SSTable *table){

// 无序表的输入

ElemType *t=table->elem;for(int i=0;ilength;i++){

t++;

scanf(“%d”, t);

getchar();} } void Destroy(SSTable *table){

//销毁表

free(table->elem);free(table);} void PrintTable(SSTable *table){

// 打印查找表中的元素

int i;ElemType *t=table->elem;

１６ for(i=0;ilength;i++){ t++;printf(“%d ”, *t);

} } //顺序（哨兵）查找算法

int Search_Seq(SSTable *table, ElemType key){

/*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/

table->elem[0]=key;

//设置哨兵 int result=0;

// 找不到时，返回0 int i;for(i=table->length;i>=1;i--)

{

//从后往前找

if(table->elem[i]==key)

} {

} result=i;

//找到关键字的时候，该元素的位置 break;

return result;

//找不到时返回 }

１７

void Sort(SSTable *table){

// 排序算法

int i, j;ElemType temp;

for(i=table->length;i>=1;i--)

// 从前往后找 {

for(j=1;j

}

int Search_Bin(SSTable *table, ElemType key){ /*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元

} {

} if(table->elem[j]>table->elem[j+1]){

//从小到大排列

} temp=table->elem[j];table->elem[j]=table->elem[j+1];//元素后移 table->elem[j+1]=temp;素在表中的位置，否则为0.*/

int low=1;

１８

} int high=table->length;

//置区间初值

int result=0;// 找不到时，返回0 while(low <= high){

} return result;int mid=(low+high)/2;

//中间的数据元素 if(table->elem[mid]==key){ result=mid;break;}

//找到待查元素 else if(keyelem[mid]){ high=mid-1;}

//继续在前半区间进行查找 else { low=mid+1;}

//继续在后半区间进行查找

// 主函数

１９ int main(int argc, char* argv[]){

SSTable *table;

int r;

//元素的位置 int n;ElemType key;printf(“输入 n:”);scanf(“%d”,&n);

Create(&table, n);//建立表

cout<<“请输入”<

printf(“您输入的 %d 个值是：n”,n);

PrintTable(table);//打印无序表 cout<

printf(“顺序法查找运行结果如下：n ”);Search_Seq(table,key);//顺序（哨兵）查找算法 r=Search_Seq(table,key);

if(r>0)

printf(“ 关键字 %d 在表中的位置是： %dn”,key, r);

else

printf(“查找失败，表中无此数据。n”);

２０ Sort(table);//对无序表进行排序

printf(“数据排序后的顺序如下：n ”);PrintTable(table);//打印有序表 printf(“n”);

printf(“折半查找法运行结果如下：n ”);

r=Search_Bin(table,key);//折半查找算法 if(r>0)printf(“ 关键字 %d 在表中的位置是： %dn”,key, r);

else

{

5.数据结构与算法课程设计题目 篇五

1．成绩管理

问题描述：给出n个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数

学、英语、物理），设计一个简单的成绩管理程序。

基本要求：

（1）建立成绩表，能够插入、删除、修改学生的成绩记录；（2）按任一单科成绩排序；(3)计算每名学生的平均成绩；

(4)统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单(5)根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。

(6)成绩表保存在文件中, 可以从文件读取数据。

测试数据：学生可以根据自己班级的考试成绩单，任意截取一部分做为测试数据 2．一元多项式简单计算

问题描述：设计一个简单一元多项式计算器。基本要求：(1)输入并建立多项式；(2)输出多项式；

(3)两个多项式相加，输出结果多项式；(4)两个多项式相减，输出结果多项式。

提高要求：可以根据输入变量的值，计算出多项式的结果，且算法的效率高。测试数据：可任意选取两个一元多项式，可以是一般的多项式，也可以是稀疏多项式。3．舞伴问题

问题描述：一班有m个女生、n个男生(m不等于n), 举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。

基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。

测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据 提高要求：计算出任意一位男生(编号为X)和任意一位女生(编号为Y), 在第K曲配对跳舞的情况。

4．文学研究助手（*）

问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。基本要求：英文小说存于一个文本文件中，待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计, 结果保存到文件中。

提高要求：模式匹配选取KMP算法

测试数据：以你的C/C++/JAVA源程序模拟英文小说，相应语言的保留字集作为待统计的词汇集。

5．哈希表的设计与实现（*）

问题描述：针对某个单位电话号码簿，设计一个哈希表，并完成相应的建表和查表程序。基本要求：设每个记录有下列数据项：电话号码、用户名、住址。从键盘输入各记录，以用户名为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录，并计算查找长度, 哈希表保存到文件中。

测试数据：取某个单位电话号码簿中的30个记录。

提高要求：将电话号码薄以文件形式保存到盘上，能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素的功能。

6．管道铺设施工的最佳方案（*）

问题描述:需要在某个城市的n个小区铺设管道，则在这n个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。

基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1条管道输出到显示器的同时, 也保存于文件中。

测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。提高要求：显示原始图及选择n-1条管道后的图。

7．安排教学计划（**）

问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两个学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课程恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

基本要求：输入参数包括学期总数，一学期的学分上限，每门课程的课程号、学分和直接先修课的课程号；允许两种策略，一是使学生在各学期的学习负担尽量均匀，二是使课程尽量集中在前几个学期；若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定, 可以从键盘读取数据也可以从文件读取数据, 结果保存到文件中。

测试数据：学期总数为6，学分上限为10，该专业共开设12门。以08级某专业必修课与选修课为例，选择12门课程及相应学分，制定一个表明各门课程先后约束关系的有向图。

提高要求：产生多种不同的方案，并使方案之间的差异尽可能地大。8．停车场管理程序(**)问题描述：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

基本要求：每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费，单位时间的停车费用由用户从键盘输入）。

测试数据：设输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。

提高要求：设停车场有南、北两个门，每个门都可以进、出车辆。9．计算表达式的值(**)问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。

基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。

测试数据：任意选取一个符合题目要求的表达式。提高要求：（1）对于表达式中的简单错误，能够给出提示；

（2）表达式中可以包括单个字母表示的变量。

10．设计Huffman 编码器与解码器（***）

问题描述：利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。

基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）测试数据：英文文件。

提高要求：用二进制表示编码，生成二进制的编码文件。11．银行业务模拟（***）

问题描述：设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候, 当任一服务窗口空闲时,处理等候客户中排在最前面的客户的业务。写一个上述银行业务的模拟系统,通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。

基本要求：每个客户到达银行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口每天办理的客户数和每种业务数。

测试数据：营业时间为8小时，其他模拟量自行设定。12．程序源代码的相似性（***）

问题描述：对于两个C++语言的源程序代码，用哈希表的方法分别统计两个程序中使用C++语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。

基本要求：建立C++语言关键字的哈希表，统计在每个源程序中C++关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。

例如: 关键字 Void Int For Char if else while do break class 程序1关键字频度 4 3 0 4 3 0 7 0 0 2 程序2关键字频度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 设s是向量X1和X2的相对距离，s=sqrt(∑(xi1-xi2)2)，当X1=X2时，s=0, 反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。

测试数据: 选择若干组编译和运行都无误的C++程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。

提高要求：建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。

13．小型文本编辑器

问题描述：设计一个行编辑程序，使其具有通常行编辑器(如Vi、Edlin)应具备的基本功能。

基本要求：编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数，统计行数等功能，对于超过一屏的长文件，应能够分页显示，查找功能用字符串匹配算法实现。设计用户接口命令，实现对文本的编辑。具体的编辑命令，可参考数据结构算法网络教学平台上提供的edlin、Vi的命令集。

测试数据：任一文本文件。

提高要求：１.可以支持“* ”、“? ”等通配符；

２.支持复制、粘贴等功能

3.支持多文档同时编辑；

提示：可以考虑用双向链表实现，每一结点表示一行字符，注意每行字符不能超过255。14．小型英汉词典

问题描述：设计一个英汉词典，支持Member(查找)、Insert(插入)、Delete(删除)操作。

基本要求：实现字典的常用方法有：有序线性表（Memeber用二分检索实现）、AVL树（二叉搜索树）、Patricia Trie、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。

测试数据：任一英文单词。提高要求：选用两种以上的方法实现字典的操作，并比较不同实现算法的时间复杂度和空间复杂度。

提示：字典可以自己建立，但必须按字母a~z建立26个文件，建议从网上下载，文件类型为txt。

备注：

1.每道题目后面的*号，表示题目的难度系数；对应的评定成绩等级为及格（无*号）、中等（*号）、良好（**号）、优秀（***号），学生完成题目的基本要求，即可得到程序设计部分的相应等级成绩，完成题目提高要求，成绩可以向上浮动，如果没有完成基本要求，成绩向下浮动，直至不及格。

6.数据结构课程设计新版 篇六

Energistics(前身是POSC)是一个全球性的、非盈利、会员制的中立组织[1]，其职责是开发、管理和推广石油和天然气上游业务数据交换标准。Energistics针对不同的技术领域建立SIGs(特别兴趣团体)，团结全球的领域专家和标准爱好者来促进本领域技术标准的开发。Energistics的会员包括石油公司、服务公司、软件提供商和监管机构的代表，目前已有100多个，包括Shell、BP、Chevron、Total、ExxonMobil、Halliburton、Schlumberger、Weatherford、Microsoft、Baker Hughes、Paradigm、PPDM、CMG等国际著名公司。

1.1 E&P业务标准模型

Energistics在某大型能源公司现行的业务流程基础上，抽象制定了E&P业务标准模型[2]，它不依赖于任何特定的组织架构或技术工具。制定该模型的目的是帮助分析业务领域内的通用业务流程、概念、词汇等，进而开发和应用一致的行业标准。该模型具有通用性和稳定性，其优点是：(1)不用再为每项标准的研究来定义业务流程，从而节省标准研究的时间;(2)这种关于业务流程、概念、词汇等的明确的、通用的定义，有助于促进标准的开发、理解和实际应用;(3)可作为定义新业务流程(如基于internet新技术产生的新业务)的基础;(4)可作为应用软件需求分析的基础;(5)可促进行业以及跨行业业务标准的形成。

该模型将石油的勘探开发业务过程分为5个阶段：勘探(Explore)→评估(Appraisal)→开发(Develop)→生产(Produce)→废弃(Abandon)。每个阶段又包含若干业务过程，每个业务过程可在不同的阶段中重复存在。这些业务过程的定义是相对独立的，可根据实际需要将它们灵活“组装”起来形成每个业务阶段的完整业务流程。这些业务过程主要包括：(1)井设计与管理(E);(2)测量(F)-井位测量、地球物理测量、测录井等;(3)开发规划(G)-处理解释评价;(4)油田基础设施设计与管理(H);(5)物资供应(I);(6)后勤服务(J);(7)金融服务(K);(8)取得或出让资产(L);(9)石油与天然气销售(M);(10)人力资源(N);(11)IT服务(O);(12)实验室(P);(13)生产(Q);(14)维护(R)。

1.2 Energistics标准体系

根据业务模型所识别的业务领域，Energistics目前已经制定了WITSML、PRODML、RESQML、Asset&Data Management、Industry Services、Geophysics、eRegulatory等SIG[3]，并相应建立了7大标准的路线，各标准发展状况如表1所示。

近几年在钻完井、油田生产和油藏3个领域形成了基于XML的标准，其它标准尚无最新成果。其中WITSML是与钻井、完井以及修井相关的标准，PRODM是以WITSML为基础延伸的与油井生产相关的标准，RESQML是与油藏相关的标准。以WITSML为例剖析其内部结构、应用情况以及前景。

2 WITSML标准剖析

WITSML(井场信息传递标准标记语言)是一种数据传输标准，旨在促进井场和基地之间钻井数据的有效传输。WITSML标准由WITS(井场信息传输标准)开发而来，其目的是创建一种统一的XML格式标准实现井数据的传输，以便能够集成不同服务商的信息。标准数据传输机制可以整合新的工具和流程，这使得地质学家和工程师可以在他们熟悉的桌面应用程序中使用实时数据。

2.1 WITSML标准的内部结构

WITSML标准包括2个可独立版本化的组成部分：数据模型和应用程序接口(API)。最新的v1.4.1版本(2011年发布)数据模型定义了27个对象[4]，如表2所示。

这些数据对象中，wellbore是well的子对象，而其它绝大多数对象又是wellbore的子对象，changeLog对象可作为其他对象的子对象(记录该对象的变化情况)，CRS是一个独立对象(坐标系)，对象之间的关系如图1所示。

注:带“●”的是正式的研究团体,带“○”的是研究分支。

WITSML基于XML文件格式，一个数据对象定义了一组数据，可以用一个单一的XML文档传送，代表了一个领域(domain)逻辑模型内的一组紧密相关的数据子集。比如，“井”这个逻辑模型包括井、井筒、钻机等数据子集。数据对象包括属性、元素和子组件(component sub-schemas)。子组件是XML结构，但不能代表完整的数据对象，而且可以属于多个数据对象。一个子组件通常只定义一类数据，并且在这个类型名前面加上“cs_”作为这个子组件的文件名。比如，cs_drillingParams.xsd里面仅仅包含钻井参数，而且它同属于bhaRun和opsReport这两个数据对象。WITSML还定义了大量常量数据类型和单位制符号。

2.2 WITSML标准的典型应用架构

利用WITSML标准实现井场数据交换的典型架构如图2所示，其中WITSML服务器是核心部分，它将传入的其它各类格式数据进行转换之后，可向网络上任何地方提供WITSML标准格式的数据服务。比如油公司、工程服务公司等相关各方可实时获取这些数据，进而开展数据展现、分析等应用。

3 WITSML标准在国内外的应用

3.1 国外应用情况及效果

多年来，很多地方的不同作业者都见证了FEWD数据在远程钻井地点和中央基地之间实时传输的价值。在过去，这类传输的问题之一就是在众多的数据传输方法中，有一部分是具有专利的，这使得终端应用程序的数据传输很不标准而且非常耗时。有了WITSML之后，可通过WITSML服务器直接将数据发送到客户端应用程序上，这意味着作业者不再依赖于应用供应商或服务商就能得到现场传回的数据，进而针对这些数据开展工作。因此，在世界各地，使用这项流程的作业者正变得越来越多。数据传递和传输方式的标准化使得作业者可以从众多供应商中获得最佳服务和软件解决方案的时候，还能保持数据的有效流动。

目前，大多数世界知名的外国石油公司、油田服务公司、仪器供应商和软件开服商均已应用WITSML标准。以Statoil、Schlumberger为例介绍WITSML的应用情况及效果[5]。

(1)实时作业支持与协同决策。Statoil公司基于WITSML建立了实时支持中心(RTS)小组。该小组负责世界各地所有Statoil作业钻机和平台的实时数据传递。该小组通过内部工程数据库，集中管理来自现场工具和传感器的地面和井下随钻地层评价(FEWD)数据，使得每个工作组都可访问任意时间的数据，及时作出钻井施工决策。同时，WITSML的应用大大强化了地质和地球物理(G&G)与工程团队之间的交叉学科协作能力。例如，可利用WITSML标准中的风险(Risk)数据对象将钻井风险同地质模型有效融合，可以将一个学科中已知的问题更好地与井设计和执行情况相结合，从而对风险和不确定性进行更有效地管理。

(2)从实时监测到实时控制。虽然WITSML并不一定能够直接实现实时控制，要实现实时控制更多的还得依靠远程控制和监测工具的开发，但实时控制还是和WITSML关键工作流程的发展结合到了一起。过去的几年，Statoil各资产小组与其他作业者中的MWD和LWD工程师以及泥浆录井工程师已经可以在远离现场的地方进行工作了。这不仅具有明显的质量健康安全环保(QHSE)管理体系优势，而且也可以让个人与提供服务的资产小组进行直接互动。

(3)服务效率和质量提升。WITSML支持更广泛的数据类型，使得服务公司快速推广应用新型的工具和测量方法。

统一的数据源类型可以缩短为了获取和传输数据而进行软件升级的时间。比如Schlumberger已经采用了统一的WITSML客户端软件，只需要在软件中更新WITSML发布的新标准代码，即可立即实现对所有客户的应答升级，大大降低了软件开发成本和时间，还有助于处理“方言问题”。现场多专业、多来源数据的合并传输，使得服务公司可以通过内部作业支持中心监测这些数据，同时还可以使远程工作人员获得集中的支持，提高了服务质量。

3.2 国内应用情况

与国际发展现状相比，国内石油企业对于WITSML标准的研究和应用明显滞后，且主要限于少数软件或仪器开发商[6]。尽管WITSML是个开放的标准，但要真正应用它需要做很多细致的研究工作。比如，分析每个数据对象里面包含的所有数据项，从而与现有数据存储模型进行对应，是一件非常麻烦的事情。解决这个问题的最好途径就是加入Energistics组织，参与该标准的研究，使用他们的研究成果，包括数据转换服务平台。而目前，国内仅有北京怡恒阳光科技发展有限公司一家单位加入了该组织，并在其软件中部分应用了WITSML标准。中石油、中石化、中海油等三大石油公司均未正式参与该标准的合作，但在接受国外公司(如Schlumberger)的技术服务时，间接使用了基于WITSML标准的数据服务。

3.3 应用WITSML的风险与对策

实时数据可以使员工在基地就能完成原来需要在现场才能完成的工作，从而减少了现场总人数。但是，这种工作模式增加了对实时数据的依赖性。一旦钻井数据传输中断，现场作业很可能必须终止，从而造成非工作时间的损失。因此，数据传输的可靠性是WITSML推广应用的最大风险。

为了规避或降低这个风险，Schlumberger公司的Deeks和StatoilHydro公司的Halland提出了一种“WITSML服务关键绩效指标(KPI)”的量化考核做法[5]，见表3。KPI是否有效的一个重要标准就是KPI不仅应能度量WITSML服务器的可用性，还应能度量服务器上高质量实时数据的可用性。

4 结论与建议

(1)以WITSML为代表的系列数据交换标准，重点关注于不同合作方、不同应用系统间的数据交换，成功回避了数据存储模型难以统一的问题，使得该标准具备推广的可行性，已被业界广泛认可和采用，越来越多的石油公司、服务公司、软硬件供应商和相关研究机构加入到Energistics组织。

(2)石油公司可实现从平台到数据库到公司总部的实时数据共享，强化运营商支持与决策;服务公司能够更大程度地简化不同源数据的整合过程，提升数据处理效率;软硬件开发商在开发新软件时，可简化数据结构分析环节，从而显著减少从设计到交付的时间。

(3)国内石油行业的信息化已经到了整合集成阶段，迫切需要WITSML这种应该尽快加入到国际信息标准的合作中来，制定企业内部甚至整个行业的井场信息交换标准，进而消除信息孤岛，消除目前存在的“现场采集数据标准不一，只能利用录井仪服务商的特定软件才能传输展示该井实时数据”等顽症，实现大范围的信息共享，减少重复开发，简化应用流程。

参考文献

[1]Energistics.About Energistics[EB/OL].http://www.energistics.org/about-energistics,2011-8-13.

[2]Energistics.E&P Business Process Reference Model[EB/OL].http://e-and-p-business-process-reference-model,2011-8-13.

[3]Energistics.Special Interest Groups[EB/OL].http://www.energistics.org/special-interest-groups-sigs,2011-8-13.

[4]Energistics.WITSML Standards[EB/OL].http://www.energistics.org/witsml-standard,2011-8-13.

[5]N.R.Deeks,Schlumberger,and T.Halland,StatoilHydro.WITSMLChanging the Face of Real-Time[C].Paper SPE 112016 presented atthe 2008 SPE/DOE.