数据结构与C程序设计
2022-09-13 15:42:34 40 举报AI智能生成
计算机考研 数据结构
作者其他创作
大纲/内容
数据结构
线性表
基本概念
线性结构
结点只存在一对一的关系
非线性结构
结点存在着一对多的关系，可细分为树形结构和图形结构
线性表是具有相同特性数据元素的一个有限序列，可以是有序也可是无序
前驱
后继
表长
空表
首元节点
头节点
头指针
结构特点
除第一个及最后一个元素外，每一个结点都只有一个前驱和一个后继
顺序存储方式【需开辟连续存储空间】
静态分配
动态分配
存储实现
静态链表
单链表
归并算法
设置头指针的好处
循环链表
归并算法
设置尾指针不设置头指针的好处
双向链表【插入和删除算法】
双向循环链表【插入和删除算法】
顺序表
顺序存储与链式存储
顺序存储
把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现
链式存储
不要要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的
优点
缺点
适用场合
索引存储结构的好处
索引存储
存储结点信息时除建立存储结点信息外，还建立附加的索引表来标识结点的地址
栈和队列
定义
数据结构
顺序栈
链栈
共享栈
循环队列
链队
栈与队列数据存取特点
存
取
递归算法
栈的应用
数值表达式求解
括号配对原理
循环队列
判空
判满
出队算法
入队算法
多维数组及广义表
数和二叉树
图
查找
排序
插入类
直接插入排序
每趟将一个待排序的关键字按照其值的大小插入到已经安排好的部分有序序列的适当位置上，直到所有排序关键字都被插入到有序序列中为止
折半插入排序
希尔排序
交换类
选择类
归并类
1.逻辑结构
集合结构
数据元素同属一个集合，单个数据元素之间没有任何关系
线性结构
数据元素之间是一对一的关系
树形结构
元素之间存在一对多的关系
图形结构
数据元素之间是多对多的关系
2.存储结构[物理结构]
顺序存储结构
一段连续的内存空间
优点：随机访问
缺点：插入删除效率低，大小固定
链式存储结构
不连续的内存空间
优点：大小动态扩展，插入删除效率高
缺点：不能随机访问
索引存储结构
为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表
优点：对顺序查找的一种改进，查找效率高
缺点：需额外空间存储索引
散列存储结构
选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲突
优点：查找基于数据本身即可找到，查找效率高，存取效率高
缺点：存取随机，不便于顺序查找
3.顺序表与线性表
基于空间的比较
存储分配的方式
顺序表的存储空间是一次性分配
链表的存储空间是多次分配的
存储密度
顺序表的存储密度=1
链表的 存储密度<1[结点中有指针域]
基于时间的比较
存取方式
顺序表可以随机存储也可以顺序存储
链表只能顺序存储
【所谓顺序存储，以读取为例，要读取某个元素必须遍历其之前的所有的元素才能找到并读取之】
插入/删除时移动元素的个数
顺序表平均需要移动近一半元素【移动元素个数与被操作元素的位置有关】
链表不需要移动元素，只需要修改指针
4.栈与队列
栈
栈是一种只能在一端进行插入或删除操作的线性表
栈顶允许插入或删除操作
栈底固定不变
栈的插入和删除操作一般称为入栈和出栈
栈的主要特点是先进后出【FILO】
队
队是一种仅允许在表的一端进行插入，另一端进行删除的操作受限的线性表
队尾可进行插入，队头可进行删除
队尾可进行插入，队头可进行删除
队的插入和删除一般称为入队和出队
队的主要特点是先进先出【FIFO】
5.广义表
形式
(a,(a,b),d,e,((i,j),k)) 长度为5、深度为3
表头
当广义表LS非空时，称第一个元素为LS的表头【a】
表尾
称广义表LS中除去表头后其余元素组成的广义表为LS的表尾【((a,b),d,e,((i,j),k))】
深度
深度的求法为广义表中每个元素的括号匹配数加1的最大值
长度
长度的求法为广义表中最大括号中的逗号数加1
表头是元素，表尾是广义表
对任意一个非空的广义表，其表头可能是单元素，也可能是广义表
表尾一定是广义表
表尾是由除了表头以外的其余元素组成的广义表，所以，需要在表尾的直接元素外面再加一层括号
6.二叉树
二叉树遍历
先序遍历 根-左-右
中序遍历 左-根-右
后续遍历 左-右-根
定义
每个结点最多只有两颗子树，即二叉树中结点的°只能为0、1、2
左右子树有顺序之分不能颠倒
深度
从根结点到叶结点最长的路径包含的结点数
如果一棵树只有一个结点，它的深度为1
如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；
同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1
同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1
如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1
性质
非空二叉树上叶子结点数等于双分支结点数加1
二叉树的第i层上最多有2^(i-1) [i>=1] 个结点
高度或深度为k的二叉树最多有2^k - 1 [k>=1]个结点
满二叉树中前K层的结点个数为2^k - 1
满二叉树中前K层的结点个数为2^k - 1
有n个结点的完全二叉树，对各结点从上到下、从左到右依次编号(编号范围1~n)，则结点之间有如下关系
若i为某结点a的编号，则
若i为某结点a的编号，则
如果i!=1，则双亲结点的编号为 i/2下取整
如果2i<=n，则a左孩子的编号为2i；如果2i>n，则无左孩子
如果2i+1<=n，则a右孩子的编号为2i+1；如果2i+1>n，则a无右孩子
具有n(n>=1)个结点的完全二叉树的高度或深度为 log2n下取整+1
特殊二叉树
满二叉树
所有分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层
完全二叉树
对一颗深度为k、有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同
二叉排序树
或者是一棵空树
或者是具有下列性质的二叉树
或者是具有下列性质的二叉树
若左子树不空，则左子树上所有结点的值均小于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树
平衡二叉树
或者为空树
或者其左右子树都是平衡二叉树
而且其左右的子数高度之差绝对值不超过1
平衡二叉树结点的平衡因子的值只可能是-1，0，1
或者其左右子树都是平衡二叉树
而且其左右的子数高度之差绝对值不超过1
平衡二叉树结点的平衡因子的值只可能是-1，0，1
在每一次树插入新元素后，树的平衡都可能被破坏，需要旋转调整树的高度，以达到平衡树结构
共分为以下四种情况
共分为以下四种情况
LL：对该结点的左儿子的左子树进行了一次插入，需右旋转【外侧插入】
LR：对该结点的左儿子的右子树进行了一次插入，先左后右【内侧插入】
RL：对该结点的右儿子的左子树进行了一次插入，先右后左【内侧插入】
RR：对该结点的右儿子的右子树进行了一次插入，需左旋转【外侧插入】
旋转原则：在旋转的时候，都是要以离新插入节点最近的不平衡子树进行旋转
注意旋转的这部分子树一定是不平衡的子树
注意旋转的这部分子树一定是不平衡的子树
AVL树的查找平均复杂度是O（log(n)）
[AVL树]为平衡二叉排序树，但平衡二叉树不一定是二叉排序树
7.邻接矩阵
定义
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，顶点序号依次为0,1,...,n-1，则G的邻接矩阵是具有如下定义的n阶方阵A：
A[i][j]=1表示顶点i与顶点j邻接，即i与j之间存在边或者弧
A[i][j]=0表示i与顶点j不邻接
邻接矩阵是图的顺序存储结构，由邻接矩阵的行数或列数可知图中的顶点数
对于无向图，邻接矩阵是对称的，矩阵中1的个数为图中总边数的两倍
矩阵中第i行或第i列的元素之和即为顶点i的度
矩阵中第i行或第i列的元素之和即为顶点i的度
对于有向图，矩阵中1的个数为图的边数
矩阵中第i行的元素之和即为顶点i的出度，第j列元素之和即为顶点j的入度
矩阵中第i行的元素之和即为顶点i的出度，第j列元素之和即为顶点j的入度
有向网[图]
拓扑排序
广度优先遍历
深度优先遍历
8.排序
稳定排序
直接插入排序
冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换它们两个
归并排序
先使每个子序列有序，再使子序列段间有序
基数排序
不稳定排序
插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
快速排序
选一个元素为枢轴，先由后往前找第一个比其小的数交换，再由前往后找第一个比其大的数交换，反复直至此元素左侧均小于右侧均大于
希尔排序
堆排序
堆是一种特殊的队列，从堆中取出元素是依照元素的优先级大小而不是进入队列的先后顺序
最大堆
任一结点的值大于或等于其子结点的值
根结点元素的值为整个堆中最大
根结点元素的值为整个堆中最大
最小堆
任一结点的值小于或等于其子结点的值
根结点元素的值为整个堆中最小
根结点元素的值为整个堆中最小
9.查找
折半查找
折半查找要求查找表顺序存储且有序
10.树
哈夫曼树
AOE网
11.其他
哈希表
C程序设计
&与*
取址运算符&用来取得其操作数的地址
*取出地址中对应的值
*取出地址中对应的值
0 条评论
下一页
