C++算法
数据结构核心考点与算法实现指南
系统梳理数据结构核心知识点，涵盖线性表、栈、队列、树、图、查找及排序等章节。内容包含基本概念、存储结构、算法实现（C/C++代码）及时间复杂度分析，适用于计算机专业学生复习备考或算法基础学习。重点讲解了二分查找、KMP、哈夫曼树、最小生成树及各类排序算法的原理与代码实现。
系统梳理数据结构核心知识点，涵盖线性表、栈、队列、树、图、查找及排序等章节。内容包含基本概念、存储结构、算法实现（C/C++代码）及时间复杂度分析，适用于计算机专业学生复习备考或算法基础学习。重点讲解了二分查找、KMP、哈夫曼树、最小生成树及各类排序算法的原理与代码实现。
具有相同数据类型的 n(n ≥ 0) 个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
// 静态分配
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
int length;
} SqList;
// 动态分配
#define InitSize 100
typedef struct {
ElemType *data;
int MaxSize, length;
} SeqList;
InitList(&L)：初始化表Length(L)：求表长LocateElem(L, e)：按值查找GetElem(L, i)：按位查找ListInsert(&L, i, e)：插入操作ListDelete(&L, i, &e)：删除操作PrintList(L)：输出操作Empty(L)：判空操作DestroyList(&L)：销毁操作// 插入操作
bool ListInsert(SqList &L, int i, ElemType e) {
if(i < 1 || i > L.length + 1) return false;
for(int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.length++;
return true;
}
// 时间复杂度 O(n)
// 删除操作
bool ListDelete(SqList &L, int i, ElemType &e) {
if(i < 1 || i > L.length) return false;
e = L.data[i - 1];
for(int j = i; j < L.length; j++) L.data[j - 1] = L.data[j];
L.length--;
return true;
}
// 时间复杂度 O(n)
// 按值查找
int LocateElem(SqList L, ElemType e) {
int i;
for(i = 0; i < L.length; i++)
if(L.data[i] == e) return i + 1;
return 0;
}
// 按位查找
int GetElem(SqList L, int i) {
if(i < 1 || i > L.length) return 0;
return L.data[i - 1];
}
bool Merge(SqList A, SqList B, SqList &C) {
if(A.length + B.length > C.MaxSize) return false;
int i = 0, j = 0, k = 0;
while(i < A.length && j < B.length) {
if(A.data[i] <= B.data[j]) C.data[k++] = A.data[i++];
else C.data[k++] = B.data[j++];
}
while(i < A.length) C.data[k++] = A.data[i++];
while(j < B.length) C.data[k++] = B.data[j++];
C.length = k;
return true;
}
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
typedef struct DNode {
ElemType data;
struct DNode *prior, *next;
} DNode, *DLinkList;
L->next = LL->next = L; L->prior = Ltypedef struct {
ElemType data[MaxSize];
int top;
} SqStack;
typedef struct {
ElemType data[MaxSize];
int front, rear;
} SqQueue;
Q.front == Q.rear(Q.rear + 1) % MaxSize == Q.front(Q.rear + MaxSize - Q.front) % MaxSize| 算法种类 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 希尔排序 | - | - | - | O(1) | 否 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 否 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 否 |
| 2 路归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 是 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 是 |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online