首页 > 编程语言 >设计一个算法删除单链表L(有头结点)中的一个最小值结点。

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

时间:2024-04-22 20:25:23浏览次数:17  
标签:结点 单链 ListNode head 有头 current 最小值 next

思路1:
定义一个变量 = 遍历每一个当前地址下面的数据和下一个作比较,谁小把谁的值给这个变量,同时记录这个小值的位置i,依次遍历比较,得到最小值和最小值的结点i的值,然后删除这个结点。
思路2:
给两个指针,p1,p2开始都指向第一个,然后p2指向下一个地址,和p1下的data作比较,得到的小值的p不动,同时记录当前地址,然后让另一个指针指向下一个,继续作比较,重复得出最小的值,然后删除这个结点。

/****************************************

  • file name:Delmin.c
  • author :[email protected]
  • data :2024/04/22
  • function :设计函数算法,实现删除单链表L(有头结点)中的一个最小值结点
  • noto :None
  • CopyRight (c) 2023-2024 [email protected] A1l Right Reseverd

****************************************/

include <stdio.h>

include <stdlib.h>

// 定义单链表结点结构体
typedef struct ListNode {
int value; // 结点的值
struct ListNode *next; // 指向下一个结点的指针
} ListNode;

// 创建新结点
ListNode* createNode(int value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (!newNode) {
printf("Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
newNode->value = value;
newNode->next = NULL;
return newNode;
}

// 插入结点到链表尾部
void appendNode(ListNode** head, int value) {
ListNode* newNode = createNode(value);
if (!*head) {
head = newNode;
} else {
ListNode
current = *head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
}

// 删除单链表中的一个最小值结点
void deleteMinNode(ListNode** head) {
if (!head || !(head)->next) {
// 链表为空或只有一个结点,无法删除最小值结点
printf("Cannot delete minimum node from an empty or single-node list.\n");
return;
}

ListNode* prev = *head; // 指向最小值结点的前驱结点  
ListNode* current = (*head)->next; // 当前遍历的结点  
ListNode* minPrev = *head; // 指向最小值结点的前驱结点的指针  
ListNode* minNode = current; // 当前找到的最小值结点  

// 遍历链表找到最小值结点  
while (current) {  
    if (current->value < minNode->value) {  
        minPrev = prev;  
        minNode = current;  
    }  
    prev = current;  
    current = current->next;  
}  

// 删除最小值结点  
if (minPrev == *head) {  
    // 最小值结点是头结点之后的第一个结点  
    *head = minNode->next;  
} else {  
    // 最小值结点不是头结点之后的第一个结点  
    minPrev->next = minNode->next;  
}  

// 释放最小值结点的内存  
free(minNode);  

}

// 打印链表
void printList(ListNode* head) {
ListNode* current = head->next; // 跳过头结点
while (current) {
printf("%d ", current->value);
current = current->next;
}
printf("\n");
}

// 释放链表内存
void freeList(ListNode* head) {
ListNode* current = head;
while (current) {
ListNode* next = current->next;
free(current);
current = next;
}
}

int main() {
ListNode* head = createNode(0); // 创建带头结点的空链表
appendNode(&head, 3); // 在链表尾部添加结点
appendNode(&head, 1);
appendNode(&head, 4);
appendNode(&head, 1); // 添加重复的最小值结点
appendNode(&head, 2);

printf("Original list: ");  
printList(head);  

deleteMinNode(&head); // 删除一个最小值结点  

printf("List after deleting a minimum node: ");  
printList(head);  

// 释放链表内存  
freeList(head);  

return 0;  

}

在这个程序中,我们首先定义了一个ListNode结构体来表示单链表的结点。然后,我们实现了创建新结点、向链表尾部添加结点、删除一个最小值结点和打印链表等功能。

deleteMinNode函数遍历链表找到最小值结点,并删除它。如果最小值结点是头结点之后的第一个结点,则直接更新头结点的next指针。否则,通过前驱结点minPrev的next指针跳过最小值结点。最后,释放最小值结点的内存。

注意,这个实现假设链表至少有一个非头结点。如果链表为空或只有一个结点(即头结点),则无法删除最小值结点,因为这种情况下不存在最小值结点。

在main函数中,我们创建了一个带头结点的单链表,并添加

标签:结点,单链,ListNode,head,有头,current,最小值,next
From: https://www.cnblogs.com/ZGLi/p/18151427

相关文章

  • 树2-二叉树拷贝, 遍历, 计算叶子结点和高度
    树2-二叉树拷贝,遍历,计算叶子结点和高度二叉树结点typedefstructBinaryNode{charch;structBinaryNode*lChild;structBinaryNode*rChild;}BinaryNode;//叶子结点的数量intsum;二叉树遍历前序//递归遍历(前序)voidRecursion(BinaryNode*roo......
  • 链表中环的入口结点
       1.先用快慢指针判断是否存在环2.返回快慢指针相遇的地方,一个指针停留在那里。3.另一个指针回到头节点4.两个节点一起走,每次走一格,再次相遇的地方就是入口节点publicclassSolution{    //判断有没有环,返回相遇的地方    publicListNodehasCycle(ListN......
  • 链表2: 动态单链表
    链表2:动态单链表定义数据结构//定义链表数据结构typedefstructLNode{intdata;structLNode*next;}LNode;初始化链表//初始化链表LNode*Init_LinkList(){//返回头指针//创建头结点LNode*header=(LNode*)malloc(sizeof(LNode));hea......
  • 链表1: 静态单链表
    链表1:静态单链表单链表的结构链表包含了数据域与指针域,数据域存储数据,指针域存储下一个结点的地址链表的特点链表的优势在于数据的删改,在链表中查询第$i$个元素需要从第一个结点开始遍历链表,,因此在数据的顺序读取中链表的优势不如数组.链表的插入操作设newN......
  • C语言简单的数据结构:单链表的有关算法题(1)
    算法题重点在于思路,代码其实并不难,这里的每一题都提供多种思路,大家可以动手写一下,并找到更好的解题方法这里先介绍前三道题目:1.单链表相关经典算法OJ题1:移除链表元素2.单链表相关经典算法OJ题2:反转链表3.单链表相关经典算法OJ题4:链表的中间结点1.单链表相关经典算......
  • C语言简单的数据结构:单链表
    目录:1.单链表的概念及结构2.单链表的实现2.1单链表的定义、创建和打印2.11单链表的定义2.12单链表的创建2.13单链表的打印2.2单链表的头插和尾插2.21尾插2.22头插2.3单链表的头删和尾删2.31尾删2.31头删2.4单链表的查找2.5单链表指定位置的插入和删除2.51指定位置前......
  • C语言单链表代码实现
    声明:著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除,求表长、有序表插入、元素逆置、2个有序表合并等。#include<stdio.h>#include<stdlib.h>//单链表的定义:typedefintDataType......
  • 数据结构:单链表
    一.链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。但是在逻辑结构上是顺序的。链表的结构其实就像的火车:车厢是独立存在的,且每节车厢都有车门。想象⼀下这样的场景,假设每节车厢的车门都是锁......
  • 解决hadoop的namenode和datanode结点启动不起来的问题
    首先介绍一下本人的情况:我的虚拟机最开始是可以启动的,后来删除了主节点,重新创建了一个主节点,并保持相同的主机名,并把从结点上的hadoop打包发到了主节点(前提已经弄好ssh和相关映射)tar-zcf~/hadoop.master.tar.gz./hadoop//将hadoop目录下的内容打包复制到~/hadoop.master.ta......
  • 【数据结构与算法篇】单链表及相关OJ算法题
    【数据结构与算法篇】单链表及相关OJ算法题......