数据结构课程设计_—_通讯录的制作

《数据结构课程设计_—_通讯录的制作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构课程设计》DataStructureCourseDesign一、课程的性质、教学目的《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。二、实验（上机）时间、地点第4,5,6,7,8,9,10,12,13,14周，每周一晚上18:30—21:10在一教南一楼机房上机。三、课程设计要求每位同学须在线性表、栈和队列、树和图三个部分中各选一题（共

2、三题）按以下要求完成课程设计：1、设计、调试、运行源程序。2、通过老师的测试及验收。3、完成实验报告。四．设计题1、线性表部分【joseph环】*问题描述：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。*要求：利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。*测试数据：m的初

3、值为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,32

4、11；应输出“-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进制存放，

5、在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。选做内容实现长整数的四则运算。2、栈和队列部分【马踏棋盘】*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵

6、输出之。*测试数据：由读者指定,可自行指定一个马的初始位置。*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。【魔王语言解释】[问题描述]有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α－>β1β2…βm（2）（θδ1δ2…δn)－>θδnθδn－1…θδ1θ在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释

7、系统，把他的话解释成人能听得懂的话。[基本要求]用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。（1）B－>tAdA（2）A－>sae[测试数据]B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