数据结构与算法笔记

一、概论

1.数据结构

2.算法

3.前置知识：类模板

• memset

  • 作用：用于将一块内存的每个字节设置为特定的值（按字节填充）。

  • 用途：通常用于初始化内存（如清零或赋固定值）。

  • 示例：

    cpp

    1 2	char buffer[100]; memset(buffer, 0, sizeof(buffer)); // 将buffer的所有字节设为0

二、线性表(父类)

定义：线性表是由元素组成的一种有限且有序的序列

特征：元素间满足一对一的关系，所有元素排成现行序列

二元组B=(K,R) 称称为开始结点，最后一个是终止结点，n称为线性表的长度，n=0为空表

具有反对称性(每个元素至多一个前驱和后继)和传递性

节点集K中有一个唯一的开始结点，没有前驱，有唯一后继

有限集K存在唯一的终止结点，有唯一前驱，但没有后继

顺序表链表等涉及的数据类型案例如下

1
2
3
4
5
6
7
8
9
10

template <class T>
class List{
    void clear();
    bool isEmpty();
    bool append(const T value);
    bool insert(const int p,const T value);
    bool delete(const int p);
    bool getValue(const int p,T& value);
    bool getPos(int & p,const T value);
}

1.顺序表（子类）

我们可以继承线性表的类

1

class arrList : public List<T>

按照数组存储的（存储空间连续）

逻辑结构和物理结构类似，都是线性的

如果设,每个元素占用L个存储单位 顺序表的插入

把对应位置腾出来，之前每个元素往后移动一位

就是把后面的都挤下去

1
2
3
4
5
6
7
8
9
10
11
12

template<class T>
bool List<T>::insert(const int p, const T value) {
    if (Curlen >= maxSize || p<0 || p > curlen) {
        return false; /*检查顺序表是否溢出，插入位置是否合法*/
    }
    for (int i = curlen; i > p; i--) {
        data[i] = data[i - 1];
    }
    data[p] = value;
    curLen++;
    return true;
}

删除也是类似

时间复杂度都是O(n)

2.链表

逻辑结构也是线性，但是是按照指针来存储的（链式）

单链表常常引入一个头结点，作为表头，避免对空表的处理（操作方便），和后续操作统一，不然第一个是把地址给指针，第二个却是给结构体里的一个成员

我们一般把头结点和尾结点的指针写在一起

时间复杂度源于寻找元素

三、栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表

允许插入和删除的那一端叫做栈顶top

另一端叫做栈底bottom

不含任何数据元素的栈叫做空栈

栈是后进后出的线性表，LIFO结构

顺序栈以尾部作为栈顶，链表栈以首元素为栈顶

(让push和pop操作时间复杂度在O(1))

维护一个单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;  // 存储的是索引
        vector<int> answer(temperatures.size(), 0);  // 初始化为0

        for (int i = 0; i < temperatures.size(); i++) {
            // 当前温度比栈顶温度高时，更新栈顶的答案
            while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
                answer[s.top()] = i - s.top();  // 计算等待天数
                s.pop();  // 处理完后弹出
            }
            // 当前温度 <= 栈顶温度时，入栈（等待更高的温度）
            s.push(i);
        }

        return answer;
    }
};

队列是先进先出的线性表

前缀表达式与后缀表达式转换

四、串

1.传统模式匹配

考虑主字符串

a b a b a c a b a c a b a b

子字符串

a b a c a b ab

判断子字符串是否在主字符串中，一个简单的思路是求出主字符串和子字符串长度一样的字符串，然后判断是否相等

思路就是遍历主字符串的首字母，然后往后延长，让长度和子字符串一样，然后判断是否相等

我们考虑两个指标i和j，i遍历主串，j遍历子串

比较s1[i+j]和s2[j]，如果一样就继续，不一样直接让i下一个、

2.KMP算法

利用已经匹配的进行跳转

由于子字符串中可能有重复的内容

也就是前缀和后缀相等，这使得我们可以省略一些遍历的步骤，比如i可以直接跳好几个

子字符串有什么样的结构可以简化呢？

