计算机理论：数据结构基本知识总结

妖狐艹你老母 2022-01-29 05:07 398阅读 0赞

### 计算机理论：数据结构基本知识总结 ###

*  数据结构
 *   *  1. 线性结构
     *   *  1.1 线性表
         *  1.2 栈
         *  1.3 队列
         *  1.4 串
         *  1.5 数组
     *  2. 树
     *   *  2.1 二叉树
     *  3. 图
     *  4. 查找
     *   *  4.1 顺序查找
         *  4.2 折半查找（二分查找）
         *  4.3 索引顺序查找（分块查找）
         *  4.4 树表查找
         *  4.5 哈希查找

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center]

# 数据结构 #

1、分类：线性结构（线性表、栈、队列、串、数组）、非线性结构（树、图）。  
2、存储结构：顺序存储、链接存储。

## 1. 线性结构 ##

1、特点：数据元素之间是一种线性关系。单一全驱和后继。

### 1.1 线性表 ###

1、单链表（n个结点通过指针连成链表，且结点只含一个指针域）、头结点、首元结点、双向链表、循环链表、静态链表  
2、单链表基本运算：查找Find\_List、插入(Insert\_List)、删除(Delete\_List)。  
3、存储方式优缺点：顺序存储（可随机存取数据、查找元素速度快，但插入、删除需移动元素（n/2、(n-1)/2））、链式存储（数据域、指针域，插入、删除无需移动元素，但只能顺序访问元素、无法随机存取）。

### 1.2 栈 ###

1、定义：先进后出的线性表。  
2、栈顶、栈底、空栈、顺序栈（上溢现象）、链栈  
3、栈基本运算：初始化栈（initStack）、判栈空（isEmpty）、入栈（push）、出栈（pop）、读栈顶元素（top）

### 1.3 队列 ###

1、定义：先进先出的线性表。相关概念：队尾、队头。  
2、基本运算：初始化队列（initQueue）、判队空（isEmpty）、入队（enQueue）、出队（deQueue）、读队头元素（frontQueue）  
3、队列顺序存储：队尾有上限、循环队列（区别队空与队满：设置标志域、保留一个元素空间）。队列链式存储：链队列。

### 1.4 串 ###

1、定义：一串文字及符号的简称。元素：字符。  
2、基本术语：串长、空串、空格串、子串、串相等、串比较。  
3、基本操作：赋值（StrAssign）、连接（Concat）、求串长（StrLength）、串比较（StrCompare）、求子串（SubString）。  
4、串的存储结构：顺序存储、链式存储

### 1.5 数组 ###

1、一维数组：长度固定、元素类型相同、元素结构一致的线性表。多维数组：定长线性表在维数上的扩张、线性表的元素还是线性表。  
2、特点：元素数目固定、元素类型相同、下标有序且受上下界约束  
3、基本操作：取值、赋值  
4、二维数组顺序存储：以行为主序、以列为主序。  
5、矩阵、压缩存储、特殊矩阵（值相同的元素或零元分布有规律）、对阶矩阵、对角矩阵、稀疏矩阵（非零元远少于零元且分布无规律）

## 2. 树 ##

1、基本概念：空树、根结子树、双亲、孩子、兄弟、结点度、叶子结点、内部结点、结点层次、树高度、有序树、无序树、森林

### 2.1 二叉树 ###

1、与树的区别：明确左右子树、结点最大度为2。  
2、3个性质：二叉树第i层（i>=1）上至多有2(i-1)个结点；深度为k的二叉树至多有(2k)-1个结点（k>=1）；对于任意一颗二叉树，若其终端结点数为n0，度为2的结点数为n1，则n0=n1+1  
4、满二叉树（深度为k的二叉树有(2^k)-1个结点）、完全二叉树（结点编号与深度相同的满二叉树的结点编号一一对应）  
5、二叉树存储结构：顺序存储（一般不采用）、链式存储（二叉链表、三叉链表）  
6、二叉树遍历：先序遍历、中序遍历、后序遍历（由根结点所在位置决定，多用递归实现）  
7、数和森林与二叉树转换（孩子兄弟表示法）、树的遍历（先根遍历、后根遍历）、森林的遍历（先序遍历、中序遍历、后序遍历）  
8、最优二叉树（带权路径长度最短的二叉树）：两结点间路径、结点的路径长度、树的带权路径长度、哈夫曼方法  
9、二叉查找树：左子树所有结点小于根结点，右子树所有结点大于根结点。

