贴几个基础的算法(页 1) - 『专业学术』 - 观海听涛BBS - 哈尔滨工业大学(威海)

zhponly 发表于 2008-4-28 22:03

贴几个基础的算法

[code]
----------------------------------------------------------------------------main.c
#include"fish.h"
int i;
int *p;
int main(void)
{
//呃,这几个排序函数,
//和红黑树的插入和删除实现...11#...
//如果参数为两个,则第一个是指向数组的指针,第二个为数组大小.
//如果是三个参数,第二个为起始位置,第三个为末位,均为实际存在的位置.
//如果要验证某个函数只要写出函数名,参数为array,大小为20.
//比如quicksort(array,0,19);
//getch();
//return 0;
}
----------------------------------------------------------------------------main.c

----------------------------------------------------------------------------fish.h
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include"AB.h"
#include"AS.h"
#include"HB.h"
----------------------------------------------------------------------------fish.h

----------------------------------------------------------------------------AB.h
extern int array[];
----------------------------------------------------------------------------AB.h

----------------------------------------------------------------------------AB.c
#include"AB.h"
int array[20]={45,34,54,2,9,76,12,22,13,37,35,71,20,67,19,41,90,52,31,29};
----------------------------------------------------------------------------AB.c

----------------------------------------------------------------------------HB.h
void maxheap(int*,int);
void maxer(int*,int,int);
void heapsort(int*,int);
void xchg(int*,int);
----------------------------------------------------------------------------HB.h

----------------------------------------------------------------------------HB.c
/*heapsort.c
*功能:堆排序
*作者:漏网之鱼,参考:<算法导论>
*日期:20080425
*参数:第一个参数为一个int型指针,第二个为数组大小
*函数结束后为已排序的数组,无返回
*/
void maxer(int *a,int i,int m)
{
int largest;
int tmp;
if(i*2+1<m)
{
if(a[i*2+1]>a)
   largest=i*2+1;
else
   largest=i;
if(i*2+2<m)
   {
   if(a[i*2+2]>a[largest])
      largest=i*2+2;
   }
tmp=a;
a=a[largest];
a[largest]=tmp;
if(largest!=i)
   maxer(a,largest,m);
}
}
void maxheap(int *a,int n)
{
int m=n/2-1;
int i;
for(i=m;i>=0;i--)
   maxer(a,i,n);
}
void xchg(int *b,int p)
{
int tmp;
tmp=b[p-1];
b[p-1]=b[0];
b[0]=tmp;
}
void heapsort(int *a,int n)
{
int i;
for(i=n;i>=1;i--)
  {
maxheap(a,i);
xchg(a,i);
  }
}
------------------------------------------------------------------------------HB.c

----------------------------------------------------------------------------AS.h
void quicksort(int *,int,int);
void insertsort(int *,int);
void mergesort(int *,int,int);
----------------------------------------------------------------------------AS.h

----------------------------------------------------------------------------AS.c
/*
*quicksort.c
*功能:快速排序的一个朴素版本.
*作者:漏网之鱼,参考:<算法导论>
*日期:20080417
*参数:第一个参数为一个int型指针,第二个为起使位置
*第三个为末位置
*函数结束后为已排序的数组
*/
#include"AS.h"
int partition(int *,int,int);
void merge(int*,int,int,int);
void copy(int*,int,int*,int);
void quicksort(int *array,int p,int r)
{
int q;
if(p<r)
{
q=partition(array,p,r);
quicksort(array,p,q-1);
quicksort(array,q+1,r);
}
}
int partition(int *array,int p,int r)
{
int x=array[r];
int j;
int i=p-1;
int tmp;
for(j=p;j<=r-1;j++)
   {
   if(array[j]<=x)
      {
      i++;
      tmp=array;
      array=array[j];
      array[j]=tmp;
      }
   }
  tmp=array[i+1];
  array[i+1]=array[r];
  array[r]=tmp;
  return i+1;
}
/*insertsort.c
*插入排序
*作者:漏网之鱼,参考:<算法导论>
*日期:20080422
*参数:第一个参数为一个int型指针,第二个为数组大小
*函数结束后为已排序的数组,无返回
*/
void insertsort(int *array,int b)
{
int j,i;
int key;
for(j=1;j<b;j++)
   {
   key=array[j];
   i=j-1;
   while((i>=0)&&(array>key))
         {
         array[i+1]=array;
         i--;
         }
   array[i+1]=key;
   }
}
/*mergesort.c
*合并排序
*作者:漏网之鱼,参考:<算法导论>
*日期:20080423
*参数:第一个参数为一个int型指针,第二个为数组的起始位置
*第三个为数组的末位置
*函数结束后为已排序的数组,无返回
*/
void mergesort(int *array,int p,int r)
{
int q=(p+r)/2;
if(p<r)
{
mergesort(array,p,q);
mergesort(array,q+1,r);
merge(array,p,q,r);
}
}
void merge(int *a,int m,int n,int l)
{
int i;
int x=n-m+1;
int y=l-n;
int *pl;
int *pr;
pl=malloc(sizeof(int)*x);
pr=malloc(sizeof(int)*y);
for(i=0;i<x;i++)
   *(pl+i)=a[m+i];
for(i=0;i<y;i++)
   *(pr+i)=a[n+1+i];
while(x+y)
   {
      if(pl[x-1]>pr[y-1])
         {
         a[l]=pl[x-1];
         x--;
         l--;
         if(!x)
            {
            copy(pr,y,a,l);
            break;
            }
         }
      else
         {
         a[l]=pr[y-1];
         y--;
         l--;
         if(!y)
            {
            copy(pl,x,a,l);
            break;
            }
         }
   }
   free(pl);
   free(pr);
}
void copy(int *s,int num,int *d,int ha)
{
while(num--)
   {
   d[ha]=s[num];
   ha--;
   }
}
----------------------------------------------------------------------------AS.c
[/code]

