添加/删除链表中的第一个元素

Adding/deleting the first element in a linked list

提问人:X_Abhishek_X 提问时间:9/2/2023 最后编辑:Vlad from MoscowX_Abhishek_X 更新时间:9/2/2023 访问量:69

问:

我正在尝试插入/删除链表中的第一个元素,但是在插入的情况下,它不会添加它,并且在删除的情况下,它会启动无限链,我无法识别问题。 我目前正在学习 DSA,所以请忽略代码中添加的任何不必要的注释

我创建的代码(C语言)

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

struct Linked_List                      //structure has to be defined first
{
    int number;
    struct Linked_List *next;
};

typedef struct Linked_List node;

void create(node *p);
int count(node *p);
void print(node *p);
node *insert(node *head);
node *find(node *p, int key);
node *delete(node *head);

int main() {
    node *head;
    head = (node *)malloc(sizeof(node));
    create(head);
    printf("\n");
    print(head);
    printf("\n\nThe total number of elements in the linked list are :- %d",count(head));
    printf("\n");
    insert(head);
    printf("\n");
    print(head);
    printf("\n");
    delete(head);
    printf("\n");
    print(head);
}

void create(node *p) {
    printf("\nInput number (Input -999 to end) :- ");
    scanf("%d", &p->number);

    if (p->number == -999) {
        p->next = NULL;
    } else {
        p->next = (node *)malloc(sizeof(node));
        create(p->next);
    }
}

int count(node *p) {
    if (p->next == NULL) {            //using the if we are not counting the last element (-999)
        return 0;                   //return 1    will add the last element to total count
    } else {
        return 1 + count(p->next);
    }

    //return 1 + count(p->next);            //FAIL (as at last returns null pointer pointing to nowhere) returns total elements including -999,
}

void print(node *p) {
    
    // printf("%d --> ", p->number);        //this fails as in the end it will pass a null pointer which doesn't points to anywhere
    // print(p->next);
    
    if (p->next != NULL) {                        //this works as it first checks if pointer is null or not 
        printf("%d --> ", p->number);            //if not it prints the number and recursion occurs
        if (p->next->next == NULL) {              //this if statement is used to print the last value which holds null pointer as outer if will not process it,
            printf("%d", p->next->number);       //it checks for next value if null pointer then prints its value
        }
        print(p->next);
    }    
}

node *insert(node *head) {
    node *new;                                  //structure of list
    node *preceding;                            // preceding -> new -> key
    int x, key;

    printf("\nEnter the new value to be added :- ");
    scanf("%d", &x);
    printf("\nValue of key item (-999 if last) {-> new -> key}:- ");
    scanf("%d", &key);

    if (head->number == key) {                            //case for first position
        new = (node *)malloc(sizeof(node));
        new->number = x;
        new->next = head;
        head = new;
    } else {
        preceding = find(head, key);
        if (preceding == NULL) {
            printf("\nKey not found!!\n");
        } else {
            new = (node *)malloc(sizeof(node));
            new->number = x;
            new->next = preceding->next;
            preceding->next = new;
        }
    }
    return head;
}

node *delete(node *head) {
    int key;        //item to be deleted
    node *preceding;
    node *p;        //temporary node
    
    printf("\nEnter the item to be deleted :- ");
    scanf("%d",&key);

    if (head->number == key) {
        p = head->next;
        free(head);
        head = p;
    } else {
        preceding = find(head, key);
        if (preceding == NULL) {
            printf("\nKey not found!!\n");
        } else {
            p = preceding->next->next;
            free(preceding->next);
            preceding->next = p;
        }
    }
    return head;
}

node *find(node *p, int key) {
    if (p->next->number == key) {           //we know it is not the first so checking 2nd from head
        return p;
    } else {                                 //checking 3rd from head
        if (p->next->next == NULL) {
            return NULL;
        } else {
            find(p->next, key);              //recursive call
        }
    }
}

