一趟快排(循环链表)源程序需要修改
下面的程序为什么不能排序阿,这样编行吗?
typedef struct lnode
{
int data1;
int data2;
int ncount; //记录当前节点是第几个节点,以便快速排序
struct lnode *next; //记录后继
struct lnode *front; //记录前驱
} lnode, *linklist;
//链表的初始化
void init_list(lnode * &l)
{
linklist p;
p=(lnode *) malloc (sizeof(lnode)) ;
if(!p)
{
cout<<"overflow!"<<endl;
return;
}
l=p;
p->front=p;
p->next=p;
p->ncount++;
return;
}
void quicksort(linklist &l,linklist start,linklist end)
{
linklist i=start;
linklist j=end; //设置左右指针
int value1=start->data1; //以多项式的幂作为关键字进行排序,并保存枢轴,幂
int value2=start->data2; //也是关键字
// cout<<value2<<endl; //ceshi
if(start->ncount<end->ncount)
{
// cout<<"正确"<<endl; //ceshui
do
{
while(i->ncount<j->ncount && j->data2>=value2)
j=j->front; //寻找大于枢轴的值,从表尾到表头
i->data1=j->data1;
i->data2=j->data2;
cout<<i->data2<<endl;
while(i->ncount<j->ncount && i->data2<=value2)
i=i->next; //寻找小于枢轴的值,从表尾到表头
j->data1=i->data1;
j->data2=i->data2;
}while(i->ncount<j->ncount); //一趟快排
i->data1=value1;
i->data2=value2; //到此实现了一趟快排
cout<<"枢轴:"<<value2<<endl;
//此时,start,end已经指向同一个单元,所以有下面的语句
//将枢轴填入其应在的位置
quicksort(l,start,j->front);
quicksort(l,j->next,end);
} //结束外层if语句
} //结束函数