VitePress KB

第一章数据结构绪论

数据：描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素：组成数据的、有一定意义的基本单位，在计算机中通常作为正常退处理。（也称为记录）
数据项：一个数据元素可以由若干个数据项组成。*（就是对象属性）*是数据不可分隔的最小单位。
数据对象：是性质相同的数据元素的集合 , 是数据的⼦集。
数据结构：是相互之间存在⼀种或多种特定关系的数据元素的集合｡
逻辑结构：数据对象中数据元素之间的相互关系｡
- 集合结构：集合结构中的数据元素除了同属于⼀个集合外,各个数据元素是 “ 平等 ” 的。
- 线性结构:数据元素之间是 ⼀对⼀ 的关系
- 树形结构:数据元素之间存在⼀种 ⼀对多 的层次关系
- 图形结构:数据元素是 多对多 的关系
物理结构 :是指数据的逻辑结构在计算机中的存储形式｡
- 顺序存储结构:把数据元素存放在地址连续的存储单元⾥ , 系和物理关系是⼀致的*（就是排队占位）*
- 链式存储结构:是把数据元素存放在任意的存储单元⾥ , 这组存储单元可以是连续的 , 也可以是不连续的｡（⽤⼀个指针存放数据元素的地址）
数据类型:是指⼀组性质相同的值的集合及定义在此集合上的⼀些操作的总称｡
例如在 C 语⾔中 , 按照取值的不同 , 数据类型可以分为两类 :
- 原⼦类型 : 是不可以再分解的基本类型 , 包括整型､实型､字符型等｡
- 结构类型 : 由若⼲个类型组合⽽成 , 型数据组成的，是可以再分解的｡例如 , 整型数组是由若⼲整
抽象 :指抽取出事物具有的普遍性的本质｡
**抽象数据类型( A b s t r a c t D a t a T y p e , A D T ) **: 指⼀个数学模型及定义在该模型上的⼀组 操作 ｡

第二章算法

算法：解决特定问题求解步骤的 描述 , 在计算机中表现为指令的有限序列 , 并且每条指令表示⼀个或多个操作｡

特性	解释
输⼊输出	算法具有零个或多个输⼊，⾄少有⼀个或多个输出.
有穷性	算法在执⾏有限的步骤之后 , ⾃动结束⽽不会出现⽆限循环 , 并且每⼀个步骤在可接受的时间内完成｡
确定性	算法的每⼀步骤都具有确定的含义 , 不会出现⼆义性｡
可⾏性	算法的每⼀步都必须是可⾏的 , 也就是说 , 每⼀步都能够通过执⾏有限次数完成｡

设计要求	解释
正确性	算法的正确性是指算法⾄少应该具有输⼊ , 输出和加⼯处理⽆歧义性､能正确反映问题的需求､能够得到问题的正确答案｡
可读性	设计的另⼀⽬的是为了便于阅读､理解和交流｡
健壮性	当输⼊数据不合法时 , 算法也能做出相关处理 , ⽽不是产⽣异常或莫名其妙的结果｡
时间效率⾼和存储量低	时间效率：指的是算法的执⾏时间 , 对于同⼀个问题 , 如果有多个算法能够解决 ,执⾏时间短的算法效率⾼ , 执⾏时间⻓的效率低｡存储量需求: 指的是算法在执⾏过程中需要的最⼤存储空间 , 主要指算法程序运⾏时所占⽤的内存或外部硬盘存储空间｡ (⽤最少的存储空间 ,花最少的时间 , 办成同样的事)

算法效率的度量⽅法
- 事后统计⽅法 : 这种⽅法主要是通过设计好的测试程序和数据 , 利⽤计算机计时器对不同算法编制的程序的运⾏时间进⾏⽐较 , 从⽽确定算法效率的⾼低｡
- 事前分析估算⽅法 : 在计算机程序编制前 , 依据统计⽅法对算法进⾏估算｡✅
⼀个程序的运⾏时间 , 依赖于算法的好坏和问题的输⼊规模
- 问题输⼊规模：是指输⼊量的多少｡
函数的渐近增⻓ ：给定两个函数 f ( n ) 和 g ( n ) ,如果存在⼀个整数 N , 使得对于所有的 n > N , f ( n ) 总是⽐ g ( n ) ⼤ , 的增⻓渐近快于 g ( n )。
判断⼀个算法的效率时 , 函数中的常数和其他次要项常常可以忽略 , ⽽更应该关注主项 ( 最⾼阶项 )的阶数｡
时间复杂度 ：记作 : T ( n )= 0 ( f ( n ) )
它表示随问题规模 n 的增⼤ , 算法执⾏时间的增⻓率和f ( n ) 的增⻓率相同 , 称作算法的渐近时间复杂度 , 简称为时间复杂度｡其中 f ( n ) 是问题规模 n 的某个函数｡
推导⼤ O 阶⽅法：
1 . ⽤常数 1 取代运⾏时间中的所有加法常数｡ 2 . 在修改后的运⾏次数函数中 , 只保留最⾼阶项｡ 3 . 如果最⾼阶项存在且不是 1 , 则去除与这个项相乘的常数｡得到的结果就是⼤ O 阶｡
分析算法的复杂度 , 关键就是要分析循环结构的运⾏情况｡
循环的时间复杂度等于循环体的复杂度乘以该循环运⾏的次数｡
算法空间复杂度：计算公式记作 : S ( n ) = 0 ( E ( n ) ) , 其中 , n 为问题的规模 , f ( n ) 为语句关于n 所占存储空间的函数｡

