数据结构-PPT第三章-栈和队列剖析.ppt

第三章 栈和队列 3.1 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。 顺序栈 顺序栈示意图 = 3.2 栈的应用 3.2.1 数制转换 void conversion( ) { initstack(S); scanf (“%d”,N); while(N){ push(S，N%8); N=N/8; } while(! Stackempty(s)){ pop(S,e); printf(“%d”,e); } }//conversion 栈使用的完整C程序实例 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -1 #define ERROR 0 typedef struct{ int *base; int *top; int stacksize; }sqstack; void push(sqstack *s,int e) { if(s-top-s-base=s-stacksize){ s-base=(int*)realloc(s-base,(s- stacksize+STACKINCREMENT)*sizeof(int)); if (!s-base)exit(OVERFLOW); s-top=s-base+s-stacksize; s-stacksize+=STACKINCREMENT; } *(s-top++)=e; } main() { sqstack s; int n,m,e; initstack(s); clrscr(); //清屏幕 scanf(“%d %d”,n,m);//n为输入数，m为基数 while(n){ push(s,n%m);n=n/m; } while(!(s.top==s.base)) { pop(s,e); printf(%d,e); } } 从演示过程可见用“穷举求解”的方法解迷宫的规则： 　 1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止； 2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本没有通道； 3．所谓“走不通”不单是指遇到“障碍物挡路”，还有“已经走过的路不能重复走第二次”，它包括“曾经走过而没有走通的路”。显然为了保证在任何位置上都能沿原路退回，需要用一个后进先出的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。 else { // 当前位置不能通过 if (!StackEmpty(S)) { Pop (S,e); while (e.di==4 !StackEmpty(S)) { MarkPrint (e.seat); Pop (S,e);} // 留下不能通过的标记，并退回一步} // while if (e.di4) { e.di++; Push ( S, e);// 换下一个方向探索 curpos = NextPos (curpos, e.di ); // 设定当前位置是该新方向上的相邻块 } // if } // if } // else } while ( !StackEmpty(S) ); return (FALSE); } // MazePa