数据结构与算法

数据结构编程心得

1. 确定好所有属性
2. 先用注释的方式将整个算法思路写下来，再一步步慢慢实现
3. 每个成员函数的编写都根据属性来进行考虑、修改
4. 确定成员函数需不需要return(鉴别方法和函数)

数组栈

先进后出规则(浏览器历史记录等)

属性

1. 容器：列表

实现思路

1. 创建一个空列表作为栈的容器(属性)
2. 获取栈的大小

• len 方法

3. 判断栈是否为空
4. 压栈

• 需要传值
• push()函数需自己实现
• 利用列表的append()方法

5. 弹栈

• 判断栈是否为空
• pop()函数为内置函数

6. 返回栈顶元素

• 判断栈是否为空
• 返回反向索引的第一个值

栈应用

1. 数字逆序输出
2. 符号匹配问题

循环队列

先进先出，循环队列

属性

1. 容器：列表
2. 队列的长度
3. 队列首部元素的索引位置

实现思路

1. 初始化队列

• 容器为列表，列表由10个None cap组成

  [None,None,None,None,None,None,None,None,None,None,None]

• 队列长度默认为0
• 队列首部元素的索引位置默认为0

2. 获取队列长度

• 使用len 方法

3. 判断队列是否为空

• 看队列长度是否为0

4. 为队列重置容器大小

• 需要传入增加大小的参数cap
• 用一个列表保存旧的队列的值
• 重新设置容器的大小：

  新的容器大小 = [None]* cap

• 将保存旧队列的列表的值重新赋值到新队列中：

  a. 保存旧队列首部元素索引
  b. 将旧列表的元素按照原本位置放置到新的容器中，映射关系公式为：
  新队列的第一个元素对应旧队列的首部元素
  新队列其他元素对于旧队列的其他元素索引位置关系公式 ：
            索引位置 = (旧队列首部元素的索引位置+1) % 旧容器的长度

• 将队列首部元素的索引置为0

5. 删除首部元素(出队)

• 判断队列是否为空
• 将首部元素的值放入一个变量中
• 将原首部元素的索引位置的值设置为None
• 使用插入队列的公式将队列的首部元素的索引位置重新设置：

  新的首部元素位置索引 = (旧的首部元素位置索引+1) % 容器的总长度

• 队列长度减1

6. 在队列尾部加入元素(入队)

• 需要传值
• 判断容器长度是否足够，若不够则调用重置容器大小的方法增加队列容器大小
• 在队列末尾加入元素的索引位置公式为：

  新元素索引位置 = (队列首部元素的索引+队列的长度) % 容器的总长度

• 为新的索引位置赋值
• 队列的长度+1

链表

单向链表

属性

结点类

1. 结点的值
2. 下一个结点的引用

链表类

1. 链表首部结点

实现思路

1. 初始化

• 首部结点(初始化为None)

2. 链表长度

• 从链表首部结点开始遍历链表，直至结点的下一个结点引用为0
• 返回链表长度

3. 判断链表是否为空

• 链表长度是否为0

4. 首部加结点

• 保留旧首部结点
• 将新首部结点的下一个结点引用修改为旧首部结点
• 修改链表的首部结点引用

5. 尾部加结点

• 遍历到链表的尾部结点
• 修改尾部结点的下一个结点引用

6. 在指定位置加入结点

• 判断链表是否为空
• 遍历到指定位置(使用循环：指定位置-1)
• 保存指定位置下一个结点的引用
• 修改指定位置下一个结点的引用指向新增结点
• 修改新增结点的下一个结点引用指向之前保存的结点引用

7. 在指定位置删除结点

• 判断链表是否为空
• 遍历到指定位置前一个位置
• 修改三个结点的引用

8. 查找指定位置的结点

• 判断链表是否为空
• 遍历到指定位置，返回结点的值

9. 打印链表

• 遍历每一个结点，并将结点的值一次追加放入一个空列表中
• 打印输出列表

双向链表

每个结点都包含了指向其前驱结点的引用和指向后驱结点的引用。在列表的起始位置添加头结点，在列表的结尾位置添加尾结点。这些结点并不存储主序列的元素

