迷宫游戏.doc

课程名称: 数据结构课程设计课程设计题目: 迷宫游戏姓 名: 院系: 计算机科学与技术学院 专 业: 计算机科学与技术 年 级: 2011级 学 号:指导教师: 王爱平2013 年 9月 14 日 目 录1 课程设计的目的32 需求分析3 3 课程设计报告内容3 3.1概要设计33.2详细设计53.3调试分析5 3.4用户手册5 3.5测试结果5 4 小结 5 5程序清单6 6 参考文献 197 程序截图 19 1.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；迷宫的墙足够结实，老鼠不能穿墙而过；正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；找出走出迷宫的所有路径，以及最短路径。3 职工管理系统的设计3.1概要设计POINT数据结构：typedef struct Point int x;int y;Pos;typedef Pos ElemType;队列数据结构：typedef struct QueueElemType *base;int front;int rear;Queue, *PQueue;栈数据结构：typedef struct StackElemType *base;ElemType *top;int stacksize;Stack, *PStack;用深度优先搜索寻找所有路径，用队列和栈寻找最优路径3.2详细设计void InitQueue(PQueue Q)/函数功能:队列初始化int EmptyQueue(PQueue Q)/函数功能:判断队列是否为空void EnQueue(PQueue Q, ElemType elem)/函数功能:进队列void DeQueue(PQueue Q, ElemType *elem)/函数功能:出队列void DestoryQueue(PQueue Q)/函数功能:销毁队列void InitStack(PStack S)/函数功能:栈初始化int EmptyStack(PStack S)/函数功能:判断栈是否为空void Push(PStack S, ElemType elem)/函数功能:压栈void Pop(PStack S, ElemType *elem)/函数功能:出栈void DestoryStack(PStack S)/函数功能:销毁栈void gotoxy(int x, int y)/函数功能:将光标移动到指定位置void color(int b)/函数功能:设置输入颜色void DrawMaze(Pos current, int ms, int st)/函数功能:画迷宫void ShowMouse(Pos before, Pos current, int ms)/函数功能:显示老鼠的位置Pos SelectDirection(Pos current)/函数功能:选择方向及其他功能void GameOver()/函数功能:游戏结束void AllPath(Pos point, int *tatol)/函数功能:寻找迷宫所有可走路径void BestPath()/函数功能:寻找迷宫最优路径void DrawPath(int n)/函数功能:显示路径void LookBack(PStack S)/函数功能:回溯void ClearVMAZE()/函数功能:清除虚拟迷宫3.3调试分析(略)3.4用户手册(略)3.5测试结果(略)4总结通过这次试验，我能够熟练的对文件进行操作，同时对链表更加熟练了5、程序清单:#include #include #include #include #include #include #define MAXLINE 25#define STACK_INIT_SIZE 20#define STACKINCREMENT 5#define MAXQUEUESIZE 100typedef struct Point /POINT数据结构int x;int y;Pos;typedef Pos ElemType;typedef struct Queue/队列数据结构ElemType *base;int front;int rear;Queue, *PQueue;typedef struct Stack/栈数据结构ElemType *base;ElemType *top;int stacksize;Stack, *PStack;void InitQueue(PQueue);int EmptyQueue(PQueue);void EnQueue(PQueue, ElemType);void DeQueue(PQueue, ElemType *);void DestoryQueue(PQueue);void InitStack(PStack);void Push(PStack, ElemType);void Pop(PStack, ElemType *);int EmptyStack(PStack);void DestoryStack(PStack);void ClearVMAZE();void AllPath(Pos, int *);void DrawPath(int);void BestPath();void LookBack(PStack);void gotoxy(int, int);void color(int);void DrawMaze(Pos, int, int);void ShowMouse(Pos, Pos, int);void GameOver();Pos SelectDirection(Pos);/*ms:游戏时间, st:关数，bound:迷宫大小, MAZE:迷宫, VMAZE:虚拟迷宫*/int ms, st = 1, bound, MAZEMAXLINEMAXLINE, VMAZEMAXLINEMAXLINE2,direction42 = 1, 0,0, -1,-1, 0,0, 1, tatol=0;long start;/起始时间Pos first, last;/迷宫的起点和终点int main()FILE *fp;char str8, chr;int i, j, flag;ms = 10;Pos current, before;system(mode con cols=56 lines=30);system(color 30);while(1)itoa(st, str, 10);strcat(str, .txt);if(fp = fopen(str, r) = NULL)gotoxy(2, bound+2);printf(Fail To Open %sn, str);exit(1);i = 0;j = 0;while(!feof(fp)/读文件，建迷宫chr = fgetc(fp);switch(chr)case n:i+;j = 0;continue;break;case :MAZEij = VMAZEij0 = 0;break;case #:MAZEij = VMAZEij0 = 1;break;case :MAZEij = VMAZEij0 = 0;last.x = j+1;last.y = i+1;break;case $:MAZEij = VMAZEij0 = 0;first.x = j+1;first.y = i+1;default:;j+;bound = i+1;fclose(fp);start = GetTickCount();current.x = first.x;current.y = first.y;flag = 0;DrawMaze(current, ms, st);while(long)GetTickCount() start+ms*1000)/游戏主循环before = current;current = SelectDirection(current);ShowMouse(before, current, ms);if(current.x = last.x & current.y = last.y)gotoxy(4, bound/2+2);for(i=1; i3)gotoxy(4, bound/2+2);for(i=1; ibound/2+2; i+)printf( );printf(VERY GOOD);exit(1);Sleep(3000);break;if(!flag)gotoxy(4, bound/2+2);for(i=1; ibase = (ElemType *)malloc(MAXQUEUESIZE*sizeof(ElemType);if(!Q-base)exit(1);Q-front = Q-rear = 0;int EmptyQueue(PQueue Q)/函数功能:判断队列是否为空if(Q-rear = Q-front)return 1;return 0;void EnQueue(PQueue Q, ElemType elem)/函数功能:进队列if(Q-rear+1)%MAXQUEUESIZE = Q-front)return;Q-baseQ-rear = elem;Q-rear = (Q-rear+1)%MAXQUEUESIZE;void DeQueue(PQueue Q, ElemType *elem)/函数功能:出队列if(Q-rear = Q-front)return;*elem = Q-baseQ-front;Q-front = (Q-front+1)%MAXQUEUESIZE;void DestoryQueue(PQueue Q)/函数功能:销毁队列free(Q-base);Q-front = Q-rear = 0;void InitStack(PStack S)/函数功能:栈初始化if(!(S-base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)exit(0);S-top = S-base;S-stacksize = STACK_INIT_SIZE;void Push(PStack S, ElemType elem)/函数功能:压栈if(S-top-S-base = S-stacksize)S-base = (ElemType *)realloc(S-base, (S-stacksize+STACKINCREMENT)*sizeof(ElemType);S-top = S-base + S-stacksize;S-stacksize += STACKINCREMENT;*(S-top +) = elem;void Pop(PStack S, ElemType *elem)/函数功能:出栈if(S-top = S-base)return;*elem = *(- S-top);int EmptyStack(PStack S)/函数功能:判断栈是否为空if(S-top = S-base)return 1;return 0;void DestoryStack(PStack S)/函数功能:销毁栈free(S-base);S-top = NULL;S-stacksize = 0;void gotoxy(int x, int y)/函数功能:将光标移动到指定位置COORD pos;pos.X = x;pos.Y = y;SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);void color(int b)/函数功能:设置输入颜色HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE) ;SetConsoleTextAttribute(hConsole, b) ;void DrawMaze(Pos current, int ms, int st)/函数功能:画迷宫int i, j;color(23);gotoxy(4, 1);for(i=0; ibound; i+)if(i = bound/2)printf(迷宫游戏第%2d关, st);elseprintf();color(43);for(i=0; ibound; i+)gotoxy(4, i+2);for(j=0; jbound; j+)if(current.x-1 = j & current.y-1 = i)printf();continue;if(last.x-1 = j & last.y-1 = i)printf();continue;if(MAZEij = 1)printf();elseprintf( );gotoxy(4+2*bound, i+2);if(0 = i | i = bound-1 | 2 = i)printf();elseprintf( );gotoxy(4+2*bound, 3);printf(TIME:%3ds, ms);gotoxy(4+2*bound, bound/2+2);printf(PATH:S/s);gotoxy(4+2*bound, bound/2+3);printf(EDIT:E/e);gotoxy(4+2*bound, bound/2+4);printf(EXIT:ESC);void ShowMouse(Pos before, Pos current, int ms)/函数功能:显示老鼠的位置long now;int time;now = GetTickCount();time = (int)(now - start)/1000;gotoxy(4+2*bound, 3);printf(TIME:%3ds, ms-time);gotoxy(4+(before.x-1)*2, before.y+1);printf( );gotoxy(4+(current.x-1)*2, current.y+1);printf();Pos SelectDirection(Pos current)/函数功能:选择方向及其他功能int i, j;char ch;fflush(stdin);if(kbhit()ch = _getch();switch(ch)case 0x48:/ upif(MAZEcurrent.y-1-1current.x-1 = 0)current.y -= 1;break;case 0x50: /downif(MAZEcurrent.y-1+1current.x-1 = 0)current.y += 1;break;case 0x4b: /leftif(MAZEcurrent.y-1current.x-1-1 = 0)current.x -= 1;break;case 0x4d: /rightif(MAZEcurrent.y-1current.x-1+1 = 0)current.x += 1;break;case 0x1b: /escexit(1);break;case e:case E:gotoxy(2, bound+2);printf(输入你要修改的坐标(x y);scanf(%d%d, &i, &j);if(i=current.x & j=current.y)printf(非法操作);Sleep(300);elseif(MAZEj-1i-1)VMAZEj-1i-10 = MAZEj-1i-1 = 0;elseVMAZEj-1i-10 = MAZEj-1i-1 = 1;system(cls);DrawMaze(current, ms, st);break;case s:case S:system(cls);ClearVMAZE();tatol = 1；AllPath(first, &tatol);ClearVMAZE();BestPath();Sleep(5000);system(cls);DrawMaze(current, ms, st);break;default:break;return current;void GameOver()/函数功能:游戏结束int i, j;color(391);for(i=0; ibound; i+)gotoxy(4, i+2);for(j=0; jbound+6; j+)printf();Sleep(50);void AllPath(Pos point, int *tatol)/函数功能:寻找迷宫所有可走路径int i, p;Pos po;VMAZEpoint.y-1point.x-10 = 2;for(i=0; i4; i+)if(0 = VMAZEpoint.y-1+directioni1point.x-1+directioni00)VMAZEpoint.y-1point.x-11 = 2+i;po.y = point.y+directioni1;po.x = point.x+directioni0;p = VMAZEpo.y-1po.x-10;VMAZEpo.y-1po.x-10 = 2;if(po.x = last.x & po.y = last.y)(*tatol) +;DrawPath(1);elseAllPath(po, tatol);VMAZEpo.y-1po.x-10 = p;VMAZEpoint.y-1point.x-10 = -2;void BestPath()/函数功能:寻找迷宫最优路径int i;Pos point, po;Queue Q;Stack S;InitQueue(&Q);InitStack(&S);EnQueue(&Q, first);while(!EmptyQueue(&Q)DeQueue(&Q, &point);Push(&S, point);VMAZEpoint.y-1point.x-10 = -1;for(i=0; i4; i+)if(0 = VMAZEpoint.y-1+directioni1point.x-1+directioni00)po.x = point.x+directioni0;po.y = point.y+directioni1;Push(&S, po);if(po.x = last.x & po.y = last.y)Push(&S, po);LookBack(&S);DrawPath(2);DestoryQueue(&Q);DestoryStack(&S);return;EnQueue(&Q, po);printf(迷宫无最优解n);DestoryQueue(&Q);DestoryStack(&S);void DrawPath(int n)/函数功能:显示路径int i, j;if(1 = n)printf(迷宫解法%3d:n, tatol);elseprintf(迷宫最优解:n);for(i=0; ibound; i+)for(j=0;