目錄

• Stack
• 單調(diào)棧：
• 一個序列有多少出棧順序：
• Queue
• Map
• 鏈表
• 哈希表
• 并查集
• 樹狀數(shù)組
• 區(qū)間最大
• 線段樹
• 區(qū)間操作
• 二叉搜索樹
• 快排
• 平衡樹- treap
• 拓?fù)渑判?/li>
• 最短路
• • • • 1.floyed
      • 2.dijkstra
      • 3.bellman_ford
      • 4.SPFA
• 函數(shù)、公式

Stack

stack<int> s; s.push();//向棧頂添加元素 s.pop();//從棧頂移除一個元素 s.top();//返回棧頂元素 s.empty();//判斷堆棧是否為空 s.size();//返回棧的大小

單調(diào)棧：

#include<stack> #include<vector> ll n,h,ans,th,tw,w; int main() {while(scanf("%lld",&n)) {if(!n)break;stack<pair<ll,ll> >stk;ans=0;for(int i=0; i<n; i++) {scanf("%lld",&h);w=0;while(!stk.empty()&&stk.top().first>=h) {th=stk.top().first;tw=stk.top().second;stk.pop();w+=tw;ans=max(ans,th*w);}stk.push(make_pair(h,w+1));}w=0;while(!stk.empty()) {ans=max(ans,stk.top().first*(w+stk.top().second));w+=stk.top().second;stk.pop();}printf("%lld\n",ans);}return 0; }

一個序列有多少出棧順序：

#include<queue> #include<stack> using namespace std; const int N=1e5+10; int a[10],n; stack<int>s; queue<int>q; bool check(queue<int>q)///判斷是否滿足要求 {for(int i=1; i<=n; i++){s.push(a[i]);///棧不為空&&棧頂元素和隊列首元素相同while(!s.empty()&&q.front()==s.top()){s.pop();///出棧q.pop();///出隊列}}if(!s.empty())///判斷棧中是否還有元素return false;///有元素，說明不是出棧順序return true;///沒有，則說明是出棧順序 } int main() {int k=1;///記錄全排列的個數(shù)printf("請輸入入棧長度\n");scanf("%d",&n);printf("請輸入入棧順序\n");for(int i=1; i<=n; i++)scanf("%d",&a[i]);sort(a+1,a+n+1);///全排列排序do{printf("Case %d:",k++);///第k個全排列for(int i=1; i<=n; i++){printf("%d ",a[i]);q.push(a[i]);///全排列的一種入隊}printf("\n");if(check(q))///判斷入棧序列的全排列是否是出棧順序printf("是出棧順序\n");else printf("不是出棧順序\n");}while(next_permutation(a+1,a+n+1)); ///全排列函數(shù)調(diào)用return 0;}

Queue

///基本操作：push();pop();front(隊首);back(隊尾);empty();size(); ///priority_queue(優(yōu)先隊列) ///出隊時，并非按先進先出的原則，而是將當(dāng)前隊列中最大的元素出隊(默認(rèn)由大到小排序)。可以重載"<"操作，重新定義 //結(jié)構(gòu)體重載: struct node {string name;float score;bool operator < (const node &a) const {return a.score<score;} } int main() {priority_queue<node>pq;return 0; } ///非結(jié)構(gòu)體重載: struct myComp() {bool operator () (const int &a,const int &b) {///由小到大排列采用">";有小到大排列采用"<"return a>b;} } int main() {priority_queue<int,vector<int>,myComp>pq;return 0; }

• priority_queue

priority_queue< type, container, function > ///默認(rèn)是一個最大堆

type：數(shù)據(jù)類型；（不可省）
container：實現(xiàn)優(yōu)先隊列的底層容器；

function：元素之間的比較方式； //構(gòu)造一個空的優(yōu)先隊列（此優(yōu)先隊列默認(rèn)為大頂堆） priority_queue<int> big_heap; //另一種構(gòu)建大頂堆的方法 priority_queue<int,vector<int>,less<int> > big_heap2; //構(gòu)造一個空的優(yōu)先隊列,此優(yōu)先隊列是一個小頂堆 priority_queue<int,vector<int>,greater<int> > small_heap; priority<node>pq_node //node為結(jié)構(gòu)體，可以自定義優(yōu)先級 struct node{int x, y;friend bool operator < (node a, node b){return a.x > b.x; //結(jié)構(gòu)體中，x小的優(yōu)先級高} } #include <functional>