就是子字符串前面的k个和从后面往前数k个，如果一样的话

其实就是利用主字符串的尾部，如果能和子字符串的头部一样，就可以省一些子字符串的遍历

比如说abba，前面有a，后面也有a，那么比如说主字符串是abbc

这时候我们其实比对到abbc了，也就是说主字符串跑到第4位

由于在j=3的时候失败了，所以也就是说j=2的时候，主字符串末尾是b，而子字符串头是a，这个压根没有一样的，所以必须要重新比了，让j=0，i++

再考虑一个例子abacab，主字符串是abacac，在j=5的时候出问题了，然后我们看j=4，从他往前看，只有一个a和前缀a一样，所以这时候应该让j=1，i++

我们把j的变化存入一个next数组就可以了，这个实际上和主字符串是没有关系的，只和子字符串有关

也就是说

如果j=0就出问题的话，那就和前面暴力一样了，直接i+1开始比就行了，那我们就要让j=0和i+1去比，所以让next[j] = -1,然后后面+一下就变成0了

next[j] = -1

然后如果有前缀和后缀可以匹配，那这就好办了，有多少个一样，就让j从哪里开始就行了 然后如果没有可以匹配的呢，那就让j=0重新开始

next数组的优化nextval

而next向量是可以优化的，因为如果第j个跳转之后，和第j个还是一样的话，那其实可以直接再跳转一次，可以省略这一步再比较

换而言之。假设next[j] = P[j],因为j不匹配，所以next[j]肯定也不匹配，所以可以再next

换而言之，直接令next[j] = next[next[j]]就可以了

一个问题，需不需要考虑多次跳转？即使省略了一步跳转，有没有可能跳转之后还是一样的？

实际上不用考虑，因为跳转之后的k肯定在j前面，而k已经被优化了，所以我们跳一步就已经是最佳的了

五、二叉树

前面链表，每一个节点后继只有一个节点，但是如果一个结点后继有多个结点，但是每个结点只有一个前驱，那这就构成一个树状的结构，然后如果最多只有两个后继结点，那就是二叉树

两个后继结点分左子树和右子树

结点拥有的子树数称为结点的度，度为0的结点称为叶子结点

二叉树有五种形态

空二叉树

只有一个根结点

有左子树无右子树

有右子树无左子树

左右子树都有

二叉树又可以分为满二叉树，完全二叉树

满二叉树：

所有分支结点都有左子树和右子树，并且所有叶子都在同一层

完全二叉树：

对每个结点编号后，编号为i的结点与同样满二叉树中结点在二叉树位置中完全相同，称为完全二叉树

扩充二叉树：

假设现在有n个结点，除了根结点，每个结点都有父结点，所以此时有n-1条边

把空的子树补上，假设补了m个子树

那么此时连接的线数是n+m-1

又因为补完之后，每个结点都有两个子树了，所以有2n个线数

所以 得 从扩充的二叉树的根到每个外部结点（没扩充之前的结点）的路径的长度之和称为外部路径长度E

扩充的二叉树从根到每个内部节点的路径长度之和为内部路径长度I

有关系 每个内部节点贡献两个子树，所以+2n

二叉树的性质

计算深度 因为

二叉树的存储结构

完全二叉树可以用顺序表存储

一般使用二叉链表存储

1
2
3
4

typedef struct BiTNode {
	char data;	//数据域struct BiTNode
	BiTNode* lChild, * rChild;	//左右子树域
}*BiTree;

二叉树的遍历

从根结点出发，按照某种次序依次访问二叉树的所有结点

前序中序后序遍历

前序遍历

如果空操作就返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历

先遍历根节点的左子树，然后再访问根结点，最后遍历右子树

后序

先遍历左子树，右子树，最后访问根节点

实现方式

1
2
3
4
5
6
7
8

//先序遍历二叉树
void TraverseBiTree(BiTree T)
{
	if (T == NULL)return;
	cout << T->data;
	TraverseBiTree(T->lChild);
	TraverseBiTree(T->rChild);
}

非递归算法

使用栈来遍历

先考虑前序遍历

