c链表排序算法

⑴ 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；

｝

(1)c链表排序算法扩展阅读：

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

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

⑵ C语言做链表的排序

主要修改了sort函数，采用冒泡排序算法进行排序的。
你其他的两个函数写的不错，就sort函数写的有问题，已经很不错了。
注意：程序结束，最好对链表进行销毁，否则，内存永远也不会释放，导致内存泄漏了。

修改如下：

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

#define N 5
typedef struct node
{
char name[20];
int score;
struct node *link;
}stud;

stud *sort(stud *head) /*排序函数*/
{
stud *temp=NULL; //默认为NULL,也就是链表的结尾
stud *ptr1=head;
stud *ptr2=head->link;

while(ptr1->link!=temp)//(ptr1!=NULL)
{
//ptr2=ptr1->link; //放在循环体下面了
while(ptr2->link!=temp)//(ptr2!=NULL)
{
if(ptr1->link->score > ptr2->link->score) //(ptr1->score > ptr2->score)
{//交换 ptr1->link和ptr2->link，而不是ptr1和ptr2，否则无法交换
ptr1->link=ptr2->link;
ptr2->link=ptr2->link->link;//temp->link=ptr2;
ptr1->link->link=ptr2;//ptr2->link=ptr1;
}
ptr1=ptr1->link;//ptr2=ptr2->link;
ptr2=ptr1->link;//从上面移动下来的
}
temp=ptr2;//新加的
ptr1=head;//ptr1=ptr1->link;
ptr2=ptr1->link;//从上面移动下来的
}
return (head);
}

stud * creat(int n)
{
stud *p,*h,*s;
int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
h->name[0]='\0';
h->link=NULL;
p=h;
for(i=0;i<n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!");
exit(0);
}
s->link=NULL;//p->link=s; //跟下句对调了一下，为了把相关的代码放在一起
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s->name);
printf("请输入第%d个人的分数",i+1);
scanf("%d",&s->score);
p->link=s; //s->link=NULL;//跟上句对调了一下，为了把相关的代码放在一起
p=s;
}
return(h);
}

void print(stud *h)
{
stud *p;

p=h->link;
printf("数据信息为：\n");
while(p!=NULL)
{
printf("%s ",&*(p->name));
printf("的分数为%d\n",p->score);
p=p->link;
}
}

void main()
{
stud *head;
head=creat(N);
head=sort(head);
print(head);
getchar();
}

⑶ C语言链表排序问题

C指的是空白的临时节点 是NULL么 你交换的地方就有问题 如果c是NULL c->next = a 就段错误了，而且在交换块的代码也不能用头指针， 你的代码实现有挺多不合理的地方，
如果是 a->b->c->d 交换b c
b->next = c->next; //b->d
a->next = c //a->c
c->next = b //c->b 连起来就是 a->c->b->d
所以单链表交换节点还需要一个变量 就是上面我说的a， 每次循环还要a = a->next
你的d是固定的 不对 指针往下走没有判空 有越界

⑷ C语言,链表怎么从大到小排序

//创建data型结构，为生成链表做准备
struct data
{
int value;
data *next;
};

//对链表进行排列的函数
void line(data *p,int n)
{ int temp,i,j;
data *tp;
for(i=0;i<n-1;i++)
for(j=0,tp=p;j<n-i-1;j++,tp=tp->next)
{ if(tp->value>tp->next->value)
{temp=tp->next->value;
tp->next->value=tp->value;
tp->value=temp;
}
}
}
以上是冒泡法对链表排序的例子；
//输出答案的函数
void answer(data *p)
{ while(p!=NULL) {
cout<<p->value<<endl;
p=p->next;

}
}
以上是遍历链表的函数p是链表的头指针

⑸ C语言单向链表排序如何实现

struct student* printf_sort(struct student *head)
{
struct student *p1,*p2,*ptemp,*pfinished=NULL;
for(p1=head;p1->next!=pfinished;)//对链表进行从大到小排序（这里用冒泡法）
//p1使之总是指向头结点，pfinished使之总是指向已排序好的最前面的结点
//ptemp作为中介，保存p2的上一个结点
{
for(p2=p1;p2->next!=pfinished;)
{
if(p2->num<p2->next->num)//p2的值小于p2->next的值，交换 {
if(p2==p1)//头结点要交换
{
p1=p2->next;
p2->next=p1->next;
p1->next=p2;
ptemp=p1;
}
else
{
ptemp->next=p2->next;
ptemp=p2->next;
p2->next=ptemp->next;
ptemp->next=p2;
}
}
else//不需要交换，则p2、ptemp前进1位
{
ptemp=p2;
p2=p2->next;
}
}
pfinished=p2;
}
}

⑹ 请问高手，怎样用C语言对一个链表排序

首先要确定一种排序算法，常用的几种有：

insert sort 插入排序

merge sort 归并排序

quick sort 快速排序

bubble sort 冒泡排序

heap sort 堆排序

radix sort 基数排序

算法性能的优劣取决于时间复杂度，一般来说，时间复杂度好的code编译起来较为麻烦，编译过程简单的算法时间复杂度相对较差.

