栈 队列 指针 链表 —— 跟WilliamYan一起学算法

又见面了!这里是《跟WilliamYan一起学算法》!
说实话今天学的其实是数据结构而非算法啊……不过数据结构是算法的基础嘛。用对了数据结构,往往可以大幅简化算法。那么,就让我们进入今天的主题吧!

定义

栈是一种采用后进先出策略的抽象数据结构,它是一种运算受限的线性表,其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶,栈顶的第一个元素被称为栈顶元素,相对地,把另一端称为栈底。

栈是一种线性的数据结构。

C++ STL stack实现

声明:

#include<stack>
using namespace std;
stack<_type_> _stackName_;

有关函数

push(val) 元素 $val$ 入栈

pop() 弹出栈顶元素

top() 返回栈顶元素

size() 返回栈大小

empty() 返回栈是否为空(bool型)

=[^size]: 此处size函数返回值为unsigned型,需注意精度问题

常规数组实现

#ifdef MAXN
#undef MAXN
#endif
#define MAXN 100000

int stack[MAXN] = {0}, stackindex = 1;

void push(int x) { stack[stackindex++] = x; }
void pop(void) { stackindex--; }
int top(void) { return stack[stackindex]; }
int size(void) { return stackindex; }
bool empty(void) { return stackindex == 0; }

#ifdef MAXN
#undef MAXN
#endif

栈相关-表达式

表达式树是不可执行的代码,它只是用于表示一种树状的数据结构,树上的每一个节点都表示为某种表达式类型。一般地,叶节点为数,非叶节点为符号

二元表达式可以很自然的联系到二叉树:以基本运算对象作为叶节点中的数据;以运算符作为非叶节点中的数据,其两棵子树是它的运算对象,子树可以是基本运算对象,也可以是复杂表达式。如图是一个表达式树。
《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

前缀、中缀和后缀表达式

中缀表达式(中缀记法)
我们平时缩写的表达式,将运算符写在两个操作数中间的表达式,称作中缀表达式。在中缀表达式中,运算符有不同的优先级,圆括号用于改变运算顺序,这使得运算规则比较复杂,求值过程不能直接从左到右顺序进行,不利于计算机处理。

后缀表达式
将运算符写在两个操作数之后的表达式称作后缀表达式。后缀表达式中没有括号,并且运算符没有优先级。后缀表达式的求值过程能够严格按照从左到右的顺序进行,有利于计算机处理。

前缀表达式
前缀表达式是将运算符写在两个操作数之前的表达式。和后缀表达式一样,前缀表达式没有括号,运算符没有优先级,能严格按照从右到左的顺序计算。

另外,算式表达式和表达式树的关系如下:

  • 表达式树的先根遍历:前缀表达式
  • 表达式树的中根遍历:中缀表达式
  • 表达式树的后根遍历:后缀表达式

表达式的转换

利用表达式树

给定一个表达式的中缀形式:(4+1*(5-2))-6/3
首先将每个运算加上括号,区分优先级,得到(4+(1*(5-2)))-(6/3)
括号外的-优先级最低,作为根节点,(4+(1*(5-2)))作为左子树,(6/3)作为右子树;
递归的转换4+(1*(5-2)),+最为根节点,4是左子树,(1*(5-2))是右子树。*是右子树的根节点,1是左子树,(5-2)是右子树。最后计算(5-2),-是根节点,5是左子树,2是右子树。得到的表达式树如文章之初给出的图。

构造好表达式树之后,前缀表达式和中缀表达式可根据先根遍历和后根遍历得到。
前缀表达式:- + 4 \* 1 - 5 2 / 6 3
后缀表达式:4 1 5 2 - \* + 6 3 / -

利用栈

将中缀表达式转换为后缀表达式
step1:初始化一个栈和一个后缀表达式字符串
step2:从左到右依次对中缀表达式中的每个字符进行以下处理,直到表达式结束

  • 如果字符是‘(’,将其入栈
  • 如果字符是数字,添加到后缀表达式的字符串中
  • 如果字符是运算符,先将栈顶优先级不低于该运算符的运算符出栈,添加到后缀表达式中,再将该运算符入栈。注意,当‘(’在栈中时,优先级最低
  • 如果字符是‘)’,将栈顶元素出栈,添加到后缀表达式中,直到出栈的是‘(’
    step3:如果表达式结束,但栈中还有元素,将所有元素出栈,添加到后缀表达式中

例如给定一个表达式的中缀形式:(4+1*(5-2))-6/3,栈中元素和表达式的变化如下表所示:

《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

最后得到后缀表达式为 4 1 5 2 - * + 6 3 / -

将中缀表达式转换为前缀表达式
中缀表达式转换到前缀表达的方法和转换到后缀表达式过程一致,细节上有所变化
step1:初始化两个栈s1 和s2
step2:从右到左依次对中缀表达式中的每个字符进行以下处理,直到表达式结束

  • 如果字符是‘)’,将其入栈
  • 如果字符是数字,添加到s2中
  • 如果字符是运算符,先将栈顶优先级不低于该运算符的运算符出栈,添加到s2中,再将该运算符入栈。当‘)’在栈中时,优先级最低
  • 如果字符是‘(’,将栈顶元素出栈,添加到s2中,直到出栈的是‘)’
    step3:如果表达式结束,但栈中还有元素,将所有元素出栈,添加s2中
    step4:将栈s2中元素依次出栈,即得到前缀表达式

