数据结构复习-栈和队列

《数据结构复习-栈和队列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第三章栈和队列从数据结构的角度看：它们和线性表相M从数据类型的角度看：它们和线性表不同线性表栈队列Insert(L,i,x)Insert(Szn+1,x)Insert(Qzn+1,x)n+l)

2、aieElemSet,i=l,2,...,n,n>0>数据关系:Rl={

3、ai-1,aieD,i=2z...,n}约定an端为栈顶，al端为栈底。基本操作：InitStack(&S)操作结果：构

4、造一个空栈S。DestroyStack(&S)初始条件：栈S己存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S己存在。操作结果：将S淸为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S己存在。操作结果：返回S的元索个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S己存在。操作结果：插入元索e为新的栈顶元索。Pop(&S,&e)初始条件：栈S

5、己存在fl非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack3.2栈的应用举例例一、数制转换十进制数N和其他d进制数的转换足计算机实现计算的基本闷题，其解决方法很多，其中一个简单算法-基于下列原理：N=(Ndivd)xd+Nmodd(典屮：div为整除运算，mod为求余运算)例如：(1348)10=(2504)8，其运算过程如下:Ndiv81682122Nmod840N13481682120假没现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制幣数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进

6、制数的各个数位，而打印输出，一般來说应从高位到低位进行，怡好和计算过程相反。因此，若将计算过程屮得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。voidconversion(){//对于输入的任意一个非负十进制狼数，打印输出//与其等值的八进制数InitStack(S);//构造空找scanf("%d",N);while(N){Push(S,N。/。8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d"ze);}}//conversion这足利用栈的记进先出特性的最简

7、单的例子。在这个例子中，栈操作的序列足直线式的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分敗稍力去考虑数组不标增减等细节问题。例二、括号匹配的检验假设表达式中允许包含两种括兮：圆括兮和方括兮，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或([())或(()])均为不正确的格式。检验拈号是否匹配的方法可用"期待的急迫程度n这个概念來描述。例如考虑

8、下列括号序列：[([][])]12345678分析可能出现的不匹配的情况：1)到来的右拈弧非是所''期待"的；2)到來的是''不速之客"；3)H到结束，也没宥到来所''期待"的。statusmatching(string&exp){//检验表达式中所含括弧足否正确嵌套，若足，则返回//OK,否则返回ERRORintstate=1;while(i<=length(exp)&&state){swithofexp[i]{case左拈弧：{Push(S,exp[i]);i++;break;}case丁：

9、op(S)="(")……}>if(state&&StackEmpty(S))returnOKelsereturnERROR;>例三、行编辑程序问题一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。每接受一个字符即存入川户数据区"不恰当。较好的做法是，没立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误吋可以及吋更正。例如，可用一个退格符表示前一个字符无效；可用一个退行符"@"，表示当前行屮的字符

10、均无效。例如，假设从终端接受了这样两行字符：whli##ilr#e(s#*s)outcha@putchar(*s=#++);则实际有效的