《数据结构课程设计报告模板.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告模板.doc（32页珍藏版）》请在三一办公上搜索。
1、课程设计说明书课程名称： 数 据 结 构 与 算 法 专业： 计算机科学与技术 班级： 103013 姓名： 徐粤玲 学号： 03 指导教师： 苑擎飏 成绩： 完成日期： 2012 年 1 月 12 日任 务 书题目：黑白棋系统设计内容及要求：1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。2.课程设计要求实现黑白两色棋子的对峙开发环境：vc+6.0实现目标：（1） 熟
2、悉的运用c语言程序编写代码。（2） 能够理清整个程序的运行过程并绘画流程图（3） 了解如何定义局部变量和整体变量；（4） 学会上机调试程序，发现问题，并解决（5） 学习使用C+程序来了解游戏原理。（6） 学习用文档书写程序说明摘 要本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量
3、减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。关键词：黑白棋 编程 设计s目 录1.引 言42.课题分析73.具体设计过程83.1设计思路83.2程序设计流程图83.3.函数实现说明124.程序运行结果145.软件使用说明186.结论21参 考 文 献23附录：源代码241.引 言数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法：Sartaj Sahni在他的数据结构、算法与应用一书
4、中称：“数据结构是数据对象，以及存在于该对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。Clifford A.Shaffer在数据结构与算法分析一书中的定义是：“数据结构是 ADT（抽象数据类型Abstract Data Type） 的物理实现。” Lobert L.Kruse在数据结构与程序设计一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储
5、细节以及运算的实现。数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。 1.1. 重要意义一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数
6、据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。 1.2. 研究内容 在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐欧克努特教授
7、开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理 。 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系
8、统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找
9、出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据的不可分割的最小单位。有两类数据元素：一类是不可分割的原子型数据元素，如：整数5，字符 N 等；另一类是由多个
10、款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出生日期又可以由三个数据项：年、月和日组成，则称出生日期为组合项，而其它不可分割的数据项为原子项。关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 主 关键字，否则称之为 次 关键字。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现
11、在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。2.课题分析编写一个黑白棋游戏的C程序，包括以下功能：初始状态：在一个8*8的棋盘中央交叉排放黑白棋子各两枚，白棋先走。（1）每个棋手下棋时，摆子的位置必须是以自己的棋子能包围住对方一个或多个棋子，被包围住的对方棋子将成为自己的棋子。包围的方向可以是上下左右以及斜线8个方向，只要能连成一线即可。（2）当轮到某一个棋手下子，但是他没有可以包围对方棋子的位置时，他必须停步，让对方走棋，直到他可以走为止。（3）当棋盘上一方的棋子为0或者下满64格，游戏结束，棋子少者输。（
12、4）当一局结束后，可以选择y/n选择是否继续下一局游戏3.具体设计过程3.1设计思路 程序界面应是一个二维平面图，所以数据的表示用二维数组，数组两个下标可以表示棋盘上的位置，数组元素的值代表棋格中的状态，共有三种情况，分别是空格、黑棋和白棋。这样给数组元素的取值设定为0、1、2，其中0代表空格，*代表白色棋子，0代表黑色棋子。这样程序的主要工作是接收棋手按键操作，一旦接收到回车键，说明棋手摆子，先判断是不是有效位置，也就是能不能包围住对方棋子，如果能，便为棋子所在的位置往上下、左右、左上、左下、右上、右下8个方向寻找被包围住的所有棋子（必须是连续的，中间不能有空格），将这些被包围住的对方棋子都
13、变成自己的棋子，然后对当前棋盘中的黑白棋个数进行统计并输出结果。如果没有这样的位置可以落子，则停步，让对方走棋，重复上述步骤，直到游戏结束。3.2程序设计流程图 系统功能流程图，首先我们先初始化系统功能，定义各项函数，并初始化一些参数变量。然后绘制棋盘。然后按enter键进行游戏，当我们输入一个横纵坐标时，系统会判断此坐标是否合法，若合法则落子，并翻转相应的棋子。最终判断双方的胜负情况。如图3.1所示：开 始结 束 游 戏初始化系统功能画出棋盘按键操作是否为有效位置？按键是否为回车键？落 棋变成自己的棋子统计黑白棋个数，输出成绩。输出胜利者信息关闭图形系统否是否是图3.1 程序整体流程图图3.
14、2为下棋流程图。首先我们进入游戏，然后由玩家先落子。先判断落子位置是否已经有棋子了，若有则重新输入。若没有，再判断是否能够引起棋子的翻转，若可以则落子，将对方的棋子变成自己的棋子，反之换由对方下子。当一方走完之后，换另一方走。如下图所示： 开始玩家走棋落子位置是否有棋子是否引起棋盘变化落棋变为自己的我棋，得分换电脑走棋结束是否否是 图3.2 人机对战模块流程图 图3.3为成绩运行流程图，当棋盘上的每一个格子都有棋子的时候，系统将遍历棋盘，然后根据棋盘上棋子的花色分别代表的是哪一方，在哪一方的成绩上+1.遍历完后，判断双方分数的大小，并输出结果。如下图所示：开始输出初始成绩Ifij=0Ifij=
15、*玩家score+1电脑score+1玩家score电脑scorecscorescorescore玩家赢电脑赢否是是是否否图3.3 成绩输出模块程序流程图3.3.函数实现说明(1)void main()主函数功能：在主函数中，首先定义使用到的常数、全局变量、函数原型说明。盘状态用数组 a88，初值为0，表示空格。函数的实体部分，开始初始化图形系统，然后通过调用函数display()先画出棋盘，调用make_move()和computer_move()进行人机对战函数开始游戏，一旦游戏结束后，关闭图形系统，程序结束。(2)void display（）棋盘绘制函数功能：函数display()通过f
16、or循环，对棋盘界面进行了绘制用法：此函数调用方式为void display(char boardSIZE);说明：参数是一个二维数组，size为定义的长度。值为8返回值：无(3)int valid_moves（） 有效步骤函数功能：通过此函数来判断电脑或玩家下的棋子是否是有效的。用法：此函数调用方式为int valid_moves(char boardSIZE,int movesSIZE,char player);说明：char boardSIZE为棋盘，int movesSIZE为玩家输入的横纵坐标，char player为判断的玩家为电脑还是人返回值： int(4)void make_m
17、ove（）下棋函数功能：定义坐标，控制变量并通过for循环来判断翻转棋子。达到同一方向上将对方 的棋子翻转为自己的棋子。用法：此函数调用方式为void make_move(char boardSIZE,int row,int col,char player)说明：int row,int col分别代表其中的横纵坐标返回值： 无(5)void computer_move()电脑下棋函数功能： 主函数通过调用该函数，获取电脑的下棋位置。该函数分别又调用make_move(); valid_moves();new_score=best_move();函数，以获取最佳的下棋位置用法：此函数调用方式为v
18、oid computer_move(char boardSIZE,int movesSIZE,char player);说明：int movesSIZE为玩家输入的横纵坐标，char player为判断的玩家为电脑 还是人返回值： 无(6)int get_score()分数获取函数的声明功能：用此函数来获取电脑和玩家的分数，以便判断最终的胜负用法：此函数调用方式为(char boardSIZE,char player);说明：char boardSIZE是一个二维数组，来控制棋盘变量。char player是代表玩 家的一个参数返回值： int(7)int best_move（）功能：best
19、_move是电脑下子最佳位置判断的一个函数，通过不断地比较，用了两次 for循环，并遍历棋盘上*的个数，来获取最佳位置。用法：此函数调用方式为int best_move(char boardSIZE,int movesSIZE, char player);说明：同void computer_move()返回值： int4.程序运行结果 图4.1为初始界面,当我们选择运行程序时，便会出现如下图的界面。根据上面文字的内容，我们可以了解游戏的规则。并按enter键，进行游戏。如下图所示：图4.1初始界面图 图4.2为进入游戏后的首界面，下图是按enter键之后进入的游戏界面。第一局游戏时，玩家的棋子
20、用0代替，电脑的棋子用*代替。初始界面中，棋盘上便已有了在棋盘正中央的相互交叉的棋子。这是初始界面的一种情况。如下图所示：图4.2游戏首界面图 图4.3为运行过程中，双方对峙的截图。在游戏过程中，轮到玩家下棋的时候，系统会出现：输入坐标的提示，此时，我们的输入方式是第一个为数字，代表棋盘的横坐标，第二个为字母，代表棋盘的纵坐标，中间无空格。如下图所示：图4.3对峙过程图 图4.4为对峙结束后，得到分值的结果图。最后，系统会提示，是否要重新开始游戏，我们可以通过y/n选择是否继续。如果选择y系统将会开始一局新的游戏，并初始化棋盘。若输入n，系统将不再进行游戏，退出。如下图所示：图4.4双方对峙结
21、果图5.软件使用说明黑白棋是一款娱乐型的游戏，在与锻炼人的脑力和反应能力的。在本程序中，先切换到相应的界面下，然后根据提示来完成下一步操作。在本程序中纵坐标是数字，横坐标是字母。根据坐标轴的性质来确定每一步棋的位置。并根据与之相对应的提示来完成结果。例如：电脑无棋可走，这是一步无效操作等。图5.1为程序进入游戏后的初始界面图5.1程序初始界面图 下图为图5.2，是程序运行过程中的截图。当我们输入1a是，提示我们无效，请重新输入，当输入3f是，亦是如此。此程序过程是输入不合法的过程。在做了相应的操作后，再继续操作。玩家一定要根据提示来进行下一步操作，所以上图的正确坐标是6e。图5.2无效运行的过
22、程图 图5.3是玩家要尽可能的使盘上的的子来变成己方的，避免不必要的损失。有是电脑会没有棋可走，你可以在继续走！图5.3无棋可走情况图6.结论课程设计是培养学生综合运用所学知识 ,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对我们的实际工作能力的具体训练和考察过程.随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握程序开发技术是十分重要的，而C语言又是最常见，功能最强大的一种高级语言，因此做好C语言课程设计是十分必要的。回顾起此次课程设计，至今我们仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整半个月的日子里，
23、可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体，指针，链表通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。我做的是黑白棋的课程设计，虽
24、然是很简单的一个小的程序，但对我一个初学者来说却是一个很大的困难。更加是第一次做课程设计，所以第一天下午在机房做了一个下午却丝毫没有进展，最主要是不知从何开始，这个时候才知道上课老师们不厌其烦的教导是多么的宝贵，这个时候才后悔上课的时候没有认真的听讲。可是现在一切都晚了，还好时间还算是充裕，只好拿出书本重新复习一下。特别是结构体，绘制棋盘的部分，几乎是一片空白，不知从何着手。不过经过几天的努力，大体上把课本上的知识点看了一遍，知识点也都基本是撑握了，所以一下一步就是开始正式的编程序了。不过毕竟是个新手，还是不知如何下手，于是就在网上下了一篇类似的程序，经过仔细的研究，终于读懂了C语言编程的基本
25、过程和方法。经过一波三折，终于开始正式编程。编程是一件很枯燥很无聊的事情，但是出于完成作业，得到学分的压力，还必须强破自己坚持下去，按照老师所说的模块化思想，分部分的进行编写。而且编程是一件高精度、模范化的事情，稍有疏乎都会影响全局，也可能因为某一处的小的错误而导致整个程序的无法运行。所以认真仔细就是非常重要的了。开始的时候真的感觉编程是一件很无聊的事情，不过当一个程序运行成功的时候那种喜悦是无法言语的，那种成就感是无法比拟的。又经过几天的努力，终于把程序完成了，尽管程序还是有很多错误和漏洞，不过还是很高兴的。无论如何是自己的劳动成果，是自己经过努力得到的成绩，同时也是学习C语言的一次实践作业
26、，自己进步的证明。通过这次课程设计，使我对C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对C语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。 在课程设计过程中，收获知识，提高能力的同时，我也学到了很多人生的哲理，懂得怎
27、么样去制定计划，怎么样去实现这个计划，并掌握了在执行过程中怎么样去克服心理上的不良情绪。因此在以后的生活和学习的过程中，我一定会把课程设计的精神带到生活中，不畏艰难，勇往直前！参 考 文 献 1 谭浩强.C程序设计（第三版），清华大学出版社，2005.72 郭翠英.C语言课程设计案例精编, 中国水利水电出版社,2004.33 朱振元.数据结构（面向对象语言描述），清华大学出版社，2004.24 张翔.C语言函数大全，电子工业出版社，2002.45徐金梧.TURBO C实用大全，机械工业出版社，1996.5附录：源代码#include #include #define SIZE 8void di
28、splay(char boardSIZE);int valid_moves(char boardSIZE,int movesSIZE,char player);void make_move(char boardSIZE,int row,int col,char player);void computer_move(char boardSIZE,int movesSIZE,char player);int get_score(char boardSIZE,char player);int best_move(char boardSIZE,int movesSIZE,char player);vo
29、id main() char boardSIZESIZE=0; int movesSIZESIZE=0; int row=0; int col=0; int no_of_games=0; int no_of_moves=0; int invalid_moves=0; int comp_score=0; int user_score=0; char y=0; char x=0; char again=0; int player=0;printf(玩法说明n);printf(1.开辟新局者持黑子，加入者持白子。n);printf( 我先执白棋 - (*)n 你执黑棋 - (0).n);printf
30、(n祝你好运! 请按enter键，进行游戏.n);scanf(%c,&again); do player=+no_of_games%2; no_of_moves=4; for(row=0;rowSIZE;row+) for(col=0;col=0&y=0&xSIZE&ySIZE&movesxy) make_move(board,x,y,0); no_of_moves+; break; else printf(不是有效位置，请重新输入。n); else if(+invalid_moves2) fflush(stdin); printf(n没有可下位置，电脑下棋。n); scanf(%c,&aga
31、in); else printf(n没有多余位置，本局游戏结束。n); else if(valid_moves(board,moves,*) invalid_moves=0; computer_move(board,moves,*); no_of_moves+; else if(+invalid_moves2) printf(n没有可下位置，你下棋。n); else printf(n没有多余位置，本局游戏结束。n); while(no_of_movesSIZE*SIZE&invalid_moves2); display(board); comp_score=user_score=0; for(
32、row=0;rowSIZE;row+) for(col=0;colSIZE;col+) comp_score+=boardrowcol=*; user_score+=boardrowcol=0; printf(最后分数：); printf(电脑： %dt玩家： %dnn,comp_score,user_score); fflush(stdin); printf(你还想玩一次吗？(y/n):); scanf(%c,&again); while(tolower(again)=y); printf(n谢谢使用此游戏。n);void display(char boardSIZE) int row=0;
33、 int col=0; char col_label=a; printf(n ); for(col=0;colSIZE;col+) printf( %c,col_label+col); printf(n); for(row=0;rowSIZE;row+) printf( +); for(col=0;colSIZE;col+) printf(-+); printf(n%2d|,row+1); for(col=0;colSIZE;col+) printf( %c |,boardrowcol); printf(n); printf( +); for(col=0;colSIZE;col+) print
34、f(-+); printf(n);int valid_moves(char boardSIZE,int movesSIZE,char player) int rowdelta=0; int coldelta=0; int row=0; int col=0; int x=0; int y=0; int no_of_moves=0; char opponent=(player=0)?*:0; for(row=0;rowSIZE;row+) for(col=0;colSIZE;col+) movesrowcol=0; for(row=0;rowSIZE;row+) for(col=0;colSIZE
35、;col+) if(boardrowcol!= ) continue; for(rowdelta=-1;rowdelta=1;rowdelta+) for(coldelta=-1;coldelta=1;coldelta+) if(row+rowdelta=SIZE| col+coldelta=SIZE| (rowdelta=0&coldelta=0) continue; if(boardrow+rowdeltacol+coldelta=opponent) x=row+rowdelta; y=col+coldelta; for(;) x+=rowdelta; y+=coldelta; if(x=
36、SIZE|y=SIZE) break; if(boardxy= ) break; if(boardxy=player) movesrowcol=1; no_of_moves+; break; return no_of_moves;void make_move(char boardSIZE,int row,int col,char player) int rowdelta=0; int coldelta=0; int x=0; int y=0; char opponent=(player=0)?*:0; boardrowcol=player; for(rowdelta=-1;rowdelta=1
37、;rowdelta+) for(coldelta=-1;coldelta=1;coldelta+) if(row+rowdelta=SIZE| col+coldelta=SIZE| (rowdelta=0&coldelta=0) continue; if(boardrow+rowdeltacol+coldelta=opponent) x=row+rowdelta; y=col+coldelta; for(;) x+=rowdelta; y+=coldelta; if(x=SIZE|y=SIZE) break; if(boardxy= ) break; if(boardxy=player) wh
38、ile(boardx-=rowdeltay-=coldelta=opponent) boardxy=player; break; int get_score(char boardSIZE,char player) int score=0; int row=0; int col=0; char opponent=player=0?*:0; for(row=0;rowSIZE;row+) for(col=0;colSIZE;col+) score-=boardrowcol=opponent; score+=boardrowcol=player; return score;int best_move
39、(char boardSIZE,int movesSIZE,char player) int row=0; int col=0; int i=0; int j=0; char opponent=player=0?*:0; char new_boardSIZESIZE=0; int score=0; int new_score=0; for(row=0;rowSIZE;row+) for(col=0;colSIZE;col+) if(!movesrowcol) continue; for(i=0;iSIZE;i+) for(j=0;jSIZE;j+) new_boardij=boardij; make_move(new_board,row,col,player); new_score=get_score(new_board,player); if(scorenew_score) score=new_score; return score;void computer_move(char boardSIZE,int movesSIZE,char player)
