考研数据结构之线性表(1.7)——练习题之删除单链表的最小值结点(C表示)_二木成林的博客-程序员宝宝

技术标签: C  数据结构  

题目

设计一个算法删除单链表L(有头结点)中的一个最小值结点。

分析

先谈谈我自己写的思路:(1)寻找到最小值结点,返回最小值结点的指针或者返回最小值结点在链表中的序号位置;(2)删除指定位置的最小值结点。

关于寻找链表中的最小值结点,可以先考虑将链表的开始结点(第一个结点)设置为最小值结点,然后将最小值结点与链表中的每个结点进行比较,如果比最小值结点小的话,就将该结点置为最小值结点,反之继续比较,最后返回。

核心代码如下:

/* 在单链表中查找结点元素data值最小的结点 */
/* *list指的是要查找最小值结点的链表 */
LNode * findMin(LNode *list) {
	LNode *temp=list->next; // 开始结点
	LNode *min=list->next; // 最小值结点,意思是将开始结点设置为最小值结点
	while(temp!=NULL) { // 循环条件,当head!=NULL时
		if(temp->data<min->data) { // 比较当前结点的数据与最小值结点的数据
			min=temp; // 如果小于最小值的结点的数据,那么就将该结点设置为最小值结点
		}
		temp=temp->next; // 循环到下一个结点
	}
	return min; // 返回最小值结点
}

/* 删除单链表中最小值结点 */
/* *list指的是要操作的单链表;*minNode指的是要被删除的最小值结点 */
void deleteMinNode(LNode *list,LNode *minNode) {
	LNode *temp=list->next;// 开始结点,即第一个结点
	LNode *pre=list; // 头结点
	LNode *tempDelNode; // 临时保存要被删除的结点
	while(temp!=NULL) { // 循环遍历单链表中的所有结点
		if(temp->data==minNode->data) { // 比较当前结点与最小结点的值是否相等,如果相等,则删除当前结点,否则继续寻找下一个
			tempDelNode=temp; // 临时保存要被删除的最小值结点
			pre->next=tempDelNode->next;// 将头结点指向被删除结点的下一个结点,实现删除操作连接新链表
			free(tempDelNode); // 释放结点资源
			break; // 跳出循环
		} else { // 如果不相等,就去下一个结点进行判断
			pre=temp; // 记录终端结点指向temp
			temp=temp->next; // 到单链表的下一个结点
		}
	}

}

完整代码如下:

#include <stdio.h>
#include <stdlib.h>
// 声明单链表结构体
struct LNode {
	int data;
	struct LNode *next;
};

/* 通过用户输入数据创建一个单链表,由用户输入整型测试数据 */
/* 返回一个单链表 */
LNode * createList() {
	LNode *head;
	LNode *p1,*p2;
	p1=p2=(LNode *)malloc(sizeof(LNode));
	head=(LNode *)malloc(sizeof(LNode));
	scanf("%ld",&p1->data);
	int i=0;
	while(p1->data!=0) { // 当用户在控制台输入0时结束循环
		i+=1;
		if(i==1) {
			head->next=p1;
		} else {
			p2->next=p1;
		}
		p2=p1;
		p1=(LNode *)malloc(sizeof(LNode));
		scanf("%ld",&p1->data);
	}
	p2->next=NULL;
	return head;
}

/* 打印单链表 */
/* *list指的是要被打印输出的单链表 */
void printList(LNode *list) {
	LNode *temp=list->next;// 单链表的开始结点
	printf("\n");
	while(temp!=NULL) { // 循环单链表
		printf("%ld\t",temp->data); // 打印单链表中的data数据
		temp=temp->next; // 遍历至下一个结点
	}
	printf("\n"); // 换行
}

