signed

QiShunwang

“诚信为本、客户至上”

常用数据结构与排序算法--笔记

2021/3/21 9:10:57   来源:

数据结构:数据存储内存时,决定了数据顺序和位置关系的便是"数据结构"。

线性排列-数据结构

1、链表:
每个数据都有1个"指针",指向下一个数据的内存地址。
特点:(单向)只能从第一个数据开始访问,但是
增删快(不会对位置发生影响)
复杂度:访问 O(n);增删 O(1)
循环链表(环形链表):最后一个数据尾指针指向第一个数据的内存地址。
双向链表:头指针
指向上一个数据内存地址,
尾指针
指向下一个数据内存地址。
(双向链表)缺点:1、指针数的增加会导致存储空间的需求增加;
2、添加删除数据时需要改变更多的指针方向。
2、数组
随机访问:通过下标算出内存地址
特点:访问速度快,但是增删慢,增删在中间位置时需要(腾出一个位置,然后后面的数据需要往后挪,或者消除一个位置,后面数据往前挪),对数据位置会产生影响。
复杂度:访问O(1) 增删O(n)
3、栈
特点:先进后出,后进先出(只能先访问最新添加的数据,增删数据的操作只能在一端进行)
称为:Last In First Out,简称LIFO
操作:
入栈:push-添加数据
出栈:pop -取出数据
4、队列
特点:先进先出,后进后出(入队一端口,出队另一端口,先访问到最先进去的数据)
称为:First In First Out,简称FIFO
操作:入队-添加数据
出队-取出(删除)数据
5、哈希表
存储的是由键值对组成的数据,通过键找到对应的值
键:通过哈希函数算出键的值
哈希冲突:存储位置重复;
哈希冲突解决:
1、链地址法:利用链表在已有的数据的后面插入新的数据
2、开放地址法:发生哈希冲突时,立刻计算一个候补地址(数组上的位置)并将数据存进去,如果仍然冲突将继续循环计算候补地址。
图-数据结构
1、堆(涉及-狄克斯特拉算法)
树性结构,被用于实现"优先队列"
优先队列也是一种数据结构:可以自由添加数据,但是取出数据要从最小值开始按顺序取出。数据都存储在节点当中。
规则:
1、最顶点必须是最小值
2、子节点必须大于父节点
3、一般新数据都是从最下面一行靠左的位置开始放入数据,没有空间的话,就往下一行的最左端开始存储。
2、二叉树(二叉搜索树或二叉排序树)
规则:
1、每个节点最多有两个子节点
2、左子节点小于父节点,右子节点大于父节点
补充说明:虽然文中介绍的二叉查找树中一个结点最多有两个子结点,但我们可以把子结点数扩展为 m(m 为预先设定好的常数)。像这种子结点数可以自由设定,并且形状均衡的树便是 B 树。

算法
1、冒泡排序
说明:就是重复"从序列右边开始比较相邻的两个数字大小",再根据两个数字的大小判断是否置换两数字的位置
时间复杂度为 O(n的二次方)
2、选择排序
说明:就是重复"从待排序的数据中寻找最小值,将其与序列最左边的数字进行位置替换",注:序列中寻找最小值使用的是线性查找。
时间复杂度为 O(n的二次方)
3、插入排序
说明:就是一种从列的左端开始依次对数据进行排序。排序过程中,假设最左端数据是已经完成排序的,然后依次与右端(未排序区域)进行数据的比较,若左侧的数据大于取出的数据,就进行位置替换,直至左侧数据小于或者最左端时,结束比较。
时间复杂度为 O(n的二次方)