文档章节

小蚂蚁学习数据结构(27)——题目——一个关于链表的题目

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/01/31 08:34
字数 886
阅读 128
收藏 3

题目要求

已知单链表中结点结构定义如下:

typedef int ElemType;

typedef struct LNdoe{

    ElemType data;

    struct LNode * Next;

}LNode,*Linklist;

写出将带头结点的非空单链表L中值最小的元素取出插在第一个元素结点前的类_C算法,

例如:对于线性表(20,6,18,45,22,3,47,23),操作的结果是:(3,20,6,18,45,22,47,23)注:假设线性表中的元素各不相同。

void Link_Min_Insert(Linklist &L);

# include <stdio.h>
# include <stdlib.h>

typedef int ElemType;

//链表节点结构体
typedef struct LNode
{
	ElemType data;
	struct LNode * Next;
}LNode, * Linklist;

# define OK    1
# define ERROR 0

//创建一个链表
Linklist CreatList( void );
//列表遍历
void ListTraveler( Linklist );
//操作链表
void Link_Min_Insert( Linklist &L );

/*
	创建一个链表
	return pHead 头指针 
*/
Linklist CreatList( void )
{
	int n, i, j;
	Linklist p, pTail;
	//第一步,创建一个没有实际意义的头结点
	Linklist pHead = ( Linklist )malloc( sizeof( LNode ) );
	if( NULL == pHead )
	{
		printf( "动态内存分配失败!\n" );
		return ERROR;
	}
	pHead -> Next = NULL;	//头结点初始化完毕
	pTail = pHead;			//将头指针交个一个中间变量,用于指针下移
	
	//第二步,开始创建链表
	printf( "请输入需要常见的结点个数:\n" );
	scanf( "%d", &n );
	
	for( i = 0 ; i < n; ++i )
	{
		printf( "请输入第%d个元素:", i+1 );
		scanf( "%d", &j );
		
		p = ( Linklist )malloc( sizeof( LNode ) );
		if( NULL == p )
		{
			printf( "动态内存分配失败!\n" );
			return ERROR;
		}
		p -> data = j;
		p -> Next = NULL;
		pTail -> Next = p;
		pTail = p;
	}
	
	return pHead;
}

/* 遍历这条链表 */
void ListTraveler( Linklist pHead )
{
	Linklist p = pHead;
	
	if( NULL == p )
	{
		return;
	}
	else
	{
		while( NULL != p -> Next )
		{
			p = p -> Next;
			printf( "%d ", p -> data );
		}
		printf( "\n" );
	}
}

/*
	将链表中最小的一个值插入到链表头部
	做了这么长铺垫,这才是今天题目的要求 ┗( T﹏T )┛
*/
void Link_Min_Insert( Linklist &L )
{
	/*
		我的思路:
			1,先创建一个节点,存放最小值节点的信息
			2,循环一次,查找出最小的值和他的前驱节点指针
			3,将最小节点释放掉
			4,在开头将这个值插入
	*/
	Linklist p = L, q;
	Linklist r, fid;
	
	if( NULL == p )
	{
		exit(-1);
	}
	else
	{
		//1,先创建一个节点,存放最小值节点的信息
		q = ( Linklist )malloc( sizeof( LNode ) );
		if( NULL == q )
		{
			printf( "动态内存分配失败!\n" );
			exit(-1);
		}
		
		//2,循环一次,查找出最小的值和他的前驱节点指针,并且保存前驱指针
		q -> data = p -> Next -> data;
		while( NULL != p -> Next )
		{
			r = p;
			p = p -> Next;
			if( p -> data <= q -> data )
			{
				q -> data = p -> data;
				q -> Next = p -> Next;
				fid = r;
			}
		}
		
		//3,释放最小值节点空间
		free( fid -> Next );
		fid -> Next = q -> Next;
		
		//4,将新的最小结点q,插入到第一个位置
		q -> Next = L -> Next;
		L -> Next = q;
	}
}

