你好，很高兴遇见你.jpg
编者按：8.13-8.18
基本概念
数据结构：数据对象与加上其上的操作相关联，实现这些操作的方法就是算法。
线性结构：有序数据元素的集合
数据结构
算法：有限指令集-输入-输出-终止
一个好的算法：时间复杂度(耗费时间的长短)+空间复杂度(占用内存的大小)
复杂度分析：logn<n<nlogn<n2<n3
线性结构
两大存储结构：顺序存储和链式存储
三大线性结构：线性表，堆栈，队列
三大操作：查找插入删除
堆栈和队列：
共同点：既是具有一定操作约束的线性表又是线性结构
不同点：堆栈一端插入删除，先入后出；队列一端插入，一端删除，先入先出
顺序存储------结构：
线性表：数组Data+最后一个元素位置Last
堆栈：数组Data+栈顶位置Top
队列：数组Data+队列头元素位置front+队列尾元素位置rear
链式存储------结构：
线性表：数据域Data+指向下一个元素的位置Next
堆栈：数据域Data+指针域Next
队列：链表结点结构：数据域Data+指针域Next
链表队列结构：front rear
线性结构.png
树
树的表示：链表域+指针域(儿子兄弟表示法)
[1]二叉树
存储：顺序存储(数组)+链式存储(Data&Left&Right)
遍历：先序中序后序(递归+堆栈)+层序(队列)
[2]二叉搜索树(BST)：
定义：非空左子树的键值都小于根结点，非空右子树的键值都大于根结点，左右子树都是二叉搜索树
查找：递归&非递归(尾递归函数改为迭代函数)
插入删除：递归
[3]平衡二叉树(AVL)：
定义：二叉搜索树，空树或任一结点平衡因子<=1
插入：四种情况旋转—发现者&麻烦结点
[4]最大堆：
定义：数组表示的完全二叉树，任一结点是子树所有结点的最大值
操作：创建&插入&删除&建堆
[5]哈夫曼树(最优二叉树)：
定义：带权路径长度(WPL)最小的二叉树
构造：每次把权值最小的两棵二叉树合并（利用堆选取）
[6]集合：
集合表示：树结构，树的每个结点代表一个集合元素，两个集合相当于两棵树。
数组存储：数据域Data+指针域父结点的下标(根结点的下标为-1)
集合运算：查找某个元素所在的集合&]集合的并运算
树.png
图
什么是图：
定义：表示多对多关系；由非空有限顶点集合V和有限边集合E组成，不考虑重边和自回路。
分类：无向图，有向图，网络(带权重)
表示：邻接矩阵-稠密图-边很多；邻接表-稀疏图-边很少
图的遍历：
深度优先搜索(DFS)：等价于树的先序遍历
广度优先搜索(BFS)：等价于树的层序遍历
存储方式：邻接表和邻接矩阵
最短路径：
无权图单源最短路算法—BFS
有权图单源最短路算法—Dijkstra-迪杰斯特拉算法
多源最短路算法：Floyd—弗洛伊德算法
最小生成树：
Prim算法—普里姆算法：不断找邻接点中回路最小的边
Kruscal算法—克鲁斯卡尔算法：直接找出V-1条最小的边
拓扑排序：
定义：拓扑序-图中从V到W有一条有向路径，则V一定排在W之前；有向无环图。
思路：队列存储；初始化-入度为0的顶点入队；循环每个顶点，对它的邻接点入度-1，如果入度为0则入队。
图.png
小贴士
本文总结自数据结构视频教程第1讲~第8讲：
http://mooc.study.163.com/learn/1000033001?tid=2001531009#/learn/content
更多笔记：
可加微信sophie_ru，免费奉献，一起交流，一起成长~
小结
1.一个阶段的任务不完成就会影响下一个阶段的任务。人生也是这样，一个阶段不努力就会拖累下一个阶段的进程，以前不努力现在开始还债，现在不努力以后好日子会等着你，出来混，总有一天要还的—《英雄本色》
2.在立即行动面前，方法反而显得没那么重要。—《把时间当做朋友》
3.这是一个以能力论英雄的时代，不努力就一定会被淘汰，天下武功，唯快不破。但是最近发现在努力面前，还有一个东西更重要，往小了说，是练好内功和精通构建自己的知识体系，选最好的平台让自己的快速成长，往大了说，就是清醒的思维和认知，这也就轻而易举解释了同样起跑线甚至同样努力的毕业生五年十年后为什么会拉开巨大的差距。
4.昨天清理了一波无用书单，发现自己又醒悟了一把，看书也是需要效率的。再翻到自己的C博客，发现知识没有学习精通，没有归纳进自己的知识系统，之后兜兜转转一直在走弯路，继续醒悟了一把。
网友评论