世界经典算法问题交流探讨

moonsky · 发表于 2003-4-30 20:50:51

堆排序

[code:1]int heapsort(int p[],int n);

/*
* 堆排序算法在 1964 年由 J. Williams 发明。
* 不稳定，不需要辅助空间。
*/
static int insertheap(int p[],int i,int n);

int heapsort(int p[],int n)
{
int op=0;
int i,temp;

/* 从叶子节点建立对应的上级根节点来建造堆 */
for (i=n/2-1; i>=0; i--) {
op+=insertheap(p,i,n);
}
/* 选择堆顶的最大值与尾部的值交换，
   * 把这个值重新插入堆 */
for (i=n-1; i>=1; i--) {
temp=p[0];
p[0]=p[i];
p[i]=temp;
op++;
op+=insertheap(p,0,i);

}
return op; /* 返回比较操作数 */
}

static int insertheap(int p[],
   int i, /* 要插入的元素的位置 */
   int n) /* 列表长度 */
{
int op=0;
int j,temp;
temp=p[i]; /* 要插入的元素已经在根节点位置上，保存它的值 */
j=i*2+1; /* 要比较的节点位置是当前根节点的左子节点 */

/* 要比较的节点位置在列表范围内 */
while (j<n) {
/* 要比较的左子节点有对应的子节点，并且
   * 当前根节点的左子节点小于右子节点 */
if (j<n-1 && p[j]<p[j+1])
j++; /* 要比较的节点位置是当前根节点的右子节点 */
/* 要插入的值小于当前做比较的子节点 */
if (temp<p[j]) {
p[i]=p[j];  /* 做比较的子节点的值上移到当前根节点 */
i=j; /* 当前根节点下移到做比较的子节点的位置上 */
j=i*2+1; /* 要比较的节点位置是当前根节点的的左子节点 */
}
/* 要插入的值小于当前做比较的子节点 */
      else
break; /* 停止下移 */
op+=2;
/* 分别与左右子节点做比较操作。
   * 这是堆排序比快速排序多做比较操作的根源 */
}
p[i]=temp; /* 插入要插入的值 */
op++;
return op;
}
[/code:1]

moonsky · 发表于 2003-4-30 20:52:30

就地归并排序算法的未做优化实现

[code:1]int imergesort(int p[], int n);

extern int insertsort(int p[], int n);
extern int appendsort(int p[], int m, int n);
extern int binarysearch(int p[],int n, int v, int *m);
static int exchange(int src[],int dest[],int n);
static int swapMergeSort(int p[], int swap[], int n, int count);
static int swapMerge(int work[], int swap[], int m, int n,int flag);
static int replaceMerge(int p[],int m, int q, int n);
#define IN 1
#define OUT 0

/*
* in-place 归并排序算法的始作俑者和优化实现请参见：
* http://www.diku.dk/hjemmesider/ansatte/jyrki/Experimentarium/
* 其优化的最终结果是“在理论上比高级版本的堆排序优越，在实际上
* 比常规的堆排序慢50%”。不稳定，不需要辅助空间。
* 余之实现意图说明标志性的方法而未做任何优化。
*/
int imergesort(int p[], int n)
{
int op=0;
int i;
int k=n; /* 在头部的未排序的元素数目 */
int m=0; /* 在尾部的已排序的元素数目 */

i=k/2;
/* 用列表的前半部分做交换空间，
   * 对列表的后半部分做归并排序。*/
op+=swapMergeSort(&p[n-i],p,i,0);
m=m+i;
k=k-i;
while(k>4) {
i=k/2;
/* 用未排序子列表的后半部分做交换空间，
   * 对未排序子列表的前半部分做归并排序*/
op+=swapMergeSort(p,&p[i],i,0);
/* 把新排序出来的子列表与早先排序出来
   * 的子列表做不对称归并，它们之间的未
   * 排序空间被置换到列表头部。*/
op+=replaceMerge(p,i,n-m,m);
/* 列表的头部是未排序的，而尾部是已排序的 */
m=m+i;
k=k-i;
}
/* 最后的剩下的几个元素直接插入到已排序的列表中 */
if(k<m)
op+=appendsort(p,k,n);
else /* 整个列表只有几个元素的时候 */
op+=insertsort(p,n);

return op; /* 返回操作数 */
}

