是用链表的存储结构寻找出子序列，并进行二路归并
 
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
    int value;
    Node *next;
}Node;
class Linklist
{
    private:
        Node *l;
        int lenth;
    public:
    void creat(Linklist *p,int n)//建立链表
    {     
         Node*head,*pre;
         p->lenth=n;
        for(int i=1;i<=p->lenth;i++)
        {  
           p->l=(Node*)mallloc(sizeof(Node));
           if(i==1)
           {
               pre=head=p->l;
               p->l->next=NULL;
           }
           else
           {
                pre->next=p->l;
                pre=p->l ;
                printf("输入节点值:");
                scanf("%d",&p->l.value);
            }
        }
        pre->next=NULL;
        p->l=head;
    }
};
void serch(Linklist&p)//查找出子序列
{Node*b[100],*p1,*q；
int j=0,k=0;
p1=p.l->next;
q=p1->next;
while(p1&&q)
    {
if(p1->value<q->value)
        {
        p1=p1->next;
        }
else
        {
        b[j++]=p1//子序列尾结点
        p1=q;
        q=q->next;
        }
    }
for(p1=p.l->next;p1;p1=e2->next) //两两归并所有子序列
    {
      e1=end[j];e2=end[j+1]; //确定两个子序列
      if(e1->next) merge(L,p1,e1,e2); //归并
      end[k++]=e2; //用新序列的尾指针取代原来的尾指针
      j+=2; //转到后面两个子序列
 
    }
}
void merge(Linklist &p,Node*p1，Node*e1,Node *e2)
//L为链表头结点，p为第一个子序列的头结点，e1,e2分别为序列的尾结点
{
    Node*q,*r;
    q=p1;
    r=e1->next;
    while(q!=e1->next&&r!=e2->next)//不超出序列范围
    {  
        if(q->value<r->value)
        {p1->next=q;
        q=q->next;
        }
            
        else
        {
          p1->next=r;
          p1=r;
          r=r->next;
        }
    while(q!=e1-next)//第一子序列还有剩余，第二个已遍历结束
        {p1->next=q;
        p1=q;
        q=q->next;
        }
    while(r!=e2->next)
        {p1->next=r;
         p=r;
        r=r->next;
        }
 
    }
}
 
 
int main()
{
    Linklist *p;
    int n;
    printf("输入结点个数:");
    scanf("%d",&n);
     creat(p,n);
    serch(p);
    return 0;
}

[ 本帖最后由 weimanqing 于 2012-5-15 19:28 编辑 ]