数据结构课程设计级幻灯片.ppt

《数据结构课程设计级幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构课程设计级幻灯片.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计级第1页，共56页，编辑于2022年，星期六二、数据结构课程设计要求二、数据结构课程设计要求1.学生必须仔细阅读数据结构课程设计方案，认真主动完成学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。课设的要求。有问题及时主动通过各种方式与教师联系沟通。2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。师汇报。3.课程设计按照教学要求需要两周时间

2、完成（课程设计按照教学要求需要两周时间完成（2周共十天）。周共十天）。第2页，共56页，编辑于2022年，星期六三、实习基本内容三、实习基本内容 本次课程设计完成如下模块（共本次课程设计完成如下模块（共23个模块，个模块，学生可以在其中至少挑选学生可以在其中至少挑选5-6个功能块完成，个功能块完成，其中其中8、9、10、13在做在做5个以下不算数，个以下不算数，5个以上算数个以上算数）第3页，共56页，编辑于2022年，星期六1校园导游程序校园导游程序 问题描述：用无向网表示你所在学校的校园景点平面图，问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称

3、、简介等图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。要求能够回答有关景点介绍、游览路径等问题。基本要求：查询各景点的相关信息；查询图中任意两个景点间基本要求：查询各景点的相关信息；查询图中任意两个景点间的最短路径；查询图中任意两个景点间的所有路径；增加、删的最短路径；查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。除、更新有关景点和道路的信息。选作内容：选作内容：求多个景点的最佳（最短）游览路径。求多个景点的最佳（最短）

4、游览路径。区分机动车道和人行道。区分机动车道和人行道。实现导游图的仿真界面。实现导游图的仿真界面。第4页，共56页，编辑于2022年，星期六数据结构：数据结构：typedef struct messageint num;/景点代码char name100;/景点名称char pro500;/简介Ciceroni;第5页，共56页，编辑于2022年，星期六Ciceronischool10=1,行政楼行政楼n,2,食堂食堂n,3,赛博楼赛博楼,信息分院办公室所在地信息分院办公室所在地n,4,求是求是楼楼,实验楼计算机中心实验楼计算机中心n,5,格致楼格致楼,法学管理学院法学管理学院,6,工程实习中

5、心工程实习中心,金工实习金工实习n,7,仰仪楼仰仪楼,机电机电计测分院计测分院n,8,体育馆体育馆,旁边有篮球场旁边有篮球场足球场足球场还有网还有网球场球场n,9,一号教学楼，主要以阶梯教室为主一号教学楼，主要以阶梯教室为主n,10,二号教学楼，小教室为多二号教学楼，小教室为多n;/*景点名称景点名称和简介和简介*/操作：操作：/*给景点之间的路径赋最大值给景点之间的路径赋最大值*/*最短路径的最短路径的C语言函数语言函数*/*输出最短路径和最短距离函数输出最短路径和最短距离函数*/*输入景点代码查景点名称和简介输入景点代码查景点名称和简介*/*输入景点代码查到其它景点的最短距离输入景点代码查

6、到其它景点的最短距离*/第6页，共56页，编辑于2022年，星期六2员工管理系统员工管理系统问题描述：问题描述：每个员工的信息包括：编号、姓名、每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、系统能够完成员工信息的查询、更新、插入、删除、排序等功能。删除、排序等功能。基本要求：基本要求：排序：排序：按不同关键字，对所有员工按不同关键字，对所有员工的信息进行排序；的信息进行排序；查询：查询：按特定条件查找员工；按特定条件查找员工；更新：更新：按编号对某个员工的某项信息进行修改；按编号对某个

7、员工的某项信息进行修改；插入：插入：加入新员工的信息；加入新员工的信息；删除：删除：按编号删除按编号删除已离职的员工的信息。已离职的员工的信息。选作内容：实现图形用户界面。选作内容：实现图形用户界面。第7页，共56页，编辑于2022年，星期六要求通过链表实现要求通过链表实现数据结构：数据结构：structworkerscharname15;/姓名姓名chardepartment18;/单位单位chargender;/性别性别unsignedintage;/年龄年龄unsignedlongtelephone;/电话电话unsignedlongwage;/工资工资unsignedlongnum;/

