c++ 链表快速排序
#include<iostream>
using namespace std;
struct Node
{
int data;
struct Node * prior;
struct Node * next;
};
void Print(Node * head);
Node * Copy(Node * head);
Node * Partion(Node * front,Node * end);
void Qsort(Node * head);
void Qsort1(Node * front,Node * end);
void main()
{
int n=6;
int a[100]={4,5,2,0,8,3};
Node * head = new Node;
Node * r = head;
for (int i=0;i<n;i++)
{
Node * s = new Node
s->data = a[i]; r->next = s;
s->prior = r;
r = s; }
r->next = NULL; Print(head);
}
Node * Partion(Node * front,Node * end)
{
Node * p = front;
Node * q = end;
int i,j;
Node * t;
int s=p->data;
while(1)
{
i=100;j=100;
t=p;
while(t->next)
{
i--;
t=t->next;
}
t=q;
while(t->next)
{
j--;
t=t->next;
}
if(i>=j)
{
p->data=s;
return p;
}
while((q->data>s)&&(i<j))
{
q=q->prior;
j--;
}
p->data=q->data;
while((p->data<s)&&(i<j))
{
p=p->next;
i++;
}
q->data=p->data;
}
}
void Qsort(Node * head)
{
Node * head1 = Copy(head);
Node * front = head1->next;
Node * end = head1->next;
while(end->next)
{
end = end->next;
}
Qsort1(front,end);
Print(head1);
}
void Qsort1(Node * front,Node * end)
{int i=100,j=100;
Node * t=front;
while(t->next)
{
i--;
t=t->next;
}
t=end;
if(i<j)
{
Node * pivotloc = Partion(front,end);
Qsort1(front,pivotloc->prior);
Qsort1(pivotloc->next,end);
}
}
//链表的复制
Node * Copy(Node * head)
{
Node * head1 = new Node;
Node * p = head1;
Node * q = head->next;
while(q)
{
Node * s = new Node;
s->data = q->data;
p->next = s;
s->prior = p;
p = s;
q=q->next;
}
p->next=NULL;
return head1;
}
//打印结果
void Print(Node * head)
{
Node * t=head->next;
while(t)
{
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
程序有错误，求助啊
P.S:我会用数组做，但是作业要求是链表,有更简单的链表代码也可以发上来啊
答案： //用c语言编写的，里面实现了链表排序。你自己去看吧。#include "stdio.h"
#include"stdlib.h"
#define NULL 0
#define error 0
#define ok 1
#define overflow -2
#define infeasible -1
//类型定义
typedef int Status;
typedef int ElemType;
//定义链表的存储结构
typedef struct LNode
{int data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; //链表的类型
Status GetElem_l(LinkList L, int i , ElemType &e)
//L为带头结点的单链表，当第i 个元素存在时，其值赋给e.
{int j;
LinkList p ;
p=L->next; j=1;
while(p&&j<i) //顺序找第i个元素.
{p=p->next; ++j;}
if(!p||j>i) return error;
e=p->data;
return ok;
}
//逆序创建链表
void CreatList_L1(LinkList &L,int n) //n为元素个数，L为头结点
{int i;
LinkList p;
L=(LinkList)malloc(sizeof(LNode)); //生成头结点
L->next=NULL;
for(i=n;i>0;i--) //链头插入法
{ p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
//正序创建单链表
void CreatList_L2(LinkList &L,int n ) ///n为元素个数，L为头结点
{int i ;
LinkList p,q;
L=(LinkList )malloc(sizeof(LNode));
q=L;
for(i=0;i<n;i++) //链尾插入法
{ p=(LinkList )malloc(sizeof(LNode));
scanf("%d",&p->data);
q->next=p;
q=p;
}
q->next=NULL;
}
//输出链表
void print(LinkList L)
{LinkList p;
p=L->next;
while(p)
{printf("%d ",p->data);
p=p->next;
}
}
//链表的插入操作
int ListInsert(LinkList &L,int i,int e)
{LinkList p,s;
int j;
p=L;j=0;
while(p&&j<i-1)
{p=p->next; ++j;}
if(!p||j>i-1) return error;
s=(LinkList)malloc(sizeof(LNode));
s->data=e; s->next=p->next;
p->next=s;
return ok;
}
//链表的删除操作
int ListDelete(LinkList &L,int i,int &e)
{LinkList p,q;
int j;
p=L; j=0;
while(p->next&&j<i-1)
{ p=p->next; ++j;}
if(!(p->next)||j>i-1) return error;
q=p->next;p->next=q->next;
e=q->data;free(q);
return ok;
}
//对链表的元素进行排序
Status sortlinklist(LinkList &L)
{LinkList p,q,r;
ElemType t;
p=L->next; //p指向链表第一个元素结点
while(p->next!=NULL)
{q=L->next; //q指向链表第一个元素结点
while(q->next!=NULL)
{r=q->next;
if(q->data>r->data) //相邻两个元素比较、交换
{t=q->data; q->data=r->data; r->data=t; }
q=q->next;
}
p=p->next;
}
return ok ;
}
void mergelist_l(LinkList la, LinkList &lb, LinkList &lc)
{LinkList pa,pb,pc;
pa=la->next; pb=lb->next ;
lc=pc=la;
while(pa&&pb)
if(pa->data <=pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
pc->next=pa?pa:pb;
free(lb);
}
//主函数通过调用创建、插入、删除用输出函数完成链表的基本操作
void main()
{LinkList L1,L2,L3;
int n,ins,del,i;
//创建一个先进先出单链表
printf("please input fifo linklist's node number n:\n");
scanf("%d",&n);
printf("please input the linklist %d nodes data \n",n);
CreatList_L2(L2,n);
print(L2);
printf("\n");
//创建一个后进先出单链表
printf("please input lifo linklist's node number n:\n");
scanf("%d",&n);
printf("please input the linklist %d nodes data \n",n);
CreatList_L1(L1,n);
print(L1);
printf("\n");
//对链表进行插入操作
printf("please input the insert node's locate i and value e\n");
scanf("%d%d",&i,&ins);
ListInsert(L1,i,ins);
print(L1);
printf("\n");
//对链表进行删除操作
printf("please input the delete node's locate i\n");
scanf("%d",&i);
ListDelete(L1,i,del);
print(L1);
printf("\n%d\n",del);
//对链表进行排序
sortlinklist(L1);
printf("\n the L1 list's sort is:\n");
print(L1);
printf("\n the L2 list's sort is:\n");
sortlinklist(L2);
print(L2);
//对链表进行合并
printf("\n the merge result is : \n" );
mergelist_l(L1,L2,L3);
print(L3);
}
上一个：C++语言好学吗？
下一个：如何学好C++语言软件编程？
