單鏈表簡單選擇排序演算法

① 單鏈表的選擇排序

#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("%8d",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 n;
printf("輸入數字的個數(n):\n");
scanf("%d",&n);
head=creat(n);
printf("輸出數字:\n");
output(head);
paixu(head);
}

② 若待排序列用帶頭結點的單鏈表存儲,試給出簡單選擇排序演算法. 求大神！

voidselectsort(pointer&h)//h為頭指針
{
	pointerpCur=h;
	pointerpCurPre=NULL;
	pointerpMin=pCur;
	pointerpMinPre=pCurPre;
	boolbFirstFlag=true;

	while(pCur)
	{
		//遍歷以pCur為頭節點的鏈表中key值最小的節點
		pMin=pCur;
		pMinPre=pCurPre;
		pointerpTemp1=pCur;
		while(pTemp1->next)
		{
			if(pMin->key>pTemp1->next->key)
			{
				pMin=pTemp1->next;
				pMinPre=pTemp1;
			}

			pTemp1=pTemp1->next;
		}

		//交換key值最小的節點與pCur節點的位置
		if(pCur->next==pMin)
		{
			pCur->next=pMin->next;
			pMin->next=pCur;
			pCurPre->next=pMin;
		}
		else
		{
			pointerpTemp2=pCur->next;
			pCur->next=pMin->next;
			pMin->next=pTemp2;

			if(pCurPre)
			{
				pCurPre->next=pMin;
			}

			if(pMinPre)
			{
				pMinPre->next=pCur;
			}
		}

		if(bFirstFlag)
		{
			h=pMin;
			bFirstFlag=false;
		}

		pCurPre=pMin;
		pCur=pMin->next;
	}
}

③ 鏈表的選擇排序

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

④ 對單鏈表中的數據進行排序，用哪種演算法比較好

typedef struct __LINK
{
int data;
struct __LINK *next;
} LinkNode_t;

//冒泡排序單連表, 交換值方式
bool LinkSort( LinkNode_t* &head )
{
assert( head != NULL );
bool change = true;
LinkNode_t* p = head;
LinkNode_t* pStop = head->next;
int ifirst = 0;

while ( pStop && pStop->next )
{
pStop = pStop->next;
}

LinkNode_t* pFlag = head;

while ( change )
{
change = false;
for ( p = head->next; p != pStop; p = p->next )
{
if ( p->data < p->next->data )
{
int value = p->data;
p->data = p->next->data;
p->next->data = value;
change = true;
}
if ( p->next == pStop ) pFlag = p;
}
pStop = pFlag;
}
return true;
}

⑤ 編寫一個演算法，用單鏈表表示的待排序關鍵碼序列上實現簡單選擇排序。（用c寫）

#include"stdio.h"
#include<malloc.h>

typedef char ElemType;

typedef struct LNode
{ElemType data;
struct LNode *next;
}LinkList;

void CreateListR(LinkList *&L,ElemType a[],int n) //尾插法建表
{
LinkList *s,*r;int i;
L=(LinkList *)malloc(sizeof(LinkList));
r=L;
for(i=0;i<n;i++)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}

void InitList(LinkList *&L) //初始化線性表
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}

void DispList(LinkList *L) //輸出線性表
{
LinkList *p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
}

void CombList(LinkList *L1,LinkList *L2,LinkList *&k) //兩個集合的交
{
LinkList *p=L1->next ,*q=L2->next ,*b,*a,*c;

k=(LinkList *)malloc(sizeof(LinkList));
b=k;a=p;
while(q!=NULL)
{
while(a!=NULL)
{
if(a->data==q->data)
{
c=(LinkList *)malloc(sizeof(LinkList));
c->data=a->data;b->next=c;b=b->next;
}
a=a->next;
}
q=q->next;
a=p;
}
b->next=NULL;
}

