算法数据结构总结.docVIP

**大学 算法与数据结构课程设计 课 程： 算法与数据结构 专 业： 计算机科学与技术 班 级： 08级计算机2班 学 号： * 姓 名： ** 2010 年 11 月 18日 本次算法与数据结构实践课中我们小组主要选择了两个课题，一个是迷宫的创建及求解问题，另一个是停车场管理系统问题，还选做了一个敢死队的问题。 在迷宫创建及求解这个问题中，我主要负责的是求解迷宫这个模块。迷宫求解采用的是课本中的回溯法，其求解过程就是沿着一个方向进行探索，若能走通，则继续向前走；否则原路返回，换一个方向在进行探索，直到找到了出口，或者所有可能的探索都失败而告终。 在探索过程中，可以用一个栈来保存探索的序列。其算法框架如下： 创建一个（保存探索过程的）空栈： 把入口位置压入栈中： While 栈不空时{ 取栈顶位置并设置为当前位置； While 当前位置存在试探可能{ 取下一个试探位置； If（下一个位置是出口） 打印栈中保存的探索过程然后返回 If （下一个位置是通道） 把下一个位置进栈并且设置为当前位置； } } 这个模块在程序中对应的代码段是： Status InitStack(Stack *s) /*创建栈s并初始化为空栈*/ { s-base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); /*分配内存空间*/ if(!s-base) Error(Overflow); s-top=s-base; s-stacksize=STACK_INIT_SIZE; return OK; } Status DestroyStack(Stack *s) /*销毁栈*/ { s-top=NULL; s-stacksize=0; free(s-base); s-base=NULL; return OK; } Boolean StackEmpty(Stack *s) /*核对栈是否为空栈*/ { if(s-top==s-base) return TRUE; else return FALSE; } int StackLength(Stack *s) /*得到栈的长度*/ { if(s-tops-base) return (int)(s-top-s-base); else return 0; } Status Push(Stack *s,SElemType e) /*入栈*/ { if(s-top-s-base=s-stacksize) { s-base=(SElemType *)realloc(s-base, (s-stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s-base) Error(Overflow); s-top=s-base+s-stacksize; s-stacksize+=STACKINCREMENT; } *s-top++=e; return OK; } SElemType Pop(Stack *s,SElemType e) /*出栈*/ { if(s-top==s-base) Error(Pop); e=*--s-top; return e; } Status GetTop(Stack *s,SElemType *e) /*e置到栈顶*/ { if(s-top==s-base) Error(GetTop); *e=*(s-top-1); return OK; } Boolean Pass(PosType curpos) /*检测目前位置是否可通*/ { if(maze[curpos.x][curpos.y].td==1 maze[curpos.x][curpos.y].foot==0maze[curpos.x][curpos.y].mark==0) return TRUE; else return FALSE; } void MarkPrint(PosType seat) /*标记位置*