数据结构课程设计-大数相乘和贪吃蛇.docx

数据结构课程设计 学院： 计算机科学与工程学院 _班级： 学生姓名： 设计题目：大数相乘&贪吃蛇游戏完成日期： 2018 年 1 月 03 日 1、 课程论文题目大数相乘2、 程序设计思路1、 顺序存储两个大数分别于A、和B中。2、 把这个数组中的每一位数字单独进行乘法运算。3、 找到最高位在数组中的项ci,然后依次输出各位上的数值。4、 通过主函数来调用其它各个函数。3、 数据结构设计一、 输入阶段采用一维数组A,B。二利用函数计算阶段调用一维数组c。4、 功能函数设计：一、 找出每一项的所有项首先找规律，如下图所示，进行乘法a0 a1 a2b0 b1 b2b2a0 b2a1 b2a2b1a0 b1a1 b1a2b0a0 b0a1 b0a2下标值和 0 1 2 3 4 i=4 i=3 i=2 i=1 i=0(循环时的i的数值)即有 下标之和=m+n-2-i，由此限定条件可设计循环得出每一列的所有项。故首先解决了找出每一列所有项的问题。二、计算从地位到高位的每一位的值。显然考虑到进位的问题，故必须从低位到高位依次计算，对于每一列，第一项除以10取余数，保留在原位存入从,所得商进位存入mm。然后对于第二列，第一项加进位mm，然后取余数存入su，在加第二项，取余数存入从,求商存入进位mm，直到该列所有项参与运算到该列结束时，求的最终的从和mm。依次进行后面的运算。三、找出反向存入结果从中的首项。因为最高位一定不为零，故可以设计程序从c开始判断，当从i不等于零时，即为最高项。四、设计主函数，依次调用如上函数。然后通过for循环5、主函数#include#include#include#defineN100voidswap(char*str,intp,intq);voidmenu();voidmultil();char*LargeNum_multi(char*A,char*B);voidswap(char*str,intp,intq)chartemp;while(p=1&A0=1&B0=9)intm=strlen(A);intn=strlen(B);inti,j;char*result;intmultiFlag;intaddFlag;result=(char*)malloc(sizeof(char)*(m+n+1);for(i=0;im+n;i+)*(result+i)=0;resultm+n=0;swap(A,0,m-1);swap(B,0,n-1);for(i=0;i=n-1;i+)multiFlag=0;addFlag=0;for(j=0;j=1&B0=1&A0=1&A0=1&B0=9)printf(0);menu();elseif(B0=0&(A0=-)printf(0);menu();elseif(B0=-&A0=0)printf(0);menu();elseif(B0=0&A0=0)printf(0);menu();voidmultil()charAN;charBN;printf(t输入第一个数字：a=);scanf(%s,&A);printf(t输入第二个数字：b=);scanf(%s,&B);printf(t输出结果：a*b=);char*res=LargeNum_multi(A,B);if(res0!=0)printf(%c,res0);printf(%s,res+1);menu();voidmenu()/菜单printf(nnt+-大数相乘-+n);printf(t+1、进行大数相乘+n);printf(t+2、退出程序+n);printf(t+（请输入数据）+n);intitem;printf(nt请输入菜单选项：);scanf(%d,&item);switch(item)case1:printf(nt+进行大数相乘计算：n);multil();break;case2:printf(nt+退出程序成功：n);exit(0);break;default:printf(nt+请在1和2之间进行选择n);menu();break;intmain()menu();return0; 二、贪吃蛇 1、 需求分析1.1设计目的 贪吃蛇是家喻户晓的益智类小游戏，选择这个题目一是为了将我们所学的知识加以运用，二是一直以来贪吃蛇这个小游戏就比较吸引人，它的实现对于以前的我们而言都是很神秘的。我们希望通过自己所学的知识把它剖析开来，真真正正地了解它的本质和精髓。同时更进一步地掌握c语言、c+（本实验是用c+进行开发的）以及数据结构的理论知识与实际应用，熟悉基本的游戏软件开发过程。根据分析后的贪吃蛇结构设计出相应的游戏流程，主要内容包括：游戏开始，定义活动范围（Map），随机出现食物，方向控制，游戏结束，分数以及难度的显示。1.2设计内容1.通过输入地图长度、宽度，划出snake活动的区域，同时选择游戏难度，游戏难度通过移动速度来决定。2.食物的随机生成3. 用键盘上的上、下、左、右键对snake的活动方向进行控制。蛇身方向的处理，控制蛇头的移动，定一个双向链表，用来保管每次移动完以后，每一节蛇身的位置，下一次的时候，每一个蛇身读取前一个蛇身的坐标，就可以实现蛇的整体移动。移动完以后，新的坐标被保管进数组，如此一直循环下去。选择的数据结构：双向链表、队列、广度优先搜索4.撞墙和撞到本身，撞墙判断蛇头坐标是否到边界。撞到本身，做一个循环判断蛇头的坐标是否和其他蛇身相等。流程图如下：二、概要设计功能块各函数列表：bool Auto:bfs(int sx,int sy,int ex,int ey)/广度优先搜索函数，用于搜索路径void snake:add_head(int xx,int yy)/增加蛇头结点void snake:del_tail()/删除蛇尾结点void Map:initMap()/初始化地图void Map:outputMap()/打印出游戏当前的状态void move:get_food()/随机生成食物int move:movesnake()/移动蛇身bool move:turn_dir(char op)/snake移动方向控制bool game()/开始游戏， void welcome()/进入游戏结构体细分功能：struct point int x,y,step;/储存搜索状态 int path900;struct snake_node int x;/蛇头结点横坐标 int y;/蛇头结点纵坐标 int rank;/第几个蛇结点;四、测试分析4.1首页面4.2游戏玩法4.3游戏界面4.5游戏结束页面，可以选择继续五、用户使用说明开发环境：VS2015运行环境：VS2015游戏操作：进入首页后根据提示操作六、总结：6.1、需求分析方面：在分析问题过程中总会不断遇到新的要求、新的挑战。在这个分析过程中，对于实验的要求和实验的目的是明确的，但在具体讨论到功能的实现时产生了两大难题：一是蛇身的处理，二是如何移动及移动路径。这两个问题后来通过数据结构中的双向链表和广度优先搜索的只是得到了较好的解决。根据分析后的贪吃蛇结构设计出相应的游戏流程，主要内容包括：游戏开始，定义活动范围（Map），随机出现食物，方向控制，游戏结束，分数以及难度的显示等，游戏流程还是比较简洁清晰的。6.2、数据结构对实验需要实现功能经过分析后得出此次实验需要用到的数据结构有双向链表和队列，其中还引用了广度优先搜索的内容，其中双向链表用于保存整个贪吃蛇每节蛇身位置，队列和广度优先遍历则是在玩家选择了自动模式后，实验用于查找贪吃蛇的路径，自动进行游戏。在存储结构方面，比如说游戏的最高分，则是以文件读取形式为主，在游戏结束后将分数与历史最高分进行比较，若分数高于历史最高分，则改写文件中保存分数的内容。6.3、遇到的问题 在本次实验中主要遇到了如何保存游戏历史最高分和如何让游戏自动运行的问题。由于游戏每次开始都会现实历史最高分，而历史最高分是随着游戏的每次进行而时时更新的，所以不能在程序内部进行保存，所以选择了运用文件进行保存操作。7、附录（程序源代码）#include#include#include#include#define U 1#define D 2#define L 3 #define R 4 /蛇的状态，U：上 ；D：下；L:左 R：右typedef struct SNAKE /蛇身的一个节点int x;int y;struct SNAKE *next;snake;/全局变量/int score = 0, add = 10;/总得分与每次吃食物得分。int status, sleeptime = 200;/每次运行的时间间隔snake *head, *food;/蛇头指针，食物指针snake *q;/遍历蛇的时候用到的指针int endgamestatus = 0; /游戏结束的情况，1：撞到墙；2：咬到自己；3：主动退出游戏。 /声明全部函数/void Pos();void creatMap();void initsnake();int biteself();void createfood();void cantcrosswall();void snakemove();void pause();void gamecircle();void welcometogame();void endgame();void gamestart();void Pos(int x, int y)/设置光标位置COORD pos;HANDLE hOutput;pos.X = x;pos.Y = y;hOutput = GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleCursorPosition(hOutput, pos);void creatMap()/创建地图int i;for (i = 0; i58; i += 2)/打印上下边框Pos(i, 0);printf();Pos(i, 26);printf();for (i = 1; ix = 24;tail-y = 5;tail-next = NULL;for (i = 1; i next = tail;head-x = 24 + 2 * i;head-y = 5;tail = head;while (tail != NULL)/从头到为，输出蛇身Pos(tail-x, tail-y);printf();tail = tail-next;int biteself()/判断是否咬到了自己snake *self;self = head-next;while (self != NULL)if (self-x = head-x & self-y = head-y)return 1;self = self-next;return 0;void createfood()/随机出现食物snake *food_1;srand(unsigned)time(NULL);food_1 = (snake*)malloc(sizeof(snake);while (food_1-x % 2) != 0) /保证其为偶数，使得食物能与蛇头对其food_1-x = rand() % 52 + 2;food_1-y = rand() % 24 + 1;q = head;while (q-next = NULL)if (q-x = food_1-x & q-y = food_1-y) /判断蛇身是否与食物重合free(food_1);createfood();q = q-next;Pos(food_1-x, food_1-y);food = food_1;printf();void cantcrosswall()/不能穿墙if (head-x = 0 | head-x = 56 | head-y = 0 | head-y = 26)endgamestatus = 1;endgame();void snakemove()/蛇前进,上U,下D,左L,右Rsnake * nexthead;cantcrosswall();nexthead = (snake*)malloc(sizeof(snake);if (status = U)nexthead-x = head-x;nexthead-y = head-y - 1;if (nexthead-x = food-x & nexthead-y = food-y)/如果下一个有食物/nexthead-next = head;head = nexthead;q = head;while (q != NULL)Pos(q-x, q-y);printf();q = q-next;score = score + add;createfood();else /如果没有食物/nexthead-next = head;head = nexthead;q = head;while (q-next-next != NULL)Pos(q-x, q-y);printf();q = q-next;Pos(q-next-x, q-next-y);printf( );free(q-next);q-next = NULL;if (status = D)nexthead-x = head-x;nexthead-y = head-y + 1;if (nexthead-x = food-x & nexthead-y = food-y) /有食物nexthead-next = head;head = nexthead;q = head;while (q != NULL)Pos(q-x, q-y);printf();q = q-next;score = score + add;createfood();else /没有食物nexthead-next = head;head = nexthead;q = head;while (q-next-next != NULL)Pos(q-x, q-y);printf();q = q-next;Pos(q-next-x, q-next-y);printf( );free(q-next);q-next = NULL;if (status = L)nexthead-x = head-x - 2;nexthead-y = head-y;if (nexthead-x = food-x & nexthead-y = food-y)/有食物nexthead-next = head;head = nexthead;q = head;while (q != NULL)Pos(q-x, q-y);printf();q = q-next;score = score + add;createfood();else /没有食物nexthead-next = head;head = nexthead;q = head;while (q-next-next != NULL)Pos(q-x, q-y);printf();q = q-next;Pos(q-next-x, q-next-y);printf( );free(q-next);q-next = NULL;if (status = R)nexthead-x = head-x + 2;nexthead-y = head-y;if (nexthead-x = food-x & nexthead-y = food-y)/有食物nexthead-next = head;head = nexthead;q = head;while (q != NULL)Pos(q-x, q-y);printf();q = q-next;score = score + add;createfood();else /没有食物nexthead-next = head;head = nexthead;q = head;while (q-next-next != NULL)Pos(q-x, q-y);printf();q = q-next;Pos(q-next-x, q-next-y);printf( );free(q-next);q-next = NULL;if (biteself() = 1) /判断是否会咬到自己endgamestatus = 2;endgame();void pause()/暂停while (1)Sleep(300);if (GetAsyncKeyState(VK_SPACE)break;void gamecircle()/控制游戏 Pos(64, 15);printf(不能穿墙，不能咬到自己n);Pos(64, 16);printf(用.分别控制蛇的移动.);Pos(64, 17);printf(F1 为加速，F2 为减速n);Pos(64, 18);printf(ESC ：退出游戏.space：暂停游戏.);Pos(64, 20);status = R;while (1)Pos(64, 10);printf(得分：%d , score);Pos(64, 11);printf(每个食物得分：%d分, add);if (GetAsyncKeyState(VK_UP) & status != D)status = U;else if (GetAsyncKeyState(VK_DOWN) & status != U)status = D;else if (GetAsyncKeyState(VK_LEFT) & status != R)status = L;else if (GetAsyncKeyState(VK_RIGHT) & status != L)status = R;else if (GetAsyncKeyState(VK_SPACE)pause();else if (GetAsyncKeyState(VK_ESCAPE)endgamestatus = 3;break;else if (GetAsyncKeyState(VK_F1)if (sleeptime