Hades 你的问题我想出来了，哈哈

    你问的是20层的平衡二叉树最少有几个节点，我忘了你当时给我的答案了，但是现在我想出来正确答案了。不知和你的正确答案一样否。
    正确答案应该是  （2的18次方 加 2的17次方 加 1）
    如果是N层二叉树的话（N大于2），最小平衡二叉树的节点个数应该是：
                    2的（N-2）次方 + 2的（N-3）次方 + 1
-------------------- 嘿嘿，YZ95！

这都行。I服了YOU了，看来你还得看看书才行

你的答案和我的一样吗？？我个人认为，答案肯定对

--------------------
嘿嘿，YZ95！ [ 2001-10-10 22:35:22 yz95 修改 ]

要是你个人都不认为答案肯定对，你就不会帖出来了：）我上次说的（N）=（N-1）+（N-2）+1的意思是：每个最少平衡二叉树的接点数等于一个（N-1）层的最少平衡儿茶树个数+（N-2）层平衡儿茶树个数+1。这个题本身没什么大的价值。关键是它的这种低归思想。

好了，今天来个新问题好否？：）：）：）
写一算法：输入为一个链表的头指针。输出是给它排序的链表的头指针。
算法要求是：
    1：用分治法（快速排序的方法）。
    2：不用任何辅助物理接点（原地的意思）。
    3：算法中只能有指针变量。
    4：要有稳定性（原来有两个相等的接点，要在排序后仍然保持他们原来的逻辑顺序） --------------------   Optimistic is my color
　 We spend our time on something from dawn to dark
   Day in and day out
　 Sun rise and down　
　 Make an own goal to confront life　
   Self-discovery is the first step toward self-appreciation
   成功只会降临在自认为会成功的人身上

我写过这样的一个程序，和你的要求差不多
    2：不用任何辅助物理接点（原地的意思）。
    3：算法中只能有指针变量。
    4：要有稳定性（原来有两个相等的接点，要在排序后仍然保持他们原来的逻辑顺序）
但，是不是快速排序我不知道（我懒的查书），我把同类项合并了（是我们数据结构课程设计）。源程序你到ftp;//202.112.230.124看吧，具体要求是对多项式相乘。
下面是排序函数：
struct node
{
int x;//指数
float a;//系数
struct node  *next;
} ;
struct node *sort(struct node *ab)//对数据进行排序,并合并同类项
{ //使数据按从大到小，并没有可再合并的同类项

struct node *temp,*temp1,*temp2;//temp2指向temp的前一个节点
int t=1,i=0;//t存放输入时的多项式个数
temp=ab->next;
temp2=ab;
temp1=ab;
if(temp==NULL)//判断是否为只有一项的式子
{
return(ab);
}
while(temp!=NULL)
{
temp1=ab;
t++;
i=0;
while(temp!=temp1||temp==NULL)
{
if (temp1->x==temp->x)//相等,合并同类项
{
temp1->a=temp1->a+temp->a;
temp=temp->next;

i=1;
free(temp2->next);
temp2->next=temp;
break;
}
if(temp1==ab)//和第一项比较,temp指向第二项
{
if(temp->x<temp1->x)//如果第二项的系数小于等于第一项的系数
{


temp2->next=temp->next;
temp->next=temp1;
temp1=temp;
temp=temp2->next;
ab=temp1;
i=1;

if (temp==NULL)
{
break;
}
break;

}
}
if (temp->x<temp1->next->x)
{
temp2->next=temp->next;
temp->next=temp1->next;
temp1->next=temp;
temp=temp2->next;

i=1;
if (temp==NULL)
{
break;
}
break;
}
temp1=temp1->next;
}
if(!i)
{
temp=temp->next;
temp2=temp2->next;
}

}
return(ab);
}

[ 2001-10-12 23:08:36 yz95 修改 ]

好象严重违背我的原意

将就一下吧

把有难度的东西都给避了

