《数据结构课程设计》大纲.docx
《《数据结构课程设计》大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构课程设计》大纲.docx（30页珍藏版）》请在冰点文库上搜索。
《数据结构课程设计》大纲
《数据结构课程设计》大纲
一、《数据结构课程设计》的目标
《数据结构》是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。
本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术。
本课程将为整个专业的学习以及软件设计水平的提高打下良好的基础。
《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践，设置《数据结构课程设计》实践环节十分重要。
本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。
实验学时为36。
二、《数据结构课程设计》的要求
设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。
通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
三、《数据结构课程设计》的内容
每5人组成一个小组，每个小组从下面题目中随机抽取1个题目，分工协作，共同完成。
1.算术表达式求值
2.一元稀疏多项式计算器
3.航空客运订票系统
4.电梯模拟
5.迷宫问题
6.长整数四则运算
7.简单行编辑程序
8.多维数组
9.校园导游程序
10.银行业务模拟
11.教学计划编制问题
12.全国交通咨询模拟
13.在国际象棋盘上马遍历问题；
14.银行业务活动的模拟；
15.程序分析；
16.哈夫曼编/译码器；
17.学籍管理系统；
18.图书管理系统（要求B树建立书号索引）。
四、《数据结构课程设计》的考核方式
采用上机情况、程序质量、实习报告相结合的形式，满分为100分。
1．上机情况（30%）
包括出勤情况、调试表现。
2．程序质量（50%）
3．实习报告（20%）
设计大纲实习题
校园导游程序
[问题描述]
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。
要求能够回答有关景点介绍、游览路径等问题。
[基本要求]
（1）查询各景点的相关信息；
（2）查询图中任意两个景点间的最短路径。
（3）查询图中任意两个景点间的所有路径。
（4）增加、删除、更新有关景点和道路的信息。
[选作内容]
（1）求多个景点的最佳（最短）游览路径。
（2）区分机动车道和人行道。
（3）实现导游图的仿真界面。
员工管理系统
[问题描述]
每个员工的信息包括：
编号、姓名、性别、出生年月、学历、职务、电话、住址等。
系统能够完成员工信息的查询、更新、插入、删除、排序等功能。
[基本要求]
（1）排序：
按不同关键字，对所有员工的信息进行排序。
（2）查询：
按特定条件查找员工。
（3）更新：
按编号对某个员工的某项信息进行修改。
（4）插入：
加入新员工的信息。
（5）删除：
按编号删除已离职的员工的信息。
[选作内容]
实现图形用户界面。
算术表达式求值
[问题描述]
一个算术表达式是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。
假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：
#（7+15）*（23-28/4）#。
引入表达式起始、结束符是为了方便。
编程利用“算符优先法”求算术表达式的值。
[基本要求]
（1）从键盘读入一个合法的算术表达式，输出正确的结果。
（2）显示输入序列和栈的变化过程。
[选作内容]
扩充运算符集合。
引入变量操作数。
操作数类型扩充到实数。
括号匹配的检验
[问题描述]
假设表达式中允许有两种括号：
圆括号和方括号，其嵌套的顺序随意，即CC或[（[][]）]等为正确格式，[（]）或（（（]均为不正确的格式。
检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。
例如：
考虑下列的括号序列：
[ （ [ ] [ ] ） ]
1 2 3 4 5 6 7 8
当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，……，依次类推。
可见这个处理过程正好和栈的特点相吻合。
[基本要求]
设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中，若是右括号，则或者是和当前栈顶的括号相匹配，或者是不合法的情况，输出“此串括号匹配不合法”。
在初始和结束时，栈应该是空的。
[测试数据]
输入#（[]（））#，结果“匹配”
输入#[（）]#，结果“此串括号匹配不合法”
#为起始和结束标志。
设计指导书概述
“数据结构”是计算机专业一门重要的专业技术基础课程。
本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍了常用的多种查找和排序技术，并对进行性能分析和比较，内容非常丰富。
本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础，数据结构课程是计算机专业的一门核心的关键性课程。
这门课程由于以下原因，使得掌握具有较大难度：
●内容丰富，学习量大，给学习带来困难；
●贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；
●所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；在解答问题时也会因此而困难重重。
●隐含在各部分的技术和方法丰富，也是学习的重点和难点。
由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分重要。
为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，通过要求完成对一些典型问题的分析及其实现的各环节,使学生掌握所用到的一些技术,提高知识面。
数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态变量及链表，算法的编码，递归技术，与特定问题相关的技术等。
侧重于与线性链表、二叉树和树、图结构、数组结构相关的算法的设计。
其中侧重于（或若干种）基本算法或解题方法，并以此为基础进行推广提高的基础。
通过实验内容的训练，突出构造性思维训练的特征，提高学生组织数据与进行编写大型程序能力。
上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常，实习题中的问题比平时的习题复杂得多，也更接近实际。
实习着眼于原理与应用的结合点，使读者学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。
平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作,以至一整套软件工作规范的训练和科学作风的培养。
此外，还有很重要的一点是：
机器是比任何教师都严厉的检查者。
为了达到上述目的，本书安排了6个主实习单元，除实习0作为预备练习之外，其它各单元的训练重点在于基本的数据结构，而不强调面面俱到。
各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及几部分教学内容。
在每个实习单元中安排有难度不等的2—5个实习题，每个题目的题号之后标有难度系数，对于特别推荐题也作了标记。
与习题的情况类似，在一个单元之内比较题目难度才有意义。
此外，难度系数是根据题目的基本要求而给出的。
每个实习题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等5个部分组成。
问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；
基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；
测试数据部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；
实现提示对实现中的难点及其解法思路等问题作了简要提示；
选做内容向那些尚有余力的读者提出了更严峻的挑战，同时也能开拓其他读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。
不难发现，这里与传统的做法不同，题目设计得非常详细。
会不会限制读者的想象力，影响创造力的培养呢?
回答是：
软件发展的一条历史经验就是要限制程序设计者在某些方面的创造性，从而使其创造能力集中地用到特别需要创造性的环节之上。
实习题目本身就给出了问题说明和问题分解求精的范例，使读者在无形中学会模仿，它起到把读者的思路引上正轨的作用，避免坏结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学检查。
题目设计策略是：
一方面使其难度和工作量都较大，另——方面给读者提供的辅助和可以模仿的分也较多。
当然还应指出的是，提示的实现方法未必是最好的，读者不应拘泥于此，而应力开发更好的方法和结构。
在每个实习单元中，每人可以从中选做一个实习题。
类似于习题，本题集也为每个实习题注了一个难度从①至⑤的难度系数，同样，它也只是一个相对的量，只对同一单元内的实习题起到区别难度的作用，读者无须对不同单元内的实习题进行难度比较，事实上，如果实习1中难度为③的题尚感困惑，在经过几个练习之后，你会对实习6中难度为③的题感到轻而易举。
经验表明，如果某题的难度略高于自己过去所对付过的最难题目的难度，则选择此题能够带来最大的收益，切忌过分追求难题。
较大的题目，或是其他题目加上某些选做款项则适合于多人合作。
在实现的时候应注意，要尽量减少依赖于具体机器计算环境的用法，例如，某些机器上的PascaI语言编译程序版本允许语言中出现“EXIT”过程调用，作用是终止程序的执行。
若使用，也应在注释中指出。
这样得出的程序易于在不同机器上运行（有好的可移植性），而于要目的在于培养良好的习惯。
Pascal语言是结构化程序设计语言，具有递归能力，可移植性也较好，是特别推荐的实现语言。
本书的一个特点是为实习制定了严格的规范（见下一节）。
一种普遍存在的错误观念是，调试程序全凭运气。
学生花2个小时的机上时间只找出一个错误，甚至一无所获的情况是常见的。
其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误有重要性性，也不知道应该如何努力。
实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。
严格按照实习步骤规范进行实习不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作用。
在每个实习单元提供了一个完整的实习报告示例，在起到实习报告规格范例作用的同时，还隐含地提供了很多有益的东西，比如基于数据类型的系统划分方法；递归算法设计方法和技巧；对于有天然递归属性的问题如何构造非递归算法；以及所提倡的程序设计风格等等。
但从另一个方面看，计算机学科在不断发展，可以使用的语言工具越来越丰富，在本书中的实习示例还只是应用面向过程的语言进行设计和编写程序，同样的实习题，请教也可以用面向对象的语言来实现。
希望书中的实习报告示例能起到一个抛砖引玉的作用，以迎来读者更多更优良的设计范例。
实习步骤
随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。
然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。
一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。
虽然数据结构课程中的实习题的复杂度远不如（从实际问题中提出来的）一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的5个步骤：
1．问题分析和任务定义
通常，实习题目的陈述比较简洁，或者说是有模棱两可的含义。
因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。
注意：
本步骤强调的是做什么，而不是怎么做。
对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。
例如：
输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。
这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。
2．数据类型和系统设计
在设计这一步骤中需分逻辑设计和详细设计两步实现。
逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。
在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。
作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。
详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类Pascal语言写出过程或函数形式的算法框架。
在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。
3．编码实现和静态检查
编码是把详细设计的结果进一步求精为程序设计语言程序。
程序的每行不要超过60个字符。
每个过程（函数）体，即不计首部和规格说明部分，一般不要超过40行。
最长不得超过60行，否则应该分割成较小的过程（函数）。
要控制1D1语句连续嵌套的深度。
其他要求参见第一篇的算法书写规范。
如何编写程序才能较快地完成调试是特别要注意的问题。
对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。
然而，不管你是否写出编码的程序，在上机之前，认真的静态检查却是必不可少的。
多数初学者在编好程序后处于以下两种状态之一：
一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。
这两种态度是极为有害的。
事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。
上机动态调试决不能代替静态检查，否则调试效率将是极低的。
静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。
如果程序中逻辑概念清楚，后者将比前者有效。
4．上机准备和上机调试
上机准备包括以下几个方面：
（1）高级语言文本（体现与编译程序用户手册）的扩充和限制。
例如，有些Pascal编译程序限制FOR语句的循环控制变量为局部简单变量等。
（2）如果用Pascal语言，要特别注意平时惯用的类Pascal语言与标准Pascal语言之间的细微差别。
（3）熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。
（4）掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。
“磨刀不误砍柴工”。
计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG调试程序。
上机调试程序时要带一本高级语言教材或手册。
调试最好分模块进行，自底向上，即先调试低层过程或函数。
必要时可以另写一个调用驱动程序。
这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。
在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。
调试中遇到的各种异常现象往往是预料不到的，此时不应“苦思具想”，而应动手确定疑点，通过修改程序来证实它或绕过它。
调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。
5．总结和整理实习报告
实习报告规范
实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下7个内容：
1．需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？
并明确规定：
（1）输入的形式和输入值的范围；
（2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：
包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2．概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
3．详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法（伪码算法达到的详细程度建议为：
按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数和过程的调用关系图。
4．调试分析
内容包括：
a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；
b．算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和
改进设想；
c．经验和体会等。
5．用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。
6．测试结果
列出你的测试结果，包括输入和输出。
这里的测试数据应该完整和严格，最好多于需求分析中所列。
7．附录
带注释的源程序。
如果提交源程序软盘，可以只列出程序文件名的清单。
在以下各实习单元中都提供了实习报告实例。
值得注意的是，实习报告的各种文档资料，如：
上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写（当然可以也应该最后用实验报告纸誊清或打印）。
实习题目
实习○抽象数据类型
三元组ADT
[问题描述]
设计实现抽象数据类型“三元组”。
每个三元组由任意三个实数的序列构成，基本操作包括：
创建一个三元组，取三元组的任意一个分量，置三元组的任意一个分量，求三元组的最大分量，求三元组的最小分量，两个三元组的对应分量相加或相减，给三元组的各分量同乘一个比例因子，显示三元组，销毁三元组等。
[基本要求]
实现创建一个三元组，取三元组的任意一个分量，置三元组的任意一个分量，求三元组的最大分量，求三元组的最小分量，显示三元组等基本操作。
[测试数据]
由学生任意指定。
[实现提示]
用结构体封装“三元组”的三个分量，并利用typedef对结构体或结构体指针重新命名。
注意：
如果要实现销毁三元组，则应利用typedef对结构体指针重新命名，并使用C语言的动态分配库函数。
[选作内容]
实现两个三元组的对应分量相加或相减，给三元组的各分量同乘一个比例因子，销毁三元组等操作。
有理数ADT
[问题描述]
设计实现抽象数据类型“有理数”。
[基本要求]
实现有理数的加法、减法，以及求有理数的分子、分母等基本操作。
[测试数据]
由学生依据软件工程的测试技术自己确定。
注意测试边界数据，如有理数0。
[实现提示]
用结构体封装与“有理数”对应的分子和分母。
[选作内容]
实现有理数的乘法、除法运算。
复数ADT
[问题描述]
设计实现抽象数据类型“复数”。
[基本要求]
实现复数的加法、减法、乘法，以及求复数的实部、虚部等基本操作。
[测试数据]
由学生依据软件工程的测试技术自己确定。
注意测试边界数据，如复数0。
[实现提示]
用结构体封装与“复数”对应的实部、虚部。
[选作内容]
实现复数的除法运算。
实习一线性表
本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。
通过本次实习还可帮助读者复习高级语言的使用方法。
城市链表
[问题描述]
将若干城市的信息，存入一个带头结点的单链表。
结点中的城市信息包括：
城市名，城市的位置坐标。
要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。
[基本要求]
（1）给定一个城市名，返回其位置坐标；
（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。
[测试数据]
由学生依据软件工程的测试技术自己确定。
注意测试边界数据。
约瑟夫环
[问题描述]
约瑟夫（Joeph）问题的一种描述是：
编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
[基本要求]
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
[测试数据]
m的初值为20；密码：
3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
[实现提示]
程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。
设n≤30。
[选作内容]
向上述程序中添加在顺序结构上实现的部分。
线性表的逆置
[问题描述]
分别以不同存储结构实现线性表的就地逆置。
线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,…,an）逆置为（an，an-1，…，a2，a1）。
[基本要求]
用顺序存储结构实现线性表的就地逆置，并将结果输出。
[测试数据]
由学生依据软件工程的测试技术自己确定。
注意测试边界数据，如空表。
[实现提示]
设三个连续的指针，分别指向当前结点、当前结点的前趋、当前结点的后继。
[选作内容]
利用单链表作为存储结构。
首先先建立线性表的带头结点的单链表表示形式，之后在不借助辅助结点空间的情况下实现单链表的逆置，并将结果输出。
长整数运算
[问题描述]
设计一个程序实现两个任意长的整数求和运算。
[基本要求]
利用双项循环链表实现长整数的存储，每个结点含一个整型变量。
任何整型变量的范围是 -（215-1）~（215-1）。
输入和输出形式：
按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。
[测试数据]
（1）0；0；应输出“0”。
（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。
（3）-9
升级会员 