第七章 排序（桶排序）
要求对输入的字符串进行排序 可变字符串的基数排序代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<iostream>#include<vector>#include<cstring>#include<cstdio>using namespace std;/** 对String类对象的数组进行基数排序* 假设全为ASCII码* 并设所有字符串的长度都以maxLen为界*/void radixSort(vector<string>& arr, int maxLen){ const int BUCKETS = 256;//把字符看作256进制的数 vector<vector<string>> wordsByLength(maxLen +...
第九章 图论算法（搜索和拓扑排序）
搜索图的类12345678910111213141516171819202122232425#include <iostream>#include <list>#include <vector>#include<queue>using namespace std;class Graph { int V; // 图的顶点数 vector<list<int>> adj; // 邻接表public: Graph(int V); // 构造函数 void addEdge(int v, int w); // 添加边 void DFSUtil(int v, bool visited[]); // 用于DFS的辅助递归函数 void DFS(int v); // 深度优先遍历函数 void BFS(int s); // 宽度优先遍历函数};Graph::Graph(int V) { this->V = V; ...
第九章 图论算法（最小生成树）
Prim算法Prim算法是一种用于寻找加权连通图的最小生成树（MST）的贪心算法。该算法从任意一个顶点开始，逐步将最近的未访问过的顶点添加到正在构建的最小生成树中，直到所有顶点都被包含在内。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;const int MAX = 100; // 假设图的最大顶点数为100int graph[MAX][MAX]; // 图的邻接矩阵表示bool visited[MAX]; // 访问标记数组int parent[MAX]; ...
第九章 图论算法（最短路径）
Dijkstra算法Dijkstra算法是一种用于寻找带权重图中单源最短路径的经典算法。它适用于非负权重的图。算法的基本思想是从起点开始，逐步扩展到其他顶点，每次都选择当前距离最小的顶点进行扩展，直到所有顶点都被处理完毕。 在C++中，可以使用优先队列（通常使用std::priority_queue）来高效地实现Dijkstra算法。 代码实现Graph类123456789101112131415161718192021222324252627#include <iostream>#include <vector>#include <queue>#include <limits>#include <utility>using namespace std;const int INF = numeric_limits<int>::max();class Graph { int V; // 图的顶点数 vector<vector<pair<int,...
第二章 表、栈和队列
链表单链表1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include <iostream>using namespace std;// 定义节点结构体struct Node { int data; Node* next; Node(int d) : data(d), next(nullptr) {}};// 定义单链表类class SinglyLinkedList {private: Node* head;public: SinglyLinkedList() : head(nullptr) {} // 在链表末尾添加新节点 void addAtEnd(int value); ...
第八章 不相交集类（并查集）
完整代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<iostream>#include<vector>#include<cstring>#include<cstdio>using namespace std;class DisjSets{public: explicit DisjSets(int numElements); int find(int x) const; int find(int x); void unionSets(int root1, int root2);private: vector<int> s;};DisjSets::DisjSets(int numElements) :s{ numElements,-1...
第六章 优先队列（堆）
提醒注意vector元素之间赋值要调用move函数 二叉堆结构性质 类的声明123456789101112131415161718192021222324252627282930313233#pragma one#include<vector>#include<iostream>using namespace std;template<typename Comparable>class BinaryHeap{public: explicit BinaryHeap(vector<Comparable>& items) :this->array(items.size()+10),this->currentSize(items.size()) { for (int i = 0; i < items.size(); i++) { this->array[i + 1] =...
第四章 树（AVL树)
AVL树节点声明12345678910111213static const int ALLOWED_IMBALANCE = 1;//AVL树允许的最大高度差struct AvlNode{ int element; AvlNode* left;//左子节点 AvlNode* right;//右子节点 int height;//高度 AvlNode(const int& e, AvlNode* lt, AvlNode* rt, int h = 0) :element(e),left(lt),right(rt),height(h){} AvlNode(int && e,AvlNode*lt,AvlNode*rt,int h=0) :element(move(e)),left(lt),right(rt),height(h){}}; 函数height1234int height(AvlNode* t)//返回节点的高度，如果节点没有子节点则返回-1{ return t == nullptr...
