数据结构课程设计报告范文

年4月19日数据结构课程设计报告范文文档仅供参考，不当之处，请联系改正。扬州大学信息工程学院《数据结构》课程设计报告题目：“井字棋”小游戏班级：学号：姓名：指导教师：

一、课程题目“井字棋”小游戏二、需求分析计算机和人对弈问题。计算机之因此能和人对弈是因为有人将对弈的策略事先已存入计算机。由于对弈的过程是在一定规则下随机进行的，因此，为使计算机能灵活对弈就必须对对弈过程中所有可能发生的情况以及相应的对策都考虑周全，而且，一个“好”的棋手在对弈时不但要看棋盘当时的状态，还能预测棋局发展趋势，甚至最后结局。因此，在对弈问题中，计算机操作的对象是对弈过程中可能出现的棋盘状态——称为格局。例如图1所示为井子棋的一个格局，而格局之间的关系是由比赛规则决定的。一般，这个关系不是线性的，因为从一个棋盘格局能够派生出几个格局，例如从图1所示的格局能够派生出5个格局，如图2所示，而从每一个新格局又可派生出4个可能出现的格局。因此，若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一颗倒长的“树”。树根是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从树根沿树杈到某个叶子的过程。“树”能够是某些非数值计算问题的数学模型，是一种数据结构。图1棋盘格局示例图2对弈树的局部三、概要设计该课题的数据类型比较简单，只需要一个Nodes类型记录棋子所在位置和当前状态即可。其中包括基本操作的函数有：初始化棋盘函数、判断当前位置是否为空函数、放置棋子函数、判断棋盘是否为满函数、判断输赢函数、棋局状态函数、选择最佳落子位置函数和打印棋盘函数。intIsWin(intside)，其功能是依次从行、列、对角线判断是否有三个棋子连成一线。intPostionValue()，能够返回四种状态，分别为电脑赢、玩家赢、平局和游戏正在进行。NodesBestMovement(intside)是该问题的关键模块，其功能为得到当前格局下最佳落子位置，具体实现将在详细设计中阐述。intmain()，主函数，游戏系统界面设计，其功能是引导玩家进入游戏，选择游戏模式（玩家先手或电脑先手），并显示游戏界面。四、详细设计（1）数据类型Nodes定义如下：typedefstruct{ introw;//行 intcolumn;//列 intcond;//游戏状态}Nodes;（2）NodesBestMovement(intside)作为实现该课题的关键模块，其算法设计借鉴了“四皇后”问题的解决思路（即回溯法）。很多问题用回溯和试探求解时，描述求解的状态不是一颗满的多叉树。当试探过程中出现的状态和问题所求解产生矛盾时，不再继续试探下去，这时出现的叶子结点不是问题的解的终结状态。这类问题的求解过程可看成是在约束条件下进行先序（根）遍历，并在遍历过程中剪去那些不满足条件的分支。如图3所示，这是一个四叉树，树上每个结点表示一个局部布局或一个完整布局。根结点表示棋盘的初始状态：棋盘上无任何棋子。图3四皇后问题的棋盘状态树依据以上分析，能够很容易得出一个结论。求得当前格局下最佳落子位置的过程，即为在约束条件下遍历一颗状态树的过程。遍历中访问结点的操作为，判断棋局是否仍在继续，若是，则转而求对手的最佳落子位置；否则就返回当前输赢状态。若返回结果为输，将棋子移至下一个位置；为平局，先将该位置暂存；为赢，将该位置作为最佳位置返回。该模块的伪码算法如下：NodesBestMovement(intside){ //从棋盘第一格开始依次尝试最佳位置。 if(游戏已经结束)返回游戏结果; elsefor(i=0;i<MAX_SIZE;i++){for(j=0;j<MAX_SIZE;j++){ if(第i行第j列为空){ 在该位置放置一个棋子; 求对手的最佳位置;//node=BestMovement(opponent); 移走该位置的棋子; if(该位置有更好的终结状态)暂存该位置; } } } 返回最佳位置;}//BestMovement五、测试数据及运行结果图4游戏界面（电脑先手）图5游戏结局六、源程序#include<stdio.h>#include<stdlib.h>#defineMAX_SIZE3#defineFALSE0#defineTRUE1#defineEMPTY0#defineHUMAN1#defineCOMPUTER2#defineHUMAN_WIN0#defineDRAW1#defineCOMPUTER_WIN2#definePLAYING3typedefstruct{ introw; intcolumn; intcond;}Nodes;intBoard[MAX_SIZE][MAX_SIZE];voidInitBoard(){ introw,column;for(row=0;row<MAX_SIZE;row++)for(column=0;column<MAX_SIZE;column++)Board[row][column]=EMPTY;}intIsEmpty(introw,intcolumn){if(Board[row][column]==EMPTY)returnTRUE;elsereturnFALSE;}voidPlace(introw,intcolumn,intpiece){Board[row][column]=piece;}intIsFull(){inti=0,j=0;for(i=0;i<MAX_SIZE;i++)for(j=0;j<MAX_SIZE;j++){if(Board[i][j]==EMPTY)returnFALSE;}returnTRUE;}intIsWin(intside){introw,column;//判断一行for(row=0;row<MAX_SIZE;row++){for(column=0;column<MAX_SIZE;column++)if(Board[row][column]!=side)break;if(column>=MAX_SIZE)returnTRUE;}//判断一列 for(column=0;column<MAX_SIZE;column++){for(row=0;row<MAX_SIZE;row++)if(Board[row][column]!=side) break;if(row>=MAX_SIZE) returnTRUE;}//判断主对角线if(Board[0][0]==side&&Board[1][1]==side&&Board[2][2]==side)returnTRUE;//判断副对角线if(Board[0][2]==side&&Board[1][1]==side&&Board[2][0]==side)returnTRUE;returnFALSE;}intPostionValue(){returnIsWin(COMPUTER)?COMPUTER_WIN:(IsWin(HUMAN)?HUMAN_WIN:(IsFull()?DRAW:PLAYING));}NodesBestMovement(intside){Nodesnode,bestNode; intopponent;intresult;introw,column,bestRow=0,bestColumn=0;intcondition;if((result=PostionValue())!=PLAYING){node.cond=result;returnnode;}if(side==COMPUTER){ opponent=HUMAN; condition=HUMAN_WIN;}else{opponent=COMPUTER;condition=COMPUTER_WIN;}for(row=0;row<MAX_SIZE;row++){for(column=0;column<MAX_SIZE;column++){ if(IsEmpty(row,column)){ Place(row,column,side); node=BestMovement(opponent); Place(row,column,EMPTY); if((side==COMPUTER&&node.cond>condition)||(side==HUMAN&&node.cond<condition)){ condition=node.cond; bestRow=row; bestColumn=column; } } } } bestNode.row=bestRow; bestNode.column=bestColumn; bestNode.cond=condition; returnbestNode;}voidPrint(){introw,column;for(row=0;row<MAX_SIZE;row++){for(column=0;column<MAX_SIZE;column++){if(Board[row][column]==EMPTY)printf("");elseif(Board[row][column]==HUMAN)printf("X");elseprintf("O");} printf("\n"); }}intmain(){ NodesplayNode; intchoice,first; inta,b; intresult; while(TRUE){ while(TRUE){ printf("请选择你要进行的操作：\n"); printf("1：开局\n"); printf("2：退出\n"); scanf("%d",&choice); if(choice==1) break; if(choice==2) exit(0); printf("你的输入有误，请重新输入。\n"); } system("cls"); InitBoard(); while(TRUE){ printf("请决定人机对战时谁先走第一步？\n1：人\n2：电脑\n"); scanf("%d",&first); if(first==1||first==2){ break; } printf("输入错误，请重新选择。\n"); } system("cls"); printf("人的棋子为O，电脑的棋子X。\n"); if(first==1){while(TRUE){while(TRUE){printf("请输入你落子所在的行数，列数（格式：ab（a,b在0~2之间））：");scanf("%d%d",&a,&b);if(a>=0&&a<MAX_SIZE&&b>=0&&b<MAX_SIZE&&IsEmpty(a,b))break;printf("你输入的位置不合法，请重新输入：\n");} Place(a,b,HUMAN); Print(); if((result=PostionValue())!=PLAYING) break; playNode=BestMovement(COMPUTER); Place(playNode.row,playNode.column,COMPUTER); printf("电脑落子后的棋盘为：\n"); Print(); if((result=PostionValue())!=PLAYING) break;}} elseif(first==2){ while(TRUE){ printf("电脑落子后棋盘状态为：\n"); playNode=BestMovement(COMPUTER); Place(playNode.row,playNode.column