C语言 如何删除双向链表中的所有最小数

2vuwiymt  于 2022-12-11  发布在  其他
关注(0)|答案(3)|浏览(144)

我有一个函数，可以删除双向链表中最小的节点，但是如果有多个相同值的整数，这个函数会删除第一个，我需要做的是，这个函数会删除所有最小的值。
我想我需要做一个循环，检查链表中的所有值，如果它们是==到最小的值，就删除它们。

#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: %d\n\n", n);

    ptr = head;

    while(ptr != NULL)
    {
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n", ptr->number, ptr, ptr->prev, ptr->next);
        ptr = ptr->next;
    }

    head = deleteSmallest(head, n);

    printf("\n\n");

    ptr = head;

    while(ptr != NULL)
    {
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n", 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;
    }
}
c

3条答案

按热度按时间
qf9go6mv

qf9go6mv1#

我想我需要做一个循环，检查链表中的所有值，如果它们是==到最小的值，就删除它们。
我不太理解当前函数的逻辑（特别是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 EOF\n");
            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:%p\n",
            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:%p\n",
            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: %d\n", 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
赞(0）分享  回复(0）举报  2022-12-11
cwxwcias

cwxwcias2#

我将把逻辑分成几部分：

  • 查找列表中最小 * 值 *（整数）的函数
  • 用于从列表中删除具有给定值的节点的函数
  • 使用以上两个函数实现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));
}
赞(0）分享  回复(0）举报  2022-12-11
aamkag61

aamkag613#

如果你关心的是性能，你可以用addToFront()代替addAtEnd()，这样可以减少从O(n^2)到O(n)输入数字的渐近时间。
如果你必须一次又一次地删除最小值，链表并不是一个很好的选择。正如你所观察到的，如果你想找到最小值，就必须遍历所有的输入，每次都需要O(n)。在这种情况下，binary heap允许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 != '\0')
            { 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: %s\n",
        int_heap_pop(&ints), int_heap_to_string(&ints));
    printf("empty\n");
    goto finally;
catch:
    success = EXIT_FAILURE;
    perror("count");
finally:
    int_heap_(&ints);
    return success;
}

我使用了我的implementation of a binary heap，我试着让它变得很标准，这和heapsort的功能很接近。

赞(0）分享  回复(0）举报  2022-12-11
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com