鏈表選擇排序演算法

A. 以單鏈表為存儲結構，編寫簡單選擇排序演算法（需預先創建符合要求的單鏈表）

選擇排序：從頭至尾掃描序列，找出最小的一個元素，和第一個元素交換，接著從剩下的元素中繼續這種選擇和交換方式，最終得到一個有序序列。

出這題的人是個坑貨，鏈表交換很麻煩。
每次遍歷找最小值時候 還要用一個指針定位到它前面一個， 才好交換。

B. 如何用交換鏈表節點的方式對鏈表進行選擇法排序

//鏈表的選擇排序，以key為關鍵字進行排序
//交換整個節點（ data key..so on）
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int key;
int data;
//so..on
struct node*pro;
struct node*next;
}*linklist;
typedef struct node mylist;
//Create 函數創建鏈表並且給數據域賦值
// data 用首項為2 的公差為5的數組賦值
//key 為用戶輸入的數值 當輸入-1時代表輸入完畢
//輸入時會看不到data的值
linklist Create()
{
linklist head,temp;
linklist p;
int num;
int num2=2,step=5;
head=(linklist)malloc(sizeof(mylist));
head->key=-1;
temp=head;
head->pro=NULL;
scanf("%d",&num);
while(num!=-1)
{
p=(linklist)malloc(sizeof(mylist));
/*temp->next=p;
p->pro=temp;*/
p->key=num;
p->data=num2;
temp->next=p;
p->pro=temp;
temp=p;
scanf("%d",&num);
num2+=step;
}
p->next=NULL;
return head;

}
int listlength(linklist head)
{
linklist p=head->next;
int n=0;
while(p!=NULL)
{
n++;
p=p->next;
}
return n;

}
void show(linklist head)
{
linklist p=head->next;
while(p)
{
printf("(%d,%d) ",p->data,p->key);
p=p->next;
}
printf("\n");

}
linklist findmax(linklist head)
{
linklist imax=NULL;
linklist p=head->next;
linklist prenode=head;
imax=p;
while(p)
{

if(p->key>=imax->key)
{
prenode=p->pro;
imax=p;
}
p=p->next;
}
/*假刪除並沒有free
只是讓key最大的節點在這個表中消失，
並返回在另一個表中出現*/
prenode->next=imax->next;
if(imax->next)
imax->next->pro=prenode;

return imax;
}
linklist sort(linklist head)
{
linklist head2,newmax;
int length=listlength(head);
printf("length=%d\n",length);
head2=(linklist)malloc(sizeof(mylist));
head2->next=NULL;
head2->pro=NULL;
for(int i=0;i<length;i++)
{
newmax=findmax(head);
if(newmax!=NULL)
{
newmax->next=head2->next;
if(head2->next)
{
head2->next->pro=newmax;

}
newmax->pro=head2;
head2->next=newmax;
}
}
free(head);
return head2;

}
void main()
{
linklist p,p1;
p=Create();
show(p);

p1=sort(p);
show(p1);

}

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

D. 設計一個用鏈表表示的直接選擇排序演算法，並用程序實現

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
typedef struct VNode
{
int info;
struct VNode *next_node;
}Node;
void input(Node*head, int number)
{
if(number!=0)
{
int i;
Node *t;
t=(Node *)malloc(sizeof(Node));
head->next_node=t;
scanf("%d",&i);
t->info=i;
input(t,number-1);
}
}
void output(Node*head, int count)
{
Node *t;
if(count!=0)
{
t=head->next_node;
printf("%d ",t->info);
output(t,count-1);
}
}
void select(Node*head, int num)
{
int tem=0;
if(num!=0)
{
int min_node;
Node *t;
Node *r;
Node *q;
t=head->next_node;
r= head->next_node;
q=head;
min_node= t->info;
for(int i=0;i<num;i++)
{
if(min_node>t->info)
{
min_node= t->info;
r=t;
tem=i;
}
t=t->next_node;
}
for(int j=0;j<tem;j++)
q=q->next_node;
q->next_node=r->next_node;
r->next_node=head->next_node;
head->next_node=r;
select(head->next_node,num-1);
}
}
int main()
{
int num;
Node *head;
head=( Node *)malloc(sizeof(Node));
printf("請輸入序列數據的個數：");
scanf("%d",&num);
printf("請輸入序列的數據：\n");
input(head,num);
printf("\n選擇排序後的序列為：\n");
select(head,num);
output(head,num);
getch();}