第三章线性表

线性表 ( L i s t ) : 零个或多个数据元素的有限序列｡
若将线性表记为 ( a1 ,..., a i-1 , a i , a i+1 ,⋯, a n ) , 则表中 a i -1 领先于 a i , a i 领先于 a i +1 , 称 a i -1 是 ai 的直接前驱元素 , a i + 1 是 ai 的直接后继元素｡当 i = 1 , 2 ,...,n-1时 , ai 有且仅有⼀个直接后继 , 当 i = 2 , 3 , ... , n 时 , a i 有且仅有⼀个直接前驱｡
线性表元素的个数 n ( n ≥ 0 ) 定义为线性表的⻓度 , 当 n = 0 时 , 称为空表｡
在较复杂的线性表中 , ⼀个数据元素可以由若⼲个数据项组成｡

线性表的抽象数据类型

json

A D T 线 性 表 ( L i s t )
Data
		线 性 表 的 数 据 对 象 集 合 为 ( a 1 ,a2,...,a n } , 每 个 元 素 的 类 型 			均 为 D a t a T y p e ｡ 其 中 , 除 第⼀ 个 元 素 a1 外 , 每 ⼀ 个 元 素 有 且 		只 有 ⼀ 个 直 接 前 驱 元 素 , 除 了 最 后 ⼀ 个 元 来 a n 外 , 每 ⼀ 个 元 素 		有 且 只 有 ⼀ 个 直 接 后 继 元 素 ｡ 数 据 元 素 之 间 的 关 系 是 ⼀ 对 ⼀ 的
		关 系 ｡
Operation
		Initlist (*L) 	: 初 始 化 操 作 , 建 ⽴ ⼀ 个 空 的 线 性 表 L ｡
		ListEmpty (L) 	: 若 线 性 表 为 空 , 返 回 t r u e , 否 则 返 回 f a l s e 
		Clearlist (*L) 	: 线 性 表 清 空 ｡
		GetElem ( L , i , * e ) : 将 线 性 表 L 中 的 第 i 个 位 置 元 素 值 返 回 															给 e ｡

		LocateElem ( L , e ) : 		在 线 性 表 L 中 查 找 与 给 定 值 e 相 等 的 元 															素 , 如 果 查 找 成 功 , 返 回 该 元 素 在 表 中 															序 号 表 示 成 功 ; 否 则 , 返 回 ⼝ 表 示 失 败 ｡

		ListInsert ( * L , i , e ) : 在 线 性 表 ⼯ 中 的 第 i 个 位 置 插 ⼊ 新 元 																	素 e

		ListDelete ( * L , i , * e ) : 删 除 线 性 表 L 中 第 i 个 位 置 元 素 , 并 																		⽤ e 返 回 其 值 ｡

		ListLength (L) : 返 回 线 性 表 L 的 元 素 个 数 ｡
endADT

线性表的顺序存储结构: ⽤⼀段地址连续的存储单元依次存储线性表的数据元素｡
顺序存储⽅式：⼀维数组来实现顺序存储结构 , 即把第⼀个数据元素存到数组下标为 0 的位置中 , 接着把线性表相邻的元素存储在数组中相邻的位置｡
地址：存储器中的每个存储单元都有⾃⼰的 编号
地址计算⽅法:
- 假设占⽤的是 c 个存储单元 , 那么线性表中第 i + 1 个数据元素的存储位置和第 i 个数据元素的存储位置满⾜下列关系 ( L O C 表示获得存储位置的函数 ) ｡
  LOC(a i +1) = LOC(a i) + c
- 对于第 i 个数据元素 a 的存储位置可以由 a 1 推算得出
  LOC(a i) = LOC(a1) + (i-1)*c

线性表顺序存储结构的忧缺点

优点	缺点
1. ⽆须为表示表中元素之间的逻辑关系⽽增加额外的存储空间 2. 可以快速地存取表中任⼀位置的元素	1. 插⼊和删除操作需要移动⼤量元素 2. 当线性表⻓度变化较⼤时 , 难以确定存储空间的容量 3. 造成存储空间的 “ 碎⽚ ”

线性表的链式存储结构: 在链式结构中 , 除了要存数据元素信息外 , 还要存储它的后继元素的存储地址｡
为了表示每个数据元素 a i 与其直接后继数据元素 a i+ 1 之间的逻辑关系 , 对数据元素 a i 来说 , 除了存储其本身的信息之外 , 还需存储⼀个指示其直接后继的信息 ( 即直接后继的存储位置 )
数据域:存储数据元素信息的域
指针域:存储直接后继位置的域
指针 (或链):指针域中存储的信息
结点 ( N o d e ):数据域+指针域
线性表 ( a 1 , a 2 ,⋯, a n ) 的链式存储结构：n 个结点 ( a 1 的存储映像 ) 链结成⼀个链表
单链表：链表的每个结点中只包含⼀个指针域。
头指针：链表中第⼀个结点的存储位置
头结点：在单链表的第⼀个结点前附设⼀个结点，头结点的数据域可以不存储任何信息。

