文档章节

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

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/01/31 08:34
字数 886
阅读 110
收藏 3
点赞 1
评论 0

题目要求

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

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



© 著作权归作者所有

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

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

范大脚脚 ⋅ 2017/11/22 ⋅ 0

若干数据结构 && 算法面试题【四】(更新ing)

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

shangluyi ⋅ 2016/07/08 ⋅ 0

从今天开始挑战 LeetCode

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

落英坠露 ⋅ 昨天 ⋅ 0

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

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

嗜学如命的小蚂蚁 ⋅ 2016/01/29 ⋅ 0

腾讯阿里网易游戏华为科大讯飞面经

本人是一非科班妹子,在找实习的过程中面试了腾讯、阿里、网易游戏、华为、科大讯飞(面试的顺序),前面三个都挂了。。。 1.腾讯提前批——游戏客户端开发 自我介绍+项目经历(问的很细) ...

牛客网 ⋅ 06/13 ⋅ 0

数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian ⋅ 2017/08/30 ⋅ 0

解读哈希表

说明:本文分为三部分内容,第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法。 第一部分:Top K 算法详解 问题描述 百度...

hanbing94 ⋅ 2015/08/30 ⋅ 1

基于Huffman编码的压缩程序

有同学在51CTO上学习了数据结构课程,希望我能给一个曾经做过的应用软件,让大家对数据结构知识练练手,这个建议非常好,学以致用嘛。因此特地翻出我曾经写过的一个程序,把这个题目送给那些...

王顶老师 ⋅ 2014/05/17 ⋅ 0

小蚂蚁学习C语言(30)——C语言初识链表(上)

链表,c语言和数据结构的一个连接 算法: 通俗定义: 解题的方法和步骤 狭义定义: 对存储数据的操作,对不同的存储结构要完成某一个功能所执行的操作是不一样的 比如,要输出数组中所有元素...

嗜学如命的小蚂蚁 ⋅ 2015/12/26 ⋅ 0

经典算法学习——合并两个有序链表

类似的,合并两个有序的数组或者链表也是剑指Offer中的经典题型。题目描述如下:输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是按照递增排序的。我这里以合并链表来实现。...

chenyufeng1991 ⋅ 2016/08/21 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 30分钟前 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 41分钟前 ⋅ 0

如何将S/4HANA系统存储的图片文件用Java程序保存到本地

我在S/4HANA的事务码MM02里为Material维护图片文件作为附件: 通过如下简单的ABAP代码即可将图片文件的二进制内容读取出来: REPORT zgos_api.DATA ls_appl_object TYPE gos_s_obj.DA...

JerryWang_SAP ⋅ 59分钟前 ⋅ 0

云计算的选择悖论如何对待?

导读 人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云...

问题终结者 ⋅ 今天 ⋅ 0

637. Average of Levels in Binary Tree - LeetCode

Question 637. Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每...

yysue ⋅ 今天 ⋅ 0

IDEA配置和使用

版本控制 svn IDEA版本控制工具不能使用 VCS-->Enable Version Control Integration File-->Settings-->Plugins 搜索Subversion,勾选SVN和Git插件 删除.idea文件夹重新生成项目 安装SVN客户......

bithup ⋅ 今天 ⋅ 0

PE格式第三讲扩展,VA,RVA,FA的概念

作者:IBinary 出处:http://www.cnblogs.com/iBinary/ 版权所有,欢迎保留原文链接进行转载:) 一丶VA概念 VA (virtual Address) 虚拟地址的意思 ,比如随便打开一个PE,找下它的虚拟地址 这边...

simpower ⋅ 今天 ⋅ 0

180623-SpringBoot之logback配置文件

SpringBoot配置logback 项目的日志配置属于比较常见的case了,之前接触和使用的都是Spring结合xml的方式,引入几个依赖,然后写个 logback.xml 配置文件即可,那么在SpringBoot中可以怎么做?...

小灰灰Blog ⋅ 今天 ⋅ 0

冒泡排序

原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第...

人觉非常君 ⋅ 今天 ⋅ 0

Vagrant setup

安装软件 brew cask install virtualboxbrew cask install vagrant 创建project mkdir -p mst/vmcd mst/vmvagrant init hashicorp/precise64vagrant up hashicorp/precise64是一个box......

遥借东风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部