计算机软件技术基础3-2 数据结构与算法(栈和队).ppt

常用数据结构及其运算;§3.1 概述 §3.2 线性表 §3.3 栈与队 §3.4 树与二叉树 §3.5 图 §3.6 查找与排序;3.3 栈与队;3.3.1 栈的结构和运算;3.3.1 栈的结构和运算;顺序栈 ? 用向量作为存储结构，可用一维数组s[1:m] 表示。 m－栈的最大容量。 Top－栈顶指示器。top=0，栈空；top=m，栈满。;顺序栈(C++描述);（1）进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶。 void SqStack::Push(ElemType x) { if( top stacksize-1) { top++; data[top]=x; } else cout”栈满”; } ;（2）出栈操作 若栈不空，则删除栈顶元素，用result返回其值。 void SqStack::Pop(ElemType result) { if(top -1) { result= data[top]; top--; } else cout栈空; };（3）取栈顶元素 若栈不空，则用result返回栈顶元素。 void SqStack::GetTop(ElemType result ) { if(top -1) { result= data[top]; } else cout栈空; } ;链栈 ? 链栈是用链表作为栈的存储结构，top为栈顶指 针，指示栈顶元素位置，若top=NULL,则表示栈 空。链栈一般不会出现上溢，除非内存中已不 存在可用空间。;? 链栈的插入（进栈）：;链式栈(C++描述) ;（1）进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶。 void LinkStack::Push(ElemType x) { SNode *p=new SNode; if(p!=NULL) { p-data=x; p-next=top; top=p; } };（2）出栈操作 若栈不空，则删除栈顶元素，用result返回其值。 void LinkStack::Pop(ElemType result); { SNode *p; if(top!=NULL){ result = top-data; p=top; top=top-next; delete p; } };4. 栈的应用 (1) 表达式求值（用于高级语言的编译程序） ?运算符：** / * + - ; 优先数：3 2 2 1 1 0; 需建立两个栈：操作数(NS)、运算符(OS)。 ? 算法思想：置NS为空， “； ”作为OS的栈底元素。自左至右扫描表达式： ① 若为操作数，将其压入NS栈 ② 若为运算符，与OS栈顶元素比较优先级： OS栈顶，则将当前运算符压入OS栈。 = OS栈顶，则从NS栈中弹出两个操作数x、y，再从OS栈中弹出一个运算符θ，构成一条机器指令：xθy→T??将结果T送入NS栈。 = “；”，且OS栈顶也为“；”，则表示表达式处理结束，此时NS栈顶的元素即为此表达式的值。;? 举例：设表达式为：A / B ** C + D; 过程为：; ? 过程嵌套－－多重嵌套时，用栈将各层断点信息依次入栈，当各层子过程返回时，以相反的次序从栈顶取出（FILO, or, LIFO）; ? 递归调用－－一个过程通过过程调用语句 直接或间接地调用自己的过程。;(3) 回溯求解算法;4）算法描述Pack(T,n,W,S,top){ top=0; i=1; //初始化 while (T0 i=n) { if (T-W[i]==0||(T-W[i]0in)) { top++; S[top]=i; T=T-W[i]; } //可选 if (T==0) return(1); //有解 else ｛ if (i==ntop0){ i=S[top]; top--; T+=W[i]; }//退栈 i++; //取下一个 } }//end while return(0);};4 7 3 5 4 2; N=( N div d)*d+N mod d ; div为整除运算 ，mod为求余 （1344)10=(2504)8 N N div 8 N