目录

1 数据结构理论

1.1 数据

1.2 数据结构概念

1.3 算法的概念

1.3.1 算法与数据结构的区别

1.3.2 算法的比较

1.3.3 算法的特性

1.4 数据结构分类

1.4.2 物理结构 

2 线性表

2.1 线性表基本概念

2.2 线性表的顺序存储

2.2.1 线性表顺序存储(动态数组)的设计与实现

2.2.2 优缺点

2.3 线性表的链式存储(单向链表)

2.3.1 线性表的链式存储(单项链表)的设计与实现

2.3.2 优缺点

3 栈与队列

 3.1 栈（stack）

3.1.1 基本概念、特性、操作

 3.1.2 栈的顺序存储

3.1.3 栈的链式存储

3.1.4 栈的案例（应用）

3.2 队列

3.2.1 基本概念

 3.2.2 队列的顺序存储

 3.2.3 队列的链式存储

 4 树和二叉树

4.1 树的基本概念

4.2 树的表示法

 4.2.1 图形表示法

4.2.2 广义表表示法

4.2.3 左孩子右兄弟表示法

 4.3 二叉树概念

4.3.1 基本概念

4.3.2 二叉树的表示

 4.3.3 二叉树的遍历

 4.3.4 二叉树的非递归遍历

4.3.5 二叉树的层次遍历

 4.4.6 二叉树的应用：哈夫曼树 – 哈夫曼编码

---

1 数据结构理论

1.1 数据

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

1.2 数据结构概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构是计算机存储、组织数据的方式。是相互之间存在一种或多种特定关系的数据元素集合

1.3 算法的概念

算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立存在的一种解决问题的方法和思想。

对于算法而言，语言并不重要，重要的是思想。

1.3.1 算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法。

• 算法是为了解决实际问题而设计的。
• 数据结构是算法需要处理的问题载体。
• 数据结构与算法相辅相成。、

1.3.2 算法的比较

现在我们需要写一个求1 + 2 + 3 + … + 100的结果程序，你应该怎么写呢？

大多数人马上会写出下面代码

	var i int
		sum := 0
		n := 100
		for i = 0; i <= n; i++ {
			sum = sum + i
		}
		fmt.Printf("%d", sum)

当然，如果这个问题让高斯来去做，他可能会写如下代码：

sum := 0
	n := 100
	sum = (1+n)*n/2
	fmt.Printf("%d",sum)

很显然，不论是从人类还是计算机的角度来看，下列的算法效率会高出很多，这就是一个好的算法会让你的程序更加的高效。

1.3.3 算法的特性

算法具有五个基本的特性：输入、输出、有穷性、确定性和可行性

• 输入输出：算法具有零个或多个输入、至少有一个或多个输出。
• 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
• 确定性：算法的每一步骤都有确定的含义，不会出现二义性。
• 可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

1.4 数据结构分类

按照视点的不同，我们把数据结构分为逻辑结构和物理结构。

1.4.1 逻辑结构

• 集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。各个数据元素是平等的。他们共同属于同一个集合，数据结构中的集合关系类似于数学中的集合，如下图所示

• 

• 线性结构：线性结构中的数据元素之间是一对一的关系。如图。

• 

• 树形结构：树形结构中是数据元素之间存在一种一对多的层次关系，如图。

• 

• 图形结构： 图形结构的数据元素是多对多的关系，如图。

• 

• 1.4.2 物理结构 

• 顺序存储：是把数据元素存放在地址连续的存储单元里，其数据的逻辑关系和物理关系是一致的，如图。

• 

  如果所有数据结构都很简单有规律，一切就好办了，可实际上，总有人想要插队，或者放弃排队，所以元素集合中就会添加、删除掉成员，显然面对这样时常要变化的结构，顺序存储是不科学的，那怎么办呢？

• 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关数据的位置。如图。

• 

• 2 线性表

• 2.1 线性表基本概念

