我试图用C创建一个函数来删除每个奇数定位的节点。例如,1,2,3,4
变得2,4
。
这是我尝试过的,但它似乎不起作用。我说的是deletee
函数。我修改了它,但列表似乎没有改变。
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int val;
struct node *next;
} node;
typedef struct ll {
node *head;
} ll;
ll *newll() {
ll *k = malloc(sizeof(ll));
k->head = NULL;
return k;
}
void insert(ll *l, int vl) {
node *tmp = malloc(sizeof(node));
tmp->next = NULL;
tmp->val = vl;
if (l->head == NULL) {
l->head = tmp;
return;
}
node *s = l->head;
while (s->next != NULL)
s = s->next;
s->next = tmp;
}
void printll(ll *l) {
node *s = l->head;
while (s != NULL) {
printf("%d ", s->val);
s = s->next;
}
}
void deletee(ll *l) {
node *k = l->head;
while (k != NULL && k->next != NULL) {
node *tmp = k->next->next;
k = tmp;
}
}
int main() {
ll *ll1 = newll();
insert(ll1, 5);
insert(ll1, 6);
insert(ll1, 8);
insert(ll1, 9);
insert(ll1, 10);
insert(ll1, 11);
deletee(ll1);
printll(ll1);
return 0;
}
更新ll.head
和node.next
,所以指向node
的指针是不够的,除非你想对头部进行特殊处理。相反,让我们使用指向要更新的指针的指针。
void delete_node(node** node_ptr_ptr) {
node* to_delete = *node_ptr_ptr;
*node_ptr_ptr = to_delete->next;
free(to_delete);
}
void delete_every_second(ll* l) {
node** node_ptr_ptr = &( l->head );
while (1) {
if (*node_ptr_ptr == NULL) break;
delete_node(node_ptr_ptr);
if (*node_ptr_ptr == NULL) break;
node_ptr_ptr = &( (*node_ptr_ptr)->next );
}
}
假设您从以下内容开始:
+------+ +------+ +------+ +------+
| head ------>| val | +-->| val | +-->| val |
+------+ +------+ | +------+ | +------+
| next ---+ | next ---+ | next --->NULL
+------+ +------+ +------+
node** node_ptr_ptr = &( l->head );
后:
+------+ +------+ +------+ +------+
| head ------>| val1 | +-->| val2 | +-->| val3 |
+------+ +------+ | +------+ | +------+
^ | next ---+ | next ---+ | next --->NULL
| +------+ +------+ +------+
|
+-----+
|
+------+ |
| ptr ----+
+------+
node* to_delete = *node_ptr_ptr;
后:
+------+
| del ----+
+------+ |
|
+------+
|
v
+------+ +------+ +------+ +------+
| head ------>| val1 | +-->| val2 | +-->| val3 |
+------+ +------+ | +------+ | +------+
^ | next ---+ | next ---+ | next --->NULL
| +------+ +------+ +------+
|
+-----+
|
+------+ |
| ptr ----+
+------+
*node_ptr_ptr = to_delete->next; free(to_delete);
后:
+------+ +------+ +------+
| head -------------------->| val2 | +-->| val3 |
+------+ +------+ | +------+
^ | next ---+ | next --->NULL
| +------+ +------+
|
+-----+
|
+------+ |
| ptr ----+
+------+
node_ptr_ptr = &( (*node_ptr_ptr)->next );
后:
+------+ +------+ +------+
| head -------------------->| val2 | +-->| val3 |
+------+ +------+ | +------+
+---------------->| next ---+ | next --->NULL
| +------+ +------+
|
+------+ |
| ptr ----+
+------+
这段代码中:
while(k!=NULL)
{
if(k->next!=NULL && k->next->next!=NULL)
k->next=k->next->next;
}
你有一个无限循环,因为你不改变循环中k
的值。
另外:您必须先删除/释放k->next
内存,否则会出现内存泄漏。
我会简单地重写如下:
void deletee(ll *l)
{
if (l->head == NULL)
return;
node* tmp = l->head;
l->head = l->head->next; // skip first item
free(tmp);
node* k=l->head;
while(k!=NULL && k->next!=NULL)
{
tmp = k->next;
k->next = k->next->next;
free(tmp);
k = k->next;
}
}
结果(如预期(:
6 9 11
-
tmp
存储下一个值以供将来删除
我们将下一个元素 - 设置为要删除的元素的下一个元素,以便后者被取消链接
- 我们免费
tmp
- 然后我们跳到新的下一个元素并继续
您更改了 deletee
函数的代码,但仍然不正确:
void deletee(ll *l) {
node *k = l->head;
while (k != NULL && k->next != NULL) {
node *tmp = k->next->next;
k = tmp;
}
}
您根本不修改列表。
这是一个带有指向指针的解决方案,以避免空列表和列表中的第一个节点出现特殊情况。 k
指向删除节点时必须更新的链接,则在每次删除后都会将其推送到保留的节点,但列表末尾除外:
void deletee(ll *l) {
node **k = &l->head;
while (*k != NULL) {
/* delete the node */
node *tmp = *k;
*k = (*k)->next;
free(tmp);
if (*k != NULL) {
/* skip the preserved node */
k = &(*k)->next;
}
}
}