基本介紹
- 中文名：鍊表選擇法
- 鍊表選擇法：就是鍊表選擇排序，
- 情況：交換節點就等價於交換數據的順序
- 簡介：將待排序序列存放於此鍊表中
鍊表選擇法,內容簡介,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，建表結束*/
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:\n");
while(temp2!=NULL)
{
printf("%5d",temp2->data);
temp2=temp2->next;
}
}
printf("\n");
}
主函式測試運行
void main()
{
Node *temp3;
LinkList l;
printf(" =====(end by -1)======\npress \"enter\" after input the nember each time:\n");
l=CreateFromTail2();
temp3=l->next;
if(temp3==NULL)
printf("NO LINKLIST!!!");
else
{
printf("List before sorting is:\n");
while(temp3!=NULL)
{
printf("%5d",temp3->data);
temp3=temp3->next;
}
}
printf("\n");
linkSort(l);
}
編譯運行說明
分別根據以上頭檔案程式創建相應的兩個頭檔案：common.h和linklist.h，並在linklist.h中包含common.h，將尾插法創建鍊表的程式代碼以及鍊表選擇排序核心程式與主函式寫在一個檔案中（例如命名為test.c），然後將common.h、linklist.h、test.c三個檔案置於一個資料夾中編譯即可運行，輸入時以-1作為輸入結束標誌！
鍊表選擇排序指針指向示意圖
鍊表選擇排序指針示意圖(20張)
鍊表選擇排序指針示意圖(20張)
運行結果示意圖
可以參照一下圖中的輸入方式運行以上檔案：‘
運行結果示意圖(4張)