insert sort 的时间复杂度较差，但是编译简单，也是最常用的一种排序算法，下面是C＋＋的inplementation(递归):

typedef struct node* LIST;

struct node {

int key;

node* next;

};

//需要一个插入函数

LIST _insert (LIST L, node* pNew)

{

if (L == NULL)

return pNew;

if (pNew->key < L->key)

{

pNew->next = L;

return pNew;

}

L->next = _insert (L->next, pNew);

return L;

}

LIST _insertsort (LIST L)

{

if (L == NULL) //空链，无须排序，返回.(递归的跳出条件）

return L;

node* tail = L->next;

L->next = NULL;

return _insert (_insertsort(tail), L);

}

⑺ c和c++中如何对链表进行排序呢

你说的链表是什么链表?
单链表、循环链表、双向链表?
其实没什么难的，主要是指针指来指去容易糊涂
你可以找本数据结构的书，找到上面的链表操作，在草稿纸上画个图，就明白了。
链表插入排序的算法:
备注:key
为链表节点的关键码;
link为节点的链接指针
getKey()
取当前节点的关键码
getLink()取当前节点的链接指针
setKey()
给当前节点的关键码重新赋值
setLink()给当前节点的指针重新赋值
int
LinkInsertSort
()
{
list.Vector[0].setKey(MaxNum);
list.Vector[0].setLink(1);
list.Vector[1].setLink(0);//初始化，形成只有头节点的循环链表
for(int
i=2;i<=list.CurrentSize.i++)//向一个有序的链表中插入一个节点，需要对链表进行检索，currentsize为当前链表长度;
{
int
current=list.Vector[0].getLink();//current
指向当前节点
int
pre
=
0;//pre指向current的前驱
while
(list.Vector[current].getKey()<=
List.Vector[i].getKey())//查找插入位置
{
pre
=
current;current
=
list.Vector[current].getLink();
//
每查找完一个节点，pre要跟上current，current要指向下一个节点。
}//以下操作是节点i插入pre
与
current之间
List.Vector[i].setLink(current);//将节点i的后继指针指向current
list.Vector[pre].setLink(i);//
将current的前一节点的后继指针指向i
}
}

⑻ C语言 链表怎么排序 急求大虾

排序！这是一个庞大的话题，有插入排序，插入排序又分直接插入排序、希尔排序等，还有交换排序，交换排序有冒泡排序、快速排序，还有选择排序，有直接选择排序、归并排序等等…而且还不断的有新的排序方法产生…不知道你要哪一种…新手一般用选择排序和冒泡排序，方法简单，两重循环。

⑼ 链表选择排序的C语言算法实现

common.h
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
linklist.h
#include common.h
typedef int ElemType;
typedef struct Node /*结点类型定义*/
{
ElemType data;
struct Node * next;
}Node, *LinkList; /* LinkList为结构指针类型*/
void CreateFromTail(LinkList L)
{
Node *r, *s;
char c;
int flag =1; /*设置一个标志，初值为1，当输入$时，flag为0，建表结束*/
r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/
}
}
} 尾插法创建链表程序
/*_*====尾插法创建链表，返回链表头指针====*_*/
LinkList CreateFromTail2()
{
LinkList L;
Node *r, *s;
int c;
int flag =1;
L=(Node * )malloc(sizeof(Node));
L->next=NULL;
r=L;
while(flag)
{
scanf(%d,&c);
if(c!=-1)
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;
}
}
return L;
} void linkSort(LinkList l)
{
Node *p,*q,*m,*n;
Node *temp1,*temp2;
if(l->next==NULL)
printf(NO LINKLIST!!!);
else
{
p=l;q=l->next;
while(q->next!=NULL)
{
m=p->next;
n=q->next;
temp1=m;
while(temp1->next!=NULL)
{
if(temp1->next->data<q->data && temp1->next->data<n->data)
{
m=temp1;n=temp1->next;
}
temp1=temp1->next;
}/*_*====此循环用于找到基准(q)以后的序列的最小的节点=====*_*/
if(m!=p->next || (m==p->next && m->data>n->data))
{
p->next=n;
p=n;
m->next=q;
m=q;
q=q->next;
n=n->next;
p->next=q;
m->next=n;
}/*_*======此条件用于交换两个节点*_*/
else
{
p=p->next;
q=q->next;
}/*_*======此条件用于没有找到最小值时的p，q后移操作*_*/
}/*_*=====外循环用于从前往后扫描，通过移动p,q指针实现=======*_*/
temp2=l->next;
printf(List after sorting is: );
while(temp2!=NULL)
{
printf(%5d,temp2->data);
temp2=temp2->next;
}
}
printf( );
} void main()
{
Node *temp3;
LinkList l;
printf( =====(end by -1)====== press enter after input the nember each time: );
l=CreateFromTail2();
temp3=l->next;
if(temp3==NULL)
printf(NO LINKLIST!!!);
else
{
printf(List before sorting is: );
while(temp3!=NULL)
{
printf(%5d,temp3->data);
temp3=temp3->next;
}
}
printf( );
linkSort(l);
}