## 3. 图 ##

1、基本概念：图是由点集和边集构成的二元组。有向图（弧、出度、入度、强连通图），无向图（度、连通图）、完全图（任意两个顶点相连）、路径、子图、网  
2、图的存储结构：邻接矩阵表示法、邻接链表表示法

## 4. 查找 ##

1、查找表：由同一类型的数据元素（或记录）构成的集合  
2、查找表分类：静态查找表（只做查询和检索），动态查找表（查询、检索、插入、删除）  
3、关键码（数据元素的某一数据项的值，用于识别数据元素）、主关键码（唯一标识一个数据元素的关键码）、次关键码（能标识多个数据元素的关键码）  
4、查找成功，查找不成功，查找基本操作（将记录关键码与给定值比较）、查找成功的平均查找长度（ASL）

### 4.1 顺序查找 ###

1、定义：从表中第一个记录开始，将给定值与记录关键码逐个比较，若相等则查找成功，若都不等则查找失败  
2、缺点：n较大时，ASL较大，查找效率较低。优点：算法简单、适应面广、不要求存储结构、记录无须有序

### 4.2 折半查找（二分查找） ###

1、记录已排序，将给定值与中间记录的关键码比较，若相等则查找成功；若不等则缩小范围，直至查找成功或区间中无元素（查找失败）。  
2、折半查找判断树（二叉查找树）  
3、缺点：插入删除元素时需移动大量元素，要求记录表顺序存储且有序排列。优点：比顺序查找效率高。适用范围：查找表不易变动且查找频繁。

### 4.3 索引顺序查找（分块查找） ###

1、定义：将查找表分块，块间有序（索引表），块内无序。查找时先在索引表确定待查记录所在块，再在块内进行顺序查找  
2、当块内记录数s等于n的平方根时ASL最小  
3、顺序查找、折半查找和索引顺序查找常用于静态线性表。效率：顺序查找<索引顺序查找<折半查找

### 4.4 树表查找 ###

1、二叉查找树查找：若二叉查找树非空，将给定值与根结点关键码比较，若相等则查找成功，若不相等则根据比较大小前往左右子树查找，直至查找成功或子树为空（查找失败）  
2、二叉查找树插入：若二叉查找树为空，则构造存储该关键码的新结点；若二叉查找树非空，则根据新关键码找到其位置并插入。此方法主要用于构建一个二叉查找树  
3、二叉查找树具有类似于折半查找的特性、采用链式存储结构、是动态查找表的一种适宜表示

### 4.5 哈希查找 ###

1、哈希表，哈希造表或哈希散列（映射过程）、哈希地址或散列地址（存储位置）：根据设定的哈希函数和处理冲突的方法，将一组关键码映射到一个有限的连续的地址区间上，并以关键码在地址区间中的像作为记录在表中的存储位置  
2、冲突：关键码不同，而哈希函数值（哈希地址）相同。  
3、冲突处理方法：开放定址法（增量序列：线性探测再散列、二次探测再散列、随机探测再散列。聚集现象），链地址法（将具有相同哈希函数值的记录组织成一个链表）  
4、哈希查找：根据哈希函数计算元素的哈希地址，若该单元为空则查找失败；若非空，将给定值与元素比较，若相等则查找成功，否则重新计算下一个哈希地址继续查找。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODAxNjQy_size_16_color_FFFFFF_t_70_pic_center]: /images/20220129/10180aa5796c454c971f3490faf6f4e6.png