/*
* 前提：0 -> m-1 和 q -> q+n-1 是两个有序列表，
* 中间从 m -> q-1 是大小为 q-m 的未排序的空间。
* 要求 q>=2*m，即中间的未排序空间大于等于左面的列表。
* 结果：归并出从 q-m 开始的大小是 m+n 的有序列表，
* 0 到 q-m-1 是被置换出来的大小是 q-m 的未排序的空间。
*/
static int replaceMerge(int p[], /* 要归并的列表即左列表的头位置 */
   int m, /* 左列表的长度 */
   int q, /* 右列表的头位置 */
   int n) /* 右列表的长度 */
{
int op=0;
int i=0,j=0,t=0;
int w=n/m; /* 两个子列表大小的比 */
int r;
int *left=p;
int *right=&p[q];
int *dest=&p[q-m];
while (i<m && j<n) {
/* 把左列表的一个元素与右列表的 w 个元素中的最大值做比较 */
if (left[i]>=right[j+w-1]) {
/* 选择的左列表元素大于等于右列表的 m 个元素。*/
op+=exchange(&right[j],&dest[t],w);
t=t+w;
j=j+w;
}else{
/* 以左列表一个元素作为查找值在右列表的 w 个元素中找到小于
   * 查找值的元素个数 */
op+=binarysearch(&right[j],w,left[i],&r);
if (r!=0) {
op+=exchange(&right[j],&dest[t],r);
t=t+r;
j=j+r;
}
op+=exchange(&left[i],&dest[t],1);
t++;
i++;
}
if (w>n-j)
w=n-j;
}
if (i<m)
op+=exchange(&left[i],&dest[t],m-i);

return op;
}
/*
* 交换过程，操作数是 2*n+1 而不是 3*n，但不保持目标列表的
* 原有次序，故只能用在有序列表与无序列表之间的交换。
*/
static int exchange(int src[],int dest[],int n)
{
int i,temp;
if (n==0)
return 0;
temp=dest[0];
for(i=0;i<n-1;i++) {
dest[i]=src[i];
src[i]=dest[i+1];
}
dest[i]=src[i];
src[i]=temp;
return 2*n+1;
}

static int swapMergeSort(int work[], int swap[], int n, int count)
{
int op=0;
int m;
count++;
m=n/2;
if(n<=8) {
op+=insertsort(work,n);
if (count%2==0)
op+=exchange(work,swap,n);
} else {
op+=swapMergeSort(work,swap,m,count);
op+=swapMergeSort(work+m,swap+m,n-m,count);
op+=swapMerge(work,swap,m,n,count);
}
return op;
}

static int swapMerge(int work[], int swap[], int m, int n, int flag)
{
int *src, *dest;
int i=0, j=m, t=0;
int temp;

flag%=2;
if (flag==OUT) {
src=work;
dest=swap;
}
else { /* flag==IN */
src=swap;
dest=work;
}

temp=dest[t];
while (i<m  && j<n) {
if (src[i] <= src[j]) {
dest[t] = src[i];
t++;
src[i] = dest[t];
i++;
} else {
dest[t] = src[j];
t++;
src[j] = dest[t];
j++;
}
}
while (i<m) {
dest[t] = src[i];
t = t++;
if (t<n)
src[i] = dest[t];
else
src[i] = temp;
i = i++;

}
while (j<n) {
dest[t] = src[j];
t++;
if (t<n)
src[j] = dest[t];
else
src[j] = temp;
j++;
}
return 2*n+1;
}
[/code:1]