[[i] 本帖最后由 zhponly 于 2008-5-1 11:36 编辑 [/i]]

yiyanwan77 发表于 2008-4-29 12:00

观海需要这样的好贴！

文愚无缘 发表于 2008-4-29 12:18

标准模板库有这些东东了吧。

kioecn 发表于 2008-4-29 12:58

有时间把《数据结构》上面的算法上传下，一个一个都试过了，

kioecn 发表于 2008-4-29 13:03

回复 1# zhponly 的帖子

那本《算法导论》是英文版的吧?老厚了，摸到了都怕，别说看了

建议楼主加点注释吧，更清晰易懂

zhponly 发表于 2008-4-29 13:53

[quote]原帖由 [i]文愚无缘[/i] 于 2008-4-29 12:18 发表 [url=http://bbs.ghtt.net/redirect.php?goto=findpost&pid=1230724&ptid=104484][img]http://bbs.ghtt.net/images/common/back.gif[/img][/url]
标准模板库有这些东东了吧。 [/quote]
还是不一样吧,标准库有不代表我会呀.......

zhponly 发表于 2008-4-29 13:54

[quote]原帖由 [i]kioecn[/i] 于 2008-4-29 12:58 发表 [url=http://bbs.ghtt.net/redirect.php?goto=findpost&pid=1230921&ptid=104484][img]http://bbs.ghtt.net/images/common/back.gif[/img][/url]
有时间把《数据结构》上面的算法上传下，一个一个都试过了， [/quote]
好啊..呵......等着捏.....[em19]

zhponly 发表于 2008-4-29 13:57

[quote]原帖由 [i]kioecn[/i] 于 2008-4-29 13:03 发表 [url=http://bbs.ghtt.net/redirect.php?goto=findpost&pid=1230942&ptid=104484][img]http://bbs.ghtt.net/images/common/back.gif[/img][/url]
那本《算法导论》是英文版的吧?老厚了，摸到了都怕，别说看了

建议楼主加点注释吧，更清晰易懂 [/quote]
呵...不是的,英语不太好,看不太懂那个,我借山大的中文版的.其实中文版译得不太好,我看红黑树那章时花了不少时候,现在才写出来插入算法,删除的还没实现........
注释........感觉后面的挺复杂的,这几个只是基本的排序算法....思路十分清晰.....不用注释吧......

蓝月鸟 发表于 2008-4-29 14:24

俺是买酱油滴
[em33]

[table][tr]
[td][size=2]老掉牙[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/HanoiTower.htm][u][size=2][color=#0000ff]河内塔 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/FibonacciNumber.htm][u][size=2][color=#0000ff]费式数列 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/PascalTriangle.htm][u][size=2][color=#0000ff]巴斯卡三角形 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/ThreeColorsFlags.htm][u][size=2][color=#0000ff]三色棋 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MouseGoMaze.htm][u][size=2][color=#0000ff]老鼠走迷官（一） [/color][/size][/u][/url][/list][list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MouseGoMaze2.htm][u][size=2][color=#0000ff]老鼠走迷官（二） [/color][/size][/u][/url][/list][list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/KnightTour.htm][u][size=2][color=#0000ff]骑士走棋盘 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/EightQueen.htm][u][size=2][color=#0000ff]八个皇后 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/EightCoins.htm][u][size=2][color=#0000ff]八枚银币 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/LifeGame.htm][u][size=2][color=#0000ff]生命游戏 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MatchString.htm][u][size=2][color=#0000ff]字串核对 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MultiColorHanoiTower.htm][u][size=2][color=#0000ff]双色、三色河内塔[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/KnapsackProblem.htm][u][size=2][color=#0000ff]背包问题（Knapsack Problem）[/color][/size][/u][/url][/list]
[size=2]数、运算[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MathPI.htm][u][size=2][color=#0000ff]蒙地卡罗法求 PI[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/EratosthenesPrime.htm][u][size=2][color=#0000ff]Eratosthenes 筛选求质数[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/BigNumber.htm][u][size=2][color=#0000ff]超长整数运算（大数运算） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/LongPI.htm][u][size=2][color=#0000ff]长 PI[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/GCDPNumber.htm][u][size=2][color=#0000ff]最大公因数、最小公倍数、因式分解[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/PerfectNumber.htm][u][size=2][color=#0000ff]完美数 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/ArmstrongNumber.htm][u][size=2][color=#0000ff]阿姆斯壮数 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MaxGuest.htm][u][size=2][color=#0000ff]最大访客数 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/InFixPostfix.htm][u][size=2][color=#0000ff]中序式转后序式（前序式）[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/PostfixCal.htm][u][size=2][color=#0000ff]后序式的运算 [/color][/size][/u][/url][/list]
[size=2]关于赌博[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/ShuffleCard.htm][u][size=2][color=#0000ff]洗扑克牌（乱数排列） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/CrapsGame.htm][u][size=2][color=#0000ff]Craps 赌博游戏 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/JosephusProblem.htm][u][size=2][color=#0000ff]约瑟夫问题（Josephus Problem）[/color][/size][/u][/url][/list]
[size=2]集合问题[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/Permutation.htm][u][size=2][color=#0000ff]排列组合 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/GrayCode.htm][u][size=2][color=#0000ff]格雷码（Gray Code） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/PossibleSet.htm][u][size=2][color=#0000ff]产生可能的集合 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/NOfM.htm][u][size=2][color=#0000ff]m元素集合的n个元素子集 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/SeparateNumber.htm][u][size=2][color=#0000ff]数字拆解 [/color][/size][/u][/url][/list][/td][td][size=2]排序[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/ScoreRank.htm][u][size=2][color=#0000ff]得分排行 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/SelectionInsertionBubble.htm][u][size=2][color=#0000ff]选择、插入、气泡排序[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/ShellSort.htm][u][size=2][color=#0000ff]Shell 排序法 - 改良的插入排序[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/ShakerSort.htm][u][size=2][color=#0000ff]Shaker 排序法 - 改良的气泡排序[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/HeapSort.htm][u][size=2][color=#0000ff]Heap 排序法 - 改良的选择排序[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/QuickSort1.htm][u][size=2][color=#0000ff]快速排序法（一） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/QuickSort2.htm][u][size=2][color=#0000ff]快速排序法（二） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/QuickSort3.htm][u][size=2][color=#0000ff]快速排序法（三） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MergeSort.htm][u][size=2][color=#0000ff]合并排序法 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/RadixSort.htm][u][size=2][color=#0000ff]基数排序法 [/color][/size][/u][/url][/list]
[size=2]搜寻[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/LinearSearch.htm][u][size=2][color=#0000ff]循序搜寻法（使用卫兵） [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/BinarySearch.htm][u][size=2][color=#0000ff]二分搜寻法（搜寻原则的代表）[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/InterpolationSearch.htm][u][size=2][color=#0000ff]插补搜寻法 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/FibonacciSearch.htm][u][size=2][color=#0000ff]费氏搜寻法 [/color][/size][/u][/url][/list]
[size=2]矩阵[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/SparseMatrix.htm][u][size=2][color=#0000ff]稀疏矩阵 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/MultiToOneDim.htm][u][size=2][color=#0000ff]多维矩阵转一维矩阵 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/TriangleArray.htm][u][size=2][color=#0000ff]上三角、下三角、对称矩阵[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/OddArray.htm][u][size=2][color=#0000ff]奇数魔方阵 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/FourNArray.htm][u][size=2][color=#0000ff]4N 魔方阵 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/TwoNOneArray.htm][u][size=2][color=#0000ff]2(2N+1) 魔方阵 [/color][/size][/u][/url][/list]
[size=2]堆叠、伫列[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/StackByArray.htm][u][size=2][color=#0000ff]堆叠 - 使用阵列实作 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/StackByLink.htm][u][size=2][color=#0000ff]堆叠 - 使用链结实作（C 语言动态记忆体宣告）[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/StackByObject.htm][u][size=2][color=#0000ff]堆叠 - 使用 Java 作物件封装[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/QueueByArray.htm][u][size=2][color=#0000ff]伫列 - 使用阵列实作 [/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/QueueByLink.htm][u][size=2][color=#0000ff]伫列 - 使用链结实作（C语言动态记忆体宣告）[/color][/size][/u][/url][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/QueueByObject.htm][u][size=2][color=#0000ff]伫列 - 使用Java 作物件封装[/color][/size][/u][/url][/list]
[size=2]其它[/size] [list][*][url=http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/Quine.htm][u][size=2][color=#0000ff]自产生程式（quine） [/color][/size][/u][/url][/list][/td][/tr][/table]

fantasy 发表于 2008-4-29 15:35

不错呵

谢啦

zhponly 发表于 2008-5-1 11:31

[code]
-------------------------------------------------------------------------BRT.h
#define RED  1
#define BLACK 0
typedef struct BRTREE
   {
      int color;
      int key;
      struct BRTREE *left;
      struct BRTREE *right;
      struct BRTREE *parent;
   }rbt;
extern rbt nil;
void rbinsert(rbt*,rbt*);
extern rbt *root;
void init(void);
rbt * rbdelete(rbt*,rbt*);
-------------------------------------------------------------------------BRT.h

-------------------------------------------------------------------------BRT.c
#include"RBT.h"
#define NUL 0
rbt nil;
rbt *root;
void rbinsertfixup(rbt *,rbt *);
void rbdeletefixup(rbt *,rbt *);
rbt *rbtreemin(rbt *a)
{
while(a->left!=&nil)
   a=a->left;
//找到最小的那个key.....
return a;
}
rbt *successor(rbt *x)
{
rbt *y;
if(x->right!=&nil)
return rbtreemin(x->right);
y=x->parent;
while(y!=&nil&&(x=y->right))
   {
   x=y;
   y=y->parent;
   }
//找到前驱,也就是仅比它大的某一个key......
return y;
}
void init(void)
{
nil.key=32767;
nil.left=NUL;
nil.right=NUL;
nil.parent=NUL;
nil.color=BLACK;
root=&nil;
}
void leftrotate(rbt *x)
{
rbt *tmp;
tmp=x->right;
x->right->parent=x->parent;
x->right=x->right->left;
x->right->parent=x;
if(x==root)
{
root=tmp;
// printf("leftrotate %d\n",root->key);
  //其实这个是比较麻烦的,我开始做得比较简单
//应该把parent和父节点的left或right同时改变的
}
else if(x==x->parent->left)
x->parent->left=tmp;
else
x->parent->right=tmp;
x->parent=tmp;
tmp->left=x;
}
void rightrotate(rbt *y)
{
rbt *tmp;
tmp=y->left;
y->left->parent=y->parent;
y->left=y->left->right;
y->left->parent=y;
if(y==root)
{
root=tmp;
// printf("leftrotate %d\n",root->key);
}
else if(y==y->parent->left)
y->parent->left=tmp;
else
y->parent->right=tmp;
y->parent=tmp;
tmp->right=y;
}
void rbinsert(rbt *r,rbt *z)
{
rbt *y=&nil;
rbt *x=r;
while(x!=&nil)
   {
   y=x;
   if(z->key<x->key)
      x=x->left;
   else
      x=x->right;
   }
//printf("%d%d\n",x->key,y->key);
//插入算法和查询二叉树插入相同
//大于向右,小于向左,最后插入到一个叶节点
z->parent=y;
if(y==&nil)
{
   root=z;
   z->parent=&nil;
   }
else if(z->key<y->key)
   y->left=z;
else
   y->right=z;
z->left=&nil;
z->right=&nil;
z->color=RED;
rbinsertfixup(r,z);
}
void rbinsertfixup(rbt *r,rbt *z)
{
   rbt *y;
while(z->parent->color==RED)
//如果z的parent的颜色不是红的就不用改了.....
   {
   if(z->parent==z->parent->parent->left)
      {
         y=z->parent->parent->right;
         if(y->color==RED)
            {
            z->parent->color=BLACK;
            y->color=BLACK;
            z->parent->parent->color=RED;
            z=z->parent->parent;
            //第一种情况,z的叔叔是红色的
   //把z的父亲和叔叔变成黑色,z变成z的父亲的父亲
   //再次进入while
            }
         else if(z==z->parent->right)
            {
            z=z->parent;
            leftrotate(z);
            //这种情况有点诡异,左转以后z是黑色,z父亲是红色
   //所以还进入while,会到第三种情况
            }
         else
            {
            z->parent->color=BLACK;
            z->parent->parent->color=RED;
            rightrotate(z->parent->parent);
            //把z的父节点和父父节点染色,右转
            }
      }
   else
   //这个和上面对称,就是左右反相.....
      {
         y=z->parent->parent->left;
         if(y->color==RED)
            {
            z->parent->color=BLACK;
            y->color=BLACK;
            z->parent->parent->color=RED;
            z=z->parent->parent;
            }
         else if(z==z->parent->left)
            {
            z=z->parent;
            rightrotate(z);
            }
         else
            {
            // printf("zpc %d,zppc %d",z->parent->color,z->parent->parent->color);
            z->parent->color=BLACK;
            z->parent->parent->color=RED;
            //printf("rk%d\n",root->key);
            leftrotate(z->parent->parent);
            // printf("rk%d\n",root->key);
            }
         }
      }
root->color=BLACK;
//最后把根节点染成黑色,插入第一个节点及类似情况用到....
}
rbt * rbdelete(rbt *r,rbt *z)
{
//删除时忘了检验z是不是空了....
//找到z的前驱...用来代替z
rbt *y,*x;
if(z->left==&nil||z->right==&nil)
y=z;
else
y=successor(z);
if(y->left!=&nil)
x=y->left;
else
x=y->right;
x->parent=y->parent;
if(y->parent==&nil)
root=x;
else if(y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
if(y!=z)
z->key=y->key;
if(y->color==BLACK)
rbdeletefixup(r,x);
//还是染色比较麻烦些.....
return y;
}
void rbdeletefixup(rbt *r,rbt *x)
{
rbt *w,*y;
while(x!=&nil&&x->color==BLACK)
   {
   if(x=x->parent->left)
      {
      w=x->parent->right;
      //第一种情况
      if(w->color==RED)
         {
         w->color=BLACK;
         x->parent->color=RED;
         leftrotate(x->parent);
         w=x->parent->right;
         }
      //第二种情况
      if(w->left->color==BLACK&&w->right->color==BLACK)
         {
         w->color=RED;
         x=x->parent;
         }
      //第三种情况
      else if(w->right->color==BLACK)
         {
         w->right->color=BLACK;
         w->color=RED;
         rightrotate(w);
         w=x->parent->right;
         }
      else
      //第四种情况....
         {
         w->color=x->parent->color;
         x->parent->color=BLACK;
         w->right->color=BLACK;
         leftrotate(x->parent);
         x=root;
         }
      }
   else
   //和前面相对,左右相反...
      {
      w=x->parent->left;
      if(w->color==RED)
         {
         w->color=BLACK;
         x->parent->color=RED;
         rightrotate(x->parent);
         w=x->parent->left;
         }
      if(w->right->color==BLACK&&w->left->color==BLACK)
         {
         w->color=RED;
         x=x->parent;
         }
      else if(w->left->color==BLACK)
         {
         w->left->color=BLACK;
         w->color=RED;
         leftrotate(w);
         w=x->parent->left;
         }
      else
         {
         w->color=x->parent->color;
         x->parent->color=BLACK;
         w->left->color=BLACK;
         rightrotate(x->parent);
         x=root;
         }
      }
   }
x->color=BLACK;
//最后一个染色......
}
-------------------------------------------------------------------------BRT.c
[/code]

[[i] 本帖最后由 zhponly 于 2008-5-1 11:32 编辑 [/i]]

愤青的心声 发表于 2008-5-1 12:39

大家都这么专业

june 发表于 2008-5-1 12:48

限时精华

zzshaka 发表于 2008-5-1 14:48

[quote]原帖由 [i]蓝月鸟[/i] 于 2008-4-29 14:24 发表 [url=http://bbs.ghtt.net/redirect.php?goto=findpost&pid=1231408&ptid=104484][img]http://bbs.ghtt.net/images/common/back.gif[/img][/url]
俺是买酱油滴
[em33]

老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）骑士走棋盘八个皇后八枚银币生命游戏字串核对双色、三色河内塔背包 ... [/quote]介个经典..[em03]

页: [1]

观海听涛BBS's Archiver

贴几个基础的算法

回复 1# zhponly 的帖子

不错呵