【星海随笔】数据结构知识总结

---

数据结构

数据结构的研究内容：

• 数据的逻辑结构，数据的存储结构 及 数据的抽象运算。

数据结构中，从逻辑上可以把数据结构分为

•   线性结构  和  非线性结构
  1

• 线性结构：线性表、栈、队、串、数组。
• 非线性结构：树结构、图结构。

线性表的存储结构：顺序存储结构和链式存储结构。

• -顺序存储结构：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

• • 顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高，缺点是插入或删除元素时不方便。

• -链式存储结构：其结点在存储器中的位置是随意的，既逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现。

• • 链式存储时，其相邻数据元素可随意存放，但所占存储空间可分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时方便，使用灵活。缺点是存储密度小，存储空间利用率低。

• -对比

• • 顺序表适用于查找静态的操作。
• • 链式适宜于做插入、删除这样的动态操作。
• • 若线性表的长度变化不大，且其主要操作上查找，则采用顺序表；
• • 若线性表的长度变化较大，且其主要操作是插入、删除操作、则采用链式表。

• -数据结构基本运算：修改、插入、删除、查找、排序。

扩展：

• 索引存储：存储信息的同时，建立附加的索引表，索引表中的每一项成为索引项，索引项的一般形式（关键字，地址）

• • 优点：检索速度快。
• • 缺点：增加索引表，占用较多存储空间，增删数据时也要修改索引表，花费较多的时间。
• • 总结，以空间换时间的数据结构。

• 散列存储：根据元素的关键字直接计算出该元素的存储位置，也称Hash存储

• • 优点：检索，增删节点操作都很快
• • 缺点：散列函数不好可能会出现元素存储单元的冲突，解决冲突会增加时间 ，空间的开销。

单链表

单链表增加一个头结点，便于实现单链表的插入及删除运算

后缀表达式

计算步骤为：

• 遇到数字时，将数字压入栈；
• 遇到运算符时，弹出栈顶的两个数字，并运算，结果入栈
• 重复这个步骤直到表达式最右侧
• 运算得出结果，整个过程只需要一个保存操作及运算结果的栈。

栈

可以实现递归函数和返回数据结构

二维数组

数据结构中,二维数组占用单元

例如A[10][8] 有10 * 8个单元

广义表

对于长度为1的广义表A，若有Head(A)=Tail(A) 则A = (())

广义表 LS = ( ( (a),(b) ) , ( c,(d) , (e,(f) ) ) , ( g , h ) )
表头为 （ （a）,(b) ）即为最外面括号包含的第一个括号内容的全部，其余为表尾。

堆 栈 队列
循环队列：
队头指针出：front = (front + 1) % maxSize
队尾指针出：rear = (rear + 1) % maxSize
队列初始化：front = rear =0
队空条件：front == rear
队满条件：(rear + 1)% maxSize == front

二叉树

由n个节点构成的有限集（n>=0），n=0时为空树。
有且仅有一个根结点；
TL 和 TR 分别称为左子树和右子树。
每个结点度最多为2，有左右之分，不能随意调换。调换后为新的树，与之前的树不同。
形态上有：斜二叉树、满二叉树、完全二叉树
遍历时间复杂度：最好的是完全二叉树为 O（log2n）
最坏的是O(n)
满二叉树的节点数计算公式为：2^k - 1

扩展

二分查找平均搜索长度（ASL）：

•  每个节点层数只和（例如 1 * 1 + 2 *2 + 3 * 3 。。。） /  节点总数
  1

例：13个数值
– 7 （1乘1）
4 – 11（2乘2）
…（3乘n）

注意：要先求得中位数，未得到指定位置大于则 low = mid + 1，小于等于则high = mid - 1
依次类推

二叉树

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

• 进行中序遍历可以得到所有结点的有序序列

树

前序遍历：
后续遍历：左根，右子树为空

• 每个非根结点中所包含的非关键字个数满足
• [ m / 2 ] - 1 <= n <= m -1

森林节点转为二叉树

1.每棵树转换为二叉树
2.去将第二颗树作为第一颗树的右子树
3.将第三棵树作为第二颗树的右子树

哈夫曼树

只含有根结点的二叉树

• • 将两颗根结点权值最小的二叉树，合成一颗新的二叉树；
    1

• • 每次合并就产生一个新结点。进行n-1次合并。
    1

• • 共产生 n - 1 个新结点
    1

哈夫曼树是带权路径长度WPL最小的二叉树
WPL = （W1 * L1 + W2 * L2）

哈夫曼编码

• 取边
• 左子树为0，右子树为1

求路径

迪杰斯特拉（dijkstra）

以一个起点开始，不断以该起点出发找最短路径，并生成图。
算法是按照路径长度不减的次序求出各条路径的

普里姆算法

全局搜索最小权值边，并选用。不能生成环路。

普里姆算法和克鲁斯卡尔算法适用于最小生成树的生成；