moonsky · 发表于 2003-4-30 20:55:52

两路归并排序算法

[code:1]#include <stdlib.h>
int mergesort(int p[], int n);
extern int insertsort(int p[], int n);
extern int stablesort(int p[], int n);
static int merge_sort(int p[], int swap[], int n, int count);
static int merge(int work[], int swap[], int m, int n, int flag);

/*
* 归并排序算法在 1938 年由 IBM 发明并在电动整理机上实现。
* 在 1945 年由 J. von Neumann 首次在 EDVAC 计算机上实现。
* 稳定，需要与序列同等大小的辅助空间。这里实现的是两路归并算法。
*/
#define IN 1
#define OUT 0

int mergesort(int p[], int n)
{
int op=0;
int * work=p;
int * swap;
int i,j,w;
int count=0; /* 初始计数为偶数 */

if (n<=16)
return insertsort(work,n);
swap=(int*)calloc(n,sizeof(int));
if (swap==NULL)
return 0;
for(i=0;i+7<n;i+=8)
op+=insertsort(work+i,8);
if (i<n)
op+=insertsort(work+i,n%8);
for(i=8;i<n;i*=2) { /* i 为路段长度 */
w=i*2; /* w 为路段长度乘以归并的路数 */
for(j=0;j+w-1<n;j+=w)
/* 平衡的两路归并 */
op+=merge(work+j,swap+j,i,w,count);
if (i+j<n)
/* 不平衡的两路归并 */
op+=merge(work+j,swap+j,i,n%w,count);
else
/* 换入或换出剩余的一个路段 */
op+=merge(work+j,swap+j,n%w,n%w,count);
count++; /* 计数增加 */
}
if (count%2) /* 计数为奇数 */
for (i=0;i<n;i++)
work[i]=swap[i];
free(swap);
return op;
}

/*
* 两路归并过程。
*/
static int merge(int work[], /* 工作空间，就是要归并的列表 */
   int swap[], /* 交换空间，不小于工作空间 */
   int m, /* 前半部分列表长度和后半部分列表的开始位置 */
   int n, /* 列表总长度 */
   int flag) /* 换入换出标志 */
{
int *src, *dest;
int i=0, j=m, t=0;

flag%=2;
if (flag==OUT) {
src=work;
dest=swap;
}
else { /* flag==IN */
src=swap;
dest=work;
}
while (i<m  && j<n) {
if (src[i] <= src[j]) {
dest[t] = src[i];
t++;
i++;
} else {
dest[t] = src[j];
t++;
j++;
}
}
while (i<m) {
dest[t] = src[i];
i = i++;
t = t++;
}
while (j<n) {
dest[t] = src[j];
j++;
t++;
}
return n;
}

/**************************************/
/* 下面是递归实现，留做参考       */
/**************************************/
int mergeSort(int p[], int n)
{
int op=0;
int * temp;

if (n<=16)
return insertsort(p,n);
temp=(int*)calloc(n,sizeof(int));
if (temp==NULL)
return 0;
op=merge_sort(p,temp,n,0);
free(temp);
return op;
}

static int merge_sort(int work[], int swap[], int n, int count)
{
int op=0;
int i, m;
count++; /* 计数增加 */
m=n/2;
if(n<=8) {
op+=insertsort(work,n);
if (count%2==0) /* 计数为偶数 */
for (i=0;i<n;i++)
swap[i]=work[i];
} else {
op+=merge_sort(work,swap,m,count);
op+=merge_sort(work+m,swap+m,n-m,count);
op+=merge(work,swap,m,n,count);
}
return op;
}[/code:1]

moonsky · 发表于 2003-4-30 20:57:28

快速排序算法

[code:1]int quicksort(int p[],int n);
extern int insertsort(int p[], int n);
static int partition(int p[],int n,int *m);
static int quick_sort(int p[],int n);

