思路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