void AddList(LinkList *L1,LinkList *L2,LinkList *&k) //兩個集合的並
{
LinkList *p=L1->next ,*q=L2->next ,*b,*a,*c;

k=(LinkList *)malloc(sizeof(LinkList));
b=k;a=p;

while(q!=NULL)
{
int x=0;
while(p!=NULL)
{
if(p->data==q->data)x++;
p=p->next;
}
if(!x)
{
c=(LinkList *)malloc(sizeof(LinkList));
c->data=q->data;b->next=c;b=b->next;
}
q=q->next;
p=a;
}
b->next=a;
}

void RankList(LinkList *&L) //按從小到大排列
{
LinkList *p=L->next,*q,*r;
if (p!=NULL)
{ r=p->next;
p->next=NULL;
p=r;
while (p!=NULL)
{ r=p->next;
q=L;
while (q->next!=NULL && q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}
int main()
{
ElemType a[5]={'a','b','c','d','e'},b[4]={'e','f','g','h'};
LinkList *h1,*h2,*p1,*p2;

InitList(h1); //初始化順序表h
InitList(h2);
CreateListR(h1,&a[0],5); //依次採用尾插入法插入a，b，c，d，e元素
CreateListR(h2,&b[0],4);
printf("單鏈表1為：");
DispList(h1); printf("\n"); //輸出順序表h
printf("單鏈表2為：");
DispList(h2); printf("\n");

CombList(h1,h2,p1); //求兩個單鏈表的交
printf("這兩個單鏈表的交為：");
DispList(p1); printf("\n");

AddList(h1,h2,p2); //求兩個單鏈表的並
printf("這兩個單鏈表的並為：");
DispList(p2); printf("\n");

RankList(p2); //對單鏈表按從小到大排列
printf("這個單鏈表排列後為：");
DispList(p2); printf("\n");

return 0;
}

這個是我以前做的作業，你可拿去借鑒一下，其實程序這東西還是要自己多看多寫，自然就會不斷進步，如果只是拿別人的而不自己去思考很難有進步哦。
祝你能學習進步。

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

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

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

⑦ 鏈表排序的演算法

我看過了程序，覺得思想應該是這樣的，9次遍歷該鏈表。每次找出一個MAX，並將他賦給一個新的結點，同時刪除原鏈表中這個最大值。
最後將這些新的接點組成一個鏈表，就是排好序的。
現在來看看程序中的錯誤，主要是在排序中：
⒈while條件錯誤，假如是temp!=NULL,想一想遍歷到鏈表最一個值，這時temp不為NULL，而temp->next為NULL，while循環中用到了這個，所以程序崩潰。修改方法：該while條件，或是改循環中的temp->next。
⒉swaptemp->next=swaptemp->next->next;錯誤,會使程序崩潰，理由同上，應該是swaptemp->data=max;swaptemp=swaptemp->next;
⒊對max的處理應該放在while循環外面，這樣才能對最大的max處理。
程序看上去比較得亂，也就沒有調試，說了這么多你應該能自己調試成功吧。再說一下，盡量不要讓程序有警告，有時警告也會讓你的程序無法正常運行！

⑧ 單鏈表的簡單排序

最簡單的選擇排序具體看代碼：

#include<cstdio>
#include<cstdlib>
#include<ctime>
structnode{
intval;
node*next;
node(intv):val(v),next(NULL){}
};
//從小到大，最簡單的選擇排序
node*linklist_sort(node*head){
node*nhead=newnode(0);
while(true){
node*temp=head,*maxpre=head;
for(;temp->next;temp=temp->next){
if(temp->next->val>maxpre->next->val){
maxpre=temp;
}
}
if(temp==head)break;
temp=maxpre->next;
maxpre->next=temp->next;
temp->next=nhead->next;
nhead->next=temp;
}
head->next=nhead->next;
returnhead;
}
voidtraval(node*head){//遍歷單鏈表
while(head->next){
printf("%d",head->next->val);
head=head->next;
}
printf("
");
}
intmain(){
srand(time(NULL));
node*head=newnode(0);
for(inti=0;i<10;i++){
node*t=newnode(rand()%1000);
t->next=head->next;
head->next=t;
}
traval(head);
head=linklist_sort(head);
traval(head);
return0;
}

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

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