/*
* 快速排序算法在 1962 年由 C. Hoare 发明。
* 不稳定，需要与 lg(n) 成比例的辅助空间。
*/
static struct stackframe { /* 栈帧 */
int * list;
int length; /* 可以省略 */
};
static struct stackframe sp[64]; /* 栈指针 */
static unsigned int randx; /* 伪随机数 */

int quicksort(int p[],int n)
{
int op=0;
int i;
int *h,l;
int m; /* 基准值的位置 */
struct stackframe *fp; /* 帧指针*/
struct stackframe *stp; /* 栈顶指针 */

if (n<=16)
return insertsort(p,n);
for(i=1;i<n;i<<=1); /* i=[lg(n)] */
randx=p[0]%7875;
stp=sp+i-1;
fp=sp;
fp->list=p;
fp->length=n;
while (fp>=sp) {
h=fp->list;
l=fp->length;
/*  采用 D. Musser 的限定划分深度的建议 */
while (l>16 && fp<=stp) {
op+=partition(h,l,&m);
fp->list=h+m+1;
fp->length=l-m-1;
fp++;
l=m;
}
fp--;
}
op+=insertsort(p,n);
return op;
}

/*
* 基准值选择采用 C. Hoare 建议的随机选择策略。
*/
static int partition(int p[],int n,
   int *m ) /* 返回的基准值的位置 */
{
int i=0; /* 头指针 */
int j=n-1; /* 尾指针 */
int pivot; /* 基准值 */
int k;
if (n<=0)
return 0;
randx=(randx*421+1663)%7875; /* 线性同余伪随机数 */
k=randx%n;
/* 随机选择某个位置的元素作为基准值并保存它，
   * 接着把头指针指向的元素复制到这个位置上 */
pivot=p[k];
p[k]=p[i];
/* p[i] 已被交换到 p[k]，可以覆盖 */
while (i<j) { /* 头指针先于尾指针 */
while (i<j && p[j]>=pivot) /* 尾指针指向的元素大于基准值 */
j--; /* 前移尾指针 */
if (i<j) {
p[i]=p[j]; /* 替换当前p[i]内容为p[j]的内容 */
i++; /* 后移头指针 */
}
/* p[j] 已被交换可以覆盖 */
while (i<j && p[i]<=pivot) /* 头指针指向的元素小于基准值 */
i++; /* 后移头指针 */
if (i<j) {
p[j]=p[i]; /* 替换当前p[j]内容为p[i]的内容 */
j--; /* 前移尾指针 */
}
/* p[i] 已被交换可以覆盖 */
}
/* 如果最后一次交换的是 p[j]，则 i 指针会移动成 i=j */
p[i]=pivot; /* 把保存的基准值保存到当前位置上 */
*m=i; /* 返回基准值当前的位置 */
return n;
}

/**************************************/
/* 下面是递归实现，留做参考       */
/**************************************/
int quickSort(int p[],int n)
{
if (n<=16)
return insertsort(p,n);
randx=p[0]%7875;
return quick_sort(p,n);
}

static int quick_sort(int p[],int n)
{
int op=0;
int m;

if (n<=16)
op+=insertsort(p,n);
else {
op+=partition(p,n,&m);
op+=quick_sort(p,m);
op+=quick_sort(p+m+1,n-m-1);
}
return op;
}[/code:1]

moonsky · 发表于 2003-4-30 20:59:14

基数排序算法

[code:1]#include <stdlib.h>
int radixsort(int p[], int n);

int distribute(int *src, int *dest, int n, int idx);
/*
* 基数排序算法的最早书面记述在 1923 年由 IBM 发表。当时实
* 现在电动排序机上。在 1954 年由 H. Seward 在计算机上实现。
* 稳定，需要与序列同等大小的辅助空间。
*/
int radixsort(int p[], int n)
{
int * swap;

swap=(int *)calloc(n,sizeof(int));
if (swap==NULL)
return 0;

/* 如果处理器不是小端字节序，而是大端字节序，
* 则下标应是 3,2,1,0 */
distribute(p, swap, n, 0);
distribute(swap, p, n, 1);
distribute(p, swap, n, 2);
distribute(swap, p, n, 3);

free(swap);
return 4*(2*n+512);
}