存储根结点的右子树地址，然后往左向下，存储器下一个结点的右子树地址，继续往下，直到尽头，然后最后一个叶子出栈，访问右子树，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void Preorder()
{
    stack<binarytree*> a;
    binarytree* p = this;
    a.push(p);
    while (!a.empty())
    {
        while (p != nullptr)
        {
            a.push(p);
            cout << p->val;
            p = p->left;
        }
        p = a.top();
        a.pop();
        p = p->right;
    }
}

层次遍历法（BFS)

由于完全二叉树可以直接按层序编号，变成顺序表的形式，所以我们直接遍历每一层就行了

那么，如何根据编号确定父结点和孩子结点呢？

如果结点在第i个位置

那么 怎么证明呢，很简单，我们把第i个结点后面的结点都砍掉，然后再进行扩充二叉树，扩充的时候，先填满i所在的那一层，然后再填充下一层，直到第i个结点的右子树

那么，根据前面的性质，要填充i+2个（因为有i+1个结点）,那么，最后一个结点是第2i+3，在数组里的位置就是2i+2

所以右子树就是2i+2,那自然左子树就是2i+1了

然后根据子树寻找父结点，更简单了

线索二叉树

一般二叉树都是通过链式存储的，对于有n个结点的二叉树，只用到了n-1个指针，而一共有2n个指针，这样就浪费了n+1个指针，那么这样就浪费了很多，如何利用起来呢

我们可以将空的左子树指针，指向前驱，然后空的右子树指针，指向后继，这样就可以把一个二叉树转换成一个双向链表，遍历起来就方便了，我们把指向前驱和后继的指针叫做线索

当然，这个前驱和后继，和遍历方式有关，先序和中序、后序都不一样

当然，为了区分左子树指针是不是空的，还需要增加标志位

Ltag,如果是0就是左子树，否则就是前驱

二叉搜索树

我们可以找一个这样的二叉树

满足，左子树<根节点<右结点，

这样十分便于我们搜索

有点像二分法，我们查找一个值，先从根结点开始，如果比根节点大，往右走，如果比根结点小，往左走，然后如此循环，直到找到，或者遍历到空，那就说明没有

插入操作

如果二叉树不为空，直接插入，否则先查找，得到最后停留的子树，然后继续插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

bool InsertBST(Bitree*& T, int key) { 
    Bitree* p = nullptr;
    if (!SearchBST(T, key, nullptr, p)) { // 初始父节点为nullptr
        Bitree* s = new Bitree;
        s->val = key;
        s->left = s->right = nullptr;

        if (!p) {       // 空树情况
            T = s;      
        }
        else if (key < p->val) {
            p->left = s;
        }
        else {
            p->right = s;
        }
        return true;
    }
    return false;
}

删除操作

如果只有单子树，直接嫁接就行

如果两个子树都有，可以寻找中序遍历的前驱和后继

用前驱或者后继来代替被删除的子树

六、堆

堆就是一种特殊的完全二叉树，满足偏序关系

即父结点大于等于子结点，或者小于等于

前者称为大堆顶，后者称为小堆顶

堆的构建

从第一个非叶子结点 i =[n/2]开始，比较子节点，以小堆顶为例，如果父结点比最小的子节点小，就交换，如此递归

为什么从非叶子节点开始呢？因为叶子结点没有子树，那么以他为节点的二叉树，自然满足堆了

建堆就是倒着让每个元素下沉，如果一个根结点大于最小的子树，就让他下沉，交换这两个结点，同时这可能会影响子树的堆，因此要递归交换完的位置

也可以考虑自上而下，一边插入一边构建，也就是说一直siftup

插入

将不断与父节点对比，直到根节点，不断上浮siftup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void siftUp(int index) {
	while (index > 0)
	{
		int parent = (index - 1) / 2;
		int temp = heap[index];
		if (heap[index] > heap[parent])
		{
			break;
		}
		heap[index] = heap[parent];
		heap[parent] = temp;
		index = parent;
	}
}
void push(int val) {
	heap.push_back(val);
	siftUp(heap.size() - 1);
}

