数据结构与算法代码练习

发表于 | 更新于 | 分类于 | 阅读次数：

推荐网址:https://blog.csdn.net/weixin_41624982/article/details/89486592

基本概念

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1.描述:抽象数据类型(ADT),是计算机领域中被广泛接受的一种思想和方法,也是一种设计和实现程序模块的有效技术.模块通过接口来提供功能所需的信息,并不涉及具体实现细节.
2.概念:①数据表示的完全暴露②对象表示和操作对具体表示的依赖性③抽象数据类型提供的操作包括三类,构造操作,解析操作,变动操作.④Python所有的内置类型都是一种抽象数据类型⑤ADT是一种思想也是一种技术
数据结构:指相互之间存在一种或多种特定关系的的数据元素的集合
数据结构划分:逻辑结构、物理结构、数据运算
数据结构的分类：栈（Stack）、队列（Queue）、树（Tree）、堆（Heap）、数组（Array）、链表（Linked List）、图（Graph）、散列（Hash）
3.几种排序算法介绍:
    1.冒泡排序:就是两两比较,互换位置,每一轮找到一个最大值放在数组右边,多轮循环就排好了.代码主要涉及循环次数和两两互换条件的判断.  优化:当一轮交换后数组顺序没有变化的时候停止排序
    2.快速排序(左右指针法,挖坑法):数组中确定一个基准数,将大于基准数的放在右边,小于基准数的放在左边.具体实现是首先确定一个基准数(通常为数组第一个数),从后往前找到小于基准数的第一个数,并记下位置,与基准数互换位置,然后在从前往后找到大于基准数的第一个数,与基准数互换位置,再从后往前(前一次记录的位置开始)找到小于基准数的第一个数,重复,直到从前找的位置和从后找的位置大于等于,左边的全部比基准数小,右边比基准数大.然后两边再分别使用相同方法,循环    优化:①随机选取基准值(否则在一个完全有序的数组里，我们的快速排序就会退化为log（n^2②配合使用插入排序③当大量数据且重复数据较多时,用三路快排(小于,等于,大于)--->推出双路快排为将等于部分分散到左右两端
    3.选择排序:首先在数组中找到最大(最小)的元素,然后在剩余数组中找到最大(最小),以此类推,直到排序完成
    4.插入排序,类似于排序扑克牌,取出一个数据然后与已经排好序数组的比较,插入到合适的位置,以此类推,
    5.归并排序:采用分治法,分为分和治两个阶段,分,指的是将一个数组分成两部分,然后重复不断的分直到只剩一个个单一的元素.然后在对左右两边的数组进行治,将左右两边的数组分别排序好,得到两个排好序的数组.最后进行合并.合并的原理是两个数组第一个数字比较,小的放到新的数组里的第一位,然后小的数的那个数组的第二个数,继续与宁一个数组的第一位数相比较,两者小的放入到新数组第二位,如此循环得到排序好的新数组
    6.希尔排序===>插入排序的改进(缩小增量排序):首先选择一个间隔x(小于n)将全部数组分成若干个子序列(相同间隔x的放一起),每一个子序列中进行插入排序,合并后.缩小间隔,重复子序列划分和排序,直到间隔x为1(https://blog.csdn.net/weixin_37818081/article/details/79202115?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase)
x每次减半或者1/3都可
	7.堆排序:堆是一颗完全二叉树,每个节点的值总是不大于或者不小于父节点的值,由此形成大顶堆和小顶堆.首先将所有数字存储在堆中,按照大顶堆建堆,每次将最大的数取出,剩下的数继续可以找到最大的数,如此可以找到倒叙新的数组,将取出的数字按照相反的顺序进行排列,数字就完成了排序
	8.桶排序:根据待排序数组中的最大和最小值(差值和映射规则判断)确定桶的个数,然后遍历每一个元素放在指定的桶中,最后得到排序好的结果,
顺序表、链表、堆栈、队列、树、二叉树、平衡二叉树、红黑树；算法将涉及排序算法（冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序）、查找算法（顺序查找、二分法查找、二叉树查找、哈希查找）
几种树
1
2
3
4
满二叉树:除了叶子结点,每一个节点都有两个子节点(深度k  节点总数为(2^k)-1,则它就是满二叉树)
完全二叉树:若二叉树的深度为k,除了k层外,其余各层的结点数都达到最大,第k层所有的节点都连续集中在最左边
平衡二叉树:左子树和右子树的的深度之差的绝对值不能超过1,且左右子树都是平衡二叉树
最优二叉树(哈夫曼树):树的带权路径长度达到最小,

####python实现链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList(牛客网)==形如栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
#例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        if not listNode:
            return []
        l = []
        head = listNode
        while head:
            l.insert(0,head.val)
            head = head.next
        return l
二分法(仅当列表是有序的时候有用)=====第一种算法
1
2
3
4
5
6
简单查找(傻找):如1到100中找99,一个个找需要99次.
二分查找每次排除一半的数字
对于简单查找找到需要n步,而对于二分法查找找到需要log以2为底n的对数
low = 0  high = len(ls) - 1
mid = (low + high)//2
然后根据值对比修改high和low,小了low = mid +1 ,大了high = mid-1

大O表示法(记录的是最糟糕最长的时间情况)

1
2
3
4
5
6
7
8
9
10
11
12
13
用来表示算法的运行时间,以及运行时间随着列表的增长的变化情况:如对数越往后几乎不增长,而线性一直增长很快
常见的五种大O表示法
O(logn)、O(n)、O(n*logn)、O(n**2)、O(n!)
logn优于n优于nlogn优于n**2优于n!
·算法的速度并非指的是时间而是操作数的增速
·讨论算法的速度时,我们说的是随着输入的增加,其运行时间将以怎样的速度增加
·算法的运行时间用大O表示法表示
·O(logn)比O(n)快,当需要搜索的元素越多时,前者比后者快的多

计算机内存可以看成一个个抽屉,每个抽屉有对应的物理地址

常见的大O运行时间:
    1.二分查找  O(logn)、简单查找 O(n)、 快速排序 O（平均nlogn，最糟糕n**2）、选择排序O（n**2）、旅行商问题O（n！）

####数组和链表

1
2
3
4
5
6
7
数组表明所有代办事项在计算机的内存中是相连的,紧靠在一起,当后面位置被占用的时候,就需要整体迁移到有空闲位置的地方(他们必须相连),添加元素速度很慢
解决方法:
    1.给预留位置,先占内存  缺点:①额外预留的位置用不上 ②待办事项超过指定预留后,还得转移
    2.使用链表解决
链表:链表中的元素可以存储在内存中的任何地方,链表中的每一个元素都存储了下一个元素的地址,使一系列内存连接在一起.链表中添加元素很简单,只要将后一个元素的地址放到前一个元素中即可
    
使用链表时根本就不需要移动元素,如为数组分配1000个位置,内存有1000个位置但不在一起,就无法为该数组分配内存.而链表不需要考虑那么多

链表在插入数据上面的优势特别明显(无论结尾插入还是中间插入),数组在随机读取速度的优势特别明显,链表删除数据也比较方便。不同如插入，删除操作一定能成功，插入操作当内存空间不够时，插入操作可能会失败。删除操作任何情况都能成功

1
2
链表读取时间O(n),存储时间O(1),删除时间O(1)
数组读取时间O(1),存储时间O(n),删除时间O(n)
1
2
3
4
为什么数组都是以0为开头的索引?
从0开始让基于数组的代码编写起来更容易,因此程序员都坚持这么做.

通常情况下数组用的多,数组支持随机访问,而链表只支持顺序访问

选择排序=====第二种算法

1
2
如一堆数中按照大小进行排序,每次的时间复杂读为O(n),执行n次,总的为O(n**2)
每次取一个最大,依次排
python实现选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def func(ls,data_max):
    for i in range(len(ls)):
        if ls[i]>data_max:
            data_max = ls[i]
    return data_max
ls = [1,21,15,20,3,5,6,2,13]
ls2 = []
data_max = ls[0]
def func2():
    for  i  in  range(len(ls)):
        max_data = func(ls,data_max)
        ls2.append(max_data)
        ls.remove(max_data)
    return ls2
func2()

快速排序(D&C算法)=====第三种算法(基础:递归)

1
2
3
4
5
6
7
8
9
10
11
12
快排比选择排序快很多,是一个优雅的算法(并非一种解决问题的算法,而是一种解决问题的思路)
工作原理:1.找出简单的基线条件  2.确定如何缩小问题的规模,使其符合基线条件

有时候循环可以简单的完成任务,为何还要使用递归方式呢,因为函数式编程语言(如Haskell)没有循环,只能使用递归来编写这样的函数

快速排序思想为通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比宁一部分的所有数据都要小,然后按此方法对两部分数据进行快速排序,整个排序过程可以递归进行

快排流程:
    1.首先设定一个分界值,通过该分界值将数组分成左右两部分(随机选取通常为数组的第一个值)
    2.将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边.使得左边的数值都小于等于分界值.右边的元素都大于或等于分界值
    3.然后左边和右边的数据可以独立排序.左边的数据又可以取一个分界值,将此部分数据局变成左右两部分,同样在左边放置最小值,右边放置最大值.右侧的数据做类似的处理
    4.重复上述步骤.递归进行.

图地址:https://bkimg.cdn.bcebos.com/pic/b7003af33a87e950707fdf2110385343fbf2b416?x-bce-process=image/resize,m_lfit,w_220,h_220,limit_1

快排图

####合并排序(归并排序)

1
2
3
4
5
合并排序的时间总是O(nlogn),而快排平均时间为O(nlogn),最糟糕时候为n**2
流程:
    1.将待排序的元素分成大小大致相同的两个字序列
    2.将两个字序列进行合并排序
    3.将排序好的有序序列进行合并,得到最终的有序序列

图地址:https://upload-images.jianshu.io/upload_images/13629684-ba3a964b7c17782c.png?imageMogr2/auto-orient/strip|imageView2/2/w/487/format/webp

img

插入排序

1
基本思想:把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列中,知道所有的记录插完为止,得到一个新的有序序列

散列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
散列表也称为散列映射、映射、字典和关联数组。
散列表：散列函数和数组共同创建的一种数据结构。散列表使用数组来存储数据
①散列函数总是将同样的输入映射到相同的索引。
②散列函数将不同的输入映射到不同的函数。
③散列函数知道数组有多大，只返回有效的索引。

散列表适用于:①模拟映射关系 ②防止重复 ③缓存\记住数据,以免服务器通过处理来生成它们
冲突:当键已经存在时,再赋给它新值,就会覆盖原来的值,这种情况称为冲突

对比:
    散列表查找花费的时间为常量O(1),简单查找的运行时间为线性时间,二分查找的花费的时间为对数时间
    
小结:
    1.可以结合散列函数和数组来创建散列
    2.冲突很糟糕,应该使用可以最大程度的减小冲突的散列函数
    3.散列表的查找、插入和删除速度都非常快
    4.散列表适合用于模拟映射关系
    5.一旦填装因子超过0.7，就该调整散列表的长度
    6.散列表可用于调整长度
    7.散列表非常适合用于防止重复

广度优先搜索(通过队列实现,顺序添加,顺序查找)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
广度优先搜索是用来解决最短路径问题的,是一种用于图的查找算法,主要解决两类问题
	·从节点A出发,有前往节点B的路径吗
    ·从节点A出发,前往节点B的哪条路径最短
基础(图相关知识):
    图由节点和边组成,一个节点可能与众多节点直接相连,这些节点被称为邻居
    有向图:有箭头指向自己但没有指向别人.rama->adit
    无向图:没有箭头,直接相连的节点互为邻居.ross-lilei
一度关系胜过二度关系,二度胜过三度,关系以此类推.因而先在一度中搜索,然后二度...一直到搜索到为止.

队列是先进先出的,栈是后进后出的,你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须为队列
对于检查过的人务必不要再去检查,否则会陷入无限循环

运行时间：
时间至少为O（边数）。将每一个添加到队列的时间是O(1),因此广度搜索的运行时间O(人数加边数)

狄克斯特拉算法

1
2
3
4
5
6
7
8
9
10
11
加权图:带权重的图
非加权图:不带权重的图
获取加权图的最短路径使用狄克斯特拉算法,获取非加权图的最短路径使用广度优先搜索算法(狄克斯特拉算法只适用于有向无环图)
当权重为正时狄克斯特拉算法才管用
如果包含负权边,请使用贝尔曼-福德算法

基本思路:
    1.找出最便宜的节点,即可在最短时间内到达的节点
    2.更新该节点的邻居的开销
    3.重复这个过程,直到对图中的每个节点都这样做了
    4.计算最短路径

第一步:找出最便宜的节点.使用散列表,把它当成一个列表

父节点 节点 耗时
起点 A 6
起点 B 2
起点 终点 未知

2

找出最短耗时2,节点B是最近的

第二步:计算经节点B前往其各个邻居所需的时间

父节点 节点 耗时
B A 5(2+3)
B B 2
B 终点 7(2+5)

第三步:重复操作

贪婪算法(贪心算法)===局部最优解,企图以这种方式获得全局最优解

1
2
3
4
5
6
7
8
9
10
11
12
指的是,在对问题求解时,总是做出当前看来最好的选择,也就是说,不从整体最优上加以考虑,做出的是某种意义的局部最优解
常见的问题:
    1.背包问题:有一个背包，背包容量是M=150kg。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量(每次挑选最大价值\每次挑选重量最大\每次挑选单位价值最大)===不一定最优,可能局部最优
    2.马踏棋盘:在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径.
    3.集合覆盖问题：假设存在需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号。

基本思路:
    1.建立数学模型来描述问题
    2.把求解的问题分解成若干子问题
    3.对每一个子问题求解,得到子问题的局部最优解
    4.把子问题对应的局部最优解合成原来整个问题的一个近似最优解
优点:贪婪算法易于实现、运行速度快，是不错的近似算法

动态规划(DP=dynamic programming)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
这是一种解决棘手问题的方法,将问题分解成若干个小问题,先着手解决这些小问题
动态规划原理:
    编号动态规划:最大不下降子序列
    划分动态规划:矩阵链乘、凸多边形三角剖分
    数轴动态规划:0-1背包
    前缀动态规划:最长公共子序列
    树形动态规划:最优二分搜索树
        
基本思想:问题的最优解如果可以由子问题的最优解推导得到,则可以先求子问题的最优解,在构造原问题的最优解,若子问题的有较多的重复出现,则可以自底向上从最终子问题向原问题逐步求解

使用条件:可分为多个相关子问题,子问题的解被重复使用
    
动态规划算法的设计步骤:
    1.分析优化解的结构
    2.递归的定义最优解的代价
    3.自底向上地计算优化解的代价保存,并获取构造最优解的信息
    4.根据构造最优解的信息构造最优解
    
动态规划的特点:
    1.把原始问题分成一系列子问题
    2.求解每个子问题,并将结果保存在一个表里,以后用到时直接存取,不重复计算,节省计算时间
    3.自底向上的计算
    4.整体问题最优解取决于子问题的最优解
DP核心思想:尽可能缩小解空间

树算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
树:树是一种管理有像树干、树枝、树叶一样关系的数据得数据结构
   树由节点（顶点）和边（枝）构成，并且有一个节点作为起始点。这个起始点作为树的根节点。由此形成父节点、子节点、叶子节点
节点的子树的根称为节点的孩子，相应的该节点称为孩子的双亲，同一双亲的孩子之间互称为兄弟，节点的祖先是从该节点所经分支上的所有结点

基本概念：

节点的度：一个节点含有的子树的个数称为该节点的度
叶节点或终端节点：度为0的节点称为叶节点
非终端节点或分支节点：度不为0的节点
双亲结点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点
兄弟节点:具有相同父节点的节点互称为兄弟节点
树的度:一棵树中,最大的节点的度称为树的度
节点的层次:从根开始定义起,跟为第一层,根的子节点为第二层
树的高度或深度:树中节点的最大层次
堂兄弟节点:双亲在同一层的节点称为堂兄弟节点
节点的祖先:从跟到该节点所经分支上的所有节点
子孙:以某节点为根的子树中任一节点都称为该节点的子孙
森林:由m棵互不相交的树的集合称为森林

在计算机中数据的存储有两种结构,顺序存储和链式存储,对树而言,顺序存储结构显然是不行的,而链式存储结构也是有缺点的
第一种:链式存储结构中的节点需含有子节点的引用和指针,但在树中子节点的不确定性导致无法固定具体节点中有几个引用或指针
第一种(改): 对于上面的存储结构会过多的浪费空间,那么在结点中声明一个动态链表Nodes来存放可能的子节点node
第二种:使用数组+链表结合的方式表示树

图地址:https://img2018.cnblogs.com/blog/1244002/201809/1244002-20180921160023094-1488648937.png

img

各种树介绍

1
2
3
4
5
6
7
8
#有序树与无序树
有序树:树中任意节点的子节点之间有顺序关系
无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称自由树
#二叉树
完全二叉树:叶结点只能出现在最底层的两层,且最底层叶节点均处于次底层叶节点的左侧.
满二叉树:除了叶子结点外每一个节点都有左右子叶,且叶子结点都处在最底层的二叉树(最标准那种)
平衡二叉树:又被称为avl树(非avl算法),且具有以下性质,它是一颗空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一颗平衡二叉树,平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
红黑树:是一种自平衡二叉查找树,典型的用途是实现关联数组

堆

1
2
3
4
5
6
7
8
9
堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针,堆根据堆属性来排序,堆属性决定了树中节点的位置
堆的常用方法:
    ·构建优先队列
    ·支持堆排序
    ·快速找出一个集合中的最小值(或者最大值)
堆分为最大堆和最小堆
最大堆:父节点的值比每一个子节点的值都要大.
最小堆:父节点中的值比每一个子节点的值都要小
堆属性非常有用,常常被当做优先队列使用,因为可以快速访问到最重要的元素

排序算法时间复杂读

数据结构与算法