E. 以單鏈表為存儲結構實現簡單選擇排序的演算法

單向鏈表的相關操作
實現功能：
1. 創建一個新鏈表。

2. 插入節點。

3. 刪除節點。
4. 插入法排序鏈表（從小到大）。

5. 選擇法排序鏈表（從小到大）。

6. 顯示當前鏈表。

0. 退出程序。

代碼見參考資料

F. 對已經建好的單鏈表排序 （求演算法）要准確

void SelectSort_LinkList(LinkList H)//選擇排序，帶頭結點的單鏈表
{
int temp;
LNode*p=H->next,*q,*s;

if(p==NULL)
{
printf("空表\n");
return;
}
while(p->next!=NULL)
{
q=p;
s=p->next;
while(s!=NULL)
{
if(q->data>s->data)
q=s;
s=s->next;
}
if(q!=p)
{
temp=q->data;
q->data=p->data;
p->data=temp;
}
p=p->next;
}
}

G. 鏈表的選擇排序

C語言

經典演算法－－單鏈表選擇排序第一種：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("輸入數字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void paixu(Linklist head)
{Linklist p,q,small;int temp;

for(p=head->next;p->next!=NULL;p=p->next)
{small=p;
for(q=p->next;q;q=q->next)
if(q->data<small->data)
small=q;
if(small!=p)
{temp=p->data;
p->data=small->data;
small->data=temp;}
} printf("輸出排序後的數字:\n");
output(head);
} void main()
{Linklist head;
int x,j,n;
printf("輸入數字的個數(n):\n");
scanf("%d",&n);
head=creat(n);
printf("輸出數字:\n");
output(head);
printf("已排序的數字:\n");
paixu(head);
}
第二種：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("輸入數字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} Linklist selectsort(Node *g)
{ Node *p,*q,*t,*s,*h;
h=(Node *)malloc(sizeof(Node));
h->next=g;
p=h;
while(p->next->next!=NULL)
{
for(s=p,q=p->next;q->next!=NULL;q=q->next)
if(q->next->data<s->next->data)
s=q;
if(s!=q)
{
t=s->next;
s->next=t->next;
t->next=p->next;
p->next=t;
}
p=p->next;
}
g=h->next;
free(h);
return g;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void main()
{Linklist head;
int x,j,n;
printf("輸入數字的個數(n):\n");
scanf("%d",&n);
head=creat(n);
printf("輸出數字:\n");
output(head);
head=selectsort(head);
printf("已經排序的數字:\n");
output(head);
}

H. 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；
｝
(8)鏈表選擇排序演算法擴展閱讀：
return表示把程序流程從被調函數轉向主調函數並把表達式的值帶回主調函數，實現函數值的返回，返回時可附帶一個返回值，由return後面的參數指定。
return通常是必要的，因為函數調用的時候計算結果通常是通過返回值帶出的。如果函數執行不需要返回計算結果，也經常需要返回一個狀態碼來表示函數執行的順利與否（-1和0就是最常用的狀態碼），主調函數可以通過返回值判斷被調函數的執行情況。

I. C語言的鏈表怎麼排序

==========================
功能：選擇排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/

/*
選擇排序的基本思想就是反復從還未排好序的那些節點中，
選出鍵值（就是用它排序的欄位，我們取學號num為鍵值）最小的節點，
依次重新組合成一個鏈表。

我認為寫鏈表這類程序，關鍵是理解：
head存儲的是第一個節點的地址，head->next存儲的是第二個節點的地址；
任意一個節點p的地址，只能通過它前一個節點的next來求得。

單向鏈表的選擇排序圖示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鏈表）
head 1->next 3->next 2->next n->next

---->[NULL]（空鏈表）
first
tail

---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序後鏈表）
first 1->next 2->next 3->next tail->next

圖10：有N個節點的鏈表選擇排序

1、先在原鏈表中找最小的，找到一個後就把它放到另一個空的鏈表中；
2、空鏈表中安放第一個進來的節點，產生一個有序鏈表,並且讓它在原鏈表中分離出來（此時要注意原鏈表中出來的是第一個節點還是中間其它節點）；
3、繼續在原鏈表中找下一個最小的，找到後把它放入有序鏈表的尾指針的next,然後它變成其尾指針；
*/
struct student *SelectSort(struct student *head)
{
struct student *first; /*排列後有序鏈的表頭指針*/
struct student *tail; /*排列後有序鏈的表尾指針*/
struct student *p_min; /*保留鍵值更小的節點的前驅節點的指針*/
struct student *min; /*存儲最小節點*/
struct student *p; /*當前比較的節點*/

first = NULL;
while (head != NULL) /*在鏈表中找鍵值最小的節點。*/
{
/*注意：這里for語句就是體現選擇排序思想的地方*/
for (p=head,min=head; p->next!=NULL; p=p->next) /*循環遍歷鏈表中的節點，找出此時最小的節點。*/
{
if (p->next->num < min->num) /*找到一個比當前min小的節點。*/
{
p_min = p; /*保存找到節點的前驅節點：顯然p->next的前驅節點是p。*/
min = p->next; /*保存鍵值更小的節點。*/
}
}

/*上面for語句結束後，就要做兩件事；一是把它放入有序鏈表中；二是根據相應的條件判斷，安排它離開原來的鏈表。*/

/*第一件事*/
if (first == NULL) /*如果有序鏈表目前還是一個空鏈表*/
{
first = min; /*第一次找到鍵值最小的節點。*/
tail = min; /*注意：尾指針讓它指向最後的一個節點。*/
}
else /*有序鏈表中已經有節點*/
{
tail->next = min; /*把剛找到的最小節點放到最後，即讓尾指針的next指向它。*/
tail = min; /*尾指針也要指向它。*/
}

/*第二件事*/
if (min == head) /*如果找到的最小節點就是第一個節點*/
{
head = head->next; /*顯然讓head指向原head->next,即第二個節點，就OK*/
}
else /*如果不是第一個節點*/
{
p_min->next = min->next; /*前次最小節點的next指向當前min的next,這樣就讓min離開了原鏈表。*/
}
}

if (first != NULL) /*循環結束得到有序鏈表first*/
{
tail->next = NULL; /*單向鏈表的最後一個節點的next應該指向NULL*/
}
head = first;
return head;
}

/*
==========================
功能：直接插入排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/

/*
直接插入排序的基本思想就是假設鏈表的前面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;
}

/*
==========================
功能：冒泡排序(由小到大)
返回：指向鏈表表頭的指針
==========================
*/

/*
冒泡排序的基本思想就是對當前還未排好序的范圍內的全部節點，
自上而下對相鄰的兩個節點依次進行比較和調整，讓鍵值（就是用它排
序的欄位，我們取學號num為鍵值）較大的節點往下沉，鍵值較小的往
上冒。即：每當兩相鄰的節點比較後發現它們的排序與排序要求相反時，
就將它們互換。

單向鏈表的冒泡排序圖示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鏈表）
head 1->next 3->next 2->next n->next

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

圖14：有N個節點的鏈表冒泡排序

任意兩個相鄰節點p、q位置互換圖示:
假設p1->next指向p，那麼顯然p1->next->next就指向q,
p1->next->next->next就指向q的後繼節點，我們用p2保存
p1->next->next指針。即：p2=p1->next->next，則有：
[ ]---->[p]---------->[q]---->[ ]（排序前）
p1->next p1->next->next p2->next
圖15

[ ]---->[q]---------->[p]---->[ ]（排序後）

圖16

1、排序後q節點指向p節點，在調整指向之前，我們要保存原p的指向節點地址，即：p2=p1->next->next；
2、順著這一步一步往下推,排序後圖16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;
3、在圖15中p2->next原是q發出來的指向，排序後圖16中q的指向要變為指向p的，而原來p1->next是指向p的，所以p2->next=p1->next;
4、在圖15中p1->next原是指向p的，排序後圖16中p1->next要指向q,原來p1->next->next（即p2)是指向q的，所以p1->next=p2;
5、至此，我們完成了相鄰兩節點的順序交換。
6、下面的程序描述改進了一點就是記錄了每次最後一次節點下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點為止。
因為後面的都已經是排好序的了。
*/
struct student *BubbleSort(struct student *head)
{
struct student *endpt; /*控制循環比較*/
struct student *p; /*臨時指針變數*/
struct student *p1;
struct student *p2;

p1 = (struct student *)malloc(LEN);
p1->next = head; /*注意理解：我們增加一個節點，放在第一個節點的前面，主要是為了便於比較。因為第一個節點沒有前驅，我們不能交換地址。*/
head = p1; /*讓head指向p1節點，排序完成後，我們再把p1節點釋放掉*/

for (endpt=NULL; endpt!=head; endpt=p) /*結合第6點理解*/
{
for (p=p1=head; p1->next->next!=endpt; p1=p1->next)
{
if (p1->next->num > p1->next->next->num) /*如果前面的節點鍵值比後面節點的鍵值大，則交換*/
{
p2 = p1->next->next; /*結合第1點理解*/
p1->next->next = p2->next; /*結合第2點理解*/
p2->next = p1->next; /*結合第3點理解*/
p1->next = p2; /*結合第4點理解*/
p = p1->next->next; /*結合第6點理解*/
}
}
}

p1 = head; /*把p1的信息去掉*/
head = head->next; /*讓head指向排序後的第一個節點*/
free(p1); /*釋放p1*/
p1 = NULL; /*p1置為NULL，保證不產生「野指針」，即地址不確定的指針變數*/

return head;
}

/*
==========================
功能：插入有序鏈表的某個節點的後面(從小到大)
返回：指向鏈表表頭的指針
==========================
*/

/*
有序鏈表插入節點示意圖：

---->[NULL]（空有序鏈表）
head

圖18：空有序鏈表（空有序鏈表好解決，直接讓head指向它就是了。）

以下討論不為空的有序鏈表。
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（有序鏈表）
head 1->next 2->next 3->next n->next

圖18：有N個節點的有序鏈表

插入node節點的位置有兩種情況：一是第一個節點前，二是其它節點前或後。

---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
head node->next 1->next 2->next 3->next n->next

圖19：node節點插在第一個節點前

---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
head 1->next 2->next 3->next node->next n->next

圖20：node節點插在其它節點後
*/
struct student *SortInsert(struct student *head, struct student *node)
{
struct student *p; /*p保存當前需要檢查的節點的地址*/
struct student *t; /*臨時指針變數*/

if (head == NULL) /*處理空的有序鏈表*/
{
head = node;
node->next = NULL;
n += 1; /*插入完畢，節點總數加1*/
return head;
}

p = head; /*有序鏈表不為空*/
while (p->num < node->num && p != NULL) /*p指向的節點的學號比插入節點的學號小，並且它不等於NULL*/
{
t = p; /*保存當前節點的前驅，以便後面判斷後處理*/
p = p->next; /*後移一個節點*/
}

if (p == head) /*剛好插入第一個節點之前*/
{
node->next = p;
head = node;
}
else /*插入其它節點之後*/
{
t->next = node; /*把node節點加進去*/
node->next = p;
}
n += 1; /*插入完畢，節點總數加1*/

return head;
}

/*

測試代碼如下：

*/

/*測試SelectSort():請編譯時去掉注釋塊*/

/*
head = SelectSort(head);
Print(head);
*/

/*測試InsertSort():請編譯時去掉注釋塊*/

/*
head = InsertSort(head);
Print(head);
*/

/*測試BubbleSort():請編譯時去掉注釋塊*/

/*
head = BubbleSort(head);
Print(head);
*/

/*測試SortInsert():上面創建鏈表，輸入節點時請注意學號num從小到大的順序。請編譯時去掉注釋塊*/

/*
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%ld,%f",&stu->num,&stu->score);
head = SortInsert(head,stu);
free(stu);
stu = NULL;
Print(head);
*/

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/northplayboy/archive/2005/12/14/552388.aspx