Map

每個關(guān)鍵字只能出現(xiàn)一次，根據(jù)key值快速查找記錄，查找的復(fù)雜度基本是Log(N)
插入元素：

map<int, string> mapStudent; // 定義一個map對象 //用insert函數(shù)插入pair mp.insert(pair<int, string>(000, "student_zero")); //用insert函數(shù)插入value_type數(shù)據(jù) mp.insert(map<int, string>::value_type(001, "student_one")); mp[123] = "student_first";//用"array"方式插入 mp[456] = "student_second";

插入是否成功：

// 構(gòu)造定義，返回一個pair對象 pair<iterator,bool> insert (const value_type& val); pair<map<int, string>::iterator, bool> Insert_Pair; Insert_Pair = mp.insert(map<int, string>::value_type (001, "student_one")); if(!Insert_Pair.second)cout << ""Error insert new element" << endl;

數(shù)據(jù)的遍歷：

map<int, string>::iterator it; for(it = mp.rbegin(); it != mp.rend();it++) cout<<it->first<<" "<<it->second<<endl; ///前向迭代器 map<int, string>::reverse_iterator it; for(it = mp.rbegin(); it != mp.rend();it++) cout<<it->first<<" "<<it->second<<endl; ///反相迭代器 for(int i = 1;i <= n;i++) ///注意從1開始cout<<mp[i]<<endl; ///數(shù)組的形式

查找并獲取map中的元素
count函數(shù)來判定關(guān)鍵字是否出現(xiàn)，其缺點是無法定位數(shù)據(jù)出現(xiàn)位置,
find函數(shù)來定位數(shù)據(jù)出現(xiàn)位置，它返回的一個迭代器，當(dāng)數(shù)據(jù)出現(xiàn)時，它返回數(shù)據(jù)所在位置的迭代器，如果map中沒有要查找的數(shù)據(jù)，它返回的迭代器等于end函數(shù)返回的迭代器。
刪除與清空：

//迭代器刪除 iter = mp.find("123"); mp.erase(iter); //用關(guān)鍵字刪除 int n = mp.erase("123"); //如果刪除了會返回1，否則返回0 //用迭代器范圍刪除 : 把整個map清空 mp.erase(mp.begin(), mp.end()); //等同于mp.clear()

map中的swap用法：
swap不是一個容器中的元素交換，而是兩個容器所有元素的交換。
函數(shù)：

函數(shù)作用

