王朝百科
分享
 
 
 

链表选择法

王朝百科·作者佚名  2012-05-29  
宽屏版  字体: |||超大  

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

‍ 链表选择排序指针示意图(20张)

‍ 链表选择排序指针示意图(20张)

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

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

链表选择排序指针指向示意图链表选择排序指针示意图(20张)

链表选择排序指针示意图(20张)

运行结果示意图可以参照一下图中的输入方式运行以上文件:‘

‍ 运行结果示意图(4张)

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
如何用java替换看不见的字符比如零宽空格&#8203;十六进制U+200B
 干货   2023-09-10
网页字号不能单数吗,网页字体大小为什么一般都是偶数
 干货   2023-09-06
java.lang.ArrayIndexOutOfBoundsException: 4096
 干货   2023-09-06
Noto Sans CJK SC字体下载地址
 干货   2023-08-30
window.navigator和navigator的区别是什么?
 干货   2023-08-23
js获取referer、useragent、浏览器语言
 干货   2023-08-23
oscache遇到404时会不会缓存?
 干货   2023-08-23
linux下用rm -rf *删除大量文件太慢怎么解决?
 干货   2023-08-08
刀郎新歌破世界纪录!
 娱乐   2023-08-01
js实现放大缩小页面
 干货   2023-07-31
生成式人工智能服务管理暂行办法
 百态   2023-07-31
英语学习:过去完成时The Past Perfect Tense举例说明
 干货   2023-07-31
Mysql常用sql命令语句整理
 干货   2023-07-30
科学家复活了46000年前的虫子
 探索   2023-07-29
英语学习:过去进行时The Past Continuous Tense举例说明
 干货   2023-07-28
meta name="applicable-device"告知页面适合哪种终端设备:PC端、移动端还是自适应
 干货   2023-07-28
只用css如何实现打字机特效?
 百态   2023-07-15
css怎么实现上下滚动
 干货   2023-06-28
canvas怎么画一个三角形?
 干货   2023-06-28
canvas怎么画一个椭圆形?
 干货   2023-06-28
canvas怎么画一个圆形?
 干货   2023-06-28
canvas怎么画一个正方形?
 干货   2023-06-28
中国河南省郑州市金水区蜘蛛爬虫ip大全
 干货   2023-06-22
javascript简易动态时间代码
 干货   2023-06-20
感谢员工的付出和激励的话怎么说?
 干货   2023-06-18
 
>>返回首页<<
 
 
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有