C语言链表排序

＃include＂stdafx．h＂

＃include＜stdlib．h＞

／／创建一个节点，data为value，指向NULL

Node＊Create（intvalue）｛

Node＊head＝（Node＊）malloc（sizeof（Node））；

head－＞data＝value；

head－＞next＝NULL；

returnhead；

｝

／／销毁链表

boolDestroy＿List（Node＊head）｛

Node＊temp；

while（head）｛

temp＝head－＞next；

free（head）；

head＝temp；

｝

head＝NULL；

returntrue；

｝

／／表后添加一个节点，Create（value）

boolAppend（Node＊head，intvalue）｛

Node＊n＝Create（value）；

Node＊temp＝head；

while（temp－＞next）｛

temp＝temp－＞next；

｝

temp－＞next＝n；

return0；

｝

／／打印链表

voidPrint＿List（Node＊head）｛

Node＊temp＝head－＞next；

while（temp）｛

printf（＂％d－＞＂，temp－＞data）；

temp＝temp－＞next；

｝

printf（＂＼n＂）；

｝

／／在链表的第locate个节点后（头节点为0）插入创建的节点Create（value）

boolInsert＿List（Node＊head，intlocate，intvalue）｛

Node＊temp＝head；

Node＊p；

Node＊n＝Create（value）；

if（locate＜0）

returnfalse；

while（locate－－）｛

if（temp－＞next＝＝NULL）｛

temp－＞next＝Create（value）；

returntrue；

｝

temp＝temp－＞next；

｝

p＝temp－＞next；

temp－＞next＝n；

n－＞next＝p；

returntrue；

｝

／／删除第locate个节点后（头节点为0）的节点

boolDelete＿List（Node＊head，intlocate）｛

Node＊temp＝head；

Node＊p；

if（locate＜0）

returnfalse；

while（locate－－）｛

if（temp＝＝NULL）｛

returnfalse；

｝

temp＝temp－＞next；

｝

p＝temp－＞next－＞next；

free（temp－＞next）；

temp－＞next＝NULL；

temp－＞next＝p；

returntrue；

｝

／／获取链表长度（不包括头节点）

intSize＿List（Node＊head）｛

Node＊temp＝head；

intsize＝0；

while（temp－＞next）｛

temp＝temp－＞next；

size＋＋；

｝

returnsize；

｝

／／链表的三种排序（选择，插入，冒泡）

boolSort＿List（Node＊head）｛

intt＝0；

intsize＝Size＿List（head）；

／／选择排序

／＊for（Node＊temp＝head－＞next；temp！＝NULL；temp＝temp－＞next）｛

for（Node＊p＝temp；p！＝NULL；p＝p－＞next）｛

if（temp－＞data＞p－＞data）｛

printf（＂换％d和％d＼n＂，temp－＞data，p－＞data）；

t＝temp－＞data；

temp－＞data＝p－＞data；

p－＞data＝t；

｝

｝

｝＊／

／／插入排序

／＊for（Node＊temp＝head－＞next－＞next；temp！＝NULL；temp＝temp－＞next）｛

for（Node＊p＝head；p－＞next！＝NULL；p＝p－＞next）｛

if（p－＞next－＞data＞temp－＞data）

｛

printf（＂换％d和％d＼n＂，temp－＞data，p－＞next－＞data）；

t＝temp－＞data；

temp－＞data＝p－＞next－＞data；

p－＞next－＞data＝t；

｝

｝

｝＊／

／／冒泡排序

for（Node＊temp＝head－＞next；temp－＞next！＝NULL；temp＝temp－＞next）｛

for（Node＊p＝head－＞next；p－＞next！＝NULL；p＝p－＞next）｛

if（p－＞data＞p－＞next－＞data）｛

t＝p－＞data；

p－＞data＝p－＞next－＞data；

p－＞next－＞data＝t；

｝

｝

｝

return0；

｝

扩展资料：

return表示把程序流程从被调函数转向主调函数并把表达式的值带回主调函数，实现函数值的返回，返回时可附带一个返回值，由return后面的参数指定。

return通常是必要的，因为函数调用的时候计算结果通常是通过返回值带出的。如果函数执行不需要返回计算结果，也经常需要返回一个状态码来表示函数执行的顺利与否（-1和0就是最常用的状态码），主调函数可以通过返回值判断被调函数的执行情况。

