软件技术基础-栈,队列,矩阵.ppt

栈结构 栈的基本运算： 1. SETNULL（s）;置空操作 2. EMPTY （s）； 判空操作 3. PUSH （s，x）； 压栈 4. POP（s）； 弹栈 5. TOP（s）； 取栈顶元素 用数组实现栈 用数组实现栈 用数组实现栈 用链表实现栈 2.2用链表实现栈 用链表实现栈 用链表实现栈 练一练 练一练 练一练 练一练 * * 段景山 * 软件技术基础 主讲：杨建军 线性结构 1 2 3 4 5 6 6 5 6 5 1、堆栈 stack 栈是特殊的线性表，仅在表的一端进行插入或删除操作 an ... a2 a1 栈顶 入栈 出栈 栈底 特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则LIFO 2.1用数组实现栈 a[max] ... a[1] a[0] ... a[top] 栈顶 a[0]为栈底，top为栈顶 （1）定义 typedef struct stack_type{ elemtype data[MAXNUM]; int top; }stack_type; （2）压入 push 当新元素入栈时，栈顶上移，新元素放在栈顶。 ... stack.top = stack.top + 1; stack.data[stack.top] = new_one; new_one 栈顶元素 所在位置 a1 a2 ... （3）弹出 pop 从栈顶移出一个数据。 a[max] ... a[1] a[0] a1 a2 栈顶 栈顶元素拷贝出栈，栈顶下移 out out = stack.data[stack.top]; stack.top = stack.top - 1; elemptype pop(stack_type *stack){ elemtype out; if(stack-top = 0) error(3); else{ out = stack-data[stack-top]; stack-top = stack-top -1; } return out; } a[top] （4）栈空判断 stack.top = = 0 stack.top 0 （5）置栈空 stack.top = -1; 栈满判断：stack.top = MAXNUM - 1; a[0] stack.top 栈顶元素所在位置 a1 a2 an …… head 栈顶在 表头 （1）定义 typedef struct lstack_type{ struct node * top; int length; }lstack_type; 入栈 出栈 top typedef struct node{ elemtype data; struct node* next; }lstack_type; （2）压入push void push(stack, new_node){ new_node-next = stack-top; stack-top = new_node; stack-length ++; } （3）弹出pop node_type * pop(stack){ node_type* out; out = stack-top; stack-top = stack-top-next; stack-length --; return out; } a1 new …… stack-top （4）栈空判断 stack.top == NULL; （5）置栈空 能否简单的使用 stack.top = NULL ? 如果栈中还有链点，必须逐个将链点占用的空间释放 void clean(stack){ node_type * temp; while( ! empty(stack)){ temp = pop(stack); free(temp); } } int empty(stack){ if(stack.top == NULL) return YES; else return NO; } 1、逐个将链点弹出 2、释放链点空间 *** 栈的应用 数制转换 十进制数向 d 进制数的转换。 反向考虑: d 进制数向十进制数的转换 例， (02504)8 = (1348)10 0×8+2 ( 0×8+2 ) ×8+5 ( ( 0×8+2 ) ×8+5 ) ×8+0 ( ( ( 0×8+2 ) ×8+5 ) ×8+0) ×8+4 = 1348 ( ( ( 0×8+2 ) ×8+5 ) ×8+0) ×8+4 = 1348 N