本人本着以学习为目的整合了2021年王道数据结构考研复习指导、2019年天勤数据结构高分笔记中的大部分算法题、并给出相应的解答和示例，
在此不保证所有的题解均正确无误，仅供学习参考，请勿用于商业用途，如若侵权，请联系并删除。
如果你觉得这个仓库对你有帮助，请不要吝啬你的star!!!谢谢!!!
- 编译器版本
g++ --version
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.- 编译
g++ -o ch02.o ch02.cpp ch02_linear_table/*.cpp
g++ -o ch03.o ch03.cpp ch03_stack_queue/*.cpp
g++ -o ch05.o ch05.cpp ch05_tree/*.cpp
g++ -o ch08.o ch08.cpp ch08_sort/*.cpp -std=c++11- 目录结构
├── README.md
├── ch02.cpp
├── ch02_linear_table (顺序表、单链表)
│ ├── LinkList.cpp
│ ├── LinkList.hpp
│ ├── SqList.cpp
│ ├── SqList.hpp
│ ├── exercises.cpp
│ └── exercises.hpp
├── ch03.cpp
├── ch03_stack_queue (栈、队列)
│ ├── SqQueue.cpp
│ ├── SqQueue.hpp
│ ├── SqStack.cpp
│ ├── SqStack.hpp
│ ├── exercises.cpp
│ └── exercises.hpp
├── ch05.cpp
├── ch05_tree (二叉树、二叉排序树、树、森林)
│ ├── BiTree.cpp
│ ├── BiTree.hpp
│ ├── BinarySearchTree.cpp
│ ├── BinarySearchTree.hpp
│ ├── ThreadTree.cpp
│ ├── ThreadTree.h
│ ├── Tree.cpp
│ ├── Tree.hpp
│ ├── exercises.cpp
│ └── exercises.hpp
├── ch08.cpp
├── ch08_sort (插入、交换、选择、归并)
├── exercises.cpp
├── exercises.hpp
├── sort.cpp
└── sort.hpp
详见: data_struct/wangdao/ch02_linear_table/exercises.hpp
- 练习 2.2 线性表的顺序实现 p19-p21
void Reverse(SqList &L); // 2. 将顺序表 L 的所有元素逆置
void Reverse(ElemType A[], int m, int n, int size); // 8. 将数组顺序表位置互换
// 10. 将 R 中保存的序列循环左移 p (O<p<n ) 个位置
void del_x_2(SqList &L,ElemType x); // 3. 删除线性表中所有值为 x 的数据元素
bool Delete_Same(SqList& L); // 6. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
bool Del_s_t(SqList &L, ElemType s, ElemType t); // 4. 从有序顺序表中删除其值在给定值s与t之间(要求s<t) 的所有元素
bool Del_s_t2(SqList &L, ElemType s, ElemType t); // 5. 从顺序表中删除其值在给定值s与t之间(要求s<t) 的所有元素
bool Merge(SqList A, SqList B, SqList &C); // 7. 将两个有序顺序表合并为一个新的有序顺序表
void SearchExcgIst(ElemType A[], int n, ElemType x); // 9. 线性表递增有序，在表中查找数值为 x 的元素
int MSearch(int A[],int B[],int n); // 11. 找出两个序列 A 和 B 的中位数。
double MSearch1(int A[], int m, int B[],int n);
int MSearch2(int A[],int B[],int n); /** ❌ */
bool Del_Min(SqList &L, ElemType &value); // 1. 从顺序表中删除具有最小值的元素
int Majority (int A[], int n); // 12. 找出数组 A 的主元素
int findMissMin(int A[] , int n); // 13. 找出数组中未出现的最小正整数- 练习 2.2 线性表的链式表示 p40-p44
LinkList Search_Lst_Common(LinkList L1, LinkList L2); // 8. 给定两个单链表，编写算法找出两个链表的公共结点。
LNode* find_addr(LNode *strl , LNode *str2); // 22.找出由 str1 和 str2 所指向两个链表共同后缀的起始位置
int Search_k(LinkList list, int k); // 21.查找链表中倒数第 k 个位直上的结点(k为正整数)
LNode* FindLoopStart(LNode *head); // 24.判断一个链表是否有环，如果有，找出环的入口点并返回，否则返回 NULL。
void change_list(LNode*&h); // 25. 单链表{a1,a2,··· ,an}转换为{a1,an,a2,an-1,a3,an-2,···}
void Del_X_1(LinkList &L, ElemType x); // 1. 设计一个递归算法, 删除不带头结点的单链表 L 中所有值为 x 的结点。
void Del_X_2(LinkList &L, ElemType x); // 2. 在带头结点的单链表 L 中，删除所有值为 x 的结点
void RangeDelete(LinkList &L, int min, int max); // 7. 删除表中所有介于给定的两个值(作为函数参数给出)之间的元素的元素
void Del_Same(LinkList &L); // 12.递增有序的单链表表去重(去掉数值相同的元素)
LinkList Delete_Min(LinkList &L); // 4. 带头结点的单链表 L 中删除一个最小值结点
void MinDelete(LinkList &head); // 9. 按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间
void Del_All(LinkList &L); // 19.反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。
void R_Print(LinkList L); // 3. 带头结点的单链表从尾到头反向输出每个结点的值
LinkList Reverse_1(LinkList &L); // 5. 将带头结点的单链表就地逆置
void Sort(LinkList &L); // 6. 有一个带头结点的单链表 L，设计一个算法使其元素递增有序。
LinkList DisCreat_1(LinkList &A); // 10.将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B
LinkList DisCreat_2(LinkList &A); // 11.单链表 A 分解为A={a1,a2,··· , an,}, B={bn,bn-1,...,b2,b1}
LinkList MergeList(LinkList La,LinkList Lb); // 13.将两个按元素值递增次序排列的单链表归并为一个递减的单链表
LinkList Get_Common(LinkList A, LinkList B); // 14.从两个元素递增有序的单链表(带头结点)中的公共元素产生单链表C
void Union(LinkList &la, LinkList &lb); // 15.求两个元素递增排列的单链表 A 与 B 的交集，并存放于 A 链表中。
int Symmetry(DLinkList L); // 17.判断带头结点的循环双链表是否对称。
LinkList Link(LinkList &h1 , LinkList &h2); // 18.将循环单链表h2 链接到循环单链表h1，要求链接后的链表仍保持循环链表。
DLinkList Locate(DLinkList &L,ElemType x); // 20.非循环双向链表符合要求的 Locate(L,x) 运算的算法
int Pattern(LinkList A,LinkList B); // 16. 判断序列 B 是否是序列 A 的连续子序列
void func(LNode* &h, int n); // 23.对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点详见: data_struct/wangdao/ch03_stack_queue/exercises.hpp
- 练习 3.1 栈 p71
int dc(LNode<char> *L, int n); // 4. 判断链表的全部 n 个字符是否中心对称
typedef struct sstk{ // 5. 共享栈
int top[2];
ElemType data[MaxStackSize];
};
int push(ElemType i, ElemType x);
int pop (ElemType i);- 练习 3.2 队列
typedef struct tqueue{ // 1. 设置一个标志域 tag 的入队和出队算法
ElemType data[MaxStackSize];
int front,rear,tag;
};
int tEnQueue(tqueue &s, ElemType x);
int tDeQueue(tqueue &s, ElemType &x);
void Inverse(SqQueue<ElemType> &Q, SqStack<ElemType> &S); // 2. Q 是一个队列，S 是一个空栈，实现将队列中的元素逆置的算法。
typedef struct SSQueue{ // 3. 利用两个栈 S1, S2 来模拟一个队列
SqStack<ElemType> S1,S2;
};
int EnSSQueue(SSQueue &q, ElemType x);
int DeSSQueue(SSQueue &q, ElemType &x);
int SSQueueEmpty(SSQueue q);- 3.3 核和队列的应用 p96-97
bool BracketsCheck(char *str); // 1. 判别表达式中的括号是否配对
double p(int n,double x); // 2. 利用一个找实现递归函数的非递归计算详见: data_struct/wangdao/ch05_tree/exercises.hpp
- 练习 5.3 二叉树的遍历和索引二叉树 (p149-p151)
void InvertLevel(BiTree T); // 4. 二又树自下而上、从右到左的层次遍历算法。
int Btdepth(BiTree T); // 5. 非递归求二叉树的高度。
int BtdepthR(BiTree T);
BiTNode* BiTreePreinCreate(ElemType *A, int l1, int h1, // 6. 根据先序遍历序列和中序遍历序列建立二叉链表 (二叉树中各结点的值互不相同)
ElemType *B, int l2, int h2);
bool IsComplete(BiTree T); // 7. 判别二叉树是否为完全二叉树。
int DsonNodes (BiTree T); // 8. 计算一棵给定二叉树的所有双分支结点个数。
int DsonNodes1 (BiTree T);
void swap(BiTree T); // 9. 交换二叉树中所有结点的左、右子树。
void swap1(BiTree T);
ElemType PreNode(BiTree T, int k); // 10. 求先序遍历序列中第 k (1<= k <= 二又树中结点个数)个结点的值。
void SearchDeleteXTree(BiTree T, ElemType x); // 11. 对于树中每个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。
void Search (BiTree T , ElemType x); // 12. 在二叉树中查找值为 x 的结点，打印值为 x 的结点的所有祖先
bool SearchR (BiTree T , ElemType x);
BiTree Ancestor(BiTree ROOT, BiTNode *p, BiTNode *q); // 13. 找到 p 和 q的最近公共祖先结点 r。
BiTree AncestorR(BiTree T, BiTNode *p, BiTNode *q);
int BTWidth(BiTree T); // 14. 求非空二又树 b 的宽度(即具有结点数最多的那一层的结点个数)。
void PreToPost(ElemType pre[],int l1, int h1, // 15. 满二叉树已知其先序序列为 pre，求后序序列 post。
ElemType post[],int l2,int h2);
BiTNode* LeafToLinikedList(BiTNode* T); // 16. 二叉树的叶结点按从左到右的顺序连成一个单链表
bool Similar(BiTree T1, BiTree T2); // 17. 判断两棵二叉树是否相似
ThreadNode* InPostPre(ThreadNode* T , ThreadNode* p); // 18. 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法 。
int wpl(BiTree T); // 19. 二又树的带权路径长度
void BtreeToExp(BiTree T, int depth); // 20. 将给定的表达式树(二叉树)转换为等价的中缀表达式并输出。- 练习 5.4 树、森林 (p176-p177)
int leaves(CSTree T); // 5. 编程求以孩子兄弟表示法存储的森林的叶子结点数。
void createCSTree_Degree( // 7. 己知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子兄弟链表。
CSTree&T, ElemType e[], int degree[], int n);
int Height (CSTree bt); // 6. 以孩子兄弟链表为存储结构，请设计递归算法求树的深度。- 练习 5.5 树与二叉树的应用 (p195-p196)
bool JudgeBST(BSTree bt); // 6. 试编写一个算法，判断给定的二叉树是否是二叉排序树。
int level(BSTree bst, BSTNode *p); // 7. 设计一个算法，求出在指定结点给定二叉排序树中的层次。
int levelR(BSTree bst, BSTNode *p);
/** ★★☆ */
bool Judge_AVL(BSTree bst, int &depth); // 8. 利用二叉树遍历的**编写一个判断二叉树是否是平衡二叉树的算法。
int MinBST(BSTree bst); // 9. 设计一个算法，求出给定二叉排序树中最小和最大的关键字。
int MaxBST(BSTree bst);
void OutPut(BSTNode *bt, int key); // 10. 设计一个算法 ，从大到小输出二叉排序树中所有值不小于 k 的关键字。
BSTNode *Search_Small(BSTNode*t , int k ); // 12. 二叉排序树上查找第 k (1<=k<=n) 小的元素，并返回指向该结点的指针。- 总结 p206-p207
void DelLeafNode(BiTree bt); // 6. 从二叉树中删去所有叶结点。 (层次遍历 => 参考练习5.3_11)
int GetLevel(BiTree bt,BiTNode *p); // 7. 计算指定结点 *p 所在的层次。 (层次遍历=>参考练习5.3_5)
详见: data_struct/wangdao/ch08_sort/exercises.hpp
- 8.3 交换排序 p323-p324
void BubbleSort(ElemType A[], int n); // 2. 双向冒泡排序算法
void move(ElemType A[], int n); // 3. 把所有奇数移动到所有偶数前边的算法
void move2(ElemType A[], int n);
int Partition2(ElemType A[], int low, int high); // 4. 重新编写快速排序的划分算法，使之每次选取的枢轴值都是随机地从当前子表中选择的。
int kth_elem(ElemType A[] , int low, int high, int k); // 5. 数组中找出第 k 小的元素
int setPartition(ElemType A[], int n); // 6. 将A划分为两个不相交的子集，满足 |n_1-n_2| 最小且 |S_1-S_2| 最大
int PartitionN(ElemType A[],int n); // 4. (8.6)数组{K_1,K_2，...，K_n}, 将 K_n，放在将元素排序后的正确位置上
void Flag_A_rrange(ElemType A[],int n); // 7. 荷兰国旗问题- 8.4 选择排序 p335
void selectSort(LNode<ElemType> *&L); // 4. 在基于单链表表示的待排序关键字序列上进行简单选择排序。
bool IsMinHeap(ElemType A[], int len); // 5. 试设计一个算法，判断一个数据序列是否构成一个小根堆。- 8.6 各种内部排序算法的比较和应用
void Insert_Sort(ElemType A[] , int m, int n); // 2. 前m个元素递增有序，后n个元素递增有序，设计一个算法，使得整个顺序表有序。[1]2021年王道数据结构考研复习指导 [2]C++之函数/结构体/类 模板
-
第2章 线性表
- 顺序表的定义和基本操作
- 单链表的定义和基本操作
- 双链表的定义和基本操作
- 线性表习题集
-
第3章 栈和队列
- 栈的存储结构和算法
- 队列的存储结构和算法
- 队列和栈的习题
-
第6章 树和二叉树
- 二叉树的存储结构和基本操作(主要是二叉树)
- 二叉树的递归遍历
- 二叉树的非递归遍历
- 索引二叉树
- 树、森林、二叉树
- 二叉树习题
-
第8章 内部排序
- 插入类
- 直接插入排序
- 折半插入排序
- 希尔排序
- 交换类
- 冒泡排序
- 快速排序
- 选择类
- 简单选择排序
- 最大堆调整
- 选择类
- 简单选择排序
- 堆排序
- 归并排序
- 二路归并排序
- 插入类
-
第9章 查找
- 顺序查找
- 折半查找
- 二叉排序树
- 平衡二叉排序树
- 第1章 C++编程基础
extern void example_01_06(); // p7
extern void example_01_07(); // p33
extern void ex_01_01(); // p7
extern void ex_01_02(); // p7
extern void ex_01_05(); // p33
extern void ex_01_06(); // p33
extern void ex_01_07(); // p34- 第2章 面向过程的编程风格
extern bool example_02_01(int pos, int &elem); // p36
extern void example_02_02(); // p45 传值、传指针、传引用
extern const vector<int>* example_02_03(int size); // p54 局部静态对象
extern bool example_02_04(int pos, int& elems); // p55 内联函数lc: leetcode、面试题(smo): 剑指offer
| 题号 | 题名 | 方法 |
|---|---|---|
| 167 | 两数之和 II - 输入有序数组 | 双指针 |
| 面试题57 | 和为s的两个数字 | 双指针 |
| 977 | 有序数组的平方 | 双指针 |
| 88 | 合并两个有序数组 | 双指针 |
| 26 | 删除排序数组中的重复项 | 双指针 |
| 283 | 移动零 | 双指针 |
| 面试题03 | 数组中重复的数字 | 哈希 |
| 面试题04 | 二维数组中的查找 | 双指针 |
| 面试题06 | 从尾到头打印链表 | 双指针 |
| 面试题21 | 调整数组顺序使奇数位于偶数前面 | 双指针 |
| 面试题39 | 数组中出现次数超过一半的数字 | |
| 面试题63 | 股票的最大利润 | 打擂台法 |