线性结构(链表、栈和队列、中缀、前缀、后缀表达式转换)_已知头指针 h 指向一个带头结点的非空单循环链表,结点结构为 data | next,其中 ne

线性结构中值得探讨深究的题目~

1.已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为 data | next，其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ D ）

A：h->next=h->next->next; q=h->next; free(q);

B：q=h->next; h->next=h->next->next; free(q);

C：q=h->next; h->next=q->next; if (p!=q) p=h; free(q);

D：q=h->next; h->next=q->next; if (p==q) p=h; free(q);

讲解：

一开始我错选了B项，没有考虑到链表的特殊情况——仅有一个结点（除了带头的头节点外）。

A选项中，h->next=h->next->next修改了头结点的后继，q指针找不到第一个结点了！A错；

B选项中，假设这个链表中只剩下最后一个结点（即尾指针p指向的结点），q=h->next q指针指向带删除的第一个结点（最后一个结点），则删除后，还需要修改p指针，（  若不修改则会成为野指针！ ）B错；

C、D选项中，q=h->next;h->next=q->next，q指针指向待删除的第一个结点，头结点指向第二个结点，此时若尾指针p和q指针指向同一个位置的话，则我们需要修改尾指针p，将其指向头结点（空单循环链表），则选D

栈 - 表达式的计算 

栈模拟求中缀表达式

中缀表达式，就是我们平时的对于表达式的正常写法。

计算机计算中缀表达式

——————两个栈，一个用来储存操作数，一个用来储存操作符。

从左到右，进行表达式扫描。

出栈的操作数，先出的放操作符的右边。

 

栈模拟求后缀表达式

例如：中缀表达式：5 + (7 * 3) - 5 * (2 + 1)

则对应的后缀表达式为： 573 * + 521 + * -

方法：对中缀表达式手动加括号（（5 + (7 * 3)） -（ 5 * (2 + 1)）），然后从外往内括号，依次将其中的操作符往括号外面提取。

计算机计算后缀表达式

一个操作数栈

从左往后扫描

先出栈的操作数放右边

 

栈模拟求前缀表达式

前缀表达式怎么由中缀表达式转换过来？

———类似于后缀表达式

——————中缀表达式：5 + (7 * 3) - 5 * (2 + 1)

则对应的前缀表达式为：- + 5 * 7 3  * 5 + 2  1

方法：对中缀表达式手动加括号（（5 + (7 * 3)） -（ 5 * (2 + 1)）），然后从外往内括号，依次将其中的操作符往括号外面提取。

计算机计算前缀表达式

（和后缀表达式完全相反！！！对比记忆）

一个操作数栈

从右往左扫描

先出栈的操作数放左边

 

中缀表达式转后缀表达式栈模拟

中缀表达式转前缀表达式栈模拟