删除

将最后一个结点和根节点交换，然后这里需要下沉，和上面正好相反

七、图

图的存储

邻接矩阵

邻接表

拓扑排序

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Graph {
private:
	int verticeNum;
	int EdgeNum;
	adjList* adj;
	int* indegree;
public:
	Graph(int n, int m)
	{
		verticeNum = n;
		EdgeNum = m;
		adj = new adjList[verticeNum];
		indegree = new int[verticeNum] {0};
	}
	void addEdge(int from, int to)
	{
		adj[from].headappend(to);
		indegree[to]++;

	}
	void sort()
	{
		MinHeap indeg;
		for (int i = 0; i < verticeNum; i++)
		{
			if (indegree[i] == 0)
			{
				indeg.push(i);
			}
		}
		while (!indeg.empty())
		{
			int v = indeg.top();
			indeg.pop();
			printf("%d", v + 1);
			for (Edgenode* p = adj[v].firstedge; p != nullptr; p = p->next)
			{
				int w = p->adjvex;
				indegree[w]--;
				if (indegree[w] == 0)
					indeg.push(w);
			}
		}
	}
	
};

八、哈希表

可以用散列函数，生成每个值对应的地址，直接根据散列地址，可以在O(1)内查到元素，比如两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution{
public:
	vector<int> twoSum(vector<int>& nums,int target)
	{
		unordered_map<int,int> hashtable; #创建hash表
		for(int i = 0;i<nums.size();++i)
		{
			auto it = hashtable.find(target - nums[i]) #查找
			if (it != hashtable.end()) /*如果有直接返回，不然就把i加入哈希表*/
			{
				return(it->second,i)
			}
			hahshtable[nums[i]] = i;
 		}
 		return {}
	}
}

九、排序

快速排序

采用分治算法，选择一个轴值pivot,将原序列划分为两个子序列，其中一个序列的所有元素小于等于pivot,另一个大于pivot，这样就可以递归成排序这两个子序列的问题

1
2
3
4
5
6
7
8
9
10

void QuickSort(int* record, int start, int end)
{
	if (start < end) //当子序列只有一个元素start=end,结束递归（无需排列）
	{
		int q = Partion(record, start, end); //求出轴值所在位置
		QuickSort(record, start, q - 1);
		QuickSort(record, q + 1, end);
	}

}

那怎么求出轴值所在位置呢，我们用j遍历一遍原序列，

如果record[j]<=轴值，这说明轴值左边有一个元素

我们可以用i来统计左边的元素个数，i从start-1开始，i记录最后一个小于等于轴值的数，如果满足上述条件，此时i++

不过，既然我们是递归到子序列的排序，那其实左边的没必要排序，那我们顺手，直接让record[i]和record[j]交换，这样直接就把小于等于轴值的放过来了，然后i+1自然就是轴值的位置了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int Partion(int* record, int start, int end)
{
	int x = record[end];
	int i = start - 1;
	for (int j = start; j < end - 1; j++)
	{
		if (record[j] <= x)
		{
			i++;
			swap(record[j], record[i]);
		}
	}
	swap(record[end], record[++i]);
	return i;
}

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

for (int i = 0; i < vex.size(); i++)
{
	for (int j = i + 1; j < vex.size(); j++)
	{
		if (abs(vex[i].sum - vex[j].sum) > 1)
		{
			count++;
			continue;
		}
		int** d = new int* [n + 1];
		for (int k = 0; k <= n; k++)
		{
			d[k] = new int[n + 1];
			d[k][0] = d[0][k] = 0;
		}
		for (int k = 1; k <= n; k++)
		{
			for (int l = 1; l <= n; l++)
			{
				if (vex[i].bits[k - 1] == vex[j].bits[l - 1]) d[k][l] = 1 + d[k - 1][l - 1];
				else if (d[k - 1][l] >= d[k][l - 1]) d[k][l] = d[k - 1][l];
				else d[k][l] = d[k][l - 1];
			}
		}
		if (d[n][n] == n - 1) g.addEdge(i, j);
	}
}