期末复习
易错点
叶子结点以外的结点称为分支结点
时间复杂度
1.4
(1) \(O(nm)\)
(2) \(O(n^2)\)
(3) \(O(n^2)\)
(4) \(O(log_3n)\)
线性表
栈与队列
String类
树与二叉树
树的定义与二叉树的性质
二叉树遍历的过程
先序遍历：中 左 右
中序遍历：左 中 右
后序遍历：左 右 中
二叉树遍历的递归算法
二叉树遍历的非递归算法
层次遍历二叉树
二叉树的建立
对于完全二叉树，可以把树存储在一个数组中
但是对于大多数的二叉树，需要用链的形式来储存来减少空间的浪费
节点类型的定义
template <typename T>
struct BTNode{
T data;
BTNode<T> *left;
BTNode<T> *right;
BTNode(const T& k):data(k),left(nullptr),right(nullptr){};
BTNode():data{},left(nullptr),right(nullptr){};
~BTNode(){ }
};
二叉树类的定义
template <typename T>
class BTree {
protected:
BTNode<T>* _root;
public:
BTree():_root(nullptr){}
const BTNode<T>* root() const { return _root; }
BTNode<T>*& root() { return _root; }
void dispose()//删除二叉树
{
if (_root != nullptr)
{
dispose(_root);
_root = nullptr;
}
}
void dispose(BTNode<T>* p)
{
if (p != nullptr)
{
dispose(p->left);
dispose(p->right);
}
delete p;
}
};
根据顺序表建立二叉树
template <typename T>
void byArray(const T* pt, int cnt, BTree<T>* bt)
{
int n = cnt;
if (n == 0)
bt->root() = nullptr;
int i, j;
BTNode<T>** q = new BTNode<T>*[n];
for (i = 0; i < n; i++)
q[i] = new BTNode<T>(pt[i]);
for (i = 0; i < n; i++)
{
j = 2 * i + 1;
if (j < n)
q[i]->left = q[j];
else
q[i]->left = nullptr;
j++;
if (j < n)
q[i]->right = q[j];
else
q[i]->right = nullptr;
}
bt->root() = q[0];
}
根据广义表构建二叉树
template <typename T>
struct ListFlags {
T NullSubtreeFlag;
T LeftDelimitFlag;
T RightDelimitFlag;
T MiddleDelimitFlag;
};
static int idx = 0;
static void* pListFlags = nullptr;
template <typename T>
BTNode<T>* rootByGList(T* sList)
{
BTNode<T>* p = nullptr;
T nodeData = sList[idx];
ListFlags<T>* pFlags = (ListFlags<T>*)pListFlags;
if (isData(nodeData, pFlags))
{
p = new BTNode<T>(nodeData);
idx++;
nodeData = sList[idx];
if (nodeData == pFlags->LeftDelimitFlag)
{
idx++;
p->left = rootByGList(sList);
idx++;
p->right = rootByGList(sList);
idx++;
}
}
if (nodeData == pFlags->NullSubtreeFlag)
idx++;
return p;
}
template <typename T>
void byGList(T* sList, int cnt, BTree<T>* bt, const ListFlags<T>* pCustomListFlags = nullptr)
{
idx = 0;
ListFlags<T> DefaultFlags{ '^','(',')',',' };
if (cnt > 0)
{
ListFlags<T>* p;
if (pCustomListFlags != nullptr)
p = (ListFlags<T>*)pCustomListFlags;
else
p = &DefaultFlags;
pListFlags = p;
bt->root() = rootByGList(sList);
}
else
bt->root() = nullptr;
return;
}
template <typename T>
bool isData(const T& nodeValue, const ListFlags<T>* pFlags)
{
if (nodeValue == pFlags->NullSubtreeFlag) return false;
if (nodeValue == pFlags->LeftDelimitFlag) return false;
if (nodeValue == pFlags->RightDelimitFlag) return false;
if (nodeValue == pFlags->MiddleDelimitFlag) return false;
else return true;
}
根据先根和中根次序建立二叉树
template <typename T>
BTNode<T>* rootBy2Lists(vector<T>& preList, vector<T>& inList) {
BTNode<T>* p = nullptr;
vector<T> presub, insub;
int n = preList.size();
if (n > 0) {
T rootData = preList[0];
p = new BTNode<T>(rootData);
int k = 0;
while (k < n && inList[k] != rootData)
k++;
for (int i = 0; i < k; i++)
presub.push_back(preList[i+1]);
for (int i = 0; i < k; i++)
insub.push_back(inList[i]);
p->left = rootBy2Lists(presub, insub);
presub.clear();
insub.clear();
for (int i = 0; i < n - k - 1; i++)
presub.push_back(preList[i + k + 1]);
for (int i = 0; i < n - k - 1; i++)
insub.push_back(inList[i + k + 1]);
p->right = rootBy2Lists(presub, insub);
}
return p;
}
template <typename T>
void by2Lists(vector<T>& preList, vector<T>& inList, BTree<T>* bt) {
bt->root() = rootBy2Lists(preList, inList);
}
课后习题
9.1
1）
\[\sum_{k=0}^5 2^k=2^6-1=63 \\ 2^5=32 \]联立可得
9.2
二叉树有左子树和右子树的区别，度为2的数只是最大有两个子树而已
9.3
先序遍历:1 2 3 4 5 6 7 8 9
中序遍历:2 3 4 1 6 7 9 8 5
后序遍历:4 3 2 9 8 7 6 5 1
9.4
排序
5.1
排序算法稳定性：
| 算法 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|
| 直接插入排序 | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 冒泡排序 | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 快速排序 | \(O(nlog_2n)\) | \(O(1)\) | 不稳定 |
| 选择排序 | \(O(n^2)\) | \(O(1)\) | 不稳定 |
| 归并排序 | \(O(nlog_2n)\) | \(O(n)\) | 稳定 |
排序算法的形式
直接插入排序
void InsertSort(T* items, int cnt) {
T k;
int m, n = cnt;
int i, j;
for (m = 1; m < n; m++)
{
k = items[m];
for (i = 0; i < m; i++)
{
if (k < items[i]) {
for (int j = m - 1; j >= i; j--)
items[j + 1] = items[j];
items[i] = k;
break;
}
}
}
}
优化过的插入排序
由于前面的m-1个数字已经处于排序状态，所以可以运用查找的方法来进行优化寻找下一个数插入位置的方法，因此经过优化的插入排序的时间复杂度为 \(O(nlog_2n)\)
template <typename T>
inline int BinarySearch(T k, T* items, int cnt, int si = 0, int length = -16) {
if (length == -16)
length = cnt;
int mid = 0, left = si;
int right = left + length - 1;
while (left <= right) {
mid = (left + right) / 2;
if (k == items[mid])
return mid;
else if (k < items[mid]) {
right = mid - 1;
}
else
left = mid + 1;
}
if (k > items[mid])
mid++;
return ~mid;
}
template <typename T>
void InsertSortBS(T* items, int cnt) {
T k;
int i, j, m, n = cnt;
for (m = 1; m < n; m++) {
k = items[m];
//i = lower_bound(items, items + m, k) - items;
i = BinarySearch(k, items, cnt, 0, m);
if (i < 0)
i = ~i;
for (j = m - 1; j >= i; j--)
items[j + 1] = items[j];
items[i] = k;
}
}
冒泡排序
template <typename T>
void myswap(T& x, T& y) {
T t;
t = x;
x = y;
y = t;
}
template <typename T>
void BubbleSort(T* items, int cnt) {
for (int i = cnt-1; i > 0; i--) {
bool exchanged = false;
for (int j = 0; j < i; j++)
{
if (items[j] > items[j + 1])
{
exchanged = true;
myswap(items[j], items[j+1]);
}
}
if (!exchanged)
break;
}
}
选择排序
template <typename T>
void myswap(T& x, T& y) {
T t;
t = x;
x = y;
y = t;
}
template <typename T>
void SelectSort(T* items, int cnt) {
for (int i = 0; i < cnt; i++)
{
T minidx = i ;
for (int j = i + 1; j < cnt; j++) {
if (items[j] < items[minidx])
minidx = j;
}
myswap(items[minidx], items[i]);
}
}
快速排序的原理
1.首先确定一个基准值 \(pilot\) 一般为第一个元素
2.使用两个地址位，第二个元素的地址位为 \(i\) ，最后一个元素的地址位为 \(j\)
3.对 \(i\) 递增操作，直到找到一个 \(i\) 地址位的元素使得其值大于基准值，对 \(j\) 递减操作，只打找到一个 \(j\) 地址位的元素使得其值小于基准值
4.交换 \(i\) 与 \(j\) 两个地址位的元素，重复3中过程，直到不满足 \(i< j\)
5.\(i++,j--\) 然后交换基准元素与 \(j\) 地址位的元素，并以基准值元素为界来分别对左边的元素和右边的元素进行1到5的操作，直到只剩下一个元素为止
归并排序的原理
1.二分区间，把两边的序列认为是已经有序的序列，并将两个有序的序列合成一个有序的序列
2.对于每个想要其有序的序列，对其进行归并排序再合并
3.递归下去，就得到了一个有序的序列
排序的趟数
初始序列并不是第一趟
冒泡排序的最后一趟要跟倒数第二趟一模一样
哈希查找
探测定址法
散列链法
哈希表的实现（散列链法）
顺序查找
template <typename IIT,typename T>
int Index(IIT first, IIT end, const T& k) {
int i = 0;
auto pitems = first;
while (pitems < end && (*pitems) != k) {
i++;
pitems++;
}
if (pitems == end)
return -1;
return i;
}
template <typename IIT,typename Predicate>
int IndexIf(IIT first, IIT end, Predicate pred) {
int i = 0;
auto pitems = first;
while (pitems < end && !pred(*pitems))
{
i++;
pitems++;
}
if (pitems == end)
return -1;
return i;
}
二分查找
前提：序列已经成为有序状态
template <typename T>
int BinarySearch1(const T& k,T* items, int len) {
int left = 0;
int right = len - 1;
int mid = 0;
while (left <= right) {
mid = (left + right) / 2;//最迹在这里打i声明，不然就寄了
if (k == items[mid])
return mid;
else if (k < items[mid])
right = mid - 1;
else
left = mid + 1;
}
if (k > items[mid])
mid++;
return ~mid;
}
如果遇到不存在的数，返回的数字是这个数应该插入的地方取反
例如输出为-6，则是正确的插入位置为 \(6-1=5\)
分块查找
把数据按照某种规律储存在不同的块里面，查找的时候再对应块查找就可以了
二叉查找树、排序树与判定树
二叉查找树和二叉排序树是一样的，只是同一个东西的不同名字
二分判定树则是每次二分查找中 \(mid\) 的值