头指针与头结点的异同

头指针	头结点
1. 头指针是指链表指向第⼀个结点的指针 , 若链表有头结点 ,则是指向头结点的指针 2. 头指针具有标识作⽤ , 所以常⽤头指针冠以链表的名字 3.⽆论链表是否为空 , 头指针均不为空｡头指针是链表的必要元素	1. 头结点是为了操作的统⼀和⽅便⽽设⽴的 , 放在第⼀元素的结点之前 , 其数据域⼀般⽆意义 (也可存放链表的⻓度 ) 2. 有了头结点 , 对在第⼀元素结点前插⼊结点和删除第⼀结点 , 其操作与其它结点的操作就统 3. 头结点不⼀定是链表必须要素

节点的代码描述

/* 线 性 表 的 单 链 表 存 储 结 构 */
typedef struct Node
{
	ElemType data;
	struct Node *next;
} Node;
typedef struct Node *LinkList; /*定义 LinkList*/

结点由存放数据元素的数据域存放后继结点地址的指针域组成

单链表获得链表第 i 个数据的算法思路
1. 声明⼀个结点 p 指向链表第⼀个结点 , 初始化 j 从 1 开始 ;
2. 当 j<i 时 , 就遍历链表 , 让 p 的指针向后移动 , 不断指向下⼀结点 , j 累加 1 ;
3. 若到链表末尾 p 为空 , 则说明第 i 个元素不存在 ;
4. 否则查找成功 , 返回结点 P 的数据｡
单链表 第 i 个数据插⼊结点 的算法思路 :
1. 声明⼀结点 p 指向链表第⼀个结点 , 初始化 j 从 1 开始 ;
2. 当 j < i 时 , 就遍历链表 , 让 p 的指针向后移动 , 不断指向下⼀结点 , j 累加 1 ;
3. 若到链表末尾 P 为空 , 则说明第 i 个元素不存在 ;
4. 否则查找成功 , 在系统中⽣成⼀个空结点 S ;
5. 将数据元素 e 赋值给 s - > d a t a ;
6. 单链表的插⼊标准语句 s - > n e x t = p - > n e x t p - > n e x t = s ;
7. 返回成功｡
单链表 第 i 个数据删除结点 的算法思路 :
1. 声明⼀结点 p 指向链表第⼀个结点 , 初始化 j 从 1 开始 ;
2. 当 j < i 时 , 就遍历链表 , 让 P 的指针向后移动 , 不断指向下⼀个结点 , j 累加 1
3. 若到链表末尾 p 为空 , 则说明第 i 个元素不存在 ;
4. 否则查找成功 , 将欲删除的结点 p - > n e x t 赋值给 9 ;
5. 单链表的删除标准语句 p - > n e x t = 9 > n e x t ;
6. 将 q 结点中的数据赋值给 e , 作为返回 ;
7. 释放 q 结点 ;
8. 返回成功｡
单链表 整表创建 的算法思路 :
1. 声明⼀结点 P 和计数器变量 i ;
2. 初始化⼀空链表 L ;
3. 让 L 的头结点的指针指向 N U L L , 即建⽴⼀个带头结点的单链表 ;
4. 循环：
  - ⽣成⼀新结点赋值给 P ;
  - 随机⽣成⼀数字赋值给 P 的数据域 p - > d a t a ;
  - 将 p 插⼊到头结点与前⼀新结点之间
头插法：始终让新结点在第⼀的位置。
尾插法：每次新结点都插在终端结点的后⾯。
单链表整表删除的算法思路
1. 声明⼀结点 p 和 q ;
2. 将第⼀个结点赋值给 p
3. 循环
  - 将下⼀结点赋值给 q ;
  - 释放 p
  - 将 q 賦值给 p

使用场景选择

顺序结构	单链表结构
1、需要频繁查找 , 很少进⾏插⼊和删除操作时 2、事先知道线性表的⼤致⻓度	1、需要频繁插⼊和删除时 2、当线性表中的元素个数变化较⼤或者根本不知道有多⼤时

静态链表：⽤数组描述的链表
备⽤链表 :未被使⽤的数组元素 ,数组第⼀个和最后⼀个元素作为特殊元素处理 , 不存数据｡
静态链表的插⼊操作
1. 先获取最后一个元素的cur值
2. 将插入元素给列表中最后一个元素
3. 找到被插入i位置的元素的cur
4. 将新元素的cur改为被插入元素的cur（即第3步获取的cur）
5. 将被插入元素的cur指定为新元素存储的下标
静态链表的删除操作 *

第一章 数据结构绪论 ​

第二章 算法 ​

第三章 线性表 ​

第一章数据结构绪论

第二章算法

第三章线性表