给定一个表达式的中缀形式:(4+1*(5-2))-6/3,其前缀形式为 - + 4 * 1 - 5 2 / 6 3

=[表达式 内容来源]: https://blog.csdn.net/fireflylane/article/details/83017889 "表达式树与前中后缀表达式"

队列

定义

队列是一种采用先进先出策略的抽象数据结构,它的想法来自于生活中排队的策略

队列也是一种线性的数据结构。

C++ STL queue实现

声明:

#include<queue>
using namespace std;
queue<_type_> _queueName_;

有关函数

push(val) 元素 $val$ 入队列

pop() 弹出队列前端元素

front() 返回队列前端元素

back() 返回队列尾端元素

size() 返回队列大小

empty() 返回队列是否为空(bool型)

=[^size]: 此处size函数返回值亦为unsigned型,需注意精度问题

循环队列

如果使用顺序表作为队列的话,当处于右图状态则不能继续插入新的队尾元素,否则会因为数组越界而导致程序代码被破坏。
《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》
由此产生了由链表实现的循环队列,只有队列未满时才可以插入新的队尾元素。
《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

基本操作:

定义链表队列

定义结构体中front指示队头位置,rear指示队尾位置,base指针用于申请空间并存放数据。

《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

初始化队列

使用指针*base申请100个内存空间,frontrear分别为0,此时队列为空

《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

判断空或满

  • 初始化时,front = rear = 0 时为空,Q->rear = (0+1)%100 = 1,队列未满可以插入队列

    《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

  • 入队3个元素时,rear = 3Q->rear = (3+1)%100 = 4,队列未满

    《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

  • 入队99个元素时,rear = 99Q->rear = (99+1)%100 = 0,队列满,不可入队

    《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

  • 出队2个元素时,front = 2

    出队后,执行两次 Q->front = (Q->front + 1) % MAXQSIZE,得到Q->front = 2

    《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

  • 再次入队1个元素时,rear = 0Q->rear = (99+1)%100=0,队列未满,可以入队

    《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

指针

一般指针

定义方式

_type * _name

思考int** p,int****** p的含义?

数组

  • 一个数组由一块连续的内存单元组成
  • 数组名就是这块内存的首地址

设有数组 int a[100]

思考 a的含义?

思考 a+50 的含义?

链表

链表是一种在物理存储单元上非连续/非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

属性

(此处介绍单向链表)

  1. 相邻元素之间通过指针连接。
  2. 最后一个元素的后继指针为NULL。
  3. 链表的空间能够按需分配。
  4. 没有内存空间的浪费。

《栈 队列 指针 链表 —— 跟WilliamYan一起学算法》

下面是单向链表的声明:

class ListNode
{
private:
    int val;
    ListNode *nextp;

public:
    ListNode(int data);
    void setData(int data);
    int getData();
    void setNext(ListNode next);
    ListNode getNext();
};

ListNode::ListNode(int data)
{
    val = data;
}
void ListNode::setData(int data)
{
    val = data;
}
int ListNode::getData()
{
    return val;
}
void ListNode::setNext(ListNode next)
{
    *nextp = next;
}
ListNode ListNode::getNext()
{
    return *nextp;
}

=[链表 内容来源]: https://www.jianshu.com/p/5cb5fe19c510 "数据结构——链表"

总结

所谓算法,就是对于数据的操作和计算。因此用来存储数据的数据结构就十分重要了。
比如在很多题目中,使用优先队列可以简化每次操作前所需的排序动作,从而简化代码,加快执行速度。而优先队列,其实就是使用来实现的,这个以后会讲到的
尽管STL里有许多现成的封装函数,不过实际应用中我们还是应当考虑到执行速度问题,权衡利弊,争取写出更优秀的代码。
以上。

END

© 2019 William Yan 转载请注明出处
推荐阅读算法可视化-链表

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据