Question

C++用链表做的冒泡排序（本人能力有限，基本跳不出数组的思路）求解

//冒泡排序链表#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
int main()
{
int n=1,i=0,temp=0;bool flag=false;
Node *head=new Node;
Node *p=new Node;
p=head;
cin>>n;
while(i<n)
{
cin>>p->data;
Node *q=new Node;
p->next=q;
p=q;p->next=NULL;
i++;
}
cout<<"before"<<endl;//排序前的顺序
p=head;
do
{
cout<<p->data<<" ";
p=p->next;
}while(p->next!=NULL);
cout<<endl;

p=head;//排序过程 for(i=0;i<n-1&&flag!=false;i++)
{
flag=false;
for(int j=0;j<n-1-i;j++)
{
if(p->data>p->next->data)
{
temp=p->data;//其实就是数组冒泡的思路
p->data=p->next->data;
p->next->data=temp;
p=p->next;
flag=true;
}
else
p=p->next;
}
}
cout<<"after"<<endl;//排序后的顺序 p=head;
do
{
cout<<p->data<<" ";
p=p->next;
}while(p->next!=NULL);
return 0;
}
输出发现实际上没有实现冒泡过程，求解

Answer 1

//链表排序中交换的是指针，不是数据交换。当数据量很大时，这种方法效率非常高，省去了数据交换时间
int main()
{
int n=1,i=0;
bool flag;//交换标志
Node *head=new Node;//创建链表头，不含数据的表头
Node *p;
p=head;//调整by linyingkaia
cin>>n;
while(i<n)
{
Node *q=new Node;
q->next=NULL;//增加 by linyingkaia
cin>>q->data;//调整by linyingkaia
p->next=q;
p=q;
i++;
}
cout<<"before"<<endl;
//排序前的顺序
p=head->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
//排序过程
while(flag)
{
p=head;
flag=false;
while(p->next !=NULL && p->next->next !=NULL)
{
if(p->next->data > p->next->next->data )
{
//修改指针，非交换数据,要注意指针修改顺序，最好先自己手工画个示意图，不然容易出错
Node *temp=p->next->next ;
p->next->next=temp->next;
temp->next=p->next;
p->next=temp;
flag=true;
}
p=p->next;
}
}
cout<<"after"<<endl;
//排序后的顺序
p=head->next ;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cin>>n;
return 0;
}

Answer 2

改成如下形式就可以了。
#include<iostream>
using namespace std;

struct Node{
int data;
Node *next;
};
int main()
{
int n=1,i=0,temp=0;
bool flag=true; //起始应该为true
Node *head=new Node;
Node *p;//去掉=new Node
p=head;
p->next = NULL;
cin>>n;
Node *q = NULL;
while(i<n)//这个地方要大改,改为带头结点的链表
{
q = new Node;
p->next = q;
p = q;
cin>>p->data;
p->next = NULL;
i++;
}
cout<<"before"<<endl;
//排序前的顺序
p=head;
while(p->next!=NULL)
{
cout<<p->next->data<<" ";
p=p->next;
}
cout<<endl;

//排序过程
for(i=0;i<n-1&&flag!=false;i++)
{
flag=false;
p=head->next;//指向第一个结点
for(int j=0;j<n-1-i;j++)
{
if(p->data>p->next->data)
{
temp=p->data;
//其实就是数组冒泡的思路
p->data=p->next->data;
p->next->data=temp;
p=p->next;
flag=true;
}
else
p=p->next;
}
}
cout<<"after"<<endl;
//排序后的顺序
p=head;
while(p->next!=NULL)
{
cout<<p->next->data<<" ";
p=p->next;
}
cout<<endl;
return 0;
}