C语言链表排序 C语言链表如何排序

C语言链表排序

/*
==========================
功能：直接插入排序(由小到大)
返回：指向链表表 头的指针
==========================
*/
/*
直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值
（就是用它排序的字段，我们取学号num为键值）排好序的，对于节点n在
这个序列中找插入位置，使得n插入后新序列仍然有序。按照这种思想，依次
对链表从头到尾执行一遍，就可以使无序链表变为有序链表。

单向链表的直接插入排序图示：
---->[1]---->[3]----> [2]...---->[n]---->[NULL]（原链表）
head 1->next 3->next 2->next n->next

---->[1]---->[NULL]（从原链表中取第1个节点作为只有一个节点的有序链表）
head
图11

---->[3]---->[2]...---->[n]---->[NULL]（原链表剩下用于直接插入排序的节点）
first 3->next 2->next n->next
图12

---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
head 1->next 2->next 3->next n->next

图13：有N个节点的链表直接插入排序

1、先在原链表中以第一个节点为一个有序链表，其余节点为待定节点。
2、从图12链表中取节点，到图11链表中定位插入。
3、上面图示虽说画了两条链表，其实只有一条链表。在排序中，实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
这一点请读者务必搞清楚，要不然就可能认为它和上面的选择排序法一样了。
*/
struct student *InsertSort(struct student *head)
{
struct student *first /*为原链表剩下用于直接插入排序的节点头指针*/
struct student *t /*临时指针变量：插入节点*/
struct student *p /*临时指针变量*/
struct student *q /*临时指针变量*/

first = head->next /*原链表剩下用于直接插入排序的节点链表：可根据图12来理解。*/
head->next = NULL /*只含有一个节点的链表的有序链表：可根据图11来理解。*/

while (first != NULL) /*遍历剩下无序的链表*/
{
/*注意：这里for语句就是体现直接插入排序思想的地方*/
for (t = first, q = head ((q! = NULL) && (q->num < t->num)) p = q, q = q->next) /*无序节点在有序链表中找插入的位置*/

/*退出for循环，就是找到了插入的位置*/
/*注意：按道理来说，这句话可以放到下面注释了的那个位置也应该对的，但是就是不能。原因：你若理解了上面的第3条，就知道了。*/
first = first->next /*无序链表中的节点离开，以便它插入到有序链表中。*/

if (q == head) /*插在第一个节点之前*/
{
head = t
}
else /*p是q的前驱*/
{
p->next = t
}
t->next = q /*完成插入动作*/
/*first = first->next*/
}
return head
}

C语言链表如何排序

可以把链表设计成循环链表，用冒泡排序
在排序前设计一个交换标记，如在循环过程中有交换，则修改这个标记变量，如果在一次循环（当前节点为刚开始时节点，表示循环了一次）中，交换标记没有被修改，则表明该数列已排好序。
现在给一个双向循环链表的排序程序给你，该程序用了双向冒泡排序（也就是鸡尾酒排序法），希望对你有帮助
双向链表我用的鸡尾酒排序,也就是双向冒泡排序
#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指向前一个节点p 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(" Now,Thess %d records are : ",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")

}

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

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

C语言链表排序？？？？？？？

void sort(struct xxx *pHead)  //结构体名随便写的哈，调用时传入头指针，没问题吧？
{
struct xxx *pTemp1=pHead,*pTemp2=pHead    //要用两个临时指针的
int t //交换两数值的中间变量，这里假设它是整型
for(pTemp1->pNext!=NULLpTemp1=pTemp1->pNext)   //pNext是移位的指针，创建链表时有了
for(pTemp2=pTemp1->pNextpTemp2!=NULLpTemp2=pTemp2->pNext)//双重循环，交换排序
{
if(pTemp1->iNUMiNUM)  //如果后一个数大于前一个数
{
t=pTemp1->iNUM //交换两数
pTemp1->iNUM=pTemp2->iNUM
pTemp2->iNUM=t
}
}
printf("the numbers in the list are:")
for(pTemp1=pHeadpTemp1!=NULLpTemp1=pTemp1->pNext)//将排序后的链表输出
{
printf("%d",pTemp1->iNUM)
}
}
纯手打，望采纳！