清华大学11课件

第12章栈及其应用1本章主要内容栈的定义及其基本操作栈的实现进制转换--栈的应用实例2清华大学黄维通设计制作栈是一种只允许在栈顶进行插入和删除操作的线性表，可用数组或线性表来实现12.1栈的定义及其基本操作

3清华大学黄维通设计制作toptoptoptop栈的基本操作空栈增加元素删除元素Top为栈顶指针，随着不同操作而移动bottombottombottombottom5清华大学黄维通设计制作栈是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现栈。12.2栈的实现

6清华大学黄维通设计制作12.2.1栈的数组实现

#defineMAXLENGTH256#defineTYPEintstructTStack{inttop;TYPEelement[MAXLENGTH];};typedefstructTStackStack;7清华大学黄维通设计制作(1)清空一个栈的操作voidClearStack(Stacks){ Node*p=s; while(p!=NULL) {s=s->next; free(p); p=s;} s=NULL;}(2)获取栈顶元素的操作voidGetTop(Stacks,TYPE*element){ if(Empty(s)) element=NULL; else *element=s->element;}9清华大学黄维通设计制作(3)获取栈顶元素但同时删除该元素voidPop(Stacks,TYPE*element) {if(Empty(s))

element=NULL;else{*element=s->element;

s=s->next;

}}(4)向栈顶插入一个元素的操作voidPush(Stacks,TYPEelement) { Node*node; node=malloc(sizeof(Node)); node->field=element; node->next=s; s=node;}(5)判断是否为空栈的操作intEmpty(Stacks){return(s==NULL);}10清华大学黄维通设计制作12.3进制转换--栈的应用实例

(1)算法11清华大学黄维通设计制作voidClearStack(Stack*s) //清空栈{s->top=-1;}intEmpty(Stacks) //判断是否为空栈{ if(s.top==-1) return1; else return0;}voidGetTop(Stacks,TYPE*element)

//获取栈顶元素{if(Empty(s))element=NULL;else*element=s.element[s.top];}13清华大学黄维通设计制作voidPop(Stack*s,TYPE*element)

//获取栈顶元素但同时删除该元素{if(Empty(*s))element=NULL;else{*element=s->element[s->top];s->top--;}}voidPush(Stack*s,TYPEelement)

//向栈顶插入一个元素{if(s->top==MAXLENGTH-1) return;else {s->top++; s->element[s->top]=element; }}14清华大学黄维通设计制作voidconversion() //进制转换{Stacks;intdec;ClearStack(&s);scanf("%d",&dec);

while(dec>0){Push(&s,dec%2);dec=dec/2;}

while(!Empty(s)){Pop(&s,&dec);printf("%d",dec);}printf("\n");}15清华大学黄维通设计制作用户编辑的特点：输入时不能不出错若输入一个字即送入用户数据区，显然是不恰当的最好是一行输入一次数据区应该允许用户及时修改当前行的错误假定从终端输入如下的字符：whab##ile(s#*s)outcha@putchar(*s=#++)while(*s)putchar(*s++)假定＃：退格@：退行，当前行无效过程：先判断它是否是退格符或者退行符，若不是，就将字符压入栈顶。若是退格符：从栈顶删除一个字符若是退行符：将字符栈清为空栈行编辑程序简单的行编辑器的功能是接收用户从终端输入的程序或者数据并存入用户的数据区。17清华大学黄维通设计制作接收用户输入的数据，存入用户的数据区“#”表示退格符，“@”表示退行符。voidLineEdit(){InitStack(S); //构造空栈ch=getchar(); //从终端接收一个字符while(ch!=EOF) //EOF为全文结束符{while(ch!=EOF&&ch!='\n'){switch(ch)

{case‘#’:Pop(S,c);break; //退格，删除栈顶元素case‘@’:ClearStack(S);break;//当前行无效default:Push(S,ch);break;}//插入ch为新的栈顶元素ch=getchar(); //接收下一个字符}ClearStack(S);//重置S为空栈，以便重新放入行内容if(ch!=EOF)ch=getchar();}DestroyStack(S); //销毁栈，栈不再存在}18清华大学黄维通设计制作栈的应用－－递归编程的应用常见的阶乘运算的编程，可以引入栈的应用123n•fac(intn){floatf