复习-第3章-2.ppt

InitStack S DestroyStack S ClearStack S StackEmpty s StackLength S GetTop S e Push S e Pop S e 堆栈的基本操作 字符堆栈 typedefstruct char base inttop intstacksize CharStack StatusInitStack CharStack S voidDestroyStack CharStack S StatusStackEmpty CharStack S StatusPush CharStack S charch StatusPop CharStack S char ch StatusGetTop CharStack S char ch 括弧匹配算法 StatusMatching char exp boolstate true char p exp ch CharStackS InitStack S while p 括弧匹配算法 switch p case case case Push S p break case if GetTop S ch 中缀式转后缀式 运算符 boolINOP charch switch ch case case case case case case case case case case case returntrue default returnfalse 中缀式转后缀式 运算符的优先级 intLevel charch switch ch case case return3 case case return2 case case case case case case return1 case return0 default return0 中缀式转后缀式 逆波兰式 voidTransSuf char suffix char exp CharStackS charch c ch exp if ch 0 ch InitStack S Push S while StackEmpty S if ch ch exp if ch 0 ch else suffix 0 break DestroyStack S 中缀式转后缀式 逆波兰式 if INOP ch suffix ch else switch ch case Push S ch break case Pop S c while c q c Pop S c break default while GetTop S c 计算后缀表达式的值 操作数是1位整数 StatusCacl char suffix char else 计算后缀表达式的值 操作数是1位整数 if Pop S v2 returnERROR if Pop S v1 returnERROR switch ch case v1 v2 Push S v1 break case v1 v2 Push S v1 break case v1 v2 Push S v1 break case v1 v2 Push S v1 break default returnERROR if Pop S value DestroyStack S returnERROR else DestroyStack S returnOK C 类实现栈 括弧匹配算法 StatusMatching char exp boolstate true CharStackS charch InitStack S 初始化操作在构造函数完成while state 括弧匹配算法 switch ch case case case S Push ch break case if S GetTop ch case case typedefstruct 链队列类型QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue a1 an Q frontQ rear Q frontQ rear 空队列 习题集3 14 3 14若以1234作为双端队列的输入序列 试分别求出满足以下条件的输出序列 1 能由输入受限的双端队列得到 但不能由输出受限的双端队列得到的输出序列 2 能由输出受限的双端队列得到 但不能由输入受限的双端队列得到的输出序列 3 既不能由输入受限的双端队列得到 也不能由输出受限的双端队列得到的输出序列 习题集3 14 2个元素的情况 输入12 输出为 输入受限 12 21输出受限 12 213个元素的情况 输入123 输入受限 队列为123 输出为312 321输出受限 队列为312 321 输出 4个元素的情况 输入1234 只需考虑先输出4 这时1234必须都在队列中 输入受限的双端队列 队列为1234 输出 输出受限的双端队列 队列为4xxx 链队列结构 typedefcharElemType 数据元素类型typedefstructQNode 结点类型ElemTypedata structQNode next QNode QueuePtr typedefstruct 链队列类型QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 输出受限的链队列 StatusInitQueue LinkQueue Q voidDestroyQueue LinkQueue Q StatusClearQueue LinkQueue Q StatusQueueEmpty LinkQueue Q StatusGetHead LinkQueue Q ElemType e StatusGetTail LinkQueue Q ElemType e StatusEnQueue LinkQueue Q ElemTypee StatusEnHead LinkQueue Q ElemTypee StatusDeQueue LinkQueue Q ElemType e 初始化 销毁 StatusInitQueue LinkQueue 入队 StatusEnQueue LinkQueue 队头入队 StatusEnHead LinkQueue 火车调度 voidArrange char in LinkQueue 火车调度 switch ch case P EnHead out ch EnQueue Op E break case H EnQueue out ch EnQueue Op A break case S 火车调度 GetTail out t GetHead out h if t H EnQueue out ch EnQueue Op A elseif h P EnHead out ch EnQueue Op E else break 火车调度 while h H 调整直到 头部是硬卧DeQueue out h EnQueue Op D EnQueue out h EnQueue Op A GetHead out h EnQueue out ch EnQueue Op A while h H 调整直到 头部不是硬卧DeQueue out h EnQueue Op D EnQueue out h EnQueue Op A GetHead out h C 类实现双端队列 火车调度 voidArrange char