数据结构：栈

数据结构 栈 单链表 所有结点通过指针的链接而构成的线性表称为单链表 线性表 a1 a2 an 的单链表可直观地画成 head是单链表的头指针 指向开始结点a1 an是终端结点 其指针域为空 不指向任何结点 一个单链表由头指针head唯一标识和确定 因此 可用头指针来命名单链表 循环链表 循环链表 circularlinkedlist 是一种首尾相接的链表 将单链表表尾结点原来的空指针改为指向表头结点 就成为循环链表 循环链表并不多占存储单元 但从循环链表的任一个结点出发都可以访问到此链表的每一个结点 因为当访问到表尾结点后又能返回到头结点 1 带头指针的循环链表 通常在循环链表的表头结点前面再加一个空结点 也叫空表头结点 表空时空表头结点的指针指向其本身 如下面的图所示为空循环链表 空表头结点除指针以外的数据域是没有用的 但为了将此结点与一般结点相区别 常常是将其赋以一个特别的数据 以与一般结点相区别 2 带尾指针的循环链表 另一种方法是不设头指针而改设尾指针 这样无论是找头结点还是尾结点都很方便 因为尾结点由尾指针rear来指示 则头结点的位置是rear next next 双链表 双向链表中每个结点除了有向后指针外 还有指向其前一个结点的指针 这样形成的链表中有两条不同方向的链 因此从某一结点均可向两个方向访问 双链表的结点形式为 其中链域prior和next分别指向本结点的直接前趋和直接后继结点 如果循环链表的结点再采用双向指针 就成为双向循环链表 栈 堆栈 Stack 堆栈简称为栈 是限定在表的一端进行插入或删除操作的线性表 进行插入或删除操作的一端称为栈顶 top 另一端称为栈底 bottom 插入元素又称为入栈 push 删除元素操作称为出栈 pop 不含元素的栈称为空栈 堆栈元素的插入和删除只在栈顶进行 总是后进去的元素先出来 所以堆栈又称为后进先出线性表或LIFO Last In First Out 表 堆栈的表示 堆栈的最简单的表示方法是采用一维数组 为形象起见 一般在图中将堆栈画成竖直的 设数组名为STACK 其下标的下界为1 上界为n 一般需用一个变量top记录当前栈顶的下标值 top也叫做栈指针 本例中top 4 1 入栈 push 入栈的主要操作是先将栈顶指针加1 然后将入栈元素放到栈顶指针所指示下标值的位置上 设用下标从1到n的数组ST表示堆栈 入栈的元素值为G 则可得到入栈函数如下 入栈函数 voidpush ST intn top G if top n printf 栈溢出 n 显示栈满信息 else top top 1 ST top G 2 出栈 Pop 出栈运算时 先将栈顶的元素值赋给某个变量 以备后面的运算应用 然后栈顶指针减1 将栈顶位置下移 假设已指定的变量为x 则出栈的函数如下 出栈函数 voidpop ST inttop x if top 0 printf 空栈 n 栈为空显示相应的信息 else x ST top top top 1 栈顶位置下移 设栈S的初始状态为空 元素a b c d e f g依次入栈 以下出栈序列不可能出现的是 a b c e d f gb c a f e g da e d c b f gd c f e b a gg e f d c b a 3 3 1链堆栈 链堆栈是栈的链式存储表示 它是只允许在表头进行插入和删除运算的单链表 它与普通的单链表没有什么不同 只是将头指针head改称为栈顶指针top 链堆栈的入栈算法 在栈顶指针是top的链堆栈中插入一个值为x的结点的算法 voidpush node top intx node s s node malloc sizeof node 建立一个结点指针 s data x s next top top s 链堆栈的出栈算法 intpop node top intx node p if top NULL printf 栈为空 n else x top data p top top top next free p return x 数制转换 栈的应用 将一个非负的十进制整数N转换为另一个等价的B进制数 通过 除B取余法 来解决 由于最先得到的余数是转化结果的最低位 最后得到的余数是转化结果的最高位 因此可以用栈来解决 2 堆栈在表达式计算中的应用 一个算术表达式 例如A B 其中加号 称作运算符 而A B称为运算数 对于由两个运算数和一个运算符组成的表达式 习惯上是将运算符写在两个运算数中间 这叫做中缀形式 计算机处理表达式时 常把运算符放在两个运算数的后面或前面 1 把运算符放在两个运算数的后面 例如AB 称为后缀形式 也叫做波兰式 2 把运算符放在两个运算数的前面 例如 AB 则称做前缀形式 也叫做逆波兰表达式 栈的应用 计算表达式的值 表达式的三种形式 中缀表达式 运算符放在两个运算对象中间 如 2 1 3 后缀表达式 不包含括号 运算符放在两个运算对象的后面 所有的计算按运算符出现的顺序 严格从左向右进行 如 21 3 前缀表达式 同后缀表达式一样 不包含括号 运算符放在两个运算对象的前面 如 213 表达式的计算 由于后缀表达式中没有括号 不需判别优先级 计算严格从左向右进行 故计算一个后缀表达式要比计算一个中缀表达式简单得多 把中缀表达式转化为后缀表达式 从头到尾扫描中缀表达式 对不同类型的字符按不同情况处理 1 如果是运算数则直接放入后缀表达式 2 如果是左括号则直接入栈 3 如果是右括号 则把从栈顶直到对应左括号之间的运算符依次退栈 并清除对应的左括号 4 对于运算符 如果该运算符的优先级大于栈顶优先级 则直接入栈 若该运算符的优先级小于或等于栈顶运算符优先级 则先把栈顶运算符出栈 写入后缀表达式 然后该运算符再入栈 5 扫描完成后 取出栈中所有运算符 写入后缀表达式 a b c d 把中缀表达式转化为前缀表达式 1 求输入串的逆序 2 从头到尾扫描表达式 3 假如是运算数 把它添加到输出串中 4 假如是右括号 将它入栈 5 假如是运算符 则i 假如栈空 此运算符入栈 ii 假如栈顶是右括号 此运算符入栈 iii 假如它的优先级高于或等于栈顶运算符 此运算符入栈 iv 否则 栈顶运算符出栈并添加到输出串中 重复步骤5 6 假如是左括号 栈中运算符逐个出栈并输出 直到遇到右括号 右括号出栈并丢弃 7 假如输入还未完毕 跳转到步骤2 8 假如输入完毕 栈中剩余的所有操作符出栈并加到输出串中 9 求输出串的逆序 2 3 2 1 5 4 1 1 4 5 1 2 3 2 表达式a b c d的后缀表达式是 abcd abc d abc d abcd 假设我们要将表达式2 3 2 1 5 4 1 转换成前缀形式 原表达式的逆序是 1 4 5 1 2 3 2 23 21 5 41 算术表达式的不同运算符有不同的运算优先顺序 如 在没有括号时 乘除运算 或 要比加减运算 或 优先进行 下面用一个简单的例子说明编译系统在处理算术表达式时 是如何应用堆栈这种数据结构的 假定表达式的运算数都是使用单个字母表示的 式中无括号且只有加 减 乘 除4种运算 而没有更复杂的运算 例如表达式X Y Z 使用S1和S2两个堆栈 S1用于存储运算数 S2用于存储运算符 编译系统处理时 将表达式从左向右逐个扫视一遍 并根据不同情况按以下原则处理 1 若是运算数 则将其压入S1栈 2 若是运算符且S2栈是空栈则将其压入S2栈 3 若是运算符且S2栈为非空栈 且此