属性

结点类

1. 结点值
2. 结点前缀引用(初始值需要传入)
3. 结点后缀引用(初始值需要传入)

双向链表类

1. 尾部哨兵
2. 头部哨兵
3. 头部哨兵的后缀引用
4. 尾部哨兵的前缀引用
5. 链表长度

实现思路

1. 初始化结点类
2. 初始化双向链表类
3. 链表长度
4. 链表是否为空
5. 向链表追加结点(每次都在链表的尾部哨兵前加入)

• 保存尾部哨兵的前缀结点
• 修改尾部哨兵的前缀引用为新结点
• 修改尾部哨兵的旧的前缀结点的后缀引用为新结点
• 修改新结点的前后缀引用
• 链表长度加1

6. 在指定结点间加入新的结点(传入值，前后缀结点)

• 创建新结点，结点前后缀引用为传入的前后缀结点
• 修改前缀结点的后缀引用
• 修改后缀结点的前缀引用
• 链表长度+1
• 返回新加入的结点

7. 删除结点(传入结点)

• 判断链表是否为空
• 保存要删除的结点
• 修改删除结点的前后缀结点的引用
• 链表长度-1

8. 打印输出

• 判断是否为空
• 初始化空列表
• 遍历链表向空列表中追加元素
• 打印列表

注：在双向链表中，删除、加入结点对每一个涉及到的结点的前后缀引用都要进行修改

循环链表实现队列

队列有一个头部和尾部，但是尾部的next指针指向头部

属性

结点类

1. 结点的值
2. 下一个结点的引用

循环链表实现

1. 队列的尾部引用
2. 队列的长度

实现思路

1. 初始化结点类
2. 初始化循环队列类

• 需传入一个结点作为尾部引用
• 将尾部的next指针(头部)也指向node
• 队列长度

3. 队列长度
4. 队列是否为空
5. 队列尾部加入结点

• 保存头部结点
• 将加入结点的引用设置为头部结点
• 重置队列的尾部引用
• 长度+1

6. 队列首部删除元素

• 保存首部元素
• 修改尾部引用指向首部元素的下一个结点引用
• 长度-1
• 返回删除的元素

7. 打印

树

二叉树

每个父节点最多有两个子节点，深度搜素使用递归，广度搜索使用栈

属性

节点类

1. 节点值
2. 左子树
3. 右子树

二叉树类

1. 根节点

实现思路

1. 初始化节点类
2. 初始化二叉树类
3. 加入节点(传入节点)

• 判断根节点是否为空，为空则插入
• 根节点追加到空列表中
• 空列表不为空则循环
• 利用栈，分别判断左右子树(先左后右)是否为空，为空则插入节点，否则将该节点压栈

4. 前序遍历(传入节点)

• 按照遍历顺序分别判断左右节点是否为空，不为空则递归
• 在该节点被遍历的位置打印输出

5. 后序遍历
6. 中序遍历
7. 层序遍历

• 判断根节点是否为空
• 根节点追加到空列表中
• 空列表不为空则循环
• 打印输出列表的首部元素
• 利用栈，分别判断左右子树是否为空，不为空则将该节点压栈

8. 树高

• 判断根节点是否为空，为空返回0
• 判断左右子树的四种情况(elif)，左右子树均为空时打印输出，其他情况哪个节点不为空该节点就调用递归并加1
• 左右节点都不为空的情况下取递归次数最多的那一边

9. 叶子节点

• 判断根节点是否为空
• 判断左右子树的四种情况(elif)，左右子树均为空时打印输出，其他情况哪个节点不为空该节点就调用递归

二叉搜索树

二叉搜索树是具有有以下性质的二叉树：

• 若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
• 若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
• 左、右子树也分别为二叉搜索树。

堆

• 大顶堆：所有的父节点的值都比孩子节点大，叶子节点值最小。root 根节点是第一个节点值最大
• 小顶堆：和大顶堆相反，所有父节点值，都小于子节点值，root 根节点是 第一个节点值最小