c語言紅黑樹
㈠ 誰有數據結構與演算法分析:C語言描述高清版或者課後習題的答案
書特點如下：
●專用一章來討論演算法設計技巧，包括貪婪演算法、分治演算法、動態規劃、隨機化演算法以及回溯演算法
●介紹了當前流行的論題和新的數據結構，如斐波那契堆、斜堆、二項隊列、跳躍表和伸展樹
●安排一章專門討論攤還分析，考查書中介紹的一些高級數據結構
●新開辟一章討論高級數據結構以及它們的實現，其中包括紅黑樹、自頂向下伸展樹。treap樹、k-d樹、配對堆以及其他相關內容
●合並了堆排序平均情況分析的一些新結果
目錄
出版者的話
專家指導委員會
譯者序
前言
第1章 引論
第2章 演算法分析
第3章 表、棧和隊列
第4章 樹
第5章 散列
第6章 優先隊列（堆）
第7章 排序
第8章 不相交集ADT
第9章 圖論演算法
第10章 演算法設計技巧
第11章 攤還分析
第12章 高級數據結構及其實現索引。
㈡ 兩道編程演算法題（兩圖一道），題目如下，可以給出演算法思路或者源代碼，源代碼最好是C語言的
就會個第一題(因為第一題上已經給出了大致思路)
思路:用map容器(它的內部數據結構是一顆紅黑樹，查找和插入數據速度非常快)
map<int,st>a;//key(int)：設置為1~n的數;value(st):設置為key的前驅和後繼；
這樣一來就可以像鏈錶快速插入數據，又可以像數組隨機訪問元素(key,就相當於數組的下標)
下面是代碼和運行截圖；
看代碼前建議先了解一下map容器的具體用法;
#include<iostream>
#include<map>
#include<vector>
using namespace std;
struct st{//兩個成員變數用來儲存前驅和後繼
int left;//0
int right;//1
st()
{
left=0;
right=0;
}
};
void input(map<int,st> &a)//輸出
{
st t;
int s=0;
map<int,st>::iterator it;//迭代器(指針)
for(it=a.begin();it!=a.end();it++)//循環迭代
{
t=it->second;
if(t.left==0)//左邊等於0,說明該數是第一個數
{
s=it->first;//記錄key
break;
}
}
t=a[s];
cout<<s<<" ";
while(t.right!=0)//循環找當前數的右邊的數(右邊的為0，就說明該數是最後一個數)
{
cout<<t.right<<" ";
t=a[t.right];
}
}
int main()
{
st t,t_i,t_x,t_k,s;
map<int,st>a;
map<int,st>::iterator it;
int n,x,p,x_l,x_r;
cin>>n;
for(int i=1;i<=n;i++)//map容器賦初值(i,t)
//i:(key)下標;t:(value)結構體變數
{
a.insert(make_pair(i,t));
}
for(int i=2;i<=n;i++)
{
cin>>x>>p;
if(p==0)//x的左邊插入i
{
t=a[x];
if(t.left==0)//x的左邊沒有數
{
t_x.left=i;
t_i.right=x;
a[x]=t_x;
a[i]=t_i;
}
else//x的左邊有數
{
int x_left;
t_x=a[x];
x_left=t_x.left;
t_k=a[x_left];
t_i.right=x;
t_i.left=t_x.left;
t_k.right=i;
t_x.left=i;
a[x]=t_x;
a[i]=t_i;
a[x_left]=t_k;
}
}
else//x的右邊插入i
{
t=a[x];
if(t.right==0)//x的右邊沒有數
{
t_x.right=i;
t_i.left=x;
a[x]=t_x;
a[i]=t_i;
}
else//x的左邊有數
{
int x_right;
t_x=a[x];
x_right=t_x.right;
t_k=a[x_right];
t_i.left=x;
t_i.right=t_x.right;
t_k.left=i;
t_x.right=i;
a[x]=t_x;
a[i]=t_i;
a[x_right]=t_k;
}
}
}
for(it=a.begin();it!=a.end();it++)//循環迭代列印各個數之間的關系
{
cout<<it->first<<" ";
cout<<"左邊:";
cout<<it->second.left<<" ";
cout<<"右邊:";
cout<<it->second.right<<endl;
}
input(a);//列印序列
return 0;
}
/*
4
1 0
2 1
1 0
2 3 4 1
*/
