数据结构
- 数据结构入门
- Powered by Bill
- date: 2019/09/29
- blog: https://www.webpro.ltd
数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。
数据的逻辑结构和物理结构是数据结构的两个密切相关的方面,同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构,而算法的实现依赖于指定的存储结构。
数据结构的研究内容是构造复杂软件系统的基础,它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次;再通过抽象,舍弃数据元素的具体内容,就得到逻辑结构。类似地,通过分解将处理要求划分成各种功能,再通过抽象舍弃实现细节,就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体(即具体问题)到抽象(即数据结构)的过程。然后,通过增加对实现细节的考虑进一步得到存储结构和实现运算,从而完成设计任务。这是一个从抽象(即数据结构)到具体(即具体实现)的过程。
FAQ
Q1: 为什么要学数据结构?
- 承前启后:学语言->学算法->写程序
- 高级计算机程序设计的理论指导
- 提升编程能力
- 面试中经常问到
Q2:有哪些数据结构?
- 线性表、栈、(字符)串、数组、广义表、树、二叉树、图
- 重点是线性表、二叉树
- 对于每种数据结构会讲解其添加、更新、删除、查询、排序等操作的实现
Q3:学习境界?
- 境界一 听懂理论,听懂算法思路
- 境界二 完成主要数据结构的基本算法实现(入门)
- 境界三 更多数据结构,更多算法的实现(进一步提高数据结构功底)
- 境界四 融会贯通、举一反三,在后续开发中综合应用数据结构知识
算法
algorithm 英[ˈælɡərɪðəm] 美[ˈælɡərɪðəm]
什么是算法?
For Example: 求 1+2+3+…+100 = ?
- 依次相加c
1
2
3
4
5int res = 0;
for(int i = 0; i <= 100; i++){
res += i;
}
cout << res << endl; - 高斯求和c
1
2
3
4
5
6int res = 0;
int add_max = 100;
/* 梯形面积公式算法 */
res = (1 + add_max) * add_max / 2;
/* 三角形面积公式算法 (0+1+2+...+100, h = 101)*/
res = add_max * (add_max + 1) / 2; - 递归c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/*sum(100) = sum(99) + 100
sum(99) = sum(98) + 99
=>
sum(100) = sum(98) + 99 + 100
...
sum(100) = sum(1) + 2 + ... + 99 + 100*/
int sum(int m){
if(m > 1){
return sum(m-1) + m;
}else{
return 1;
}
}
int main(int argc, char *argv[]){
cout << sum(100) << endl;
return 0;
}
以上3个算法显然高斯求和算法的时间复杂度及空间复杂度最优
算法特征:
- 输入
- 输出
- 可行性
- 有穷性
- 确定性
时间复杂度(Time Complexity)定义
- (1)时间频度:T(n),n表示问题的规模。一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
- (2)时间复杂度:一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。在T(n)=4n²-2n+2中,就有f(n)=n²,使得T(n)/f(n)的极限值为4,那么O(f(n)),也就是时间复杂度为O(n²)
- 时间复杂度一般讨论最坏的时间复杂度
- 定义O(最坏情况<=),例如T(n) = O(n²)
- 定义Ω(最好情况>=),例如T(n) = Ω(n²)
- 定义Θ(最好情况与最坏情况同阶),例如T(n) = Θ(n²)
时间复杂度的计算
- 找出算法中的基本语句
执行次数最多的就是基本语句,通常是最内层循环的循环体 - 计算基本语句的执行次数的数量级
- 用O表示
一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
时间复杂度计算例题
1.T(n) = 1, T(n) = O(1)
1 |
|
100个简单语句其时间复杂度仍为O(1)
2.一个循环的时间复杂度为O(n)
1 |
|
T(n) = n, T(n) = O(n)
时间复杂度为O(log2(n))
c1
2
3
4
5
6
7
8int n = 8, count = 0;
for(int i = 0; i <= n; i*=2){
count++;
}
/*1,2,4,8,16,32,...
设循环x次,则2^x = n => x = log2(n)
T(n) = log2(n)
T(n) = O(log2(n))*/时间复杂度为O(n²)
c1
2
3
4
5
6int n = 8, count = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
count++;
/*T(n) = n x n
T(n) = O(n²)*/时间复杂度为O(nlog2(n))
c1
2
3
4int n = 8, count = 0;
for(int i = 0; i <= n; i*=2)
for(int j = 0; j <= n; j++)
count++;时间复杂度为O(n²)
c1
2
3
4
5
6int n = 8, count = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= i; j++)
count++;
/*T(n) = n x (1+2+3+...+n) = 0.5n + 0.5n²
T(n) = O(n²)*/
常用的时间复杂度级别
空间复杂度(Space Complexity)定义
类似于时间复杂度的讨论,一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地"进行的,是节省存储的算法,有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。
S(n) = O(g(n))
空间复杂度 O(1)。如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)
举例:c1
2
3
4
5int i = 1;
int j = 2;
++i;
j++;
int m = i + j;代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)
空间复杂度 O(n)
c1
2
3
4
5
6int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)
由此可见,递归算法效率低下,体现在空间复杂度高。
线性表(linearlist)
- Java的LinkList底层是双向链表
- ArryList是顺序表
- 相同的数据类型
- 序列(顺序性)
- 有序
数组
数组是连续的一块内存空间
链表 — 链式存储结构
非连续的内存空间
线性表实现
- Java中ArrayList底层采用数组实现
- Java中LinkedList底层采用双向链表实现
- 我们通过对ArrayList和LinkedList的简单实现练习线性表
- 实际上的ArrayList和LinkedList比我们写的要复杂
- 无论是ArrayList还是LinkedList,其都有以下(包括但不限于)方法,与存储结构无关。因此我们定义了如下接口,给ArrayList和LinkedList使用
1 |
|
ArrayList实现
- ArrayList底层是数组
Ⅰ. 用Java模拟实现ArrayList基本操作
ArrayList类
1 |
|
TestArrayList类
1 |
|
Ⅱ. 用C语言模拟实现ArrayList基本操作
1 |
|
LinkedList实现
- LinkedList底层是双向链表
- 我们用单项链表实现MyLinkedList
Ⅰ. 用Java模拟实现LinkedList基本操作
LinkedList类
1 |
|
TestLinkedList类
1 |
|
Ⅱ. 用C语言模拟实现LinkedList基本操作
1 |
|
其他线性表
- 一般为了编程方便,头节点和尾节点(如果存在)是不存储数据的
- 为了保持算法的一致性,有时添加首尾节点
双向链表
循环链表
Java中
- Vector 顺序表
- ArrayList 顺序表
- LinkedList 双向链表
Vector、ArrayList底层均为可变长度的数组。Vector线程安全,效率低,已基本弃用;ArrayList线程不安全,效率高。ArrayList扩容策略为每次扩容原长度的50%。
栈和队列
本节分为
- 栈(Stack)
- 队列(Quene)
- Java中的栈和队列
- Disruptor并发框架中的Quene
栈(Stack)
- 操作受限的线性表
- 先进后出,删除与加入均在栈顶操作
- 栈也称为堆栈,是一种线性表。
- 堆栈的特性: 最先放入堆栈中的内容最后被拿出来,最后放入堆栈中的内容最先被拿出来, 被称为先进后出、后进先出。
- 堆栈中两个最重要的操作是PUSH和POP,两个是相反的操作。
- PUSH:在堆栈的顶部加入一 个元素。
- POP:在堆栈顶部移去一个元素, 并将堆栈的大小减一。
其限制是仅允许在表的一端进行插入、删除操作,不允许在其他任何地方进行插入、删除操作。表中进行插入删除的一端称为栈顶(top),栈顶保存的元素称为栈顶元素。相对于表的另一端成为栈底(bottom)。
- 插入操作 -> 入栈
- 删除操作 -> 出栈
- 专业词汇:push入栈,pop出栈,peek栈顶元素
栈的接口:
1 |
|
队列(Quene)
队列(Queue)也是一种运算受限的线性表,它的运算限制与栈不同,是两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进),允许删除的一端称为队尾(rear),允许插入的一端称为队头 (Front),队列的操作原则是先进先出的,所以队列又称作FIFO表(First In First Out)
- 技术案例:多线程中的就绪队列和阻塞队列
- 主要操作:入队、出队
队列的接口:
1 |
|
其他队列
双端队列Deque
Java中的栈和队列类
- Stack类: 已过时,因为public class Stack<E> extends Vector<E>
- Quene 队列类
- Deque 双端队列(一般默认受限规则为栈操作)
例:用栈实现10进制转2进制
Ⅰ. Java语言实现
1 |
|
Ⅱ. C语言实现
1 |
|
Disruptor并发框架中的Quene
Disruptor框架介绍
极高性能、并发、无锁的编程框架 - Disruptor
建立在JVM平台上
每秒可处理6百万订单[官方自述]
运行在内存中
采用事件源驱动方式
无锁的Queue(高并发无锁队列事件)
[RingBuffer]是Disruptor的核心
RingBuffer采用数组实现,无首尾指针
随着不停的填充RingBuffer,序号会一直增长,直到超过这个环的最大长度(会覆盖旧的序号)
如何计算序号指向的元素?采用mod运算,序号%长度=索引,例如计算上图10的索引,10%8=2,在第2的位置
关于设置环的最大长度。上图的环长度只有8,在实际情况>>8。长度尽量设置成2n,比如1024、2048
为什么长度尽量设置成2n?如此可采用”与”运算计算索引号,即序号&(长度-1)=索引号,其效率要高于mod计算效率
通过”生产者->RingBuffer->消费者”运作,下图是一个最简单的处理链
实际情况中,生产者和消费者必定是多个线程执行。
树和二叉树
树的基本概念
什么是树?
树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树;
树(tree)是包含n(n>0)个结点的有穷集,其中:
- (1)每个元素称为结点(node);
- (2)有一个特定的结点被称为根结点或树根(root)。
- (3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。
下面的关于Tree的术语主要来自维基百科
术语 | 中文 | 描述 |
---|---|---|
Root | 根节点 | The top node in a tree. |
Child | 子节点 | A node directly connected to another node when moving away from the Root. |
Leaf | 叶子节点 | A node with no children |
Edge | 边 | The connection between one node and another. |
Path | 路径 | A sequence of nodes and edges connecting a node with a descendant. |
Height | 节点高度 | The height of a node is the number of edges on the longest path between that node and a leaf. |
Level | 层级 | The level of a node is defined by 1 + (the number of connections between the node and the root). |
Depth | 深度 | The depth of a node is the number of edges from the tree’s root node to the node. |
Degree | 度 | The number of subtrees of a node. |
相关术语 中文版
- 节点的度:一个节点含有的子树的个数称为该节点的度;
- 叶节点或终端节点:度为0的节点称为叶节点;
- 非终端节点或分支节点:度不为0的节点;
- 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
- 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
- 兄弟节点:具有相同父节点的节点互称为兄弟节点;
- 树的度:一棵树中,最大的节点的度称为树的度;
- 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
- 树的高度或深度:树中节点的最大层次;
- 堂兄弟节点:双亲在同一层的节点互为堂兄弟;
- 节点的祖先:从根到该节点所经分支上的所有节点;
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林:由m(m>=0)棵互不相交的树的集合称为森林;
下面通过几个图解释树的几个比较重要的概念
Edge、Root、Leaf
Path
Height
需要注意的是叶子节点的高度为0,如果树只有一个节点,那么这个节点的高也是0
Depth
需要注意的是根节点的深度(Depth)是0.
从Height和Depth的对比,它们的方向刚好是相反的。
对于Height和Depth不用死记,我们可以把树倒过来看,也就是我们现实生活当中的树,求某个节点的Height那肯定是从根部往上的方向;
如果是求某个节点的深度,方向肯定是向下的。
Level
节点的Level是从1开始的,Level = Depth+1,根节点的Level=1
也有很多书籍上Level是从0开始的,这样的话Level就等于Depth,根节点的Level=0
二叉树
二叉树是一个每个最结最多只能有两个分支的树,左边的分支称之为左子树,右边的分支称之为右子树。
也就是说二叉树节点的度最大也就是2,而普通的树,节点的度是没有限制的。
二叉树的分类
完美/满二叉树(Perfect Binary Tree)
完美二叉树(满二叉树)。完美二叉树满足两个特性:
- 所有的几点都包含两个子节点
- 所有的叶子节点的Height或者Level都相等
例:
完全二叉树(Complete Binary Tree)
完全二叉树是 除了最后一层都是满的(都有两个子节点),并且最后一层的节点是从左往右排列的。
完全二叉树,通俗点说就是节点按层从左往右排列。如果最后一层排满了就是完美二叉树,没有满则是完全二叉树。
所以完美二叉树一定是完全二叉树,完全二叉树不一定是完美二叉树。
一个完全二叉树可以高效的使用数组来表示。
例:
完满二叉树(Full Binary Tree)
完满二叉树就简单了,就是每个节点都有两个子节点。也就是说它比完美二叉树少了一个条件。
例:
二叉树实现
二叉树的遍历策略
将整个二叉树分为三部分
- 根
- 左子树
- 右子树
遍历方式
- 方式一
- 先序(根)遍历 根->左子->右子
- 中序(根)遍历 左子->根->右子
- 后序(根)遍历 左子->右子->根
- 方式二
- 按层次遍历
例:
- 先序遍历(DLR): 1 4 5 2 3 6 7
- 中序遍历(LDR): 4 5 1 3 2 6 7
- 后序遍历(LRD): 5 4 3 7 6 2 1
例题:
已知某二叉树,其
后序遍历结果为:5 4 3 7 6 2 1,
中序遍历结果为:4 5 1 3 2 6 7,
求其先序遍历(DLR)结果?
解:
∵ 后序遍历顺序为左子->右子->根
∴ 可知root节点为 1
由中序遍历结果得下图
在分析根1的左子树,由于 4 5 是按照中序遍历排列,可推得
4为左子树的根,5为左子树的根的右子
或者
5为左子树的根,4为左子树根的左子
由于在后序遍历中排列顺序为 5 4 3 7 6 2 1,
5 4 是根1的左子树,顺序为左子->右子->根,由于左子树至少有根,因此排列顺序为右子->根,即得到如下图:
现在我们来分析root的右子树排列状态:
由后序遍历结果 3 7 6 2 得2为右子树得根,又中序遍历结果为 3 2 6 7
因此我们可以得出下图:
后序遍历结果 6 7 , 中序遍历结果 7 6,易得7为根,6为右子,得出二叉树图形为:
得先序遍历结果为:1 4 5 2 3 6 7
按层次遍历(广度优先搜索)
结果为 1 4 2 5 3 6 7
二叉树接口
二叉链表节点
1 |
|
二叉树接口
1 |
|
二叉树操作
未完待续