数据结构复习（三）
树的定义与性质定义高度/深度
满二叉树
完全二叉树
性质
在n个节点构成的二叉树中，叶结点的个数等于度为二节点的个数+1
对于完全二叉树
对于一颗具有n个节点的完全二叉树，其非叶节点个数为n/2（向下取整），叶结点个数为n/2（向上取整）
n个结点的完全二叉树的高度为logn（向下取整）
数据结构复习（二）
KMP算法1234567891011121314151617181920212223242526void buildnext(string b,int next[]){ int m = b.size(); int k= next[0] = -1; for (int j = 0; j + 1 < m; j++)//已知next[j],求next[j+1] { while (k != -1 && b[k] != b[j]) k = next[k]; next[j + 1] = ++k; }}int KMP(string a, string b){ int n = a.size(); int m = b.size(); int next[N]; buildnext(b, next); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || a[i] == b[j])//无相等前后缀或相等，i++,j++ i++ ...
数据结构复习（一）
栈与队列及其应用
栈的实现
1234567891011const int N = 1e6 + 10;class stack{public: int top = -1; int a[N]; bool empty() { return top == -1; } void push(int x) { a[++top] = x; } int pop() { return a[top--]; } int peak() { return a[top]; }};
常见应用
进制转换(10换16)123456789101112131415161718192021222324252627#include <iostream>using namespace std;const int N = 1e6 + 10;class stack{public: int top = -1; char a[N]; bool empty() { return top == -1; } ...
三、算法基础（三）
前缀和一维
12345678910111213141516171819#include <iostream>using namespace std;const int N=1e5+10;int main(){ int n,m; cin>>n>>m; int a[N],s[N]; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; for(int i=0;i<m;i++) { int l,r; cin>>l>>r; printf("%d\n",s[r]-s[l-1]); }}
二维
12345678910111213141516171819202122232425262728293031#include <iostream>using namesp ...
二、算法基础（二）
高精度
加法（两大数相加）
减法（两大数相减）
乘法（大数×小数）
除法
##加法
123456789101112131415161718192021222324252627282930313233#include <iostream>#include <vector>using namespace std;const int N=1e5+10;vector<int>ADD(vector<int>&A,vector<int>&B){ vector<int>C; int t=0; for(int i=0;i < A.size()||i < B.size();i++) { if(i < A.size()) t+=A[i]; if(i < B.size()) t+=B[i]; C.push_back(t%10); t/=10; } if(t) C.p ...
一、算法基础（一）
排序与二分排序
快速排序
归并排序
1.快速排序
12345678910111213void quick_sort(int q[], int l, int r){ if (l >= r) return; int x=q[l+r >>1];//确定分界点，这里q[]未必要找中点 int i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r);}
2.归并排序
12345678910111213141516171819202122void merge_sort(int a[],int l,int r){ if(l>=r) retu ...