單鏈表實現選擇排序演算法

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

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

㈡ 單鏈表的簡單排序

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

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

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

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

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