链表选择排序

内容简介

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

}

编译运行说明

分别根据以上头文件程序创建相应的两个头文件：common.h和linklist.h，并在linklist.h中包含common.h，将尾插法创建链表的程序代码以及链表选择排序核心程序与主函数写在一个文件中（例如命名为test.c），然后将common.h、linklist.h、test.c三个文件置于一个文件夹中编译即可运行，输入时以-1作为输入结束标志！

链表选择排序指针指向示意图