数据结构

简介:

数据结构

逻辑结构:集合,线性,树形,图形

物理结构(存储结构);顺序存储,链式存储


算法特性:输入、输出、有穷性、确定性、可行性


常见时间复杂度

wKioL1mKiMvwjYZwAAIX-C9S4Q0299.png

常见数据结构的时间复杂度(集合,线性,树,图)

线性表(顺序存储结构、链式存储结构)

顺序存储结构:查找O(1),增加O(n),删除O(n)

链式存储结构(单链表,静态链表,循环链表,双向链表):查找O(n),增加O(1),删除O(1)


栈和队列

栈:顺序栈和链栈的时间复杂度都为O(1),空间上顺序栈要预先分配足够的空间,链栈要存储指针数据,所以都有空间浪费;


顺序队列:普通顺序队列有队列溢出的问题,入队时间复杂度为O(1),出队时间复杂度为O(n),循环顺序队列依然有队列溢出的问题,但是出入队列的时间复杂度都为O(1);

链式队列:出入队列的时间复杂度都为O(1),相对于循环顺序队列的需要一次性分配空间且空间不可变,链式队列在用到的时候才分配空间且空间不受限制。


朴素模式匹配:平均时间复杂度:O((n+m)/2),最坏时间复杂度:O((n-m+1)*m)

KMP算法:最坏时间复杂度:O(n+m),当模式与主串存在许多“部分匹配”的情况下较有优势


树的存储结构:双亲表示法、孩子表示法、孩子兄弟表示法;

二叉树:斜树、满二叉树、完全二叉树,哈弗曼树


图的概念:无向图,有向图,简单图,无向完全图,有向完全图,网,连通图

图的存储:邻接矩阵表、邻接表、十字链表、邻接多重表、边集数组

图的遍历:深度优先遍历、广度优先遍历



最小生成树算法:普里斯、克鲁斯卡尔  http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html 克鲁斯卡尔针对边来展开,变数少的时候效率较高

最短路径:迪杰斯特拉 http://blog.csdn.net/mu399/article/details/50903876、弗洛伊德 http://blog.csdn.net/bjtu_dubing/article/details/50333027

拓扑排序:

关键路径:


查找

顺序表查找:

有序表查找:折半查找、插值查找、斐波那契

线性索引查找:稠密索引,分块索引,排序索引

二叉排序树:

AVL树:

多路查找树(B树):2-3树、2-3-4树、B+树


排序

排序的概念:稳定排序,不稳定排序,内排序、外排序

排序算法:冒泡排序、简单排序,插入排序,希尔排序http://blog.csdn.net/morewindows/article/details/6668714、堆排序,归并排序 http://www.cnblogs.com/chengxiao/p/6194356.html、快速排序


本文转自 古道卿 51CTO博客,原文链接:http://blog.51cto.com/gudaoqing/1954585

相关文章
|
7月前
|
存储 C++
c++数据结构
c++数据结构
50 0
|
存储 算法 前端开发
常见数据结构
常见数据结构
62 0
|
2月前
|
存储 NoSQL 索引
【数据结构】数据结构学什么?
【数据结构】数据结构学什么?
37 5
|
7月前
|
存储 算法
【数据结构】什么是数据结构?
【数据结构】什么是数据结构?
56 0
|
7月前
|
算法 C++ 开发者
【C/C++ 数据结构 】 连通图的基本了解
【C/C++ 数据结构 】 连通图的基本了解
96 0
数据结构 2.2 单循环链表
数据结构 2.2 单循环链表
56 0
|
存储 Java C++
总结数据结构-1
总结数据结构-1
42 0
|
算法 Python
02 数据结构
02 数据结构
36 0
|
算法 索引
数据结构 静态查找
数据结构 静态查找
226 0
数据结构 静态查找
uiu
|
存储 机器学习/深度学习 算法
我对八种常见数据结构的理解(一)
我对八种常见数据结构的理解(一)
uiu
134 0
我对八种常见数据结构的理解(一)