数据结构课程设计

《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。

第、周，每周四下午13:30—15:05；第周，每周二上午9:45—12:00在三教121机房上机。

每位同学须**性表、栈和队列、树和图三个部分中各选一题（共三题）按以下要求完成课程设计：

1、设计、调试、运行源程序。

2、通过老师的测试及验收。

3、完成实验报告。

joseph环】

问题描述：编号是1，2，……n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

要求：利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列。

长整数四则运算】

问题描述：设计一个实现任意长的整数进行加法运算的演示程序。*基本要求：

利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1) (2^15 - 1)。输入和输出形式：

按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

测试数据：1）0；0；应输出“0”。

2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。

3）-9999,9999；1,0000,0000,0000；应输出“999

4）1,0001,0001；-1,0001,0001；应输出“0”。

5）1,0001,0001；-1,0001,0000；应输出“1”。

6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。

7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。

实现提示：1）每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。

2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。

选做内容。实现长整数的四则运算。

马踏棋盘】问题描述：将马随机放在国际象棋的8x8棋盘bo阿rd[0..7,0..

7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8x8的方阵输出之。

测试数据：由读者指定，可自行指定一个马的初始位置。

实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并**每次选择位置的“最佳策略”，以减少回溯的次数。

魔王语言解释】

[问题描述]

有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释**能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：

1） α1β2…βm

2）（θ1δ2…δn)－>nθδn－1… θ1θ

在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释**能听得懂的话。

基本要求]

用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。

1）b －>tada

2）a －>sae

测试数据]

b(ehnxgz)b解释成tsaedsaeezegexenehetsaedsae

若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。

[小写字母与汉字对应关系]

t d s a e z g x n h

天地上一只鹅追赶下蛋恨

重言式判别】

图的邻接矩阵存储结构建立】

问题描述：建立图的邻接矩阵存储结构（图的类型可以是有向图或有向网、无向图或无向网，学生可以任选一种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的dfs及bfs次序。

校园导游咨询】

问题描述]

1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

3）为来访客人提供图中任意景点相关信息的查询。

测试数据]由读者根据实际情况指定。

kruskal算法实现最小生成树问题】

数据结构》课程设计报告。

2024年9月22日。

目录。1 课程设计的目的x

2 需求分析x

3 课程设计报告内容x

1、概要设计x

2、详细设计x

3、调试分析x

4、用户手册x

5、测试结果x

6、程序清单x

4 小结x5 参考文献x

1、课程设计的目的。

1）熟练使用c语言编写程序，解决实际问题；

2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

2、需求分析。

1、任务：通过此系统可以实现如下功能：

1）输入航班信息：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）

2）输出航班信息：输出航班号、起始站、终点站、订票时间、机票数。

3）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；

4）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；

5)退票：可退票，退票后修改相关数据文件；

客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

6)修改航班信息：当航班信息改变可以修改航班数据文件

2、测试数据。

输入航班信息：

航班号起始站终点站时间机票数

1234 合肥北京 2010 9 25 5

1256 合肥上海 2010 9 24 2

1325 合肥南京 2010 9 26 3

分别实现航班信息的修改、查询、输出等功能。

3、课程设计报告内容。

概要设计。1）在分析题目要求的基础上，我首先设计了一个结构体，定义如下。

struct air{

int num;

char start[20];

char over[20];

char time[10];

int count;

s[n];存储订票系统的信息。

2）基本操作：

void input();输入航班信息。

void print();输出航班信息。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了