数据结构与算法4.pptx

数据结构与算法长安大学电控学院李晓辉xiaohui.li@lixiaohui.chd@Chapter 4堆栈和队列几种常见的队列规则FIFO（First In First Out）LIFO (Last In First Out)SPT (Shortest Processing Time)EDD (Earliest Due Date)堆栈和队列堆栈： 用户只能在指定的一端插入元素，并且在同一端删除元素，因此堆栈具有LIFO的特性队列： 用户在一端插入元素而在另一端删除元素，队列具有FIFO的特性堆栈进栈a0a1……an-1出栈栈顶栈顶（Top）栈底（Bottom）堆栈的ADT表示ADT Stack 　DataObject: 　D={ ai | ai∈DataType, i=1,2, …,n, n≥0 }　Operation: 　void CreateStack(Stack *s, int maxsize) \\ 栈初始化 ，构造一个空栈。　void DestroyStack(Stacks) \\ 销毁栈 BOOL IsEmpty(Stack s) \\ 检测堆栈是否为空 BOOL IsFull(Stack s) \\ 检测堆栈是否已满 void Push(Stack *s, T X) \\ 新的元素进栈End Stack顺序栈顺序栈的存储映象与线性表相同，用一个一维数组定义，不同的主要是实现各种栈操作的算法。上溢（Overflow）：当堆栈已满，再做入栈运算时出现的现象下溢（Underflow）：当堆栈为空时，做出栈元算时出现的现象顺序栈的声明Typedef struct stack{ int Top, MaxStack; T Elements[MaxStack];}Stack;top4321栈底顺序栈按压入先后次序，最后压入的元素编号为4，然后依次为3,2,1 55s.top = 55F544E44s.top = 33D3D332C2C221B1B11s.top = 00A0A00As.top = -1顺序栈示意Void CreateStack(Stack *s, int maxsize){ s-Top=-1; s-MaxStack=maxsize;}BOOL IsEmpty(Stack s){ return s.Top0;}BOOL IsFull(Stack s){ return s.Top=s.Maxsize-1;}Void Push(Stack *s, T x){ if (IsFull(*s))printf(“Overflow”); else s-Elements[++s-Top]=x;}例3-1顺序栈的操作Void Pop(Stack *s){ if (IsEmpty(*s))printf(“Underflow”); else s-Top--;}void StackTop(Stack s, T *s){ if(IsEmpty(s)) printf(“Underflow”); else *x=s.Elements[s.Top];}例3-1顺序栈的操作链式栈用单链表方式存储指针的方向从栈顶向下链接 nextdataki+2 topki+1 ki k0 ? 链式栈的定义Typedef struct node{ T Element; struct node *Link;}Node;Typedef struct stack{ Node *Top;}Stack;Void Push(Stack *s, T x){ Node *p=NewNode2(x); p-Link=s-Top; s-Top=p;}void Pop(Stack s){ Node *p=s-Top; s-Top=p-Link; free(p);}例3-1链式栈的进栈出栈顺序栈和链式栈的比较时间效率所有操作都只需常数时间顺序栈和链式栈在时间效率上难分伯仲空间效率顺序栈须说明一个固定的长度链式栈的长度可变，但增加结构性开销实际中，顺序栈比链式栈应用更广顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取站内元素顺序栈读取内部元素的时间为O（1），而链式栈要沿着指针链游走，其读取第k个元素的计算时间为O（k）栈的应用栈的特点：LIFO常用来处理具有递归结构的数据深度优先有哪些信誉好的足球投注网站表达式求值子程序/函数调用的管理消除递归栈的应用1 数值转换十进制数N转换为其他d进制数是计算机实现计算的基本问题，其解决方法很多，其中的一个简单算法是基于下列原理：　N=N/d+N%d　例如：(158)10=(236)8 , 其运算过程如下：　N N/8 N%8 　158 19 6 19 2 3 2