前一段时间有位朋友要求用链表找出中位数,闲来无事写了个链表的快排.但我想我这应该不算是真正意义上的快排,因为多了一个检查指针位置的函数,时间复杂度上应该是超了.

    另外,如果用这个思路写中位数,应该再多一个从链表头查找第 K 位数的函数,时间复杂度上也应该是超了.

    总之,程序贴出来,请大家多多指教,请高手们不吝指教,本菜多多学习才是,谢谢大家了.

#include <stdio.h>
#include<stdlib.h>

typedef struct tmp
{
    int num;
}tmp;

typedef struct st
{
    tmp *q;
    struct st *ago;
    struct st *after;
}st;

st *make_line();   //  建立链表
st *len_line(st *head);  // 查找链表的尾部
void line_sort(st *head,st *p,st *r);  //  排序
void wap(st *head,st *a,st *b);  // 交换链表的数据
void print(st *head);    // 输出
void del_line(st *head);  // 销毁链表
int check(st *p,st *r);  // 检查指针的位置

int main(void)
{
    st *head,*len;

    head=make_line();
    len=len_line(head);
    line_sort(head,head->after,len);
    print(head->after);
    del_line(head);

    return 0;
}

st *make_line()
{
    st *head,*p,*t;
    tmp *l;
    int n,i=0;

    p=t=NULL;
    while((head=(st *)malloc(sizeof(st)))==NULL);
    head->ago=head->after=NULL;
    while((scanf("%d",&n))==1)
    {
        while((p=(st *)malloc(sizeof(st)))==NULL);
        while((l=(tmp *)malloc(sizeof(tmp)))==NULL);
        l->num=n;
        p->q=l;
        if(!i)
        {
            head->after=p;
            p->ago=head;
            t=p;
            i=1;
        }
        else
        {
            t->after=p;
            p->ago=t;
            t=p;
        }
    }
    p->after=NULL;

    return head;
}

st *len_line(st *head)
{
    st *p=head;

    while(p->after)
    {
        p=p->after;
    }

    return p;
}

void line_sort(st *head,st *p,st *r)
{
    st *i,*j,*d;
    int x;

    if(check(p,r))
    {
        i=p->ago;
        x=r->q->num;
        d=p;
        for(j=p;j!=r;j=j->after)
        {
            if(j->q->num<=x)
            {
                i=i->after;
                if(i!=j)
                {
                    wap(head,i,j);
                }
            }
        }
        i=i->after;
        if(i!=r)
        {
            wap(head,i,r);
        }
        line_sort(head,p,i->ago);
        line_sort(head,i->after,r);
    }
}

void wap(st *head,st *a,st *b)
{
    tmp *t;

    t=a->q;
    a->q=b->q;
    b->q=t;
}

void print(st *head)
{
    while(head)
    {
        printf("%d ",head->q->num);
        head=head->after;
    }
    puts("");
}

int check(st *p,st *r)
{
    while(p)
    {
        if(p->after==r)
        {
            return 1;
        }
        p=p->after;
    }

    return 0;
}

void del_line(st *head)
{
    st *t=NULL;

    while(head)
    {
        t=head;
        head=head->after;
        free(t);
    }
    free(t);
}

   

占个座，小聚一会。

占位慢慢看

不知道有没有时间捣腾了
先占个楼再说

诶。。。

没太大的长进。。

不推荐用递归!

看不懂，占个位

struct a{
    unsigned int **ary; //地址表
    int cnt;//记录元素个数
};

_________________________________________________________________________________________
|   ary[0]  |   ary[1]   |            |            |            |........|   ary[cnt-1] |
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－--------－－--------－－---
      |            |            |           |            |                      |
  ____V___     ____V____    ____V____    ___V____     ___V___               ____V____
  |       | <- |        |<- |        |<- |       |<-  |      |            <-|        |
  |  st   |    |  st    |   |   st   |   |  st   |    |  st  |     ...      |  st    |
  |       |    |        |   |        |   |       |    |      |              |        |
  |       | -> |        |-> |        |-> |       |->  |      |->            |        |-> NULL
  ---------    ----------   ----------   ---------    --------              ----------
用数组的方式排列各元素，第K个元素: st *p = (st *)ary[k],利用cnt可以找到中位数

不知这样做能不能满足老大的要求。。。囧。。。
还有你的函数del_line的最后一个free应该去掉吧。。。

struct a{
    unsigned int **ary; //地址表
    int cnt;//记录元素个数
    st *head;//头   －－－》忘记加上这个了
};