/* 在单链表中查找结点元素data值最小的结点 */
/* *list指的是要查找最小值结点的链表 */
LNode * findMin(LNode *list) {
	LNode *temp=list->next; // 开始结点
	LNode *min=list->next; // 最小值结点,意思是将开始结点设置为最小值结点
	while(temp!=NULL) { // 循环条件,当head!=NULL时
		if(temp->data<min->data) { // 比较当前结点的数据与最小值结点的数据
			min=temp; // 如果小于最小值的结点的数据,那么就将该结点设置为最小值结点
		}
		temp=temp->next; // 循环到下一个结点
	}
	return min; // 返回最小值结点
}

/* 删除单链表中最小值结点 */
/* *list指的是要操作的单链表;*minNode指的是要被删除的最小值结点 */
void deleteMinNode(LNode *list,LNode *minNode) {
	LNode *temp=list->next;// 开始结点,即第一个结点
	LNode *pre=list; // 头结点
	LNode *tempDelNode; // 临时保存要被删除的结点
	while(temp!=NULL) { // 循环遍历单链表中的所有结点
		if(temp->data==minNode->data) { // 比较当前结点与最小结点的值是否相等,如果相等,则删除当前结点,否则继续寻找下一个
			tempDelNode=temp; // 临时保存要被删除的最小值结点
			pre->next=tempDelNode->next;// 将头结点指向被删除结点的下一个结点,实现删除操作连接新链表
			free(tempDelNode); // 释放结点资源
			break; // 跳出循环
		} else { // 如果不相等,就去下一个结点进行判断
			pre=temp; // 记录终端结点指向temp
			temp=temp->next; // 到单链表的下一个结点
		}
	}

}

int main() {
	/* [0.]创建初始测试单链表 */
	LNode *list,*t1,*t2,*t3,*t4;
	LNode *list2,*mergeList;
	list=createList();// 创建测试链表
	printList(list);// 打印单链表

	t1=findMin(list); // 发现最小值结点
	printf("min=%d",t1->data);// 打印输出最大值结点的data值
	deleteMinNode(list,t1);// 删除最小值结点
	printList(list);// 打印删除后的链表

	return 0;
}

测试结果如下:

可以看出上面的代码比较多,看看参考书上的算法是怎么样的。

分析如下:用p从头至尾扫描链表,pre指向*p结点的前驱,用minp保存值最小的结点指针,minpre指向minp的前驱。一边扫描,一边比较,将最小值结点放到minp中。

代码如下:

void delminnode(LNode *L){
	LNode *pre=L,*p=pre->next,*minp=p,*minpre=pre;
	while(p!=NULL){
		if(p->data<minp->data){
			minp=p;
			minpre=pre;
		}
		pre=p;
		p=p->next;
	}
	minpre->next=minp->next; // 删除*minp结点
	free(minp); 
}

其实原理都是一样的,不过参考书上的代码确实要简洁得多。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cnds123321/article/details/106256526

智能推荐

(Adobe Air) Bring a window to front by clicking the systemTrayIcon_unixboy_xujf的博客-程序员宝宝

Whiledeveloping an AIR application, I had an issue with bringing theapplication to front (above all other windows) when clicking thesystemTrayIcon.Usually, you would use the method:...

虚拟光驱 DAEMON Tools Lite 安装笔记_FerminZhang的博客-程序员宝宝