#define radix(x,y) (((unsigned char *)&(x))[(y)])
static int count[256];
/*
* 字节分布例程
*/
int distribute(int *src, int *dest, int n, int idx)
{
int i;
int index[256];
for (i=0; i<256; i++)
count[i]=0;
/* 统计每个基数的元素数目 */
for (i=0; i<n; i++)
count[radix(src[i],idx)]++;
/* 计算与每个基数相对应的堆的位置索引 */
for (index[0]=0, i=1; i<256; i++)
index[i]=index[i-1]+count[i-1];
/* 把源列表中的元素分布到各个堆中 */
for (i=0; i<n; i++)
dest[index[radix(src[i],idx)]++]=src[i];

return 2*n+512;
}
[/code:1]

moonsky · 发表于 2003-4-30 21:03:22

AVL 树数据结构

[code:1]/* avl.h */
/*
* 高度平衡二叉树的一种重要方案。
* 在 1962 年由 G. Adelson-Velsky 和 E. Landis 发明。
*/
typedef int typekey;
typedef struct avlnode { /* 高度平衡树节点 */
typekey k; /* 键 */
char *v; /* 值 */
int bal;
/* 平衡因子，当 bal==[-1,0,1] 时平衡，分别对应于左子树
   * 高过右子树一层，左右子树高度相同，右子树高过左子树一层 */
struct avlnode *left, *right; /* 指向子树的指针 */
} node, *tree;
extern tree search(typekey, tree);
extern tree insert(typekey, tree);
extern tree delete(typekey, tree);
extern int height(tree);
extern int count(tree);
extern int deltree(tree);
/* end of avl.h */
/*------------------------------------------------------------------------*/
/* avl.c */
#include <stdlib.h>
#include <stdio.h>
#include "./avl.h"

int incrhei; /* 高度增减标志 */

tree search(typekey, tree);
tree insert(typekey, tree);
tree delete(typekey, tree);
int height(tree);
int count(tree);
int deltree(tree );
static tree lrot(tree);
static tree rrot(tree);
static node* newNode(void);
static void freeNode(node*);
static void Error(void);