图

一个连通图的生成树上包含图中所有顶点的极小连通子图
无向图的邻接矩阵是一个对称矩阵。
有向无环图，称为 顶点活动网。
设有向图G含有n个顶点，e条边，使用邻接矩阵存储，时间复杂度为 O（n^2）

• 入度 (in-degree) ：以某顶点为弧头，终止于该顶点的弧的数目称为该顶点的入度

• 出度 (out-degree) ：以某顶点为弧尾，起始于该顶点的弧的数目称为该顶点的出度

• 临界矩阵：横出，列入

• 拓扑序列为去头留尾,头不断入队

算法

算法：是对特定问题求解步骤的一种描述，它是指令单有限序列，是一系列输入转换为输出的计算步骤。

五大特性：输入、输出、有穷性、确定性、可行性。

算法的设计要求：正确性、可读性、健壮性、效率与低存储量需求。

算法分析：时间复杂度、空间复杂度、稳定性。

• 算法的好坏指标：
• 时间复杂度、空间复杂度、可读性和可操作性。

稳定算法：

• 冒泡算法(一个一个排队)，插入（新队列插入），归并（2，4，8倍数对比），基数（个十百千万（箱子排序的改进））
• 简单选择排序

非稳定算法：

• 直接选择排序（直接选择一个进行对位交换），快速排序（分界值排序），希尔排序（跳跳棋排序），堆排序（类似于二叉树）
• 如果相同关键字的记录之间的相对次序保持不变，则称该排序方法是稳定的。

直接选择：

每次从待排序的无序区中选择出关键字最小的记录，将记录与该区域的第一个记录交换位置。
依次类推，做 n-1 次排序后，记录按递增有序。

快速排序：

仅需四步：
1.设定一个分界值
2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复这个步骤。

例如：一组关键字（45，53，18，49，36，76，13，97，36，32）

• 1.设置45为基准
• 2.1 开始从后往前找比45小的。32 和 45换

•    32，x，x, ..., 45
  1

• 2.2 开始从前往后照比45大的。53和 45换

•    32, 45 , x ,... , 53
  1

• 2.3 开始从后往前照比45小的。36和 45换

•   32, 36, x ,... , 45, 53
  1

依次类推最后第一轮结束得到序列：

• 32，36，18，13，36，45，76，97，49，53
  1

然后第二轮再找一个基准32。

head指针等于tail指针则结束。

栈的基本操作
InitStack(&S)：栈的初始化
StackEmpty(S)：判断栈是否为空
Push(&S,x)：进栈
Pop(&S,&x)：出栈
GetTop(S,&x)：读栈顶元素
ClearStack(&S)：销毁栈

队列的基本操作
InitQueue(&Q)：初始化队列
QueueEmpty(Q)：判队列空
EnQueue(&Q)：入队
DeQueue(&Q,&x)：出队
GetHead(Q,&x)：读队头元素

线性表的基本操作：
InitList(&L):初始化表
Length(L):求表长
LocateElem(L,e)：按值查找操作
GetElem(L,i):按位查找操作
ListInsert(&L,e):插入操作
ListDelete(&L,i,&e):删除操作
Print List(L)：输出操作
Empty(L):判空操作
DestroyList(&L):销毁操作

List的用法

#include
using namespace std;
typydef list<int> LISTTESTA;

assign() 给list赋值 
back() 返回最后一个元素 
begin() 返回指向第一个元素的迭代器 
clear() 删除所有元素 
empty() 如果list是空的则返回true 
end() 返回末尾的迭代器 
erase() 删除一个元素 
front() 返回第一个元素 
get_allocator() 返回list的配置器 
insert() 插入一个元素到list中 
max_size() 返回list能容纳的最大元素数量 
merge() 合并两个list 
pop_back() 删除最后一个元素 
pop_front() 删除第一个元素 
push_back() 在list的末尾添加一个元素 
push_front() 在list的头部添加一个元素 
rbegin() 返回指向第一个元素的逆向迭代器 
remove() 从list删除元素 
remove_if() 按指定条件删除元素 
rend() 指向list末尾的逆向迭代器 
resize() 改变list的大小 
reverse() 把list的元素倒转 
size() 返回list中的元素个数 
sort() 给list排序 
splice() 合并两个list 
swap() 交换两个list 
unique() 删除list中重复的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

C++ 关键字
下表列出了 C++ 中的保留字。这些保留字不能作为常量名、变量名或其他标识符名称。
asm else new this
auto enum operator throw
bool explicit private true
break export protected try
case extern public typedef
catch false register typeid
char float reinterpret_cast typename
class for return union
const friend short unsigned
const_cast goto signed using
continue if sizeof virtual
default inline static void
delete int static_cast volatile
do long struct wchar_t
double mutable switch while
dynamic_cast namespace template

三字符组 替换
??= #
??/
??’ ^
??( [
??) ]
??! |
??< {
??> }
??- ~