文档章节

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

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/01/31 08:34
字数 886
阅读 110
收藏 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
程序员进阶之算法练习(三十二)LeetCode专场

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

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

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

嗜学如命的小蚂蚁
2016/01/29
51
0
从今天开始挑战 LeetCode

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

落英坠露
06/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Go 使用channel控制并发

前言 channel一般用于协程之间的通信,channel也可以用于并发控制。比如主协程启动N个子协程,主协程等待所有子协程退出后再继续后续流程,这种场景下channel也可轻易实现。 场景示例 总结 ...

恋恋美食
41分钟前
1
0
Apache Flink 漫谈系列 - 持续查询(Continuous Queries)

摘要: 实际问题 我们知道在流计算场景中,数据是源源不断的流入的,数据流永远不会结束,那么计算就永远不会结束,如果计算永远不会结束的话,那么计算结果何时输出呢?本篇将介绍Apache Fl...

阿里云官方博客
45分钟前
11
0
斐波那契堆的理解,节点mark属性和势函数

斐波那契堆 看了好多博客,都是照搬算法导论的内容,没有自己的理解,比如为什么有mark属性,势函数的作用,以及为什么叫斐波那契堆,下面说说鄙人的理解。 势函数 势函数是根节点个数加上2...

杨喆
46分钟前
4
0
NIO源码详解

阻塞io和无阻塞io: 阻塞io是指jdk1.4之前版本面向流的io,服务端需要对每个请求建立一堆线程等待请求,而客户端发送请求后,先咨询服务端是否有线程相应,如果没有则会一直等待或者遭到拒 ...

沉稳2018
50分钟前
1
0
如何把已经提交的commit, 从一个分支放到另一个分支

在本地master提交了一个commit(8d85d4bca680a5dbcc3e5cfb3096d18cd510cc9f),如何提交的test_2分之上? git checkout test_2git cherry-pick 8d85d4bca680a5dbcc3e5cfb3096d18cd510cc9f......

stephen_wu
54分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部