我试图获取指针来保存新位置,但由于某种原因,它不起作用,就像插入功能一样,如下所示

new->next = head;
head = new;
c malloc singly-linked-list 函数调用

评论

0赞 chqrlie 9/2/2023
该列表有一个虚拟的初始节点。这个实现是你自己想出来的,还是你从在线DSA课程中获得的?
0赞 Vlad from Moscow 9/2/2023
@X_Abhishek_X 显示从列表中输入或删除的数据。
0赞 X_Abhishek_X 9/2/2023
@chqrlie 是的,来自一本书 E balgurusamy ANSI C
0赞 William Pursell 9/2/2023
delete(head)不会在 main 中修改。事实上,它不能。您可能只需要(或更改 api 以传递headhead = delete(head);&head)
0赞 chqrlie 9/3/2023
@X_Abhishek_X:这本书在链表章节中暴露了非常糟糕的例子。恐怕你应该忽略它并使用其他来源。

答:

1赞 Özgür Güzeldereli 9/2/2023 #1

据我了解,您正在返回头部,但您没有在主方法中设置它。你的意思是做这样的事情:

head = insert(head);
printf("\n");
print(head);
printf("\n");
head = delete(head);

另外,也许您需要在 find 方法中返回:

return find(p->next, key);              //recursive call
1赞 Vlad from Moscow 9/2/2023 #2

使用包含该值的最后一个虚拟节点的方法只会使列表的用户感到困惑。-999

例如,为什么用户自己要分配一个虚拟节点,而有 create 函数?!谁实际创建了列表、用户或函数?!create

函数中的此提示create

printf("\nInput number (Input -999 to end) :- ");

假定该值不会存储在列表中。-999

例如,在这种情况下,函数的行为是不可预测的。print

让我们来看看当列表只包含一个值为 的 dymmy 节点时的情况。-999

在这种情况下,由于以下 if 语句,将输出 nothng

if (p->next != NULL) {                        //this works as it first 

现在,我们假设 lst 包含两个节点,例如 values 和 .在这种情况下,由于嵌套的 if 语句,将输出这两个值1-999

if (p->next->next == NULL) {`

该函数有一个错误。这部分没有返回 statement.infind

    } else {
        find(p->next, key);              //recursive call
    }

此外,当列表仅包含一个节点时,该函数可以调用未定义的行为,该节点的值由此语句引起find-999

if (p->next->number == key) {           //we know it is not the first so checking 2nd from head

为什么你认为我们知道它不是列表的第一个节点?!functon 在函数中被调用,如下所示insert

preceding = find(head, key);

如果列表只包含一个虚拟节点,如何插入节点?为什么您决定用户在任何时候都知道列表只包含单个虚拟节点?他是否每次都要插入新节点时都必须调用该函数?count

最后,函数 insert 必须像这样调用

head = insert( head );

同样,函数也必须被调用delete

head = delete( head );

此外,您还需要编写一个函数,该函数将在列表不再被重新定义时释放所有分配的内存。

您应该重新编写所有代码,从列表实现中删除虚拟节点。

评论

0赞 chqrlie 9/3/2023
我100%同意。虚拟初始节点是个坏主意。代码来自一本印度书:事实上,这本书并没有完全建议使用虚拟节点,但他们确实在调用初始化它之前分配了初始节点,分配了节点并递归进行初始化......非常糟糕的榜样和破碎的教学。createnext
0赞 Vlad from Moscow 9/3/2023
@chqrlie 通常印度书籍质量低下。例如,在许多书中,functon main 被声明为 void main()。
0赞 chqrlie 9/3/2023
是的,这很常见,在这种情况下,这本书是恐怖的集合,例如函数体内部的函数原型,缺乏测试或返回值,提倡没有返回类型的过时原型和带有返回类型的无效原型......全部在 2009 年的第 9 次重印中!scanf()malloc()main()void