链表函数的几个问题 [英] Several problems with Linked Lists functions

查看：46
本文介绍了链表函数的几个问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我尝试为链表创建几个函数.这是所有这些，但我对函数 delete_All 和 delete 有问题.

I tried to create several functions for linked lists. Here are all of them, but i have problem with function delete_All and delete.

delete_All 需要删除所有给定值的元素，delete 只需要先删除.

delete_All need to delete all elements with given value, and delete only first.

我找不到的第一个错误是 free(_)(在代码中标记为HERE!!!")以及 delete_All 中无休止的程序工作当我们放入链表的head，同时放入下一个需要删除的元素值.

The first mistake that i cannt find is free(_) (marked in code as "HERE!!!") and also endless program work in delete_All when we put in head of Linked List and at the same time in the next element value which needs to be removed.

例如 (1,1,2,3,4,) 不能删除第一对1".delete 和其他一些功能不能使用free 功能.

For example (1,1,2,3,4,) cannt remove first pair "1". delete and some other functions cannt use free function.

#include <stdlib.h>
#include <stdio.h>

struct uzel {
    int n;
    struct uzel *next;
};

struct uzel *
initializef(struct uzel *head)
{
    static int c = 0;
    int a;

    printf("uzel[%d] = ", c);
    scanf("%d", &a);
    if (a == 0) {
        head->next = NULL;
    }
    else {
        c++;
        head->n = a;
        head->next = malloc(sizeof(struct uzel));
        initializef(head->next);
    }
    return head;
}

void
gprint(struct uzel *head)
{
    printf("(");
    while (head->next != NULL) {
        printf("%d ", head->n);
        head = head->next;
    }
    printf(")\n");
}

struct uzel *
delete(struct uzel *head, int val)
{
    if (head->n == val) {
        struct uzel *newhead = head;

        newhead = head->next;
        struct uzel *del = head;

        // free(del);//HERE!!!!!!!!!
        return newhead;
    }
    struct uzel *right = head;
    struct uzel *left = right;

    while (left->next) {
        right = left->next;
        if (right->next != NULL) {
            if (right->n == val) {
                struct uzel *del = right;

                left->next = right->next;
                free(del);
            }
        }                               // but here is ok!!!
        left = left->next;
    }
    return head;
}

struct uzel *
delete_all(struct uzel *head, int val)
{
    struct uzel *newhead = head;

    while (newhead->n == val) {
        newhead = head->next;
        // struct uzel* del=head;//here!!!!!!!!!!!!!!
        // free(del);
        if ((newhead->n) == NULL) {
            printf("No more elements to work with,ERROR");
            return 0;
        }
    }
    struct uzel *right = newhead;
    struct uzel *left = newhead;

    while (left->next) {
        right = right->next;
        if (right->n == val) {
            struct uzel *tmp = right;

            left->next = right->next;
            free(tmp);
        }
        else {
            left = left->next;
        }
    }
    return newhead;
}

void
addAfter(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((left->n) != after_what) {
        right = right->next;
        left = left->next;
    }
    right = right->next;
    struct uzel *newelem = malloc(sizeof(struct uzel));

    newelem->n = info;
    newelem->next = right;
    left->next = newelem;
}

void
addAfterALL(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((right->next)) {
        while (((left->n) != after_what)) {
            right = right->next;
            left = left->next;
        }
        right = right->next;
        struct uzel *newelem = malloc(sizeof(struct uzel));

        newelem->n = info;
        newelem->next = right;
        left->next = newelem;
    }
}

int
main()
{
    int a, b;
    struct uzel head2;
    struct uzel *mainhead1 = initializef(&head2);

    gprint(mainhead1);
    printf("Enter a number to delete: ");
    scanf("%d", &a);
    printf("Delete all %d ? If yes enter 2 if no enter 1: ", a);
    scanf("%d", &b);
    if (b == 2) {
        struct uzel *mainhead = delete_all(mainhead1, a);

        gprint(mainhead);
    }
    else {
        struct uzel *mainhead = delete(mainhead1, a);

        gprint(mainhead);
    }
    printf("Enter after what number u want to insert smth: ");
    int r;

    scanf("%d", &r);
    printf("Enter what number u want to insert: ");
    int u;

    scanf("%d", &u);
    printf("After all numbers %d ? If yes enter 1 If no enter 2:", r);
    int g;

    scanf("%d", &g);
    if (g == 2) {
        addAfter(u, r, mainhead1);
        gprint(mainhead1);
    }
    if (g == 1) {
        addAfterALL(u, r, mainhead1);
        gprint(mainhead1);
    }
}

推荐答案

delete 和 delete_All 的代码非常相似，所以可以移到一个通用函数.

The code for delete and delete_All is very similar, so it can be moved to a common function.

这是一个重构版本(带有一些注释)，它简化了删除代码并使其适用于两种情况.

Here's a refactored version (with some annotations) that simplifies the delete code and makes it work for both cases.

注意使用额外的 next 变量来防止释放后使用"；[这可能是调用 free 时出现问题的根源].

Note the use of the extra next variable to prevent "use after free" [which may have been the source of the issues with calling free].

#include <stdlib.h>
#include <stdio.h>

struct uzel {
    int n;
    struct uzel *next;
};

struct uzel *
initializef(struct uzel *head)
{
    static int c = 0;
    int a;

    printf("uzel[%d] = ", c);
    scanf("%d", &a);
    if (a == 0) {
        head->next = NULL;
    }
    else {
        c++;
        head->n = a;
        head->next = malloc(sizeof(struct uzel));
        initializef(head->next);
    }
    return head;
}

void
gprint(struct uzel *head)
{
    printf("(");
    while (head->next != NULL) {
        printf("%d ", head->n);
        head = head->next;
    }
    printf(")\n");
}

struct uzel *
delete_common(struct uzel *head, int val, int allflg)
{
    struct uzel *cur;
    struct uzel *prev;
    struct uzel *next;

    prev = NULL;
    for (cur = head;  cur != NULL;  cur = next) {
        next = cur->next;

        // wait for match
        if (cur->n != val) {
            prev = cur;
            continue;
        }

        // remove from middle/end of list
        if (prev != NULL)
            prev->next = next;

        // remove from head of list
        else
            head = next;

        // release the storage for the node we're deleting
        free(cur);

        // stop if we're only deleting the first match
        if (! allflg)
            break;
    }

    return head;
}

struct uzel *
delete(struct uzel *head, int val)
{

    head = delete_common(head,val,0);

    return head;
}

struct uzel *
delete_all(struct uzel *head, int val)
{

    head = delete_common(head,val,1);

    return head;
}

void
addAfter(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((left->n) != after_what) {
        right = right->next;
        left = left->next;
    }
    right = right->next;
    struct uzel *newelem = malloc(sizeof(struct uzel));

    newelem->n = info;
    newelem->next = right;
    left->next = newelem;
}

void
addAfterALL(int info, int after_what, struct uzel *head)
{
    struct uzel *left = head;
    struct uzel *right = head;

    while ((right->next)) {
        while (((left->n) != after_what)) {
            right = right->next;
            left = left->next;
        }
        right = right->next;
        struct uzel *newelem = malloc(sizeof(struct uzel));

        newelem->n = info;
        newelem->next = right;
        left->next = newelem;
    }
}

int
main()
{
    int a, b;
    struct uzel head2;
    struct uzel *mainhead1 = initializef(&head2);

    gprint(mainhead1);
    printf("Enter a number to delete: ");
    scanf("%d", &a);
    printf("Delete all %d ? If yes enter 2 if no enter 1: ", a);
    scanf("%d", &b);
    if (b == 2) {
        struct uzel *mainhead = delete_all(mainhead1, a);

        gprint(mainhead);
    }
    else {
        struct uzel *mainhead = delete(mainhead1, a);

        gprint(mainhead);
    }
    printf("Enter after what number u want to insert smth: ");
    int r;

    scanf("%d", &r);
    printf("Enter what number u want to insert: ");
    int u;

    scanf("%d", &u);
    printf("After all numbers %d ? If yes enter 1 If no enter 2:", r);
    int g;

    scanf("%d", &g);
    if (g == 2) {
        addAfter(u, r, mainhead1);
        gprint(mainhead1);
    }
    if (g == 1) {
        addAfterALL(u, r, mainhead1);
        gprint(mainhead1);
    }
}

更新:

刚刚检查了代码，在delete_all中尝试使用free(cur)时仍然有问题实际上是在删除一个列表的头部时出现的问题

just checked code, still have problems with free(cur) when trying to use it in delete_all actually the problem appears when delete a head of a list

好的.有两种方法可以拥有/使用链表的head:

Okay. There are two ways to have/use a head of a linked list:

  1. 它可以是第一个有效节点(带有数据).
  2. 它可以是一个假人"；节点(我们忽略数据的地方)，第一个有效的数据节点是 head->next 指向的节点.
  1. It can be the first valid node (with data).
  2. It can be a "dummy" node (where we ignore the data) and the first valid data node is what head->next points to.

我编写了假设 (1) 的删除函数.但是，在查看更多代码后，我相信您正在使用(2).

I coded up the delete functions assuming (1). But, after looking over the code some more, I believe you're using (2).

做任何一个都完全有效.但是，如果使用 (2)，它将重用节点结构作为列表结构.这仍然有效，但我更喜欢添加一个明确的列表结构以使事情更清楚.

It is perfectly valid to do either. But, if using (2), it is reusing a node struct as a list struct. This is still valid, but I prefer to add an explicit list struct to make things more clear.

让我更困惑的是做一个return head;.这就是我们为 (1) 所做的.如果我们做 (2)，我们可以完全消除 return 并只更新 head->next.

What added to my confusion was doing a return head;. This is what we'd do for (1). If we do (2), we can eliminate the return altogether and just update head->next.

我最初的修复假设是 (1)，这使它与其他函数使用的 (2) 不兼容.

My original fix assumed (1) and that made it incompatible with (2), which is what the other functions were using.

我已重构代码以使用单独的 list 结构.

I've refactored the code to use a separate list struct.

此外，在完成工作后，addAfter 函数需要一些工作，因为 addAfter 没有处理我们在返回后添加元素的情况返回具有相同值的节点.例如，尝试在 5 之后添加 9 列表:

Also, after getting that working, the addAfter function(s) needed some work because the addAfter didn't handle the case where we added an element after back to back nodes with the same value. For example, trying to add 9 after 5 with a list of:

1 1 2 3 4 5 5 6 7

制作:

1 1 2 3 4 5 9 6 7

代替:

1 1 2 3 4 5 9 5 6 7

再一次，两个addAfter函数可以组合和简化.

Once again, the two addAfter functions can be combined and simplified.

关于使用 list 结构的一些额外想法...

Some additional thoughts on the use of the list struct ...

当我们传递一个列表指针时，调用者不必担心被调用者是否不得不调整列表的头部列表.被调用的函数就是这样做的.

When we pass a list pointer around, the caller does not have to worry about whether the callee had to adjust the head of the list. The called function just does it.

在原始代码中，delete* 函数传回了[可能]修改的head.addAfter* 函数不能 [由于它们的性质] 更改列表的头部，因此它们不必返回更新的头部值.在这两种情况下，这些函数的调用者(即main)必须知道"这个.

In the original code, the delete* functions passed back the [possibly] modified head. The addAfter* functions could not [due to their nature] change the head of the list, so they didn't have to return an updated head value. In both cases, the caller of these functions (i.e. main) had to "know" this.

如果我们向 addAfter* 添加了一组类似的函数，该函数在 before 中插入了 info 值(例如 insertBefore*)，他们可能必须更新头部.同样，调用者必须知道这一点.

If we added a similar set of functions to addAfter* that did the insert before the info value (e.g. insertBefore*), they might have to update the head. Again, the caller would have to know about this.

因此，使用struct list实际上简化了大多数函数的代码，并允许它们具有更统一的参数集.(例如)list 是第一个参数，函数可以按照它的选择完全操作它而无需返回任何内容.

So, using struct list actually simplifies the code for most functions and allows them to have a more unified set of parameters. (e.g.) The list is the first argument and the function can fully manipulate it as it chooses without needing to return anything.

在我做这一切时，我注意到initializef 是递归.虽然这样做 是有效的，但 IMO，这 不是很好地使用递归.迭代解决方案更简洁.

As I was doing all that, I noticed the initializef was recursive. While it is valid to do that, IMO, that's not a good use of recursion. An iterative solution is cleaner.

无论如何，这是更新后的代码.希望我对边缘情况进行了更多测试.但是，您可能需要对其进行彻底测试以确保.

Anyway, here's the updated code. Hopefully, I tested it for the edge cases a bit more. But, you may want to test it thoroughly to be sure.

#include <stdlib.h>
#include <stdio.h>

struct uzel {
    int n;
    struct uzel *next;
};

struct list {
    struct uzel *head;
};

void
initializef(struct list *list)
{
    int c = 0;
    int a;
    struct uzel *newelem;
    struct uzel *prev;

    prev = NULL;
    while (1) {
        printf("uzel[%d] = ", c);

        scanf("%d", &a);

        if (a == 0)
            break;

        newelem = malloc(sizeof(*newelem));
        newelem->n = a;
        newelem->next = NULL;

        if (prev != NULL)
            prev->next = newelem;
        else
            list->head = newelem;

        prev = newelem;

        ++c;
    }
}

void
gprint(struct list *list)
{
    struct uzel *cur;

    printf("(");

    for (cur = list->head;  cur != NULL;  cur = cur->next)
        printf("%d ",cur->n);

    printf(")\n");
}

void
delete_common(struct list *list, int val, int allflg)
{
    struct uzel *cur;
    struct uzel *prev;
    struct uzel *next;

    prev = NULL;
    for (cur = list->head;  cur != NULL;  cur = next) {
        next = cur->next;

        // wait for match
        if (cur->n != val) {
            prev = cur;
            continue;
        }

        // remove from middle/end of list
        if (prev != NULL)
            prev->next = next;

        // remove from head of list
        else
            list->head = next;

        // release the storage for the node we're deleting
        free(cur);

        // stop if we're only deleting the first match
        if (! allflg)
            break;
    }
}

void
delete(struct list *list, int val)
{

    delete_common(list,val,0);
}

void
delete_all(struct list *list, int val)
{

    delete_common(list,val,1);
}

void
addAfter_common(struct list *list, int info, int after_what, int allflg)
{
    struct uzel *cur;
    struct uzel *newelem;

    for (cur = list->head;  cur != NULL;  cur = cur->next) {
        // wait for a match
        if (cur->n != after_what)
            continue;

        // get new element to add
        newelem = malloc(sizeof(*newelem));
        newelem->n = info;

        // insert new element after the match
        newelem->next = cur->next;
        cur->next = newelem;

        // ensure that we don't infinitely add elements if the element value
        // we're adding matches the value(s) we're searching for
        // (e.g.) if info and after_what are the same
        cur = newelem;

        // stop unless adding after _all_ matches
        if (! allflg)
            break;
    }
}

void
addAfter(struct list *list, int info, int after_what)
{

    addAfter_common(list,info,after_what,0);
}

void
addAfterALL(struct list *list, int info, int after_what)
{

    addAfter_common(list,info,after_what,1);
}

int
main(void)
{
    int a, b;
    struct list listx = { .head = NULL };
    struct list *list = &listx;

    initializef(list);
    gprint(list);

    printf("Enter a number to delete: ");
    scanf("%d", &a);

    printf("Delete all %d ? If yes enter 2 if no enter 1: ", a);
    scanf("%d", &b);
    if (b == 2) {
        delete_all(list, a);
        gprint(list);
    }
    else {
        delete(list, a);
        gprint(list);
    }

    printf("Enter after what number you want to insert something: ");
    int r;
    scanf("%d", &r);

    printf("Enter what number you want to insert: ");
    int u;
    scanf("%d", &u);

    printf("After all numbers %d ? If yes enter 1 If no enter 2:", r);
    int g;
    scanf("%d", &g);

    if (g == 2) {
        addAfter(list, u, r);
        gprint(list);
    }
    if (g == 1) {
        addAfterALL(list, u, r);
        gprint(list);
    }

    return 0;
}

这篇关于链表函数的几个问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