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);
}