当前位置: 首页 > >

链表选择排序

链表选择排序是使用链表实现选择排序,一般的选择排序是在数组中实现的,与在数组中实现的选择排序不同的是,链表中选择排序时每次交换数据是通过交换链表的节点来实现的,由于数据是存放与链表的节点中的,所以交换节点就等价于交换了数据的顺序。

对于一个给定的数据序列,要对这个序列进行排序戏拜厦(从小到大或从大到小),首先创建链表,将待排序序列存放于此链表中,由于我们考虑的是交换数据所在的节点,所以在需要腿朽芝交换两个节点时本质上是交换链表中的两个节点,由于在链表中没有像数组中那利用下标随机的访问元素的机制,所以需要用一个指针从头到尾进行扫描,以这样的方式来访问每一个节点。

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:\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作为输入结束标志!



友情链接: