提问人:X_Abhishek_X 提问时间:9/2/2023 最后编辑:Vlad from MoscowX_Abhishek_X 更新时间:9/2/2023 访问量:69
添加/删除链表中的第一个元素
Adding/deleting the first element in a linked list
问:
我正在尝试插入/删除链表中的第一个元素,但是在插入的情况下,它不会添加它,并且在删除的情况下,它会启动无限链,我无法识别问题。 我目前正在学习 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;
答:
据我了解,您正在返回头部,但您没有在主方法中设置它。你的意思是做这样的事情:
head = insert(head);
printf("\n");
print(head);
printf("\n");
head = delete(head);
另外,也许您需要在 find 方法中返回:
return find(p->next, key); //recursive call
使用包含该值的最后一个虚拟节点的方法只会使列表的用户感到困惑。-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 );
此外,您还需要编写一个函数,该函数将在列表不再被重新定义时释放所有分配的内存。
您应该重新编写所有代码,从列表实现中删除虚拟节点。
评论
create
next
scanf()
malloc()
main()
void
评论
delete(head)
不会在 main 中修改。事实上,它不能。您可能只需要(或更改 api 以传递head
head = delete(head);
&head
)