/*
* 二叉树查找例程
*/
tree search(typekey key, tree t)
{
while(t != NULL)
if (t->k == key)
return t;
else if (t->k < key)
t = t->right;
        else
t = t->left;
return NULL;
}
/*
* 插入例程。
*/
tree insert(typekey key, tree t)
{
if(t == NULL){ /* 当前节点为空 */
      t = newNode(); /* 建立新节点 */
t->k = key;
t->left = NULL;
t->right = NULL;
      t->bal = 0; /* 叶子节点等高平衡 */
      incrhei = 1; /* 高度增加 */
}
else if(t->k == key)/* 键已经在表中 */
      Error();
    else {
      if(t->k < key){
      t->right = insert(key, t->right);
      t->bal += incrhei; /* 右子树高度增加 */
      } else {
      t->left = insert(key, t->left);
      t->bal -= incrhei; /* 左子树高度增加 */
}
/* 某个子树增加了高度，并且两个子树高度不相同 */
if(incrhei != 0 && t->bal != 0){
/* 左子树高于右子树两层: 需要右旋 */
if(t->bal < -1) {
/* 当前节点的左子节点偏右平衡 */
        if(t->left->bal > 0)
/* 使当前节点的左子节点偏左平衡 */
t->left = lrot(t->left);
        t = rrot(t);
incrhei = 0; /* 本节点的高度不增加 */
      }
/* 右子树高于左子树两层: 需要左旋 */
else if(t->bal > 1) {
/* 当前节点的右子节点左平衡 */
        if(t->right->bal < 0)
/* 使当前节点的右子节点偏右平衡 */
t->right = rrot(t->right);
        t = lrot(t);
incrhei = 0; /* 本节点的高度不增加 */
}
else /* 某个子树高度增加了，破坏了等高平衡  */
incrhei = 1; /* 本节点的高度增加 */
     }
else
/* 它的子树未增加高度，或者某个子树增加高度后导致等高平衡  */
incrhei = 0;/* 本节点的高度不增加 */
}
return(t);
}
/*
* 删除例程
*/
tree delete(typekey key, tree t)
{
tree p;
if(t == NULL) /* 未找到 */
Error();
/* 键找到 */
else if (t->k == key) {
/* 有一个子树为空 */
if (t->left == NULL) {
p = t;
t = t->right;
freeNode(p);
incrhei = 1; /* 高度减少 */
return(t); /* 无需调整平衡 */
}
else if (t->right == NULL) {
p = t;
t = t->left;
freeNode(p);
incrhei = 1; /* 有高度变化 */
return(t); /* 无需调整平衡 */
/* 没有一个子树为空 */
} else {
if(t->bal<0) {
p = t->left;
while (p->right != NULL)
p = p->right;
t->k = p->k;
t->v = p->v;
t->left  = delete(p->k, t->left);
t->bal += incrhei; /* 左子树高度减少 */
} else {
p = t->right;
while (p->left != NULL)
p = p->left;
t->k = p->k;
t->v = p->v;
t->right  = delete(p->k, t->right);
t->bal -= incrhei; /* 右子树高度减少 */
}
}
}
/* 当前节点不是要删除的，继续查找 */
else if(t->k < key) {
t->right = delete(key, t->right);
t->bal -= incrhei; /* 右子树高度减少 */
}
else {
t->left  = delete(key, t->left);
t->bal += incrhei; /* 左子树高度减少 */
}
if (incrhei == 0 )
return(t); /* 无需调整平衡 */
/* 某个子树减少了高度，并且两个子树高度不相同 */
if(t->bal != 0){
/* 左子树高于右子树两层: 需要右旋 */
if(t->bal < -1) {
/* 当前节点的左子节点偏右平衡 */
if(t->left->bal > 0) {
/* 使当前节点的左子节点偏左平衡 */
t->left = lrot(t->left);
incrhei = 1;/* 本节点的高度减少 */
}
else if (t->left->bal == 0)
incrhei = 0;/* 本节点的高度不减少 */
   else
incrhei = 1;/* 本节点的高度减少 */
t = rrot(t);
      }
/* 右子树高于左子树两层: 需要左旋 */
else if(t->bal > 1) {
                  /* 当前节点的右子节点左平衡 */
if(t->right->bal < 0) {
/* 使当前节点的右子节点偏右平衡 */
t->right = rrot(t->right);
incrhei = 1;/* 本节点的高度减少 */
}
else if (t->right->bal == 0)
incrhei = 0;/* 本节点的高度不减少 */
   else
incrhei = 1;/* 本节点的高度减少 */
        t = lrot(t);
}
else /* 某个子树高度减少了，破坏了等高平衡 */
incrhei = 0; /* 本节点的高度不减少 */
}
/* 某个子树减少高度后导致等高平衡 */
else
incrhei = 1; /* 本节点的高度减少 */
return(t);
}

