c-如何删除双链表中所有最小的数字

Question

我有一个函数可以删除双链表中最小的节点。但是，如果有多个相同值的整数，函数会删除第一个。我需要做的是，该函数删除所有最小的值。

我想我需要做一个循环，检查链表中的所有值，如果它们是==到最小的值，就删除它们。

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
struct node *prev;
int number;
struct node *next;
} node;
node *createList(struct node *head, int n);
node *addToEmpty(node *head, int data);
node *addAtEnd(node *head, int data);
node *deleteSmallest(node *head, int n);
void cleanUp(node *head);
int main()
{
node *head = NULL;
node *ptr;
int n;
printf("Enter number of the nodes: ");
scanf("%d", &n);
head = createList(head, n);
printf("nN: %dnn", n);
ptr = head;
while(ptr != NULL)
{
printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%pn", ptr->number, ptr, ptr->prev, ptr->next);
ptr = ptr->next;
}
head = deleteSmallest(head, n);
printf("nn");
ptr = head;
while(ptr != NULL)
{
printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%pn", ptr->number, ptr, ptr->prev, ptr->next);
ptr = ptr->next;
}
// Free all the pointers
cleanUp(head);
return 0;
}
node *createList(struct node *head, int n)
{
int data;
if(n <= 0)
return head;
printf("Enter number of the 1 node: ");
scanf("%d", &data);
head = addToEmpty(head, data);
for(int i = 1; i < n; ++i)
{
printf("Enter number of the %d node: ", i + 1);
scanf("%d", &data);
head = addAtEnd(head, data);
}
return head;
}
node *addToEmpty(node *head, int data)
{
node *temp = malloc(sizeof(node));
temp->prev = NULL;
temp->next = NULL;
temp->number = data;
head = temp;
return head;
}
node *addAtEnd(node *head, int data)
{
node *temp, *tp;
temp = malloc(sizeof(node));
temp->prev = NULL;
temp->next = NULL;
temp->number = data;
tp = head;
while (tp->next != NULL)
tp = tp->next;
tp->next = temp;
temp->prev = tp;
return head;
}
node *deleteSmallest(node *head, int n)
{
node *smallest, *temp, *temporaryHead;
int position = 1;
temporaryHead = head;
smallest = head;
// Finding which node has the smallest int
for(int i = 1; temporaryHead != NULL; ++i)
{
temp = temporaryHead->next;
if(smallest->number > temporaryHead->number)
{
smallest = temporaryHead;
position = i;
}
temporaryHead = temp;
}
temporaryHead = NULL;
temp = head;
// If node is in the middle
if(position > 1 && position < n)
{
while (position > 1) {
temp = temp->next;
--position;
}
temporaryHead = temp->prev;
temporaryHead->next = temp->next;
temp->next->prev = temporaryHead;
free(temp);
temp = NULL;
}else if(position == 1)             // If node is the first element
{
head = head->next;
free(head->prev);
head->prev = NULL;
}else                               // If node is the last element
{
while(temp->next != NULL)
temp = temp->next;
temporaryHead = temp->prev;
temporaryHead->next = NULL;
free(temp);
temp = NULL;
}
return head;
}
void cleanUp(node *head)
{
node *next;
while(head != NULL)
{
next = head->next;
free(head);
head = next;
}
}

Answer 1

我想我需要做一个循环，检查链表中的所有值，如果它们==为最小值，就删除它们。

我不太理解您当前函数的逻辑(尤其是n参数)。

这里有一个函数，只允许删除一个元素，或者所有匹配最小元素。如果只有一个，那就是一次扫描。如果有更多，那就是两次扫描：

// deleteSmallAll -- delete all nodes that are the smallest
node *
deleteSmallAll(node *head,int allflg)
// allflg -- 1=delete all, 0=delete first
{
node *small = head;
int smcount = 0;
int smnum = 0;
node *cur = head;
// skip over the first element (and assume it is the smallest)
if (cur != NULL) {
cur = cur->next;
smcount = 1;
smnum = small->number;
}
// find the smallest
for (;  cur != NULL;  cur = cur->next) {
int curnum = cur->number;
// got a smaller element
if (curnum < smnum) {
smcount = 1;
small = cur;
smnum = curnum;
continue;
}
// keep count of duplicate small numbers
if (curnum == smnum) {
if (allflg)
smcount += 1;
continue;
}
}
// start with the _first_ smallest node we found
cur = small;
// remove a single smallest and loop if more to do
while (cur != NULL) {
node *next = cur->next;
node *prev = cur->prev;
// unlink it
if (prev != NULL)
prev->next = next;
else
head = next;
// unlink it
if (next != NULL)
next->prev = prev;
// NOTE: no tail pointer
#if 0
else
tail = prev;
#endif
// release the node
free(cur);
// bug out if no more of that match
if (--smcount <= 0)
break;
// find the next in the list that is the same match
for (cur = next;  cur != NULL;  cur = cur->next) {
if (cur->number == smnum)
break;
}
}
return head;
}

