数据的逻辑结构

线性结构

非线性结构

数据的存储结构

顺序存储
链式存储
索引存储
散列存储

线性表

顺序存储:用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素在物理位置上也相邻。

优点:随机存取表中的元素。
缺点:插入和删除操作需要移动元素。

链式存储:线性表的链式存储是用通过指针链接起来的结点来存储数据元素。
存储各数据元素的结点的地址并不要求是连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。另外，结点空间只有在需要的时候才申请无须事先分配。

单链表:从头结点开始往后顺序遍历整个链表。
单向循环链表:可以从表中的任一结点开始遍历整个链表。

双向链表:除尾节点外，每一个节点的的 prior指针都指向前一个节点除头节点外，每一个节点的 next指针 都指向后一个节点

双向循环链表:跟单向循环链表一样，双向循环链表其实节点结构不变只是首尾相连而已

栈

先进后出
顺序存储:预先申请栈空间，栈满则元素不能入栈.

栈的链式存储:用链表表示栈，用链表实现的栈称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。

栈 递归

栈 递归

算符优先关系表

• <:01低于02
• =:01等于02
• >:01高于02
• 空白:表达式出错
  
  【基本运算规则】
• 准备两个栈分别放置操作数和操作符
• 表达式的前后加#号，#号作为操作符优先压入栈中取到表达式的下一个运算符后，需和栈顶的运算符比较:
• • (优先级比较)栈顶运算符<当前运算符，当前运算符进栈，读下一个运算符
• • (优先级比较)栈顶运算符=当前运算符，栈顶运算符出栈，读下一个运算符
• • (优先级比较)栈顶运算符>当前运算符，运用栈顶运算符结合操作数进行计算，计算结果压入操作数栈。

队列

先进先出
顺序队列:队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队头和队尾

循环队列:循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

循环队列特征

入队操作:
入队时，将元素插入到尾指针指向的位置，并将尾指针向后移动一位。
如果尾指针已经到达数组的末尾，则将其移到数组的开头(即循环队列的环形特性)，以实现循环利用。
出队操作:
出队时，将头指针指向的元素取出，并将头指针向后移动一位。
如果头指针已经到达数组的末尾，则将其移到数组的开头。
队列长度:
队列长度等于尾指针位置减去头指针位置，但需要注意循环队列中可能存在两种情况:
当rear>front时，长度为rear-front;
当rear<front时，长度为rear-front+数组长度。

数据结构-哈希表

数据结构-二叉树

树

(1)父亲、孩子和兄弟
(2)结点的度
(3)叶子结点
(4)内部结点
(5)层次
(6)树的高度

二叉树种类

满二叉树:二叉树中每个非叶子结点都有两个非空的孩子结点。
完全二叉树:若设二叉树的深度为h，除第 h层外，其它各层(1~h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边
这就是完全二叉树。
非完全二叉树:不满足完全二叉树性质的均是非完全二叉树。

二叉树高度与结点关系

在二叉树的第i层上最多有211个结点(i≧1)
深度为k的二叉树最多有2k-1个结点

二叉树度与结点关系

在对于任何一棵二叉树，如果其叶子结点数为 No度为2 的结点数为N，则No=N1+1。

数组结构-数组与矩阵

按行存储:
Am,n= [[a11a12.an],[az1a22.aznl,.,[amram...amn]]
按列存储:
Am,n=[[a11a21.an],[a1za2..am2],.,[a1na2n…amn]]

对称矩阵

如果矩阵 AT=A，则称 A为对称矩阵

上三角矩阵与下三角矩阵

三对角矩阵

三对角矩阵又称带状矩阵:当|i-j>1时，有a[i][j]=0，其中1<=i，j<n

图的定义及存储

无向完全图

若一个无向图具有n个顶点，而每个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。无向完全图共有n(n-1)/2条边。

有向完全图

有n个顶点的有向完全图中弧的数目为n(n-1)，即任意两个不同顶点之间都有方向相反的两个弧存在，

连通图与非连通图

在无向图G中，若从顶点V到顶点V:有路径，则称顶点V;和顶点V是连通的。如果无向图G中任意两个顶点都是连通的，则称其为连通图。无向图的极大连通子图称为G的连通分量。

强连通图

有向图中，若任意两个顶点 Vi和 Vi，满足从 Vi到 Vi以及从Vj到 Vi都连通，也就是都含有至少一条通路，则称图为强连通图。有向图中的极大连通子图称为有向图的强连通分量。

邻接矩阵

有向图中邻接矩阵不一定对称。

无向图的邻接矩阵是对称的。

邻接表

在图的邻接表中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。

数据结构-图的遍历

图的遍历

图的遍历是指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程。
深度优先DFS
V1，V2，V4，V8，V5，V3，V6，V7V1，V2，V5，V8，V4，V3，V7，V6
广度优先BFS
V1，V2，V3，V4，V5，V6，V7，V8