• 线性结构是一种最简单且常用的数据结构。线性结构的基本特点是节点之间满足线性关系。本章讨论的动态数组、链表、栈、队列都属于线性结构。他们的共同之处，是节点中有且只有一个开始节点和终端节点。按这种关系，可以把它们的所有节点排列成一个线性序列。但是，他们分别属于几种不同的抽象数据类型实现，它们之间的区别，主要就是操作的不同。

  线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同

  例：先来看一个大家感兴趣的话题，一年里的星座列表，是不是线性表呢？如图所示：

• 

• 线性表的性质：

• a0 为线性表的第一个元素，只有一个后继。
• an 为线性表的最后一个元素，只有一个前驱。
• 除 a0 和 an 外的其它元素 ai，既有前驱，又有后继。
• 线性表能够逐项访问和顺序存取。

• 线性表的抽象数据类型定义： 

• ADT线性表（List）
  Data
  线性表的数据对象集合为{ a1, a2, ……, an }，每个元素的类型均为DataType。其中，除第一个元素a1外，每个元素有且只有一个直接前驱元素，除了最后一个元素an外，每个元素有且只有一个直接后继元素。数据元素之间的关系是一一对应的。
   
  Operation（操作）
  // 初始化，建立一个空的线性表L。
  InitList(*L);
  // 若线性表为空，返回true，否则返回false
  ListEmpty(L);
  // 将线性表清空
  ClearList(*L);
  // 将线性表L中的第i个位置的元素返回给e
  GetElem(L, i, *e);
  // 在线性表L中的第i个位置插入新元素e
  ListInsert(*L, i, e);
  // 删除线性表L中的第i个位置元素，并用e返回其值
  ListDelete(*L, i, *e);
  // 返回线性表L的元素个数
  ListLength(L);
  // 销毁线性表
  DestroyList(*L);
  

  2.2 线性表的顺序存储

• 通常线性表可以采用顺序存储和链式存储。我们主要探讨顺序存储结构以及对应的运算算法的实现。

  采用顺序存储是表示线性表最简单的方法，具体做法是：将线性表中的元素一个接一个的存储在一块连续的存储区域中，这种顺序表示的线性表也成为顺序表。

• 2.2.1 线性表顺序存储(动态数组)的设计与实现

  操作要点:

• 插入元素算法
  1. 判断线性表是否合法
  2. 判断插入位置是否合法
  3. 判断空间是否满足
  4. 把最后一个元素到插入位置的元素后移一个位置
  5. 将新元素插入
  6. 线性表长度加1

• 获取元素操作
  1. 判断线性表是否合法
  2. 判断位置是否合法
  3. 直接通过数组下标的方式获取元素
• 删除元素算法
  1. 判断线性表是否合法
  2. 判断删除位置是否合法
  3. 将元素取出
  4. 将删除位置后的元素分别向前移动一个位置
  5. 线性表长度减1

注意: 链表的容量和链表的长度是两个不同的概念

2.2.2 优缺点

• 优点：

• 缺点：

• 2.3 线性表的链式存储(单向链表)

• 前面我们写的线性表的顺序存储(动态数组)的案例，最大的缺点是插入和删除时需要移动大量元素，这显然需要耗费时间，能不能想办法解决呢？链表。

• 链表为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。

• 

   单链表：

• 线性表的链式存储结构中，每个节点中只包含一个指针域，这样的链表叫单链表。
• 通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一起（如图）。

概念解释：

表头结点：链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息

数据结点：链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息

尾结点：链表中的最后一个数据结点，其下一元素指针为空，表示无后继。

2.3.1 线性表的链式存储(单项链表)的设计与实现

•  插入操作：

• 

  node->next = current->next; current->next = node;

•  删除操作：

• 

  current->next = ret->next;

2.3.2 优缺点

• 优点：

• 缺点：

3 栈与队列

 3.1 栈（stack）

3.1.1 基本概念、特性、操作

概念：首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

特性：后进先出。它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

操作：

• 栈的插入操作，叫做进栈，也成压栈。类似子弹入弹夹（如下图所示）
• 栈的删除操作，叫做出栈，也有的叫做弾栈，退栈。如同弹夹中的子弹出夹（如下图所示）

 3.1.2 栈的顺序存储

• 基本概念

栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top只是栈顶元素在顺序表中的位置。

• 设计与实现

因为栈是一种特殊的线性表，所以栈的顺序存储可以通过顺序线性表来实现。

3.1.3 栈的链式存储

• 基本概念

栈的链式存储结构简称链栈。

思考如下问题：

栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？

由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

• 设计与实现

链栈是一种特殊的线性表，链栈可以通过链式线性表来实现。

3.1.4 栈的案例（应用）

• 函数调用模型

        栈是嵌套调用机制的实现基础。

• 就近匹配

几乎所有的编译器都具有检测括号是否匹配的能力，那么如何实现编译器中的符号成对检测？如下字符串: 5+5*(6)+9/3*1)-(1+3）

算法思路：

从第一个字符开始扫描
当遇见普通字符时忽略，
当遇见左括号时压入栈中
当遇见右括号时从栈中弹出栈顶符号，并进行匹配
匹配成功：继续读入下一个字符
匹配失败：立即停止，并报错
结束：
成功: 所有字符扫描完毕，且栈为空
失败：匹配失败或所有字符扫描完毕但栈非空

• 当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性
• 栈非常适合于需要“就近匹配”的场合

• 中缀表达式和后缀表达式

        后缀表达式（由波兰科学家在20世纪50年代提出）

• 将运算符放在数字后面 ===》 符合计算机运算
• 我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯

实例：

中缀转后缀算法：

遍历中缀表达式中的数字和符号：
对于数字：直接输出
对于符号：
左括号：进栈  
运算符号：与栈顶符号进行优先级比较
若栈顶符号优先级低：此符号进栈  
（默认栈顶若是左括号，左括号优先级最低）
若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
右括号：将栈顶符号弹出并输出，直到匹配左括号,将左括号和右括号同时舍弃
遍历结束：将栈中的所有符号弹出并输出

• 基于后缀表达式计算

计算机是如何基于后缀表达式计算的？例如：8 3 1 – 5 * +

计算规则：

遍历后缀表达式中的数字和符号
对于数字：进栈
对于符号：
从栈中弹出右操作数
从栈中弹出左操作数
根据符号进行运算
将运算结果压入栈中
遍历结束：栈中的唯一数字为计算结果

3.2 队列

3.2.1 基本概念

队列是一种特殊的受限制的线性表。  

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的t（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。如下图：

 3.2.2 队列的顺序存储

• 基本概念

• 顺序循环队列

 3.2.3 队列的链式存储

• 基本概念

        队列也是一种特殊的线性表；可以用线性表链式存储来模拟队列的链式存储。

3.2.4 golang队列实现 

代码来源网络：golang队列queue的实现

package main
 
import "fmt"
 
//首先定义每个节点Node结构体，Value的值类型可以是任意类型，节点的前后指针域指针类型为node
type node struct {
	value interface{}
	prev *node
	next *node
}
//继续定义链表结构，定义出头结点和尾节点的指针，同时定义队列大小size
type LinkedQueue struct {
	head *node
	tail *node
	size int
}
//获取队列大小，只需要获取LinkedQueue中的size大小即可
func (queue *LinkedQueue) Size() int  {
	return queue.size
}
//Peek操作只需要获取队列队头的元素即可，不用删除。返回类型是任意类型，用接口实现即可。
//另外如果head指针域为nil，则需要用panic抛出异常，一切ok的话，返回队头节点的数值即可.
func (queue *LinkedQueue) Peek() interface{} {
	if queue.head == nil {
		panic("Empty Queue!")
	}
	return queue.head.value
}
//添加操作在队列中是比较重要的操作，也要区分队尾节点是否为nil，
//根据是否为nil，执行不同的连接操作，最后队列的size要加1，
//为了不浪费内存新增节点的指针变量要置nil
func (queue *LinkedQueue) Add(value interface{})  {
	newnode := &node{value,queue.tail,nil}
	if queue.tail == nil{
		queue.head = newnode
		queue.tail = newnode
	}else {
		queue.tail.next = newnode
		queue.tail = newnode
	}
	queue.size++
	newnode = nil
}
//队列的删除操作也是很简单，无非是节点的断开操作。
//在此之前，需要判断链表的状态即是否为nil？
//而后移除的队列最前端的节点，先用一个新的变量节点保存队列前面的节点，进行一系列操作之后，至nil，并将长度减少即可。
func (queue *LinkedQueue) Remove() {
	if queue.head == nil {
		panic("Empty queue.")
	}
	first_node := queue.head
	queue.head = first_node.next
	first_node.next = nil
	first_node.value = nil
	queue.size--
	first_node = nil
}
func main()  {
	queue := &LinkedQueue{head: nil,tail: nil,size: 0}
	for i:= 1;i<=5;i++{
		queue.Add(i)
	}
	fmt.Println("初始化后队列大小：",queue.size)
	fmt.Println("初始化后队首：",queue.Peek())
	queue.Remove()
	fmt.Println("执行删除后队列大小：",queue.size)
	fmt.Println("执行删除后队首：",queue.Peek())
}

输出结果：

 初始化后队列大小： 5
初始化后队首： 1
执行删除后队列大小： 4
执行删除后队首： 2

 4 树和二叉树

4.1 树的基本概念

树的定义： 

由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。

树的结构特点：

• 非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
• 树的定义具有递归性，树中还有树。
• 树可以为空，即节点个数为0。

若干术语：

• 根 ——即根结点(没有前驱)
• 叶子 ——即终端结点(没有后继)
• 森林 ——指m棵不相交的树的集合(例如删除A后的子树个数)
• 有序树 —— 结点各子树从左至右有序，不能互换（左为第一）
• 无序树 —— 结点各子树可互换位置。
• 双亲 ——即上层的那个结点(直接前驱) parent
• 孩子 ——即下层结点的子树 (直接后继) child
• 兄弟—— 同一双亲下的同层结点（孩子之间互称兄弟）sibling
• 堂兄弟 —— 即双亲位于同一层的结点（但并非同一双亲）cousin
• 祖先 —— 即从根到该结点所经分支的所有结点
• 子孙 —— 即该结点下层子树中的任一结点
• 结点 —— 即树的数据元素                                              
• 结点的度 —— 结点挂接的子树数（有几个直接后继就是几度）
• 结点的层次 —— 从根到该结点的层数（根结点算第一层）  
• 终端结点 —— 即度为0的结点，即叶子             
• 分支结点 —— 除树根以外的结点（也称为内部结点）
• 树的度 —— 所有结点度中的最大值（Max{各结点的度}）        
• 树的深度(或高度) —— 指所有结点中最大的层数（Max{各结点的层次}）

下图(c)中的结点数＝ 10，树的度＝ 3，树的深度＝ 3

4.2 树的表示法

 4.2.1 图形表示法

4.2.2 广义表表示法

用广义表表示法表示上图：

中国（河北（保定，石家庄），广东（广州，东莞），山东（青岛，济南））

根作为由子树森林组成的表的名字写在表的左边。

4.2.3 左孩子右兄弟表示法

 左孩子右兄弟表示法可以将一颗多叉树转化为一颗二叉树：

 节点的结构：

 节点有两个指针域，其中一个指针指向子节点，另一个指针指向其兄弟节点。

 4.3 二叉树概念

4.3.1 基本概念

• 定义

二叉树（binary tree）是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。

• 逻辑结构

一对二（1：2）

• 基本特征

        每个结点最多只有两棵子树（不存在度大于2的结点）；

        左子树和右子树次序不能颠倒（有序树）。

• 基本形态

• 性质

性质1: 若根节点的层次为1，则二叉树第i层上至多有2i-1个结点（i>0）

性质2: 在高度为k的二叉树中，最多有2k-1个结点（k≥0）。

性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）

性质4: 具有n个结点的完全二叉树的深度必为

性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

使用此性质可以使用完全二叉树实现树的顺序存储。

如果不是完全二叉树咋整???

             ------ 将其转换成完全二叉树即可

• 满二叉树

        一棵深度为k 且有2k -1个结点的二叉树。

        特点：每层都“充满”了结点

• 完全二叉树

除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。

         理解：k-1层与满二叉树完全相同，第k层结点尽力靠左

4.3.2 二叉树的表示

二叉树主要采用链式存储结构，顺序存储结构仅适用于完全二叉树和满二叉树，还有静态链表。

• 二叉树的顺序存储结构：
• 

二叉树的链式存储结构：

二叉树的链式存储结构主要有二叉链表和三叉链表两种。

二叉链表：

二叉链表的节点结构如下：

//节点数据类型定义
type BinaryNode struct {
	Ch byte
 
	LChild *BinaryNode
	RChild *BinaryNode
}

 三叉链表：

三叉链表的的节点结构如下：

每个节点有三个指针域，其中两个分别指向子节点（左孩子，右孩子），还有一共指针指向该节点的父节点。

//节点数据类型定义
type BinaryNode struct {
	Ch byte
	LChild *BinaryNode
	RChild *BinaryNode
	Parent *BinaryNode
}

 4.3.3 二叉树的遍历

遍历的定义：

指按某条搜索路线遍访每个结点且不重复（又称周游）。

遍历用途：

它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。  

遍历方法：

牢记一种约定，对每个结点的查看都是“先左后右” 。

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。

从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

从虚线的出发点到终点的路径上，每个结点经过3次。

第1次经过时访问＝先序遍历

第2次经过时访问＝中序遍历

第3次经过时访问＝后序遍历

 4.3.4 二叉树的非递归遍历

二叉树三种遍历的递归算法可以通过设立一个栈用非递归 算法实现。以中根次序遍历为例，其非递归算法描述及栈变化 如下图所示。

 

 首先将每个节点都设置一个标志，默认标志为假，根据节点的的状态进行如下流程。

 执行上述流程，可以得到先序遍历的结果，如果想得到其他二叉树遍历结果，修改2.4步骤即可。

4.3.5 二叉树的层次遍历

二叉树的层次遍历过程及队列变化如下图所示。

 4.4.6 二叉树的应用：哈夫曼树 – 哈夫曼编码

 二叉树的路径长度：从根结点到所有结点的路径长度之和称为该二叉树的 路径长度，即

 完全二叉树的路径长度最短，反之不然。

二叉树的外路径长度：从根结点到所有叶子结点的路径长度之和称为该二叉树 的外路径长度。一种编码方案的编码总长度为对应编码二叉 树的外路径长度，完全二叉树的外路径长度最短。

二叉树的带权外路径长度：在字符使用概率各不相同的情况下，将字符的使用概率 作为二叉树中叶子结点的值，称为权。 从根到X结点的带权路径长度是X结点的权值与从根到X 结点路径长度的乘积。所有叶子结点的带权路径长度之和称 为二叉树的带权外路径长度，即

 式中， wi为第i个叶子结点的权值， li为从根到第i个叶子结 点的路径长度。

构造哈夫曼树并获得哈夫曼编码：

哈夫曼树定义为带权外路径长度最短的二叉树。如给定n个叶子结点及其权值集合，则对应的哈夫曼树不唯一 。

 构造哈夫曼树算法思路为：使权值越大的叶子结点越 靠近根结点，这样构造的二叉树，其带权外路径长度最小。

哈夫曼编码的译码：

利用哈夫曼树进行译码的过程：已知一个二进制位串S，从串S的第一位开始逐位地去匹配二叉树边上标记的0和 1， 由哈夫曼树的根结点出发，遇到0时向左，遇到1时向右，若 干连续的0和1确定一条从根到某个叶子结点的路径。一旦到达一个叶子结点，便译出一个字符。

• 采用静态链表存储哈夫曼树

        静态链表的结点结构如下：

 采用一维数组存储上述结点，对于有n个叶子结点的哈 夫曼树，数组长度为2n-1，前n个元素存储叶子结点，后n1个元素存储2度结点。设由权值集合{5,29,7,8,14,23,3,11}构 造一棵哈夫曼树，结点数组的初始状态和最终状态如下图 所示。

 若权值集合{5,29,7,8,14,23,3,11}对应字符A～H，哈夫曼 树和哈夫曼编码如下图所示。