---

更新：

希望你的基本问题已经得到了答案。

但是，正如其他人所指出的，如果仅向前遍历，那么拥有双链表有什么意义？

以下是更新版本。它使用一个单独的list结构，并向其传递指针，而不是传入head并始终返回更新后的值。

#include <stdio.h>
#include <stdlib.h>
#include <termios.h>
typedef struct node {
struct node *prev;
int number;
struct node *next;
} node;
typedef struct {
node *head;
node *tail;
} list;
int
getnum(const char *prompt)
{
char buf[100];
int data = 0;
// debug hook for input from redirected file (e.g. ./myprogram < input.txt)
struct termios tio;
int fileflg = tcgetattr(fileno(stdin),&tio) < 0;
while (1) {
printf("%s: ",prompt);
fflush(stdout);
if (fgets(buf,sizeof(buf),stdin) == NULL) {
printf("getnum: premature EOFn");
if (fileflg)
exit(1);
}
// echo the file input
if (fileflg)
fputs(buf,stdout);
if (sscanf(buf,"%d",&data) == 1)
break;
}
return data;
}
void
addAtEnd(list *lst, int data)
{
node *temp;
temp = malloc(sizeof(node));
temp->number = data;
if (lst->head == NULL)
lst->head = temp;
node *tail = lst->tail;
if (tail != NULL) {
temp->next = tail->next;
tail->next = temp;
temp->prev = tail;
}
else
temp->prev = NULL;
lst->tail = temp;
temp->next = NULL;
}
void
createList(list *lst, int n)
{
int data;
char msg[100];
for (int i = 0; i < n; ++i) {
sprintf(msg,"Enter number of the %d node", i + 1);
data = getnum(msg);
addAtEnd(lst, data);
}
}
// deleteSmallAll -- delete all nodes that are the smallest
void
deleteSmallAll(list *lst,int allflg)
// allflg -- 1=delete all, 0=delete first
{
node *small = lst->head;
int smcount = 0;
int smnum = 0;
node *cur = lst->head;
// skip over the first element (and assume it is the smallest)
if (cur != NULL) {
smcount = 1;
smnum = small->number;
cur = cur->next;
}
// find the smallest
for (;  cur != NULL;  cur = cur->next) {
int curnum = cur->number;
// got a smaller element
if (curnum < smnum) {
smcount = 1;
small = cur;
smnum = curnum;
continue;
}
// keep count of duplicate small numbers
if (curnum == smnum) {
if (allflg)
smcount += 1;
continue;
}
}
// start with the _first_ smallest node we found
cur = small;
// remove a single smallest and loop if more to do
while (cur != NULL) {
node *next = cur->next;
node *prev = cur->prev;
// unlink it
if (prev != NULL)
prev->next = next;
else
lst->head = next;
// unlink it
if (next != NULL)
next->prev = prev;
else
lst->tail = prev;
// release the node
free(cur);
// bug out if no more of that match
if (--smcount <= 0)
break;
// find the next in the list that is the same match
for (cur = next;  cur != NULL;  cur = cur->next) {
if (cur->number == smnum)
break;
}
}
}
void
cleanUp(list *lst)
{
node *next;
for (node *cur = lst->head;  cur != NULL;  cur = next) {
next = cur->next;
free(cur);
}
lst->head = NULL;
lst->tail = NULL;
}
void
print_fwd(list *lst,const char *msg)
{
node *ptr = lst->head;
printf("n%s:n",msg);
for (;  ptr != NULL;  ptr = ptr->next)
printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%pn",
ptr->number, ptr, ptr->prev, ptr->next);
}
void
print_bwd(list *lst,const char *msg)
{
node *ptr = lst->tail;
printf("n%s:n",msg);
for (;  ptr != NULL;  ptr = ptr->prev)
printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%pn",
ptr->number, ptr, ptr->prev, ptr->next);
}
int
main(void)
{
list lstx = { NULL, NULL };
list *lst = &lstx;
node *ptr;
int n;
n = getnum("Enter number of the nodes");
createList(lst, n);
printf("nN: %dn", n);
print_fwd(lst,"orig/fwd");
print_bwd(lst,"orig/bwd");
deleteSmallAll(lst, 0);
print_fwd(lst,"after1/fwd");
print_bwd(lst,"after1/bwd");
deleteSmallAll(lst, 1);
print_fwd(lst,"afterN/fwd");
print_bwd(lst,"afterN/bwd");
// Free all the pointers
cleanUp(lst);
return 0;
}