8、职工号职工号structworkers*next;第8页，共56页，编辑于2022年，星期六操作实现：操作实现：/*插入职工信息，通过链表实现插入职工信息，通过链表实现*/*具体实现职工信息的插入具体实现职工信息的插入*/*对职工信息的删除操作对职工信息的删除操作*/*修改操作修改操作*/*实现对员工信息的查找实现对员工信息的查找*/*排序排序*/*输出员工信息输出员工信息*/*显示职工工资情况显示职工工资情况计算平均工资计算平均工资*/第9页，共56页，编辑于2022年，星期六3算术表达式求值算术表达式求值问题描述：问题描述：一个算术表达式是由操作数一个算术表达式是由操作数(operand)

9、、运、运算符算符(operator)和界限符和界限符(delimiter)组成的。假设操作组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符符有左右括号和表达式起始、结束符“#”，如：，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是。引入表达式起始、结束符是为了方便。编程利用为了方便。编程利用“算符优先法算符优先法”求算术表达式的值。求算术表达式的值。基本要求：基本要求：从键盘读入一个合法的算术表达式，输出正确从键盘读入一个合法的算术表达式，输出正确的结果；显示输入序列和栈的变化过

10、程。的结果；显示输入序列和栈的变化过程。(3.14159/2+sqrt(1/32+4)+1/22*ln(1/1.1*(2+sqrt(1/32+4)*23.45;选作内容选作内容：扩充运算符集合；引入变量操作数；操作：扩充运算符集合；引入变量操作数；操作数类型扩充到实数。数类型扩充到实数。第10页，共56页，编辑于2022年，星期六4运动会分数统计运动会分数统计 任务：任务：参加运动会有参加运动会有n个学校，学校编号为个学校，学校编号为1，n。比。比赛分成赛分成m个男子项目，和个男子项目，和w个女子项目。项目编号为男子个女子项目。项目编号为男子1m，女子，女子m+1m+w。不同的项目取前五名或前

11、三名。不同的项目取前五名或前三名积分；取前五名的积分分别为：积分；取前五名的积分分别为：7、5、3、2、1，前三名，前三名的积分分别为：的积分分别为：5、3、2；哪些取前五名或前三名由学生；哪些取前五名或前三名由学生自己设定。自己设定。（m=20，n=2，请输男生项目总数，请输男生项目总数m=20，请输女生项目总数，请输女生项目总数k=20）/项目资料项目资料:请输入男生项目信息：项目名称请输入男生项目信息：项目名称;项目编号项目编号;该项目的参与人数该项目的参与人数请输入女生项目信息：项目名称请输入女生项目信息：项目名称;项目编号项目编号;该项目的参与人数该项目的参与人数/添加学生数据添加学

12、生数据intSchoolCount=0;/学校总数学校总数intboyCount=0;/男生项目男生项目总数总数intgirlCount=0;/女生项目女生项目总数总数intxm_Count=0;/项目项目总数总数XM_TABLExm_T41;/项目表项目表主要实现：主要实现：参数设置参数设置;添加学生添加学生;统计统计;学校查询学校查询;项目查询项目查询;等功能。等功能。第15页，共56页，编辑于2022年，星期六5一元多项式计算一元多项式计算任务：任务：能够按照指数降序排列建立并输出多项式；能够能够按照指数降序排列建立并输出多项式；能够完成两个多项式的完成两个多项式的相加、相乘，相加、相乘

13、，并将结果输出；并将结果输出；在上交资料中请写明：在上交资料中请写明：存储结构、多项式相加的基本过存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；结果、算法的时间复杂度、另外可以提出算法的改进方法；设有一元多项式设有一元多项式Am(x)和和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+AmxmBn(x)=B0+B1x1+B2x2+B3x3+Bnxn请实现求请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和和M(x)=Am(x

14、)Bn(x)。第16页，共56页，编辑于2022年，星期六要求：要求：1)首先判定多项式是否稀疏首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；分别采用顺序和动态存储结构实现；3)结果结果M(x)中无重复阶项和无零系数项；中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情要求输出结果的升幂和降幂两种排列情况况第17页，共56页，编辑于2022年，星期六6订票系统订票系统任务：任务：通过此系统可以实现如下功能：通过此系统可以实现如下功能：录入：录入：可以录入航班情况（数据可以存储在可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）一个数据文件中，数据

15、结构、具体数据自定）查询：查询：可以查询某个航线的情况（如，输入可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）班票价，票价折扣，确定航班是否满仓）可以输入起飞抵达城市，查询飞机航班情况；可以输入起飞抵达城市，查询飞机航班情况；第18页，共56页，编辑于2022年，星期六订票：订票：（订票情况可以存在一个数据文件中，（订票情况可以存在一个数据文件中，结构自己设定）结构自己设定）可以订票，如果该航班已经无票，可以提供可以订票，如果该航班已经无票，可以提供相关可选择航班；相关可选择航班；退票：退票：可退

16、票，退票后修改相关数据文件；可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。情况，订单要有编号。修改航班信息：修改航班信息：当航班信息改变可以修改航当航班信息改变可以修改航班数据文件班数据文件要求：要求：根据以上功能说明，设计航班信息，根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；订票信息的存储结构，设计程序完成功能；第19页，共56页，编辑于2022年，星期六航班信息数据结构航班信息数据结构typedefcharkeytype;/航班信息结构航班信息结构typedefstructchars

17、tart6;/起点站起点站charend6;/终点站终点站charsche10;/航班期航班期chartime15;/起飞时间起飞时间chartime25;/到达时间到达时间charmodel4;/机型机型intprice;/票价票价infotype;第20页，共56页，编辑于2022年，星期六/定义航班节点定义航班节点typedefstructkeytypekeyskeylen;/航班号航班号infotypeothers;/航班信息航班信息intnext;/下一航班下一航班slnode;/航班表航班表(静态链表静态链表)typedefstructslnodeslmaxspace;intkey

18、num;intlength;sllist;第21页，共56页，编辑于2022年，星期六操作实现：操作实现：（1）录入航班信息：）录入航班信息：（2）查询航班信息：）查询航班信息：可以查询某个航线的情况（如，输入航班号，查询起可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；可以输入起飞抵达城市，查询飞机航班情况；航班信息查询系统：航班信息查询系统：可以按：可以按：1.航班号航班号;2.起点站；起点站；3.终点站；终点站；4.起飞时间起飞

19、时间;5.到达时间到达时间;第22页，共56页，编辑于2022年，星期六以下选作：以下选作：（3）航班订票：航班订票：（订票情况可以存在一个数据文件中，（订票情况可以存在一个数据文件中，结构自己设定）结构自己设定）可以订票，如果该航班已经无票，可以提供相关可可以订票，如果该航班已经无票，可以提供相关可选择航班；选择航班；（4）航班退票：航班退票：可退票，退票后修改相关数据文件；可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。要有编号。（5）修改航班信息：修改航班信息：当航班信息改变可以修改航班数据文件当航

20、班信息改变可以修改航班数据文件注：因为航班号为两位字母后跟数字，所以在排序时注：因为航班号为两位字母后跟数字，所以在排序时应该使用应该使用多关键字的基数排序多关键字的基数排序对航班号进行排序。对航班号进行排序。第23页，共56页，编辑于2022年，星期六7迷宫问题求解迷宫问题求解任务：任务：可以输入一个任意大小的迷宫数据，可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，用非递归的方法求出一条走出迷宫的路径，并将路径输出；并将路径输出；要求：要求：在上交资料中请写明：存储结构、基在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、本算法（可以使用程序流程图

21、）、源程序、测试数据和结果、算法的时间复杂度、另外测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；可以提出算法的改进方法；第24页，共56页，编辑于2022年，星期六8文章编辑（不算）文章编辑（不算）功能：输入一页文字，程序可以统计出文字、数字、空格的功能：输入一页文字，程序可以统计出文字、数字、空格的个数。个数。静态存储一页文章，每行最多不超过静态存储一页文章，每行最多不超过80个字符，共个字符，共N行；要求行；要求分别统计出其中英文字母数和空格数及整篇文章总字数；分别统计出其中英文字母数和空格数及整篇文章总字数；统计某一字符串在文章中出现的次数，并输出该次数；统计某一字符串在

22、文章中出现的次数，并输出该次数；删除删除某一子串，并将后面的字符前移。某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。任何数字及标点符号。输出形式：输出形式：分行输出用户输入的各行字符；分行输出用户输入的各行字符；分分4行输出行输出全部字母全部字母数数、数字个数数字个数、空格个数空格个数、文章总字数文章总字数；输出删除某一字输出删除某一字符串后的文章；符串后的文章；第25页，共56页，编

23、辑于2022年，星期六9joseph环（不算）环（不算）任务：编号是任务：编号是1，2，n的的n个人按照顺时针方向围坐一圈，个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值数上限值m，从第一个仍开始顺时针方向自，从第一个仍开始顺时针方向自1开始顺序报数，报到开始顺序报数，报到m时停止报数。报时停止报数。报m的人出列，将他的密码作为新的的人出列，将他的密码作为新的m值，从他在值，从他在顺时针方向的下一个人开始重新从顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人报数，如此下去，直到所有人

24、全部出列为止。设计一个程序来求出出列顺序。全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输出各个人的编号。测试数据：测试数据：m的初值为的初值为20，n=7，7个人的密码依次为个人的密码依次为3，1，7，2，4，7，4，首先，首先m=6，则正确的输出是什么？，则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入要求：输入数据：建立输入处理输入数据，输入m的初值，的初值，n，输入每个人的密码，建立单循环链表。输入每个人的密码，建立单循环链表。输出形式：建立一个输

25、出函数，将正确的输出序列输出形式：建立一个输出函数，将正确的输出序列第26页，共56页，编辑于2022年，星期六数据结构：数据结构：typedefstructNodeintdata;intpassword;structNode*next;Node,*LinkList;基本操作：基本操作：/初始化单链表初始化单链表/给每个人赋密码给每个人赋密码/确定需要处理的人数确定需要处理的人数/确定开始的上限值确定开始的上限值/得到正确的顺序得到正确的顺序/输出结果输出结果第27页，共56页，编辑于2022年，星期六11建立二叉树，已知二叉树的层次序列、先序建立二叉树，已知二叉树的层次序列、先序遍历（遍历（

26、用递归或非递归的方法都可以）用递归或非递归的方法都可以）任务：任务：要求能够输入树的各个结点，并能够输出用不要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；出先序遍历序列的函数；第28页，共56页，编辑于2022年，星期六12哈夫曼编哈夫曼编/译码器译码器任务：任务：建立最优二叉树函数建立最优二叉树函数要求：可以建立函数输入二叉树，并输出要求：可以建立函数输入二叉树，并输出其赫夫曼树。其赫夫曼树。在上交资料

27、中请写明：在上交资料中请写明：存储结构、基本算存储结构、基本算法（可以使用程序流程图）、输入输出、法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；杂度、另外可以提出算法的改进方法；第29页，共56页，编辑于2022年，星期六利用哈夫曼编码进行通信可以大大提高信利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将码系统对待传数据预先编码，在接

28、收端将传来的数据进行译码（复原）。对于双工传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每信道（即可以双向传输信息的信道），每端都需要一个完整的编端都需要一个完整的编/译码系统。试为这译码系统。试为这样的信息收发站写一个哈夫曼码的编样的信息收发站写一个哈夫曼码的编/译码译码系统。系统。第30页，共56页，编辑于2022年，星期六基本要求基本要求一个完整的系统应具有以下功能：一个完整的系统应具有以下功能：（1）I：初始化：初始化（Initialization）。从终端读入字符集大小）。从终端读入字符集大小n，以及以及n个字符和个字符和n个权值，建立哈夫曼树，并将它存于文件

29、个权值，建立哈夫曼树，并将它存于文件hfmTree中。中。（2）E：编码：编码（Encoding）。利用已建好的哈夫曼树（如不）。利用已建好的哈夫曼树（如不在内存，则从文件在内存，则从文件hfmTree中读入），对文件中读入），对文件ToBeTran中中的正文进行编码，然后将结果存入文件的正文进行编码，然后将结果存入文件CodeFile中。中。（3）D：译码：译码（Decoding）。利用已建好的哈夫曼树将文件）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件中的代码进行译码，结果存入文件TextFile中。中。（4）P：打印代码文件：打印代码文件（Print）。将文

30、件）。将文件CodeFile以紧凑格以紧凑格式显示在终端上，每行式显示在终端上，每行50个代码。同时将此字符形式的编码文个代码。同时将此字符形式的编码文件写入文件件写入文件CodePrin中。中。（5）T：打印哈夫曼树：打印哈夫曼树（Treeprinting）。将已在内存中的哈夫曼）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件式的哈夫曼树写入文件TreePrint中。中。第31页，共56页，编辑于2022年，星期六测试数据测试数据（1）利用下面这道题中的数据调试程序。）利用下面

31、这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。，试设计哈夫曼编码。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。字符字符空格空格ABCDEFGHIJKLM频度频度1866413223210321154757153220字符字符NOPQRSTUVWXY

32、Z频度频度5763151485180238181161第32页，共56页，编辑于2022年，星期六13拓扑排序拓扑排序任务：编写函数实现图的拓扑排序。第33页，共56页，编辑于2022年，星期六14学生成绩管理学生成绩管理 实现功能：实现功能：输入、输出、插入、删除、查找、追加、读入、显示、输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。保存、拷贝、排序、索引、分类合计、退出。能实现对学生信息的简单管理。能实现对学生信息的简单管理。具体要求：具体要求：建立一个建立一个4个学生的信息登记表，每个学生的信息包括：学号，姓名，个学生的信息登记表，每个学生的信息

33、包括：学号，姓名，和和3门课程的成绩（门课程的成绩（FOX,C,ENGLISH）。）。程序运行时显示一个简单的菜单，例如：程序运行时显示一个简单的菜单，例如：（1）信息输入（）信息输入（INPUT）（2）总分统计（）总分统计（COUNT）（3）总分排序（）总分排序（SORT）（4）查询）查询(QUERY）其中：其中：（1）对）对4个学生的信息进行输入；个学生的信息进行输入；（2）对每个学生的）对每个学生的3门课程统计总分；门课程统计总分；(3)对对4个学生的总分按降序排序并显示出来；个学生的总分按降序排序并显示出来；(4)查询输入一个学号后，显示出该学生的有关信息；查询输入一个学号后，显示出该

34、学生的有关信息；第34页，共56页，编辑于2022年，星期六数据结构：数据结构：structstudentintnum;/学号学号charname20;/姓名姓名intfoxscore;/fox成绩成绩intcscore;/C语言语言intenglishscore;/英语成绩英语成绩structstudent*next;操作：操作：1.成绩信息输入成绩信息输入;2.统计总分统计总分;3.排序排序;4.查询查询第35页，共56页，编辑于2022年，星期六15停车场管理停车场管理设停车场设停车场（如下图所示）内只有一个可停放几量汽车的狭（如下图所示）内只有一个可停放几量汽车的狭长通道，且只有一个大

35、门可供汽车进出。汽车在停车场内长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车南端，最先到达的第一辆车停放在车场的最北端），若车场内已经停满几量汽车，则后来的汽车只能在门外的便道场内已经停满几量汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆上等候，一旦停车场内有车开走，则排在便道上的第一辆汽车即可开入；当停车场内某车辆要离开时，由于停车场汽车即可开入；当停车场内某车辆要离开时，由于停车场是狭长的通道，在它之

36、后开入车场的车辆必须先退出车场是狭长的通道，在它之后开入车场的车辆必须先退出车场为它让路，待该车辆开出大门外后，为它让路的车辆再按为它让路，待该车辆开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。原次序进入车场。在这里假设汽车不能从便道上开走。试试设计一个停车场管理程序设计一个停车场管理程序（这里只是一个假想的停车场管（这里只是一个假想的停车场管理，并不代表实际的停车场管理）。理，并不代表实际的停车场管理）。第36页，共56页，编辑于2022年，星期六分析：汽车在停车场内进出是按照栈的运分析：汽车在停车场内进出是按照栈的运算方式来实现的，先到的先进停车场；停算方

37、式来实现的，先到的先进停车场；停车场的汽车离开停车场时，汽车场内其它车场的汽车离开停车场时，汽车场内其它汽车为该辆汽车让路，也是按栈的方式进汽车为该辆汽车让路，也是按栈的方式进行；汽车在便道上等候是按队列的方式进行；汽车在便道上等候是按队列的方式进行的。因此，将停车场设计成一个栈，汽行的。因此，将停车场设计成一个栈，汽车让路也需要另一个栈来协助完成，汽车车让路也需要另一个栈来协助完成，汽车进出便道用队列来实现。进出便道用队列来实现。第37页，共56页，编辑于2022年，星期六本设计，栈采用顺序栈结构，队列用链式存储结构。本设计，栈采用顺序栈结构，队列用链式存储结构。存储结构定义如下：存储结构定

38、义如下：#definestacksize10typedefstructsqstackintdatastacksize;inttop;SqStackTp;typedefstructlinked_queueintdata;structlinked_queue*next;LqueueTp;typedefstructLqueueTp*front,*rear;QueptrTp;第38页，共56页，编辑于2022年，星期六停车场管理的算法描述如下：停车场管理的算法描述如下：1）接受命令和车号，若是汽车要进停车场，先判）接受命令和车号，若是汽车要进停车场，先判断停车场栈是否满，若不满，则汽车入栈，否则汽断停

39、车场栈是否满，若不满，则汽车入栈，否则汽车进入便道队列等候。车进入便道队列等候。2）若是汽车要离开停车场，为给汽车让路，将停）若是汽车要离开停车场，为给汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆车出停车场车场栈上若干辆汽车入临时栈，等这辆车出停车场后，临时栈中的汽车出栈，在回到停车场栈，然后后，临时栈中的汽车出栈，在回到停车场栈，然后看便道队列是否为空，若不空则说明有汽车等候，看便道队列是否为空，若不空则说明有汽车等候，从队头取出汽车号，让该车进入停车场栈。从队头取出汽车号，让该车进入停车场栈。3）重复）重复1），），2）直到为退出命令（车号为）直到为退出命令（车号为0或负数）或负数）。

40、第39页，共56页，编辑于2022年，星期六16二叉排序树与文件操作二叉排序树与文件操作功能要求：功能要求：（1）从键盘输入一组学生记录建立二叉排序树；）从键盘输入一组学生记录建立二叉排序树；（2）二叉排序树存盘；）二叉排序树存盘；（3）由文件恢复内存的二叉排序树；）由文件恢复内存的二叉排序树；（4）中序遍历二叉排序树；）中序遍历二叉排序树；（5）求二叉排序树深度；）求二叉排序树深度；（6）求二叉排序树的所有节点数和叶子节点数；）求二叉排序树的所有节点数和叶子节点数；（7）向二叉排序树插入一条学生记录；）向二叉排序树插入一条学生记录；（8）从二叉排序树中删除一条学生记录；）从二叉排序树中删除一

41、条学生记录；（9）从二叉排序树中查询一条学生记录；）从二叉排序树中查询一条学生记录；（10）以广义表的形式输出二叉排序树）以广义表的形式输出二叉排序树第40页，共56页，编辑于2022年，星期六/定义学生记录类型定义学生记录类型structstudentcharnum6;/学号学号intgrade;/成绩成绩;/定义二叉排序树节点值的类型为学生记录类型定义二叉排序树节点值的类型为学生记录类型typedefstudentElemType;/定义二叉排序树的节点类型定义二叉排序树的节点类型typedefstructBSTNodeElemTypedata;StructBSTNode*left;Str

42、uctBSTNode*rchild;BSTNode;第41页，共56页，编辑于2022年，星期六17B_树索引文件的插入、删除和查找树索引文件的插入、删除和查找功能要求：功能要求：1.从键盘输入一组关键字插入从键盘输入一组关键字插入B_树中；树中；2.向向B_树中插入一个关键字；树中插入一个关键字；3.从从B_树中删除一个关键字；树中删除一个关键字；4.从从B_树中查找一个关键字对应记录的位置；树中查找一个关键字对应记录的位置；5.遍历输出遍历输出B_树中所有关键字；树中所有关键字；6.求出一棵求出一棵B_树的深度；树的深度；7.求出一棵求出一棵B_树的节点数；树的节点数；8.内存内存B_树存

43、盘；树存盘；9.由文件中保存的由文件中保存的B_树恢复到内存中；树恢复到内存中；10.清除清除B_树，即收回树，即收回B_树中的所有节点；树中的所有节点；第42页，共56页，编辑于2022年，星期六/定义定义B_树的阶数和特定的最大关键字，可自行设定树的阶数和特定的最大关键字，可自行设定#definem3#defineMAXKEY9999/定义关键字类型为整型定义关键字类型为整型typedefintKeyType;/定义元素类型定义元素类型structElemTypeKeyTypekey;/整型关键字域整型关键字域charrest10；/字符数组域字符数组域;第43页，共56页，编辑于2022

44、年，星期六/定义定义B_树的节点类型树的节点类型structMBNodeintkeynum;/关键字个数域关键字个数域MBNode*parent;/指向父节点的指针域指向父节点的指针域KeyTypekeym+1；/保存保存n个关键字域，个关键字域，下标下标0位置未用位置未用MBNode*ptrm+1;/保存保存n+1个指向子个指向子树的指针域树的指针域Intrecptrm+1;/保存每个关键字对应记保存每个关键字对应记录的存储位置域，下标录的存储位置域，下标0位置未用位置未用;第44页，共56页，编辑于2022年，星期六18散列文件的插入、删除和查找散列文件的插入、删除和查找功能要求：功能要求

45、：（1）初始化三列文件；）初始化三列文件；（2）向散列文件中插入一个元素；）向散列文件中插入一个元素；（3）从散列文件中删除一个元素；）从散列文件中删除一个元素；（4）从散列文件中查找一个元素。）从散列文件中查找一个元素。散列文件通常采用链接法处理冲突，并且散列文件通常采用链接法处理冲突，并且把保存每个单链表表头指针的表头向量用一个把保存每个单链表表头指针的表头向量用一个文件单独存储起来，称此为散列表文件，把所文件单独存储起来，称此为散列表文件，把所有单链表中的结点用一个文件单独存储起来，有单链表中的结点用一个文件单独存储起来，称为散列主文件。称为散列主文件。第45页，共56页，编辑于2022

46、年，星期六 散列文件中每个节点的类型定义为：散列文件中每个节点的类型定义为：structFLNode/散列主文件中的节点类型散列主文件中的节点类型ElemTypedata;/值域值域intnext;/指向下一个节点的指针域指向下一个节点的指针域;其中其中data域用来存储待散列的元素，域用来存储待散列的元素，next域域用来存储下一个同义词元素在散列主文件中的用来存储下一个同义词元素在散列主文件中的存储位置，即所在节点的位置号。存储位置，即所在节点的位置号。第46页，共56页，编辑于2022年，星期六19模拟旅馆管理系统中的床位的分配与回收；模拟旅馆管理系统中的床位的分配与回收；问题描述：问题

47、描述：某旅馆有某旅馆有n个等级的房间，第个等级的房间，第i等级有等级有a个房个房间，每个等级有间，每个等级有b个床位（个床位（=i=n）.模拟旅模拟旅馆个管理系统中床位的分配和回收功能，设计馆个管理系统中床位的分配和回收功能，设计能为单个旅客分配床位，在其离店便回收床位能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。（供下次分配）的算法。第47页，共56页，编辑于2022年，星期六数据结构：数据结构：structRoomIntroomgrade;/房间等级房间等级introomprice;introomnumber;intbedN;/每个等级每个等级i的每个房间有对应等级的每个房

48、间有对应等级i铺床铺床intsex;intpeoplein;intarrtime;room100;数据结构的具体说明：数据结构的具体说明：程序中假设有程序中假设有N（10）个不同等级的房间，每个等级）个不同等级的房间，每个等级i有有对应对应i个房间，每个房有第个房间，每个房有第i铺床，如等级为的房间有铺床，如等级为的房间有个房间，每个房间有铺床并且程序用静态个房间，每个房间有铺床并且程序用静态room100数数组来实现组来实现.第48页，共56页，编辑于2022年，星期六程序设计思路及其测试提示：程序设计思路及其测试提示：（）首先先创建旅馆房间的信息，即对房间信息进行初始化，用函（）首先先创建

49、旅馆房间的信息，即对房间信息进行初始化，用函数数creat()来实现并且创建的信息保存在文件里，每执行一次服务都来实现并且创建的信息保存在文件里，每执行一次服务都对文件重新写入，保持着最近更新的数据对文件重新写入，保持着最近更新的数据（）先令（）先令t=1，满足条件，紧接着输入，满足条件，紧接着输入s的值，第一次输入的值，第一次输入s的值的值时输入非的数，满足进行订房服务的条件，接着进行旅客订房时输入非的数，满足进行订房服务的条件，接着进行旅客订房登记服务，需要注意的是本程序只适合对单个旅客进行服务登记服务，需要注意的是本程序只适合对单个旅客进行服务（）根据程序的提示，一直对输入（）根据程序的

50、提示，一直对输入s的值进行测试，如果输的值进行测试，如果输入入s的值为则进行退房服务，接着输入的值为则进行退房服务，接着输入t的值，如果输入的值，如果输入t的值的值非，则可以继续进行服务，接下去是输入非，则可以继续进行服务，接下去是输入s的值，如果输入的值，如果输入的的s为，则可以进行退房服务，否则进行订房登记服务为，则可以进行退房服务，否则进行订房登记服务（）程序中实现连续多次订房服务是利用（）程序中实现连续多次订房服务是利用输入输入s的非来实现的，的非来实现的，如果想连续多次进行退房服务，则在输入如果想连续多次进行退房服务，则在输入t（非）之后，输入（非）之后，输入s的值的值为，循环这种操