文档章节

小蚂蚁学习数据结构(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



© 著作权归作者所有

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

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

范大脚脚
2017/11/22
0
0
从今天开始挑战 LeetCode

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

落英坠露
06/22
0
0
左程云著算法与数据结构题目最优解笔记-链表

#链表 链表是面试时被提及最频繁的数据结构。链表就是通过指针将一个个节点连接起来。链表是非连续的动态内存空间,链表的查找比数组慢,但是添加和删除比数组快。 ###链表声明 public class...

hiyoung
前天
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

没有更多内容

加载失败,请刷新页面

加载更多

win32截屏并rgb24转yuv420

//最终f的内存布局为BGRA格式,需要保证buf长度足够(>w*h*4)void ScreenCap(void* buf, int w, int h){ HWND hDesk = GetDesktopWindow(); HDC hScreen = GetDC(hDesk); ......

styleman
今天
1
0
php输出mysql取出的中文为??的问题

解决方法: @ $db=new mysqli(DB_HOST,DB_USER,DB_PASSWORD,DB_DB); $db->query("set names utf8");//添加此语句,可以解决问题...

Aomo
今天
1
2
白话SpringCloud | 第五章:服务容错保护(Hystrix)

前言 前一章节,我们知道了如何利用RestTemplate+Ribbon和Feign的方式进行服务的调用。在微服务架构中,一个服务可能会调用很多的其他微服务应用,虽然做了多集群部署,但可能还会存在诸如网...

oKong
今天
2
0
【解惑】领略Java内部类的“内部”

内部类有两种情况: (1) 在类中定义一个类(私有内部类,静态内部类) (2) 在方法中定义一个类(局部内部类,匿名内部类) 1、私有内部类 —— 在方法之间定义的内部类,非静态 我们首先看看类中...

偶尔诗文
今天
1
0
sqlserver 2008 r2 直接下载地址(百度云)

之前下载的sqlserver2008发现不能附加,就卸载了,重新找到了sqlserver2008R2的百度云资源 卸载sqlserver2008还是有点麻烦,不过就是需要删除注册表中的信息 自己来回卸载了3次终于重装sqlse...

dillonxiao
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部