数据结构底子知识1

1. 数据结构先容

数据结构（英语：data structure）是盘算机中存储、构造数据的方式。
数据结构是一种具有肯定逻辑关系，在盘算机中应用某种存储结构，而且封装了相应操纵的数据元素聚集。它包罗三方面的内容，逻辑关系、存储关系及操纵。
简单来说，数据结构是对大规模的数据举行一个公道的规划，进步操纵服从。

---

常见的数据结构

• 栈（Stack）：栈是一种特别的线性表，它只能在一个表的一个固定端举行数据结点的插入和删除操纵。
  
• 队列（Queue）：队列和栈类似，也是一种特别的线性表。和栈差别的是，队列只允许在表的一端举行插入操纵，而在另一端举行删除操纵。
  
• 数组（Array）：数组是一种聚合数据范例，它是将具有雷同范例的多少变量有序地构造在一起的聚集。
  
• 链表（Linked List）：链表是一种数据元素按照链式存储结构举行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
  
• 树（Tree）：树是范例的非线性结构，它是包罗，2 个结点的有穷聚集 K。
  
• 图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一样平常称为顶点，而边是顶点的有序偶对。
  
• 堆（Heap）：堆是一种特别的树形数据结构，一样平常讨论的堆都是二叉堆。
  
• 散列表（Hash table）：散列表源自于散列函数(Hash function)，其头脑是假如在结构中存在关键字和T相称的记录，那么肯定在F(T)的存储位置可以找到该记录，如许就可以不消举行比力操纵而直接取得所查记录。       

  ---

  2.时间复杂度
  

形貌算法运行时间的函数。

---

假设算法要处置惩罚的数据总量为x，x富足大。算法为了某种目的（查找，删除，添加...）斲丧的盘算次数为y.

• y=ax+b   a是系数，b是常数       当x富足大，a b的值不敷以影响x   y和x直接干系   y=x  O(n)
  
• y=ax^2+bx+c    ab是系数，c是常数    当x富足大，abc的值不敷以影响x  y和x^2直接干系  y=x^2  O(n^2)
  
• y=a  a是常数     当x富足大，a 的值不敷以影响x   y和x无关   y=1  O(1)
  
• a^y=x  y=logax         O(logn)
  

---

2.1 长度为x的无序数组，从中找一个值a,求时间复杂度

 

第一个：查找的次数为1
第二个：查找的次数为2
....
末了一个：查找次数x

取匀称：x/2
y=x/2                 y=x            O(n)
2.2 从1加到n求时间复杂度

x=1
for(int i=2;i<=n;i++){
        x=x+i;
}
y=x     O(n)
用等差数列求和公式
sum=(1+n)*n/2
y=1   O(1)
2.3 冒泡排序  对数组举行排序

原理：前后两两数据举行比力，大的数据今后走，小的数据往前走，一轮竣事之后，一个数据到达精确位置。
第一轮：比力了x-1
第二轮：比力了x-2
第三轮：比力了x-3

第x-1轮：1
y=(x-1)+(x-2)+(x-3)+...+1
y=(x-1+1)*(x-1)/2=x*(x-1)/2=x^2/2-x/2
y=x^2      O(n/2)
2.4 有序数组用二分查找法查找数据

mid=(left+right)/2
left<=right
right=mid-1
left=mid+1
第一轮：left和right所取范围内数据总量为x  x/2^0  比力次数为1
第二轮：left和right所取范围内数据总量为x/2   x/2^1  比力次数为1
第三轮：left和right所取范围内数据总量为x/2/2   x/2^2  比力次数为1
第四轮：left和right所取范围内数据总量为x/2/2/2   x/2^3  比力次数为1
...
第k轮：left和right所取范围内数据总量为...     1       比力次数为1     y=log2x    O(logn)
                                                                x/2^(k-1)
x/2^(k-1)=1
2^(k-1)=x
k=log2x


总结：
快速判断时间复杂度：
确定命据总量n
直接对数据规模动手 O(n)
k层关于n的循环  O(n^k)
循环减半O(logn)

2.5 数组

根据下标获取值O(1)
无序数组查找O(n)

---

 
2.5.1 无序数组查找低沉时间复杂度

方法一：有序数组二分查找法O(logn)
排序O(n^2)+二分查找O(logn)

---

方法二：通过某一个算法决定命据要插入的位置---->位置=n%arr.length
哈希算法

哈希表
两个差别的数值盘算出来在同一个位置----->拉链法：在这个位置到场链表
哈希碰撞
链表长度不长O(1),链表很长O(n)
2.5.1.1 链表

单向链表 

双向链表
 

---

 
 方法三：有序二叉树
一个节点左边的值要比当前节点小，右边节点的值要比当前节点值大
10 5 20 8 15 30 1

第一层  1  2^0
第二层  2   2^1
第三层  4  2^2
第四层   8  2^3
....
第k层       2^(k-1)
x=2^0+2^1+2^2+...+2^(k-1)
x=2^k-1
k=log2x      O(logn)

---

1 2 3  4 5 6

不稳固
平衡二叉树
一个节点左边的值要比当前节点小，右边节点的值比当前节点值大
一个节点左边子树的高度  和右边子树的高度  高度差的绝对值不凌驾1
LL     LR     RR   RL 
LL

LR型旋转

RR型旋转

RL型旋转

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金