DAEMON Tools Lite是一个非常棒的虚拟光驱软件。它将帮助我们快速打开ISO文件,当然它能做到的不止这些。本文将介绍如何在Windows 7 x64下安装DAEMON Tools Lite。准备文件DTLite501-0406.exe (来源:http://dl.pconline.com.cn/html_2/1/121/id=1051&pn=0.html)安装过程运行“DTLite

Markdown开发VSCode插件推荐_COCO56(徐可可)的博客-程序员宝宝_vscodemarkdown插件

Markdown All in One该插件用于在编写文档时自动帮我们填充内容,比如支持使用快捷键调整格式,在使用列表时会自动帮我们补全下一项的值,具体可以参考作者该插件的Github仓库Markdown TOC该插件用于生成目录,比如给标题自动添加序号,具体可以参考:完美解决Markdown文件添加目录的问题或者作者该插件的Github仓库Markdown Preview Enhanced该插件用于预览效果,安装完毕之后在右键菜单里会多一个打开侧边预览的选项,更多功能可以参考作者该插件的Git.

VMware虚拟化_一直在路上的十安的博客-程序员宝宝

虚拟化是为一些组件创建基于软件的或虚拟(而不是物理)表现形式的过程。虚拟化可以应用于应用、服务器、存储和网络,它是一种可以为所有规模的企业降低 IT 开销,同时提高效率和敏捷性的最有效方式。

公关战中的兵法攻略_ChinaPR_home的博客-程序员宝宝

文丨公关之家 作者:方韵引言: 公关战的背后是数不尽的利益纠葛,借助公关战这一“软”战役,企业可以更好地打好市场瓜分这一“硬仗”。2019年的6月,注定不太平。“618”带来的“猫狗拼”大战还有余波,三个男人的厮杀还未平息,一场公关大战的序幕再次拉开。6月20日,伊利公开対撕蒙牛,发表长文《北京冬奥组委无奈奥运史上最大丑闻将上演!中粮集团蒙牛乳业联合美国企业破坏冬奥大局》。在文章中伊利痛斥...

我们计划为EasyDSS定制开发一款超低延时的EasyPlayer Flash播放器_weixin_30906671的博客-程序员宝宝

现象最近团队在做EasyDSS RTMP流媒体服务器开发的过程中,遇到了一个关于延时累积的问题,先大概描述一下过程: 在EasyRTMP Android进行长时间的RTMP推流压力测试,在EasyDSS的web客户端中进行Flash播放,起初进行播放的开始阶段,延时是极小的,大概在0.4s左右,但随着播放过程的延长,我们会观察到一个现象,一旦客户端出现...

随便推点

echarts + vue 使用_weixin_42127141的博客-程序员宝宝

&lt;template&gt; &lt;div class="h100p"&gt; &lt;div class="basic_title"&gt;监控&lt;/div&gt; &lt;div v-for="(item,index) in containerMonitor" :key="index"&gt; ...

每天记录学习的新知识 :使用Glide时,setImageResource/setImageDrawable图片不显示_清风徐来辽的博客-程序员宝宝

记录使用Glide后,需要先 ↓Glide.with(this).clear(photo);再调用setImageResource/setImageDrawable

Orcle 12c 新特性---支持克隆PDB部分表空间_Expect-乐的博客-程序员宝宝

1 说明从12.1.0.2开始,引入了User Tablespaces,简单的说就是可以按表空间(用户创建的)来克隆PDB。比如,当前PDB1中,用户新建了三个表空间tbs1,tbs2,tbs3,那么我们后期测试,可能只需要tbs1表空间中的数据,那么我们可以用USER_TABLESPACES子句来只克隆PDB1中的tbs1表空间,这样大大的缩短了可怜时间和不必要的空间开销。对于拆分数据也很有...

java mail 发件人昵称,Java使用javax.mail发送邮件 解决收件人、发件人名字乱码问题..._男爵兔的博客-程序员宝宝

/*** 格式化 Name 的地址* @param name 名字* @param email Email地址* @return 格式化的地址*/public static String formatAddress(String name, String email) {if (StringHelper.isNullOrEmpty(name)) {return email;}try {retur...

SPSS数据分析_Yang青青的博客-程序员宝宝_spss计算bmi

第一题表1 居民健康状况调查情况 编号 身高 (cm) 体重 (kg) 代谢综合征 性别 胆固醇 (mmol/L) 1 173.0 87.5 0 0 4.17 2 168.0 .

TP5框架中数据库增删改查操作getField、setField、setInc、setDec、field以及与TP3的对比_qq_2190630418的博客-程序员宝宝

TP3中读取某个字段:$User = M("User"); // 实例化User对象$nickname = $User-&gt;where('id=3')-&gt;getField('nickname');//查询ID为3的nicknameTP3更新某个字段:$User = M("User"); // 实例化User对象$User-&gt; where('id=5')-&gt;setField('name','ThinkPHP');// 更改用户的name值TP3对于统计字段(通常指的是数字

推荐文章

热门文章

相关标签