/*
* 左旋例程
*          A             C
*          / \          / \
*       B C ==> A E
*          / \       / \
*          D E    B D
* 前提：A, 偏右不平衡, C 偏右或等高平衡。
*/
static tree lrot(tree t)
{
tree temp;
int a;

temp = t;
t = t->right;
temp->right = t->left;
t->left = temp;

a = temp->bal;
/* 调整平衡因子 */
/* 假定 A 的平衡因子是 a, 节点 C 的平衡因子是 c, 节点 B 为高度 h,
   * 则节点 D 高度为 (c<0)?h+a-1;h+a-1-c => h+a-1-max(c,0);
   * 节点 E 的高度为 (c>0)?h+a-1?h+a-1+c, => h+a-1+min(c,0);
   * 节点 A 的新平衡因子是 a-1-max(c,0);
   * 节点 C 的新平衡因子是 E-(max(B,D)+1) => min(E-B-1,E-D-1)
   *    => min(a-2+min(c,0),c-1) => min(min(a-2+c,a-2),c-1)
   *    <=> min(a-2,min(a+c-2,c-1))
   */
temp->bal = a - 1 - max(t->bal, 0);
t->bal = min(a-2, min(a+t->bal-2, t->bal-1));
return(t);
}
/*
* 右旋例程
*          A             B
*          / \          / \
*       B C ==> D A
*       / \             / \
*       D E             E C
* 前提：A 偏左不平衡，B 偏左或等高平衡。
*/
static tree rrot(tree t)
{
tree temp;
int b;

temp = t;
t = t->left;
temp->left = t->right;
t->right = temp;
/* 调整平衡因子 */
b = temp->bal;
/* 调整平衡因子 */
/* 假定 A 的平衡因子是 b, 节点 B 的平衡因子是 c, 节点 C 为高度 h,
   * 则节点 D 高度为 (c<0)?h-b-1:h-b-1-c => h-b-1-max(c,0);
   * 节点 E 的高度为 (c>0)?h-b-1:h-b-1+c, => h-b-1+min(c,0);
   * 节点 A 的新平衡因子是 b+1-min(c,0)
   * 节点 C 的新平衡因子是 max(E,C)+1-D => max(E-D+1,C-D+1)
   *    => max(c+1,b+2+max(c,0)) => max(c+1,max(b+2+c,b+2))
   *    <=> max(b+2,max(b+c+2,c+1))
   */
temp->bal = b + 1 - min(t->bal, 0);
t->bal = max(b+2, max(b+t->bal+2, t->bal+1));
return(t);
}
static void Error(void)
{
printf("\nError: insert or delete key\n");
}
static node* newNode(void)
{
return (node*)calloc(1,sizeof(node));
}
static void freeNode(node * p)
{
free(p);
}
int height(tree t)
{
if (t == NULL)
return 0;
else
return 1+max(height(t->left),height(t->right));
}
int count(tree t)
{
if (t == NULL)
return 0;
else
return 1+count(t->left)+count(t->right);
}
int deltree(tree t)
{
int c=0;
if (t==NULL)
return 0;
else {
c+=deltree(t->left);
c+=deltree(t->right);
freeNode(t);
return c+1;
}
}
/* end of avl.c */[/code:1]

ShiChao · 发表于 2003-5-1 13:02:45

CSDN上面的算法版不错的

goldedge · 发表于 2003-5-1 15:52:19

c语言果然很长.

什么语言短？？？
呵呵！

wsm · 发表于 2003-5-1 16:14:48

引用:

c语言果然很长.

什么语言短？？？
呵呵！

汉语......

ShiChao · 发表于 2003-5-1 19:43:45

问一个问题：

用栈替代递归，可以提高效率，很明显吗？

wsm · 发表于 2003-5-1 20:15:21

次数大的小计算很有效

Zyroee · 发表于 2003-5-3 13:36:28

8 cuo 8 cuo

amble_shisu · 发表于 2003-5-4 13:03:55

这么简单的代码,八皇后比起十三皇后要简单了吧

fishcrazy · 发表于 2003-5-7 12:45:32

[quote:eb8a25bd12="amble_shisu"]这么简单的代码,八皇后比起十三皇后要简单了吧[/quote]
这只是规模大小的问题，不存在更加简单的说法

whr27 · 发表于 2003-5-14 22:53:43

good

		自动登录	找回密码
密码			注册