begin()	返回指向map頭部的迭代器
clear(）	刪除所有元素
count()	返回指定元素出現(xiàn)的次數(shù)
empty()	如果map為空則返回true
end()	返回指向map末尾的迭代器
rbegin()	返回一個指向map尾部的逆向迭代器
rend()	返回一個指向map頭部的逆向迭代器
size()	返回map中元素的個數(shù)
swap()	交換兩個map
upper_bound()	返回鍵值>給定元素的第一個位置

鏈表

///單鏈表中可以沒有頭結(jié)點，但是不能沒有頭指針！ ///結(jié)構(gòu)體實現(xiàn)自定義： typedef struct Link {int elem;struct Link *next; } link; link * initLink(); //鏈表插入的函數(shù)，p是鏈表，elem是插入的結(jié)點的數(shù)據(jù)域，add是插入的位置 link * insertElem(link * p,int elem,int add); //刪除結(jié)點的函數(shù)，p代表操作鏈表，add代表刪除節(jié)點的位置 link * delElem(link * p,int add); //查找結(jié)點的函數(shù)，elem為目標(biāo)結(jié)點的數(shù)據(jù)域的值 int selectElem(link * p,int elem); //更新結(jié)點的函數(shù)，newElem為新的數(shù)據(jù)域的值 link *amendElem(link * p,int add,int newElem); void display(link *p);int main() {//初始化鏈表（1，2，3，4）printf("初始化鏈表為：\n");link *p=initLink();display(p);printf("在第4的位置插入元素5：\n");p=insertElem(p, 5, 4);display(p);printf("刪除元素3:\n");p=delElem(p, 3);display(p);printf("查找元素2的位置為：\n");int address=selectElem(p, 2);if (address==-1) {printf("沒有該元素");} else {printf("元素2的位置為：%d\n",address);}printf("更改第3的位置的數(shù)據(jù)為7:\n");p=amendElem(p, 3, 7);display(p);return 0; } link * initLink() {link * p=(link*)malloc(sizeof(link));//創(chuàng)建一個頭結(jié)點link * temp=p;//聲明一個指針指向頭結(jié)點，用于遍歷鏈表//生成鏈表for (int i=1; i<5; i++) {link *a=(link*)malloc(sizeof(link));a->elem=i;a->next=NULL;temp->next=a;temp=temp->next;}return p; } link * insertElem(link * p,int elem,int add) {link * temp=p;//創(chuàng)建臨時結(jié)點temp//首先找到要插入位置的上一個結(jié)點for (int i=1; i<add; i++) {if (temp==NULL) {printf("插入位置無效\n");return p;}temp=temp->next;}//創(chuàng)建插入結(jié)點clink * c=(link*)malloc(sizeof(link));c->elem=elem;//向鏈表中插入結(jié)點c->next=temp->next;temp->next=c;return p; }link * delElem(link * p,int add) {link * temp=p;//遍歷到被刪除結(jié)點的上一個結(jié)點for (int i=1; i<add; i++) {temp=temp->next;}link * del=temp->next;//單獨設(shè)置一個指針指向被刪除結(jié)點，以防丟失temp->next=temp->next->next;//刪除某個結(jié)點的方法就是更改前一個結(jié)點的指針域free(del);//手動釋放該結(jié)點，防止內(nèi)存泄漏return p; } int selectElem(link * p,int elem) {link * t=p;int i=1;while (t->next) {t=t->next;if (t->elem==elem) {return i;}i++;}return -1; } link *amendElem(link * p,int add,int newElem) {link * temp=p;temp=temp->next;//tamp指向首元結(jié)點//temp指向被刪除結(jié)點for (int i=1; i<add; i++) {temp=temp->next;}temp->elem=newElem;return p; } void display(link *p) {link* temp=p;//將temp指針重新指向頭結(jié)點//只要temp指針指向的結(jié)點的next不是Null，就執(zhí)行輸出語句。while (temp->next) {temp=temp->next;printf("%d",temp->elem);}printf("\n"); }

哈希表

直接定址法
除留余數(shù)法（Hash表的最大長度為m，可以取不大于m的最大質(zhì)數(shù)p，然后對關(guān)鍵字進行取余運算）

并查集

const int N=2e5+10; int f[N],rankk[N]; int find(int x) {if(f[x]==-1)return x;rankk[x]+=rankk[(f[x])]; /// 由于每條邊帶權(quán),所以把邊權(quán)更新, /// 也就是更新間接連接的點；當(dāng)遞歸到某一層時 /// x還未連接到根節(jié)點上所以rank[x]表示的是x到f[x]的距離; /// 經(jīng)上一步操作,f[x]已經(jīng)接到根節(jié)點上了, /// 即rank[f[x]]表示的是父節(jié)點到根節(jié)點的距離所以x到根節(jié)點的距離就直接 /// 等于rank[x]+rank[f[x]];int t=find(f[x]);return f[x]=t; } int main() {int n,m;while(~scanf("%d %d",&n,&m)){memset(rankk,0,sizeof(rankk));memset(f,-1,sizeof(f));int ans=0;int a,b,sum;for(int i=0; i<m; i++){scanf("%d %d %d",&a,&b,&sum);a--;///區(qū)間(0,b)分為(0,a-1)和(a,b);int fx=find(a);int fy=find(b);if(fx!=fy){f[fy]=fx;rankk[fy]=rankk[a]-rankk[b]+sum;///rank[a]表示a到0的和,rank[b]表示a+1到b的和;///rank[fy]表示fx,fy的距離；}else if(rankk[b]-rankk[a]!=sum)ans++;}printf("%d\n",ans);}return 0; }

樹狀數(shù)組

int n; int bit_tree[n]; void add(int a,int b){for(int i=a;i<=n;i+=lowbit(i)){bit_tree[i]+=b;} }//這里每次修改的其實是一個后綴 void add_area(int l,int r,int v){add(l,v);add(r+1,-v);//差分后的修改方式，由于只會影響l~r,所以將r后的影響要消除 } int query_pos(int a){int ans=0;for(int i=a;i>0;i-=lowbit(i)){ans+=bit_tree[i];}return ans; }

區(qū)間最大

int max_area(int l,int r){int ans=0;while(l<=r){ans=max(ans,val[r]);r--;//每次往后跳一個for(;r-lowbit(r)>=l;r-=lowbit(r)) ans=max(ans,maxv[r]);//看r最多跳到哪里，而不超過l}return ans; } int change_pos(int p,int a){val[p]=a;for(int i=p;i<=n;i+=lowbit(i)){maxv[i]=val[i];//修改的時候重新計算值for(int j=1;j<lowbit(i);j<<=1) maxv[i]=max(maxv[i],maxv[i-j]);} } void init(int p){for(int i=p;i<=n;i+=lowbit(i)) maxv[i]=max(maxv[i],val[p]);//初始化一個位置的值可以這樣寫。 }

線段樹

char str[10]; long long int lazy[400040],sum[400040];///4倍的空間 void build(int l,int r,int o)///建樹 l，r 此節(jié)點區(qū)間長度 o下標(biāo) {if(l==r)///葉節(jié)點{scanf("%lld",&sum[o]);///直接賦值return;}int mid=(l+r)>>1;build(l,mid,o<<1);///左build(mid+1,r,o<<1|1);///右sum[o]=sum[o<<1]+sum[o<<1|1];///更新此節(jié)點的和 } void pushdown(int o,int l)///o下標(biāo) l此節(jié)點的區(qū)間長度 {if(lazy[o])///如果此時需要更新操作{lazy[o<<1]+=lazy[o];///左lazy[o<<1|1]+=lazy[o];///右sum[o<<1]+=lazy[o]*(l-(l>>1));///更新此時 左 的和sum[o<<1|1]+=lazy[o]*(l>>1);///更新此時 右 的和lazy[o]=0;///此點位置懶惰標(biāo)記取消 傳到下面兩個節(jié)點} } void update(int x,int y,int l,int r,int o,int c)///update(l,r,1,n,1,c); {///x，y操作區(qū)間 l，r樹的范圍 o下標(biāo) c具體操作（+c）if(x<=l&&y>=r)///操作區(qū)間全在樹的范圍內(nèi){sum[o]+=(r-l+1)*c;///對此時sum[o]進行更新操作lazy[o]+=c;///并懶惰標(biāo)記return ;}pushdown(o,r-l+1);///不符合 就push懶惰標(biāo)記int mid=(l+r)>>1;if(x<=mid)update(x,y,l,mid,o<<1,c);///更新左if(y>mid)update(x,y,mid+1,r,o<<1|1,c);///更新右sum[o]=sum[o<<1]+sum[o<<1|1];///更新此節(jié)點的和 } long long int query(int x,int y,int l,int r,int o) {///x，y操作區(qū)間 l，r樹的范圍 o下標(biāo)if(x<=l&&y>=r)///全包含 就輸出此時區(qū)間的和return sum[o];pushdown(o,r-l+1);///懶惰標(biāo)記函數(shù)int mid=(r+l)>>1;long long sum=0;///long long型if(x<=mid)sum+=query(x,y,l,mid,o<<1);///說明 樹的左邊與操作區(qū)間有交集if(y>mid)sum+=query(x,y,mid+1,r,o<<1|1);///o<<1|1 位運算比+-快return sum; } int main() {int n,m;while(~scanf("%d %d",&n,&m)){memset(lazy,0,sizeof(lazy));memset(sum,0,sizeof(sum));build(1,n,1);///建樹while(m--){int l,r,c;scanf("%s",&str);///字符串避免回車符if(str[0]=='Q'){scanf("%d %d",&l,&r);printf("%lld\n",query(l,r,1,n,1));///查詢函數(shù)}else{scanf("%d %d %d",&l,&r,&c);update(l,r,1,n,1,c);///操作更新函數(shù)}}}return 0; }

區(qū)間操作

題意：給定n個線段，線段可以相交，第i個線段覆蓋的區(qū)間為[li,ri]，問最少刪除多少個線段讓覆蓋每個點的線段數(shù)量小于等于k。

#include<vector> #include<set> typedef long long ll; const int N=2e5+10; using namespace std; struct node {int y;int id; }; bool operator<(node a,node b) {if(a.y!=b.y)return a.y<b.y;return a.id<b.id; } vector<node>g[N]; vector<int>a; node q; int main() {int x,y,n,k;scanf("%d %d",&n,&k);for(int i=1;i<=n;i++){scanf("%d %d",&x,&y);q.y=y;q.id=i;g[x].push_back(q);}set<node>s;for(int i=1;i<N;i++){while(s.size()&&(*s.begin()).y<i)s.erase(*s.begin());for(int j=0;j<g[i].size();j++)s.insert(g[i][j]);while(s.size()>k){a.push_back((*s.rbegin()).id);s.erase(*s.rbegin());}}printf("%d\n",a.size());int l=a.size();for(int i=0;i<l;i++)printf("%d%c",a[i],i==l-1?'\n':' ');return 0; }

二叉搜索樹

給定一棵二叉樹的中序遍歷和前序遍歷，請你先將樹做個鏡面反轉(zhuǎn)，再輸出反轉(zhuǎn)后的層序遍歷的序列。

#include<bits/stdc++.h> using namespace std; #define N 50 #include<queue> queue<int>qu; int f[N],m[N]; struct node {int l,r; } q[N]; int root; int build(int la,int ra,int lb,int rb) { //mid firstif(la>ra)return 0;int i=0;int rt=f[lb];///find rootwhile(m[i]!=rt)i++;q[rt].l=build(la,i-1,lb+1,lb+i-la);///leftq[rt].r=build(i+1,ra,lb+i-la+1,rb);///rightreturn rt; } void dfs(int root) {if(q[root].l==q[root].r&&q[root].l==0)return ;else {swap(q[root].l,q[root].r);///swapdfs(q[root].l);dfs(q[root].r);} } void bfs(int root) {int flag=0;qu.push(root);while(!qu.empty()) {int x=qu.front();qu.pop();if(!flag)flag=1,cout<<x;else cout<<" "<<x;if(q[x].l!=0)///exist->input queuequ.push(q[x].l);if(q[x].r!=0)qu.push(q[x].r);}cout<<endl; } int main() {int n;cin>>n;for(int i=1; i<=n; i++) {cin>>m[i];}for(int i=1; i<=n; i++) {cin>>f[i];}root=build(1,n,1,n);dfs(root);///swapbfs(root);///inputreturn 0; }

題意：先給一組數(shù)據(jù)構(gòu)建一顆二叉搜索樹作為標(biāo)準(zhǔn)樹。然后n組數(shù)據(jù)，判斷每組數(shù)據(jù)構(gòu)成的二叉搜索樹是否和標(biāo)準(zhǔn)樹一樣。
思路：兩棵樹如果一樣的話，就是擁有一樣的節(jié)點，在每個節(jié)點上具有相同的值。
因此在遍歷二叉樹的時候，每向下移動一個節(jié)點時，判斷是否與此時的標(biāo)準(zhǔn)樹一致。

#include<stdio.h> #include<string.h> bool flag; struct node {int val;node *l,*r; }; node *insert(node *p,int x) { ///依次插入每個值if(p==NULL) { ///節(jié)點為空，插入node *q=new node;///申請一個動態(tài)空間 new nodeq->val=x;///賦值q->l=q->r=NULL;///左右為空return q;///返回此節(jié)點地址} else { ///節(jié)點不為空 此節(jié)點有值if(p->val>x)///當(dāng)前值小于節(jié)點值p->l=insert(p->l,x);///遞歸向下尋找對應(yīng)位置 回溯賦值elsep->r=insert(p->r,x);return p;} } void check(node *root,node *room) { ///中序遍歷 傳入標(biāo)準(zhǔn)樹和判斷樹的地址if(root!=NULL&&room!=NULL) { ///都不為空 判斷值是否相同check(root->l,room->l);///中序遍歷if(root->val!=room->val)///不一致 標(biāo)記為0；flag=0;check(root->r,room->r);} else if(root!=NULL||room!=NULL) ///一個為空另一個不為空有節(jié)點值 顯然不一致flag=0; } int main() {int n;while(~scanf("%d",&n)&&n) {node *root=NULL;///標(biāo)準(zhǔn)樹 為空char str[20];scanf("%s",str);for(int i=0; i<strlen(str); i++)///構(gòu)建 標(biāo)準(zhǔn)樹root=insert(root,str[i]-'0');for(int i=0; i<n; i++) {flag=1;///標(biāo)記node *room=NULL;///判斷樹 為空scanf("%s",str);for(int j=0; j<strlen(str); j++)///構(gòu)建 判斷樹room=insert(room,str[j]-'0');check(root,room);///中序（左根右）遍歷 判斷兩棵樹是否一致if(flag)printf("YES\n");else printf("NO\n");}}return 0; }

快排

void ksort(int l, int h, int a[]) {if (h < l + 2) {return ;}int e = h, p = l;while (l < h) {while (++l < e && a[l] <= a[p]);while (--h > p && a[h] >= a[p]);if (l < h) {swap(a[l], a[h]);}}swap(a[h], a[p]);ksort(p, h, a);ksort(l, e, a);return ; }

平衡樹- treap

operator 1 : 插入一個數(shù) operator 2 : 刪除一個數(shù) operator 3 : 通過數(shù)值找排名 operator 4 : 通過排名找數(shù)值 operator 5 : 找到嚴(yán)格小于key的最大數(shù)（前驅(qū)） operator 6 : 找到嚴(yán)格大于key的最小數(shù)（后繼）const int N = 100010, INF = 1e8 + 7; int n, m; struct node {int l, r;//左右兒子int key;//真正的權(quán)值int val;//隨機的平衡因子int cnt;//相同的數(shù)有多少個int size;//整棵樹的結(jié)點個數(shù) } tr[N];int root, idx; void pushup(int p) {tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt; }int get_node(int key) {tr[ ++ idx].key = key;tr[idx].val = rand();//!堆所維護的val是隨機值,為了讓樹變得更隨機以增加搜索樹效率tr[idx].cnt = tr[idx].size = 1;return idx; }/*!往左遞歸時左兒子val大于根節(jié)點val就右旋*/ /*!往右遞歸時右兒子val大于根節(jié)點val就左旋*/void zig(int &p) { //右旋int q = tr[p].l;tr[p].l = tr[q].r;tr[q].r = p, p = q;pushup(tr[p].r), pushup(p); }void zag(int &p) { //左旋int q = tr[p].r;tr[p].r = tr[q].l;tr[q].l = p, p = q;pushup(tr[p].l), pushup(p); }void build() {get_node(-INF), get_node(INF);//兩個哨兵邊界root = 1;//-INFtr[root].r = 2;//INFpushup(root);if(tr[1].val < tr[2].val)zag(root);//因為val是隨機的，所以要判斷右兒子（因為當(dāng)前只有兩個點，只有root右兒子）//如果右兒子隨機到的val大于root就左旋 }/*operator 1 : 插入一個數(shù)*/void insert(int &p, int key) {if(!p) p = get_node(key);//如果樹中沒有這個就新建一個結(jié)點else if(tr[p].key == key) tr[p].cnt ++ ;else if(tr[p].key > key) { //大就在左邊insert(tr[p].l, key);if(tr[tr[p].l].val > tr[p].val)zig(p);} else { // 否則就在右邊insert(tr[p].r, key);if(tr[tr[p].r].val > tr[p].val)zag(p);}pushup(p); }/*operator 2 : 刪除一個數(shù)*/void remove(int &p, int key) { //刪除操作：每次旋轉(zhuǎn)都會使得它的深度+1,一直旋轉(zhuǎn)到葉子節(jié)點,然后刪除if(!p) return ;if(tr[p].key == key) { //找到了if(tr[p].cnt > 1) tr[p].cnt -- ;else if(tr[p].l || tr[p].r) {//!右旋往右走if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {//如果沒有右子樹，右旋一次就到葉子節(jié)點了。或者說左子樹隨機到的val > 右子樹隨機到的val，那么必須右旋zig(p);remove(tr[p].r, key);}//!左旋往左走else {zag(p);remove(tr[p].l, key);}} else p = 0; //如果到了葉子節(jié)點就直接刪掉} else if(tr[p].key > key) remove(tr[p].l, key); //往左邊找else remove(tr[p].r, key);//往右邊找pushup(p);//每次別忘了pushup，因為本題中維護了一個size }//下面的幾個函數(shù)只是查詢不需要修改，所以不用寫&p/*operator 3 : 通過數(shù)值找排名 */int get_rank_by_key(int p, int key) {if(!p) return 0;//如果找到了，返回左子樹個數(shù) + 自己(這里不是cnt因為根據(jù)題意，要找的排名如果相同就找最左邊的,最小的)if(tr[p].key == key) return tr[tr[p].l].size + 1;if(tr[p].key > key)return get_rank_by_key(tr[p].l, key);return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key); }/*operator 4 : 通過排名找數(shù)值 */int get_key_by_rank(int p, int rank) {if(!p) return INF;if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);if(tr[tr[p].l].size + tr[p].cnt >= rank)//左邊少加上中間的卻大于rank，說明就在中間return tr[p].key;return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);//注意遞歸到右邊時rank要減去左邊的 }/*operator 5 : 找到嚴(yán)格小于key的最大數(shù) */int get_prev(int p, int key) {if(!p) return -INF;//!左邊if(tr[p].key >= key) return get_prev(tr[p].l, key);//右邊和中間return max(tr[p].key, get_prev(tr[p].r, key)); }/*operator 6 : 找到嚴(yán)格大于key的最小數(shù) */int get_next(int p, int key) {if(!p) return INF;//!右邊if(tr[p].key <= key) return get_next(tr[p].r, key);//左邊和中間return min(tr[p].key, get_next(tr[p].l, key)); }int main() {build();scanf("%d", &n);while(n -- ) {int op, x;scanf("%d%d", &op, &x);if(op == 1)insert(root, x);else if(op == 2)remove(root, x);else if(op == 3)printf("%d\n", get_rank_by_key(root, x) - 1);//因為最前面有一個自己設(shè)的哨兵，所以得到的rank比真實的rank大1else if(op == 4)printf("%d\n", get_key_by_rank(root, x + 1));//根據(jù)rank找key,前面有一個哨兵,所以rank要從真實的rank+1變成樹里的rankelse if(op == 5)printf("%d\n", get_prev(root, x));else printf("%d\n", get_next(root, x));}return 0; }

拓?fù)渑判?/h1> ///優(yōu)先隊列加拓?fù)渑判? 入度為零即輸出！ int ans[550],ru[550]; int dp[550][550]; int n,m; void toposort() {for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(dp[i][j])ru[j]++;}}for(int i=1; i<=n; i++) {int k=1;while(ru[k]!=0)k++;ans[i]=k;ru[k]=-1;for(int j=1; j<=n; j++) {if(dp[k][j])ru[j]--;}} }

最短路

1.floyed

void floyed() {for (int k=1;k<=n;k++;)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j]; }

2.dijkstra

其實是貪心，不能有負(fù)環(huán)，如果源點到某個點的距離是到其他點的距離的最小值，能么就更新。

void dijkstra(int st) {for (int i=1;i<=n;i++)dis[i]=a[st][i];memset(vis,0,sizeof(vis));vis[st]=1;dis[st]=0;for (int i=1;i<n;i++){int minn=99999999;int k=0;for (int j=1;j<=n;j++)if (!vis[j]&&dis[j]<minn){minn=dis[j];k=j;}if (!k)return ;vis[k]=1;for (int j=1;j<n;j++)if (!vis[j]&&dis[k]+a[c][j]<dis[j])dis[j]=dis[k]+a[k][i];} }

3.bellman_ford

求單源點到其他點的最短距離，并判斷是否有負(fù)環(huán)。 bool bellman_ford() {memset(dis,0,sizeof(dis));dis[st]=0;bool rel=0;for (int i=1;i<=n;i++){rel=0;for (int j=1;j<=sumn;j++)if (dis[a[j].x]+a[j].v<dis[aij].v){dis[a[i].y]=a[j].v+dis[a[j].x];rel=1;}if (!rel)return 0;}return 1; }

4.SPFA

使用鄰接表，優(yōu)化bellman_ford，節(jié)約時間和空間。 void SPFA() {memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;vis[s]=1;que[1]=s;head=0;tail=1;while (head<tail){int tn=q[++head];vis[tn]=0;int te=link[tn];for (int i=te;i;i=e[i].next){int tmp=e[i].y;if (dis[tn]+e[i].v<dis[tmp]){dis[tmp]=dis[tn]+e[i].v;if (!vis[tmp]){q[++tail]=tmp;vis[tmp]=1;}}}}return ; }

函數(shù)、公式

lower_bound( ) 函數(shù)返回大于等于x upper_bound( )函數(shù)返回大于x

總結(jié)

以上是生活随笔為你收集整理的数据结构专题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。