int main( void )
{
	//首先创建一个头指针
	Linklist pHead = NULL;
	
	pHead = CreatList();
	
	printf( "遍历这条链表:\n" );
	ListTraveler( pHead );
	
	printf( "将链表中的最小值,放到链表的头部 ……LOAD……" );
	Link_Min_Insert( pHead );
	
	printf( "转移后的链表为:\n" );
	ListTraveler( pHead );
	
	return 0;
}
/*
	VC++6.0中输出的结果是:
	=========================================================
	请输入需要常见的结点个数:
	8
	请输入第1个元素:20
	请输入第2个元素:6
	请输入第3个元素:18
	请输入第4个元素:45
	请输入第5个元素:22
	请输入第6个元素:3
	请输入第7个元素:47
	请输入第8个元素:23
	遍历这条链表:
	20 6 18 45 22 3 47 23
	将链表中的最小值,放到链表的头部 ……LOAD……转移后的链表为:
	3 20 6 18 45 22 47 23
	==========================================================
	总结:
		功能倒是实现了,可就是感觉程序写的好繁琐,不知道还有没有
		其他简便的方法实现没。
*/


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 142
博文 161
码字总数 100864
作品 0
郑州
程序员
私信 提问
算法精讲学习笔记 链表

1.链表有关的知识 (1)链表问题算法难度不高,主要考察代码实现能力 (2)链表和数组都是一种线性结构 数组是一段连续分配的存储空间, 链表空间不一定保证连续,是临时分配的。 (3)链表的...

范大脚脚
2017/11/22
0
0
若干数据结构 && 算法面试题【四】(更新ing)

这是我的第三个面试题汇总。 想看之前的内容请移步 http://zhweizhi.blog.51cto.com/10800691/1763237 若干数据结构 && 算法面试题【一】更新完毕 http://zhweizhi.blog.51cto.com/10800691/...

shangluyi
2016/07/08
0
0
小蚂蚁学习数据结构(26)——题目——输出二叉树上值大于x的算法

题目要求: 设二叉树以二叉链表的形式存储,有关类型定义如下: typedef struct BiTNode{ int data; struct BiTNode lchild, rchild; }BiTNode, * BiTree; 下面是求输出二叉树上值大于x的类_...

嗜学如命的小蚂蚁
2016/01/29
51
0
程序员进阶之算法练习(三十二)LeetCode专场

前言 BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天是LeetCode专场练习。 正文 Copy L...

落影loyinglin
2018/08/09
0
0
从今天开始挑战 LeetCode

算法和数据结构是计算机编程重要的理论,也是一名优秀程序员的基本功,所以非常有必要对其学习和加深。 但是,算法是比较难学的,学习它需要智商。 同样一个问题,他的算法耗时 10ms,你的要...

落英坠露
2018/06/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

IDE 插件新版本发布,开发效率 “biu” 起来了

近日,Cloud Toolkit正式推出了面向 IntelliJ 和 Eclipse 两个平台的新款插件,本文挑选了其中三个重大特性进行解读,点击文末官网跳转链接,可查看详细的版本说明。 本地应用一键部署到任何...

阿里云云栖社区
28分钟前
6
0
金丝雀发布、滚动发布、蓝绿发布到底有什么差别?关键点是什么?

根据 2017 年的 DevOps 发展报告,高效能组织和低效能组织在软件交付的效率上有数量级上的差异。技术组织的软件交付能力是一种综合能力,涉及众多环节,其中发布是尤为重要的环节。 作为技术...

问题终结者
56分钟前
3
0
Kubernetes Client-go Informer 源码分析

几乎所有的Controller manager 和CRD Controller 都会使用Client-go 的Informer 函数,这样通过Watch 或者Get List 可以获取对应的Object,下面我们从源码分析角度来看一下Client go Informe...

阿里云官方博客
今天
4
0
传统IDC部署网站(三)

11. 重置密码 密钥和密码都支持远程登陆, 二选一 两个都可以登陆, 密钥相对于密码来说,相对安全一点 本地登陆无法是用密钥 修改密码 root 用户 passwd root 修改普通用户 passwd usernam...

miko0089
今天
6
0
bash特性

1.支持别名 alias 2.命令替换 $(COMMANS) 或者 `COMMAND` 3. bash支持的引号: `` :命令替换 "":弱引用,可以实现变量替换 '':强引用,不实现变量替换 4.文件名通配 globbing:(man 7 glo...

忙碌的小蜜蜂
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部