Hades,好久不见了，复习的怎样，看你的题目好像没选中科:)，祝你好运。
那个答案yz95你也敢贴:(，你说的难度在那里，这类题都不用自己编，有现成的。

kmwang，哪个答案呀，能不能指出错误？指点迷津？

人家要的是分治法，你老兄那个？？？
题目：下面这个算法是稳定的么？改成非递归。

typedef void* gpointer;
typedef const void *gconstpointer;

struct _GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

typedef struct _GList GList;
typedef gint (*GCompareFunc) (gconstpointer a,
gconstpointer b);
static GList *
g_list_sort_merge (GList       *l1,
  GList       *l2,
  GCompareFunc compare_func)
{
  GList list, *l, *lprev;

  l = &list;
  lprev = NULL;

  while (l1 && l2)
    {
      if (compare_func (l1->data, l2->data) < 0)
        {
 l->next = l1;
 l = l->next;
 l->prev = lprev;
 lprev = l;
 l1 = l1->next;
        }
      else
{
 l->next = l2;
 l = l->next;
 l->prev = lprev;
 lprev = l;
 l2 = l2->next;
        }
    }
  l->next = l1 ? l1 : l2;
  l->next->prev = l;

  return list.next;
}

GList*
g_list_sort (GList       *list,
    GCompareFunc compare_func)
{
  GList *l1, *l2;
  
  if (!list)
    return NULL;
  if (!list->next)
    return list;
  
  l1 = list;
  l2 = list->next;

  while ((l2 = l2->next) != NULL)
    {
      if ((l2 = l2->next) == NULL)
break;
      l1 = l1->next;
    }
  l2 = l1->next;
  l1->next = NULL;

  return g_list_sort_merge (g_list_sort (list, compare_func),
   g_list_sort (l2,   compare_func),
   compare_func);
}

KMWang:居然用归并的思想来分治，着眼局部后整体。我想的是先整体后局部，就象快速排序一样。呵呵。说道连表用归并还是蛮方便：）
while ((l2 = l2->next) != NULL){
      if ((l2 = l2->next) == NULL) break;
      l1 = l1->next;
}  // 用这个找到连表中间，厉害。一会还真难想到！：）
我想搞清门路了，改成非低归的就小CASE了。
一个连表分为两部分list_head,list_mid(用上面的方法找到这两个指针）。然后进连表栈（list_mid,list_head)。本来在栈底还该放个标志位，当出栈的时候说明这轮排序完成可以调用归并程序了。但是只要设置两个指针变量head和list（开始为NULL）。head用来表示已经排序好的一部分（这里有个第一次问题）。list为栈中待排序的头指针。关于平分到什么时候就不进栈了，就想下面的判断，只要这次要平分的连表只有两个接点就开始归并。这时第一次要付值给head，以后就付值给list，在每次循环中判断list是否为空。不为空就调用归并。然后又付值为空。一直到栈空就行了。好了。说了一大段。还要理论联系实际，不过现在没空去实践，可惜：（
--------------------   Optimistic is my color
　 We spend our time on something from dawn to dark
   Day in and day out
　 Sun rise and down　
　 Make an own goal to confront life　
   Self-discovery is the first step toward self-appreciation
   成功只会降临在自认为会成功的人身上

我认为这种方法也蛮有味道的。完全的快速排序翻版。实现方法是。对给的头连表设置这样3组指针：
Low_head,Low_tail,Mid_head,Mid_tail.High_head,High_tail顾名思义就是按头接点把连表经过比较分成小，中，大3部分。然后给条件低归就KO了。低归后然后衔接这3部分返回。在衔接的时候要注意由于分离了各个连表，找到尾部进行衔接有点困难，这可以设置一个全局变量Last用于记住排好序的连表的尾部接点指针。：）：）

今天蛮高兴学道了个新东西，呵呵。我就还想说个。也蛮有意思的哟。问题是：我们都知道计算机在算术运算的时候对表达式都要有中间变量，用程序实现一个给定表达式要几个中间变量（不考虑优化，也就是一个中间变量用一次后就可从新用了）。其实最多就需要两个的，怎样用程序给出分配方案？下面是个例子：
（a+b ) * ( a-b ) -a*b这个表达式的分配方案就是：
 tempt_1 = a+b
 tempt_2 = a-b
 tempt_1 = tempt_1 * tempt_2
 tempt_2 = a*b
 tempt_1 = tempt_1 _ tempt_2
有点想什么3元式，4元式。其实编译过程最后应该有这玩意的。现在用个比较简单的方法实现之分配。

中科的题很好，就是有难度。好象更变态，作为习题还是蛮好

KMWang：我现在一碰到什么程序填空就有点邪财了。本来原问题是常见的或是很简单的一个东西。他却偏要用他那破思路来整人。费半天鸟劲才能看出点门路。哎！真是困难。

哦。还忘了点了。归并是稳定的。

看了两位的帖子，真是长见识呀，希望以后两位能多发帖子呀。:D
现在我有一个问题不知两位能不能解答。
怎么用 用户界面的多线程，希望解答。
-------------------- 嘿嘿，YZ95！

那道题是出给YZ95的，我当然知道你会做了:)，你的另外一道题既是有简单的方法也不要想，那个是经典的方法？正如上面的那个排序，经典的教科书式的答案。这道题交给YZ95，从课本里找到一个最经典的解法，尽管程序比较长。
用户界面多线程的设计MSDN里面就有例子，找出来看看。
在此之前首先找出线程最小概念集合，解决一些经典问题，如生产者和消费者问题。