这是示例输入：

6
2
6
2
7
8
2

以下是示例输出：

Enter number of the nodes: 6
Enter number of the 1 node: 2
Enter number of the 2 node: 6
Enter number of the 3 node: 2
Enter number of the 4 node: 7
Enter number of the 5 node: 8
Enter number of the 6 node: 2
N: 6
orig/fwd:
NUMBER:2 ADDRESS:0x11a4280 PREVADD:(nil) NEXTADD:0x11a42a0
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:0x11a4280 NEXTADD:0x11a42c0
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)
orig/bwd:
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:0x11a4280 NEXTADD:0x11a42c0
NUMBER:2 ADDRESS:0x11a4280 PREVADD:(nil) NEXTADD:0x11a42a0
after1/fwd:
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42c0
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)
after1/bwd:
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42c0
afterN/fwd:
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42e0
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42a0 NEXTADD:0x11a4300
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:(nil)
afterN/bwd:
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:(nil)
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42a0 NEXTADD:0x11a4300
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42e0

Answer 2

我会把逻辑分成几个部分：

• 一个函数，用于查找列表中最小的值(整数)
• 从具有给定值的列表中删除节点的函数
• 使用以上两个函数来实现deleteSmallest

下面是它的样子：

int getSmallestValue(node *head) {
int smallest = head == NULL ? 0 : head->number;
while (head != NULL) {
if (head->number < smallest) {
smallest = head->number;
}
head = head->next;
}
return smallest;
}
node* deleteValue(node *head, int n) {
node* temp, *current;
while (head != NULL && head->number == n) {
temp = head;
head = head->next;
free(temp);
}
head->prev = NULL;
current = head->next;
while (current != NULL) {
temp = current;
current = current->next;
if (temp->number == n) {
temp->prev->next = current;
if (current != NULL) {
current->prev = temp->prev;
}
free(temp);
}
}
return head;
}
node *deleteSmallest(node *head, int n) {
return deleteValues(head, getSmallestValue(head));
}

Answer 3

如果您关心性能，您可能会使用addAtEnd()而不是addToFront()。这将把输入数字的渐近时间从O(n^2)减少到O(n)。

如果您必须一次又一次地删除最小值，则链表实际上并不适合。正如您所观察到的，如果要找到最小值，则必须遍历所有输入，每次都需要O(n)。在这种情况下，二进制堆将允许O(log n)删除最小值。它通过heapify来实现这一点，其中通过在O(n)中筛选来创建堆，并保持每个int的堆属性小于或等于int的子级。

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <errno.h>
static void int_to_string(const int *i, char (*const a)[12])
{ sprintf(*a, "%d", *i); }
#define HEAP_NAME int
#define HEAP_TYPE int
#define HEAP_TO_STRING
#include "heap.h"
int main(int argc, char **argv) {
struct int_heap ints = int_heap();
size_t n = 0;
int success = EXIT_SUCCESS;
(void)argc; /* Don't use. */
while(*++argv) { /* Get command line arguments. */
long argl;
char *end;
int *a;
argl = strtol(*argv, &end, 0); /* Convert to `long`. */
if(argl < INT_MIN || argl > INT_MAX || end == *argv || *end != '')
{ if(!errno) errno = ERANGE; goto catch; }
if(!(a = int_heap_buffer(&ints, n + 1))) goto catch;
a[n++] = (int)argl;
}
int_heap_append(&ints, n); /* Heapifies, O(n), <Floyd, 1964, Treesort>. */
while(ints.as_array.size) printf("pop: %d, remainder: %sn",
int_heap_pop(&ints), int_heap_to_string(&ints));
printf("emptyn");
goto finally;
catch:
success = EXIT_FAILURE;
perror("count");
finally:
int_heap_(&ints);
return success;
}

我已经使用了二进制堆的实现，我已经尝试将其标准化。这与heapsort的作用非常接近。