可以把链表设计成循环链表，用冒泡排序
在排序前设计一个交换标记，如在循环过程中有交换，则修改这个标记变量，如果在一次循环(当前节点为刚开始时节点，表示循环了一次)中，交换标记没有被修改，则表明该数列已排好序。
现在给一个双向循环链表的排序程序给你，该程序用了双向冒泡排序(也就是鸡尾酒排序法)，希望对你有帮助
双向链表我用的鸡尾酒排序,也就是双向冒泡排序
#include
#define
LEN
sizeof(struct
list)
struct
list
//双向链表有两个指针域，一个指向前节点，一个指向后继节点
{struct
list
*lp;
//lp为前节点指针，rp为后继节点指针
int
x;
struct
list
*rp;};
int
n;
struct
list
*creat(void)
{struct
list
*head;
struct
list
*p1,*p2;
//两个节点指针，p1是当前新建节点指针，p2为p1的前一个节点
n=0;
p1=p2=(struct
list*)malloc(LEN);
//申请内存空间
scanf("%d",&p1->x);
head=NULL;
//先把头指针设置为空
while(p1->x!=0)
{n=n+1;
if(n==1){p1->lp=NULL;
head=p1;}
//把head指向链表的第一个节点并把首节点的lp设为NULL
else
{p1->lp=p2;
新建了一个节点，把它的lp指向前一个节点p2
p2->rp=p1;}
把前节点的rp指针指向刚建立的节点
p2=p1;
进行迭代，p1变成下一个新节点的后继节点
p1=(struct
list*)malloc(LEN);
//每次新建节点都要向系统申请内存空间
scanf("%d",&p1->x);
}
p2->rp=NULL;
把随后的节点后继指针设为空
return(head);
}
void
print(struct
list
*head)
{struct
list
*p;
printf("\nNow,Thess
%d
records
are
:\n",n);
p=head;
if(head!=NULL)
do
{printf("%d
",p->x);
p=p->rp;
//这个是个迭代过程，把p的后继节点变成下一次要输出的节点
}while(p!=NULL);
}
void
sort(struct
list
*head)
//排序用的双向排序法，提高排序效率
{struct
list
*p,*bottom,*top;
int
f,temp;
p=head;
if(head!=NULL)
{
f=1;
bottom=NULL;
//bottom和top为数列左右冒泡的边界节点
top=NULL;
while(f==1)
//f为交换标记，如果没交换则f没变就推出循环
{f=0;
do
{
if(p->x
>
(p->rp)->x)
{temp=p->x;
p->x=(p->rp)->x;
(p->rp)->x=temp;
f=1;
}
p=p->rp;
}while(p->rp!=top);
print(head);
top=p;
if((f==0)||(top==bottom))break;
f=0;
do
{
if(p->x<(p->lp)->x)
{
temp=p->x;
p->x=(p->lp)->x;
(p->lp)->x=temp;
f=1;
}
p=p->lp;
}while(p->lp!=bottom);
bottom=p;
if(top==bottom)break;
print(head);
}
}
}
void
main()
//所有的函数都做成全局函数，可以随时调用
{struct
list
*head;
head=creat();
//建立链表
print(head);
//输出链表
sort(head);
//排序
print(head);
//输出链表
system("PAUSE");}

虽然分很少.但是我给你做出来了.而且我不重视这分的.只是把这题当作作业自己做做.代码如下:
#include "iostream"
#include "fstream"
#include "string"
using namespace std;
//class List;
struct Student{
string ID;
string name;
string gender;
string speciality;
string RoomId;
};

class ListNode{
public:
//friend class List;
ListNode(){}
ListNode(Student a):data(a),link(NULL){}
void SetNode(ListNode *temp){this->link=temp;}
friend int find(string ID2);
friend void sort();
friend void changeNode(ListNode *a,ListNode *b);
friend void printf();
friend void read();
private:
Student data;
ListNode *link;
};
ListNode *first;

void printf(){
ListNode *a=first;
while(a)
{
cout<data.ID<<" "<data.name<<" "<data.gender<<" "<data.speciality
<<" "<data.RoomId< a=a->link;
}
}

void changeNode(ListNode *a,ListNode *b){
Student temp;
temp=a->data;a->data=b->data;b->data=temp;
}

int find(string ID2){
ListNode *a=first;
while(a)
{if(a->data.ID==ID2){cout<<"Find:"< cout<data.ID<<" "<data.name<<" "<data.gender<<" "<data.speciality
<<" "<data.RoomId< return 1;
}
else a=a->link;
}
cout<<"无此记录!"< return 0;
}

void sort(){
ListNode *a=first,*b,*c;
while(a)
{ c=a;
b=a->link;
while(b)
{
if(c->data.ID>b->data.ID)c=b;
b=b->link;
}
if(a!=c)changeNode(a,c);
a=a->link;
}
printf();
}

/*class list{
public:
list(Listnode a){first=a;}
private:
ListNode *first;
};*/

void read(){
string s;
Student head;
head.gender="0";
head.ID="0";
head.name="0";
head.RoomId="0";
head.speciality="0";
ListNode *headNode=new ListNode(head);
first=headNode;
ifstream input;
input.open("c:\\data\\studentdata.txt");
if(!input)cout<<"error!"< else while(input>>s)
{ Student newstudent;
newstudent.ID=s;
input>>s;
newstudent.name=s;
input>>s;
newstudent.gender=s;
input>>s;
newstudent.speciality=s;
input>>s;
newstudent.RoomId=s;
ListNode *newnode=new ListNode(newstudent);
headNode->SetNode(newnode);
headNode=headNode->link;

}
first=first->link;

}
int main()
{
read();
cout<<"读取完毕!"< printf();
while(1){
cout<<"1.我要查询"< cout<<"2.我要排序"< cout<<"3.我要退出"< int n;
cin>>n;
if(n==1){string findID;
cout<<"请输入要查询的学号:";
cin>>findID;
find(findID);
}
else if(n==2){sort();}
else if(n==3)exit(0);
}
}
在VC++2008编译上通过.本人花了二小时做出来的,绝对达到你的要求了.在别的编译器上有问题的可以自己调试,应该问题不大.别忘了记得建立文件.而且文件里的格式如下:
004 wk M computer 116
001 dd F computer 114
002 as F english 113
003 aq M computer 114

同学，给你一段代码，里面涵盖了链表的冒泡排序！
#include
#include
typedef struct node
{
int data;/*data代表成绩分数*/
struct node *next;
}LNode,*LinkList;
LinkList Creat(void)/*创建链表，结束标志为当输入的数据为0!*/
{
LinkList H,p1,p2;
int n;
n=0;
p1=p2=(LinkList)malloc(sizeof(LNode));
printf("输入数据：");
scanf("%d",&p1->data);
H=NULL;
while(p1->data!=0)
{
n=n+1;
if(n==1)
H=p1;
else
p2->next=p1;
p2=p1;
p1=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p1->data);
}
p2->next=NULL;
return(H);
}
LinkList Sort(LinkList SL)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/
{
LinkList p,q;
int temp;
for(p=SL;p!=NULL;p=p->next)
{
for(q=p->next;q!=NULL;q=q->next)
{
if(p->data>q->data)
{
temp=q->data;
q->data=p->data;
p->data=temp;
}
}
}
return SL;
}

int main()
{
LinkList L,S,K;
L=Creat();
printf("初始化的单链表数据序列为:\n");
for(S=L;S!=NULL;S=S->next)
printf("%d ",S->data);
Sort(L);
printf("\n按递增顺序排序后的序列为:\n");
for(K=L;K!=NULL;K=K->next)
printf("%d==>",K->data);

return 0;
}
希望对你有帮助，如果有问题可以继续找我！

方法很多，我在这给楼主提供几种方案

我定义的结构体类型（注意我建的是空表头！）
typedef struct node
{
int num;
struct node *next;
}Node,*Link;

1。最笨的办法“冒泡排序”

方法一：
void NodSwap(Link P, Link A, Link B)
{
P->next = B;
A->next = B->next;
B->next = A;

return;
}

Link SortList(Link head)
{
int i;
int flag;
Link p = NULL;

for (i=0; ; i++)
{
flag = 0;

for (p=head; p->next->next != NULL; p=p->next)
{
if (p->next->num > p->next->next->num)
{
flag = 1;
NodSwap(p, p->next, p->next->next);
}
}

if (flag == 0)
{
break;
}
}

return (head);
}

方法二：
for (p=head->next; p->next->next!=NULL; p=p->next)
{
for (q=p->next; q->next!=NULL; q= q->next)
{
if (p->num > q->num)
{
定义中间变量，交换结构体里的所有成员
}
}
}

2。插入排序
Link SortList(Link head)
{
Link r = head;
Link SL = NULL;

while (r != NULL)
{
Link t = r->next;
Link cp = SL;
Link ap = NULL;

while (cp != NULL)
{
if(r->num < cp->num)
{
break;
}
else
{
ap = cp;
cp=cp->next;
}
}

if (ap == NULL)
{
r->next = SL;
SL = r;
}
else
{
r->next = cp;
ap->next = r;
}
r = t;
}

return SL;
}

3.通过建表直接进行排序

这个我就不写了，楼主可以自己试试，难度也不是很大

如果对你有所帮助，请记得采纳最佳答案，谢谢！