第三章 栈、队列和数组.ppt

《第三章 栈、队列和数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈、队列和数组栈和队列都是特殊的线性表，数组是线性表的变化形式，它们都是软件设计中常用的数据结构。1主要内容栈队列数组栈的应用——递归2栈的定义栈是只能在一端插入和删除的线性表。入栈出栈anan-1a1…栈顶栈底后进先出3栈的运算初始化栈：init_stack(S)判断栈空：stack_empty(S)取栈顶元素：stack_top(S,x)入栈：push_stack(S,x)出栈：pop_stack(S)判断栈满：stack_full(S)4顺序栈---存储结构以顺序存储方式存储的栈叫做顺序栈。ana4a3a2a10123…n-1maxsize-1datatopS类型说明：t

2、ypedefstruct{elementtypedata[maxsize];inttop;}seqstack5顺序栈---运算（1）初始化栈：voidinit_stack(seqstack*S){s->top=-1;}Top所指示元素下标比元素个数少1，即<0判断栈S是否为空：BOOLstack_empty(seqstackS){if(S.top==-1)returnTRUE;elsereturnFALSE;}取栈顶元素Voidstack_top(seqstack*S,elementtype*x);{if(empty(*S))error(“栈为空”);else*x=s->data［

3、s->top］;}Top值是否为－1栈不空，返回栈顶元素；否则出错6入栈：voidpush_stack(seqstack*S,elementtypex){if(S->top==maxsize-1)error(“溢出”);elseS->data［++s->top］=x;}顺序栈---运算（2）出栈：voidpop_stack(seqstack*S,elementtype*x){if(empty(*S))error(“栈空，不能删除”);else*x=S->data［S->top--］;}判断栈是否为满：BOOLstack_full(seqstackS){if(S.top==maxsiz

4、e-1)returnTRUE;elsereturnFALSE;}判断栈是否满了，否则不能插入判断栈是否为空，否则不能删除Top值是否为maxsize－17链栈用动态方式来存储栈可节省空间采用链表存储的栈为链栈a1a2a3an…top8栈的应用---基本应用（1）voidread_write(){stackS;intn,x;cout<<”Pleaseinputnumintn”;cin>>n;//输入元素个数init_stack(S);//初始化栈for(i=1;i<=n;i++){cin>>x;//读入一个数push_stack(S,x);//入栈}while(stack_empty(

5、S)!=TRUE){stack_top(S,x);//取出栈顶元素cout<next;//操作②，从原表中分离出表头结点u->next=P;

6、//操作③，新分离出的结点的后继指示新表表头结点P=u;//操作④，新分离出的结点成为新表的表头结点}L=P;//原表头指针指示新的表头指针}③ai-1aia1…puaiai＋1an…L②④①u10栈的应用---表达式计算编写程序以实现对任意输入的表达式的计算。例如表达式为12+5*(2+3)*6/2-4扫描基本符号是否操作数？Y栈顶运算符低于当前运算符？操作数入栈NYN运算符入栈取出S栈顶运算符和O栈顶的两个操作数运算，结果入栈O定义运算符栈S和操作数栈O栈S为空？Y结束Y111357÷8所得的余数1357÷8所得的商按此次序连接各位余数便得到最后的转换结果为25150288881

7、357516912152栈的应用---数的进制转换设计算法将十进制数转换为八进制形式。实例：voidDec_to_Ocx(inta){stackS;init_stack(S);//初始化栈while(N!=0){Mod=N%8;//求余数push_stack(S,Mod);//余数入栈N=N/8;}//求商while(!stack_empty(S)){stack_top(S,x);//取出栈顶元素cout<