pinterest.com
4364 字
22 分钟
代码背后的逻辑森林：「数据结构」课程笔记·上机
数据结构01
线性结构
链表与基础操作
- 单向链表（Singly Linked List）
struct node { int data; node *next;};
//初始化：node* head = nullptr;
void Print(node *head) { node *indexNode = head; while (indexNode->next != nullptr) { cout << indexNode->data << " "; indexNode = indexNode->next; } cout << indexNode->data << endl;}
//需要对链表进行增删操作的，都需要传入表头的引用void TailInsert(node *&head, int data) { node *newNode = new node(); newNode->data = data; newNode->next = nullptr; if (head == nullptr) { head = newNode; return; } node *findTailNode = head; while (findTailNode->next != nullptr) findTailNode = findTailNode->next; findTailNode->next = newNode;}
void HeadInsert(node *&head, int data) { node *newNode = new node(); newNode->data = data; newNode->next = head; head = newNode;}
void InsertAtPosition(node *&head, int data, int pos) { if (pos == 0) { HeadInsert(head, data); return; } node *indexNode = head; while (pos--) { indexNode = indexNode->next; } node *newNode = new node(); newNode->data = data; newNode->next = indexNode->next; indexNode->next = newNode;}
void EraseAtPosition(node *&head, int pos) { node *indexNode = head; if (pos == 0) { head = head->next; cout << indexNode->data << endl; delete indexNode; return; } pos--; while (pos--) { indexNode = indexNode->next; } node *eraseNode = indexNode->next; indexNode->next = eraseNode->next; cout << eraseNode->data << endl; delete eraseNode;}- 双向链表（Doubly Linked List）
struct node{ int data; node *prev; node *next;};
//初始化：node* head = nullptr;
void Print(node *head); // 同单向链表实现
node* GetNewNode(int val) { node *newNode = new node(); newNode->data = val; newNode->next = nullptr; newNode->prev = nullptr; return newNode;}
void HeadInsert(node *&head, int val) { node* newNode = GetNewNode(val); if (head == nullptr) { head = newNode; return; } newNode->next = head; head->prev = newNode; head = newNode;}
void TailInsert(node *&head, int val) { node* newNode = GetNewNode(val); if (head == nullptr) { head = newNode; return; } node* findTailNode = head; while(findTailNode->next != nullptr) { findTailNode = findTailNode->next; } findTailNode->next = newNode; newNode->prev = findTailNode;}
void InsertAtPosition(node *&head, int val, int pos) { if (pos == 0) { HeadInsert(head, val); } node *indexNode = head; while(pos--) { indexNode = indexNode->next; } node* newNode = GetNewNode(val); newNode->next = indexNode->next; newNode->prev = indexNode; indexNode->next = newNode; if (newNode->next != nullptr) { newNode->next->prev = newNode; }}
void EraseAtPosition(node *&head, int pos) { node *indexNode = head; if (pos == 0) { head = head->next; delete indexNode; return; } pos--; while (pos--) { indexNode = indexNode->next; } node *eraseNode = indexNode->next; indexNode->next = eraseNode->next; if (eraseNode->next != nullptr) { eraseNode->next->prev = indexNode; } delete eraseNode;}
void EraseByValue(node *&head, int val) { int cnt = 0; node *indexNode = head; while (indexNode != nullptr) { if (indexNode->data == val) { if (indexNode->next != nullptr) indexNode->next->prev = indexNode->prev; if (indexNode->prev != nullptr) indexNode->prev->next = indexNode->next; if (indexNode == head) head = indexNode->next; delete indexNode; cnt++; } else { indexNode = indexNode->next; } } if (cnt == 0) cout << "-1\n";}环形队列
#define MAX 100
int rbq[MAX]; // 数组维护的链表int head = 0;int tail = 0;int size = 0;
bool derbq(int capa, int &ret) { if (size == 0) { cout << "Empty\n"; return false; } else if (head == tail) { //cout << rbq[tail] << endl; ret = rbq[tail]; size--; } else { //cout << rbq[head] << endl; ret = rbq[head]; head = (head + capa + 1) % capa; size--; } return true;}
bool enrbq(int capa, int val) { if (size == capa) { //cout << "Full\n"; return false; } else { if (size == 0) rbq[tail] = val; else { tail = (tail + capa + 1) % capa; rbq[tail] = val; } size++; } return true;}内部排序
冒泡排序
void bubble_sort(int *a, int n) { bool flag = true; int last = n - 1; while (flag) { flag = false; int tmp; for (int i = 0; i < last; i++) { if (a[i] > a[i + 1]) { swap(a[i], a[i + 1]); flag = true; tmp = i; } } last = tmp; }}插入排序
void insert_sort(int *a, int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i-1; while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; } a[j+1] = key; }}选择排序
void selection_sort(int *a, int n) { for (int i = 0; i < n - 1; i++) { int ith = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[ith]) ith = j; } swap(a[i], a[ith]); }}快速排序
int part(int *a, int low, int high) { int privot = a[low]; while (low < high) { while (low < high && a[high] >= privot) high--; a[low] = a[high]; while (low < high && a[low] <= privot) low++; a[high] = a[low]; } a[low] = privot; return low;}void quick_sort(int *a, int low, int high) { if (low < high) { int privotPos = part(a, low, high); quick_sort(a, low, privotPos - 1); quick_sort(a, privotPos + 1, high); }}库函数：stable_sort
#include <algorithm>#include <vector>#include <string>
int main() { vector<int> intVec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; stable_sort(intVec.begin(), intVec.end());
vector<pair<string, int>> stu = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 20}, {"David", 25}, {"Eve", 30}}; stable_sort(stu.begin(), stu.end(), [](const pair<string, int>& a,const pair<string, int>& b) { if (a.second != b.second) { return a.second < b.second; else return a.first < b.first; });
for (const auto& student : stu) { std::cout << student.first << ": " << student.second << std::endl; } return 0;}树
树与基础操作
#include <iostream>#include <vector>#include <unordered_map>#include <queue>
using namespace std;
struct node { int data; node* child; node* sibling;};
const int MAXN = 1000;
node* GetNewNode(int val) { node* newNode = new node(); newNode->data = val; newNode->child = nullptr; newNode->sibling = nullptr; return newNode;}
void AddNewChild(node* parent, node* child) { if (parent->child == nullptr) parent->child = child; else { node* sibling = parent->child; while (sibling->sibling != nullptr) sibling = sibling->sibling; sibling->sibling = child; }}
void PreorderTraversal(node* root) { if (!root) return; cout << root->data << " "; node* child = root->child; while (child) { PreorderTraversal(child); child = child->sibling; }}
void PostorderTraversal(node* root) { if (!root) return; node* child = root->child; while (child) { PostorderTraversal(child); child = child->sibling; } cout << root->data << " ";}
void LevelorderTraversal(node* root) { if (root == nullptr) return; queue<node*> q; q.push(root); while (!q.empty()) { node* currnode = q.front(); q.pop(); cout << currnode->data << " "; node* child = currnode->child; while (child != nullptr) { q.push(child); child = child->sibling; } }}
void GetLeafValue(node* root, int &LeafNum) { if (!root) return; if (!root->child) { cout << root->data << " "; LeafNum++; } else { node* child = root->child; while (child) { GetLeafValue(child, LeafNum); child = child->sibling; } }}
int GetTreeHeight(node* root) { if (!root) { return 0; } int height = 0; node* child = root->child; if (child) { int childHeight = GetTreeHeight(child); child = child->sibling; height = max(height, childHeight); } return height + 1;}
int main(){ int nodeNum = 0; int index, parent; node* root = nullptr; unordered_map<int, node*> nodes; while (cin >> index >> parent) { nodes[index] = GetNewNode(index); nodeNum++; if (parent == -1) { root = nodes[index]; } else { AddNewChild(nodes[parent], nodes[index]); } } PreorderTraversal(root); cout << endl; PostorderTraversal(root); cout << endl; LevelorderTraversal(root); cout << endl; cout << nodeNum << endl; int LeafNum = 0; GetLeafValue(root,LeafNum); cout << endl; cout << LeafNum << endl; cout << GetTreeHeight(root)-1 << endl; return 0;}二叉树与基础操作
struct BiNODE { char data; BiNODE *lchild; BiNODE *rchild;}
// 第一部分 建树
// 辅助函数：创建一个新的二叉树节点BiNODE* createNode(char data) { BiNODE* newNode = new BiNODE; newNode->data = data; newNode->lchild = nullptr; newNode->rchild = nullptr; return newNode;}
BiNODE* BuildTree() { int option; cin >> option; if (option == 1) { // 按先序+两个标志位建树 int n; cin >> n; return BuildTreePreorderWithFlags(n); } else if (option == 2) { // 按先序序列+中序序列建树 int n; cin >> n; return BuildTreePreorderInorder(n); } return nullptr;}
BiNODE* BuildTreePreorderWithFlags(int n) { if (n == 0) return nullptr; char data; int ltag, rtag; cin >> ltag >> data >> rtag; BiNODE* root = createNode(data); root->lchild = (ltag == 0) ? BuildTreePreorderWithFlags(n - 1) : nullptr; root->rchild = (rtag == 0) ? BuildTreePreorderWithFlags(n - 1) : nullptr; return root;}
BiNODE* BuildTreePreorderInorder(int n) { if (n == 0) return nullptr; char* preorder = new char[n]; char* inorder = new char[n]; for (int i = 0; i < n; ++i) cin >> preorder[i]; for (int i = 0; i < n; ++i) cin >> inorder[i]; return BuildTreePreorderInorderHelper(preorder, 0, n - 1, inorder, 0, n - 1);}
BiNODE* BuildTreePreorderInorderHelper(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) return nullptr; char rootData = preorder[preStart]; BiNODE* root = createNode(rootData); int rootIndex = inStart; while (inorder[rootIndex] != rootData) ++rootIndex; int leftSize = rootIndex - inStart; root->lchild = BuildTreePreorderInorderHelper(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1); root->rchild = BuildTreePreorderInorderHelper(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd); return root;}
// 第二部分 遍历二叉树
void Recursion_Pre_Order(BiNODE* root) { if (root) { cout << root->data << " "; Recursion_Pre_Order(root->lchild); Recursion_Pre_Order(root->rchild); }}
void NoRecursion_Pre_Order(BiNODE* root) { if (!root) return; stack<BiNODE*> s; s.push(root); while (!s.empty()) { BiNODE* current = s.top(); s.pop(); cout << current->data << " "; if (current->rchild) s.push(current->rchild); if (current->lchild) s.push(current->lchild); }}
void Recursion_In_Order(BiNODE* root) { if (root) { Recursion_In_Order(root->lchild); cout << root->data << " "; Recursion_In_Order(root->rchild); }}
void NoRecursion_In_Order(BiNODE* root) { if (!root) return; stack<BiNODE*> s; BiNODE* current = root; while (current || !s.empty()) { while (current) { s.push(current); current = current->lchild; } current = s.top(); s.pop(); cout << current->data << " "; current = current->rchild; }}
void Recursion_Post_Order(BiNODE* root) { if (root) { Recursion_Post_Order(root->lchild); Recursion_Post_Order(root->rchild); cout << root->data << " "; }}
void NoRecursion_Post_Order(BiNODE* root) { if (!root) return; stack<BiNODE*> s; stack<char> output; s.push(root); while (!s.empty()) { BiNODE* current = s.top(); s.pop(); output.push(current->data); if (current->lchild) s.push(current->lchild); if (current->rchild) s.push(current->rchild); } while (!output.empty()) { cout << output.top() << " "; output.pop(); }}
void Hierachicalorder(BiNODE* root) { if (!root) return; queue<BiNODE*> q; q.push(root); while (!q.empty()) { BiNODE* current = q.front(); q.pop(); cout << current->data << " "; if (current->lchild) q.push(current->lchild); if (current->rchild) q.push(current->rchild); }}
// 第三部分 二叉树的应用
int Size_Of_Tree(BiNODE* root) { if (!root) return 0; return 1 + Size_Of_Tree(root->lchild) + Size_Of_Tree(root->rchild);}
int Height_Of_Tree(BiNODE* root) { if (!root) return 0; return 1 + max(Height_Of_Tree(root->lchild), Height_Of_Tree(root->rchild));}
bool Is_Full_Tree(BiNODE* root) { if (!root) return true; int leftHeight = Height_Of_Tree(root->lchild); int rightHeight = Height_Of_Tree(root->rchild); return leftHeight == rightHeight && Is_Full_Tree(root->lchild) && Is_Full_Tree(root->rchild);}
bool Is_Complete_Tree(BiNODE* root) { if (!root) return true; queue<BiNODE*> q; q.push(root); bool flag = false; while (!q.empty()) { BiNODE* current = q.front(); q.pop(); if (current) { if (flag) return false; // 在之前已经遇到了空节点，不能再有非空节点 q.push(current->lchild); q.push(current->rchild); } else { flag = true; // 遇到了空节点 } } return true;}
bool isBinarySearchTree(BiNODE* root) { return isBSTUtil(root, CHAR_MIN, CHAR_MAX);}
bool isBSTUtil(BiNODE* root, char minValue, char maxValue) { if (!root) return true; return (root->data > minValue && root->data < maxValue) && isBSTUtil(root->lchild, minValue, root->data) && isBSTUtil(root->rchild, root->data, maxValue);}树的应用：并查集
#include <iostream>#include <map>#define MAXN 100000using namespace std;
struct Node { int rank; //树的节点数，对根节点有意义 int parent;};
/*初始化并查集，令每个节点均为父节点*/void initSet(Node s[]) { for (int i=0; i<MAXN; i++) { s[i].rank=1; s[i].parent=-1; }}
/*查找i所属集合根节点*/int findSet(Node s[], int i) { int k = i; while(s[k].parent != -1) { k=s[k].parent; } return k;}
/*合并两个集合*/int unionSet(Node s[], int i, int j) { int root1 = findSet(s,i); int root2 = findSet(s,j); if (root1==root2) return root1; int rank1 = s[root1].rank; int rank2 = s[root2].rank; int newRank = rank1+rank2; //元素少的成为子树 if (rank1 > rank2) { s[root2].parent=root1; s[root1].rank=newRank; return root1; } else { s[root1].parent=root2; s[root2].rank=newRank; return root2; }}
int main() { int cases; cin >> cases; for (int i=0; i<cases; i++) { int cpNum; cin >> cpNum; int cnt=0; map<string, int> hash; Node s[MAXN]; initSet(s); int rankUpdate = -1; for (int j=0; j<cpNum; j++) { /*将朋友名与固定值对应*/ string f1, f2; cin >> f1 >> f2; auto it = hash.find(f1); if (it == hash.end()) hash[f1] = cnt++; it = hash.find(f2); if (it == hash.end()) hash[f2] = cnt++; int newRoot = unionSet(s,hash[f1],hash[f2]); if (s[newRoot].rank != rankUpdate) { rankUpdate = s[newRoot].rank; } cout << rankUpdate << endl; } } return 0;}数据结构02
二叉树操作
#include <iostream>#include <vector>#include <queue>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr){}; TreeNode(int val) : val(val), left(nullptr), right(nullptr){}; TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right){};};
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) { if (postorder.size() == 0) return NULL; // 后序遍历数组最后一个元素，就是当前的中间节点 int rootValue = postorder[postorder.size() - 1]; TreeNode* root = new TreeNode(rootValue); // 叶子节点 if (postorder.size() == 1) return root; // 找到中序遍历的切割点 int delimiterIndex; for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) if (inorder[delimiterIndex] == rootValue) break; // 切割中序数组 // 左闭右开区间：[0, delimiterIndex) vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); // [delimiterIndex + 1, end) vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); // postorder 舍弃末尾元素 postorder.resize(postorder.size() - 1); // 切割后序数组 // 依然左闭右开，注意这里使用了左中序数组大小作为切割点 // [0, leftInorder.size) vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); // [leftInorder.size(), end) vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end()); root->left = traversal(leftInorder, leftPostorder); root->right = traversal(rightInorder, rightPostorder); return root;}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.size() == 0 || postorder.size() == 0) return NULL; return traversal(inorder, postorder);}
void preorder(TreeNode* root, vector<int>& ans) { if (!root) return; ans.push_back(root->val); preorder(root->left, ans); preorder(root->right, ans);}
void levelorder(TreeNode* root, vector<vector<int>>& ans) { queue<TreeNode*> que; if(root) que.push(root); while(!que.empty()) { int size = que.size(); vector<int> curLevel; for (int i=0; i<size; i++) { TreeNode* curNode = que.front(); que.pop(); if (curNode->left) que.push(curNode->left); if (curNode->right) que.push(curNode->right); curLevel.push_back(curNode->val); } ans.push_back(curLevel); }}
void inverse(TreeNode* &root) { if (!root) return; swap(root->left, root->right); inverse(root->left); inverse(root->right);}
bool symCmp(TreeNode* lhs, TreeNode* rhs) { if ((!lhs && rhs) || (lhs && !rhs)) return false; else if (!lhs && !rhs) return true; else if (lhs->val != rhs->val) return false;
return symCmp(lhs->left, rhs->right) && symCmp(lhs->right, rhs->left);}
bool isSymmetic(TreeNode* root) { if (!root) return true; else return symCmp(root->left, root->right);}
void minVal(TreeNode* root, int &minNum) { if (!root) return; if (minNum > root->val) minNum = root->val; minVal(root->left, minNum); minVal(root->right, minNum);}
void maxVal(TreeNode* root, int &maxNum) { if (!root) return; if (maxNum < root->val) maxNum = root->val; maxVal(root->left, maxNum); maxVal(root->right, maxNum);}
int maxVal2(TreeNode* root) { if (!root) return INT_MIN; return (max(root->val, max(maxVal2(root->left), maxVal2(root->right))));}
int maxDepth(TreeNode* root) { // 实际上就是根节点的高度 // 先算左子树深度，再算右子树深度，再取左右深度大的加上当前节点的1 // 左右中，是后序遍历思想 if (!root) return 0; int lHeight = maxDepth(root->left); int rHeight = maxDepth(root->right); return 1+max(lHeight,rHeight);}
int getHeight(TreeNode* root) { // 返回当前节点二叉树高度，如果高度不平衡返回-1 if (!root) return 0; int lHeight = getHeight(root->left); int rHeight = getHeight(root->right); if (lHeight == -1 || rHeight == -1) return -1; return abs(lHeight-rHeight)>1 ? -1 : 1+max(lHeight,rHeight);}
int isBalance(TreeNode* root) { return (getHeight(root) != -1);}
int minDepth(TreeNode* root) { // 当只有左子树/右子树为空，并不是最低点，仍需要进入递归下一层 // 同样是后序遍历的思想，左右子树的深度是先算的 if (!root) return 0; if (!(root->left) && root->right) return 1+minDepth(root->right); if (root->left && !(root->right)) return 1+minDepth(root->left); return 1+min(minDepth(root->left),minDepth(root->right));}
int nodeNum(TreeNode* root) { if (!root) return 0; return 1+nodeNum(root->left)+nodeNum(root->right);}
bool CBTisFull(TreeNode* root, int &height) { // 判断完全二叉树是不是满 if (!root) return true; int leftDepth = 0, rightDepth = 0; TreeNode *left = root->left, *right = root->right; while (left) { left = left->left; leftDepth++; } while (right) { right = right->right; rightDepth++; } height = leftDepth; return (leftDepth == rightDepth);}
int CBTnodeNum(TreeNode* root) { if (!root) return 0; // 利用满二叉树的性质，先判断是不是满二叉树 int height; if (CBTisFull(root, height)) return (2<<height)-1; // 2左移n位相当于2^n return 1+CBTnodeNum(root->left)+CBTnodeNum(root->right);}
bool isFull(TreeNode* root) { // 判断一般二叉树是不是满 if (!root) return true; return maxDepth(root->left)==maxDepth(root->right) && isFull(root->left) && isFull(root->right);}
int main() { /* 构造如下二叉树 6 / \ 4 7 / \ / \ 1 3 5 8 */ TreeNode Node6(6); TreeNode Node4(4), Node7(7), Node1(1), Node3(3), Node5(5), Node8(8); Node4.left = &Node1; Node4.right = &Node3; Node7.left = &Node5; Node7.right = &Node8; Node6.left = &Node4; Node6.right = &Node7;
TreeNode *root = &Node6; vector<int> ans1; preorder(root, ans1); vector<vector<int>> ans2; levelorder(root, ans2); /* for (int i=0; i<ans2.size(); i++) { for (int j=0; j<ans2[i].size(); j++) { cout << ans2[i][j] << " "; } cout << endl; } */ cout << isSymmetic(root) << endl; int minNum=999; minVal(root, minNum); cout << minNum << endl; int maxNum=0; cout << maxVal2(root) << endl; cout << maxDepth(root) << endl; cout << minDepth(root) << endl; cout << nodeNum(root) << endl; cout << isFull(root) << endl; cout << CBTnodeNum(root) << endl; return 0;}二叉搜索树操作
#include <iostream>
using namespace std;
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr){}; TreeNode(int val) : val(val), left(nullptr), right(nullptr){}; TreeNode(int val, TreeNode* left, TreeNode* right) : val(val), left(left), right(right) {};};
TreeNode* insert(TreeNode* root, int val) { if(!root) { TreeNode* node = new TreeNode(val); return node; } if (val > root->val) { root->right = insert(root->right, val); } else if (val < root->val){ root->left = insert(root->left, val); } return root;}
void postorder(TreeNode* root) { if(!root) return; postorder(root->left); postorder(root->right); cout << root->val << endl;}
int main() { int val; TreeNode* root = nullptr; while(cin>>val) { root = insert(root, val); } postorder(root); return 0;}#include<iostream>
using namespace std;
struct BSTNODE { int data; BSTNODE* lchild; BSTNODE* rchild;};
BSTNODE* insert(int val, BSTNODE* root) { if (!root) { BSTNODE* node = new BSTNODE(); node->data = val; node->lchild = nullptr; node->rchild = nullptr; return node; } if (val > root->data) root->rchild = insert(val, root->rchild); else if (val < root->data) root->lchild = insert(val, root->lchild); return root;}
BSTNODE* buildTree(int *nodeArr, int arrSize){ BSTNODE* node = nullptr; for (int i=0; i<arrSize; i++) { insert(nodeArr[i], node); } return node;}
int getHeight(BSTNODE* root) { if (!root) return 0; int lHeight = getHeight(root->lchild); int rHeight = getHeight(root->rchild); if (lHeight == -1 || rHeight == -1) return -1;
return abs(lHeight-rHeight)>1 ? -1 : 1+max(lHeight,rHeight);}
bool isBalance(BSTNODE* root) { return (getHeight(root) != -1);}
int allDepth(BSTNODE* root, int depth = 1) { if (!root) return 0; return allDepth(root->lchild, depth+1) + allDepth(root->rchild, depth+1) + depth;}
int allNodeNum(BSTNODE* root) { if (!root) return 0; return allNodeNum(root->lchild) + allNodeNum(root->rchild) + 1;}
void printAVG(BSTNODE* root) { int dep = allDepth(root); int num = allNodeNum(root); printf("%0.2lf\n", dep*1.0/num);}Huffman 树
#include <iostream>#include <queue>
using namespace std;
struct Node { int data; Node* lchild; Node* rchild; Node(int val) : data(val), lchild(nullptr), rchild(nullptr){}; Node(int val, Node* lef, Node* rig) : data(val), lchild(lef), rchild(rig){};};
struct cmp { bool operator()(Node* a, Node* b) { return a->data > b->data; }};
Node* buildHuffman() { priority_queue<Node*, vector<Node*>, cmp> pq; int n; cin >> n; for (int i=0; i<n; i++) { int val; cin >> val; Node* curNode = new Node(val); pq.push(curNode); } Node* root = nullptr; while (1) { Node* Node1 = pq.top(); pq.pop(); if (pq.empty()) { root = Node1; break; } Node* Node2 = pq.top(); pq.pop(); Node* newNode = new Node(Node1->data+Node2->data, Node1, Node2); pq.push(newNode); } //cout << root->data << endl; return root;}
int cntWeight(Node* root, int height) { if (!root) return 0; if (!root->lchild && !root->rchild) return height * (root->data); return cntWeight(root->lchild, height+1)+cntWeight(root->rchild, height+1);}
int main() { Node* root = buildHuffman(); cout << cntWeight(root, 0); return 0;}数据结构03
#include <iostream>#include <vector>
using namespace std;
/* dfs 三部曲1. 确定递归函数&参数 vector<vector<int>> result //保存所有路径 vector<int> path //保存单一路径 void dfs(parameters);2. 确认终止条件 if(终止条件) { 存放结果; return; }3. 处理目前搜索节点出发的路径 for(选择本节点出发的其他节点) { 处理节点; dfs(图, 选择的节点); 回溯，撤销处理结果; }*/
vector<vector<int>> result;vector<int> path;void dfs(vector<vector<int>> graph, int x=0) { // graph 当前图； x 当前节点 if (x == graph.size()-1) { result.push_back(path); return; } for (int i=0; i<graph[x].size(); i++) { path.push_back(graph[x][i]); dfs(graph, graph[x][i]); path.pop_back(); }}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { path.push_back(0); dfs(graph); return result;}#include <iostream>#include <vector>#include <queue>
using namespace std;
int dir[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}}; // 表示四个方向
int cnt;
// grid 地图；visited 访问过节点标记；x,y 开始搜索节点的下标void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> que; que.push({x,y}); visited[x][y] = true; cnt++; while(!que.empty()) { int curx = que.front().first, cury = que.front().second; que.pop(); // 遍历四个方向 for(auto &ind: dir) { int nextx = curx + ind[0], nexty = cury + ind[1]; if (nextx<0 || nexty<0 || nextx>=grid.size() || nexty>=grid[0].size()) continue; if (!visited[nextx][nexty] && grid[nextx][nexty] == '*') { que.push({nextx, nexty}); visited[nextx][nexty] = true; cnt++; } } }}
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { if (visited[x][y] || grid[x][y] != '*') return; visited[x][y] = true; cnt++; for (auto &ind: dir) { int nextx = x + ind[0], nexty = y + ind[1]; if (nextx < 0 || nexty < 0 || nextx >=grid.size() || nexty >= grid[0].size()) continue; dfs(grid, visited, nextx, nexty); }}
int islandNum(vector<vector<char>>& grid) { int n=grid.size(), m=grid[0].size(); vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false)); int result = 0; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (!visited[i][j] && grid[i][j]=='*') { result++; //bfs(grid, visited, i, j); dfs(grid, visited, i, j); } } } return result;}
int maxIslandArea(vector<vector<char>>& grid) { int n=grid.size(), m=grid[0].size(); vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false)); int curmax = 0; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { cnt = 0; if (!visited[i][j] && grid[i][j]=='*') { //bfs(grid, visited, i, j); dfs(grid, visited, i, j); curmax = cnt > curmax ? cnt : curmax; } } } return curmax;}
int main() { int m, n; cin >> n >> m; vector<vector<char>> grid = vector<vector<char>>(m, vector<char>(n)); for (int i=0; i<m; i++) { for (int j=0; j<n; j++) { cin >> grid[i][j]; } } cout << maxIslandArea(grid) << endl; cout << islandNum(grid) << endl;}#include <iostream>
using namespace std;
#define MVNum 1000
struct AMGraph { int vexnum, arcnum; int arcs[MVNum][MVNum]; AMGraph() { cin >> vexnum >> arcnum; for (int i=1; i<=vexnum; i++) { for (int j=1; j<=vexnum; j++) { arcs[i][j] = 0; } } for (int i=0; i<arcnum; i++) { int nodex, nodey; cin >> nodex >> nodey; arcs[nodex][nodey] = 1; arcs[nodey][nodex] = 1; } } void printGraph() { for (int i=1; i<=vexnum; i++) { for (int j=1; j<=vexnum; j++) cout << arcs[i][j] << " "; cout << endl; } } bool allDegreeEven() { for (int i=1; i<=vexnum; i++) { int cnt = 0; for (int j=1; j<=vexnum; j++) { if (arcs[i][j] == 1) cnt++; } if (cnt%2 != 0) { return false; } } return true; } bool isConnectedGraph() { bool visited[MVNum] {false}; int cnt = 1; dfs(1, visited, cnt); //cout << "cnt" << cnt << endl; return cnt == vexnum; } void dfs(int curvex, bool visited[], int &cnt) { visited[curvex] = true; cnt++; for (int i=0; i<vexnum; i++) { if (arcs[curvex][i] == 1 && !(visited[i])) dfs(i, visited, cnt); } }};
int main() { AMGraph* G = new AMGraph(); //G->printGraph(); // 判断每个点的度数是不是偶数 //cout << G->allDegreeEven(); // 判断是不是连通图 //cout << G->isConnectedGraph(); cout << (G->allDegreeEven() && G->isConnectedGraph()); return 0;} 代码背后的逻辑森林：「数据结构」课程笔记·上机
https://leehenry.top/posts/debug_2_deploy/notesarchive/数据结构01/