c-如果同一索引中的下一个节点不为NULL，我如何删除单链表链接哈希表的第一个节点

Question

这是我的函数，如果我使用此函数删除第一个节点，它将删除节点的所有其余部分->下一个节点，有人能帮我吗？

struct node* popCH(char ex[]){
int hash_index = Hash(ex);
node* temp = head[hash_index];

if(temp==NULL){
return NULL;
}

while(temp->next!=NULL && strcmp(temp->next->ex,ex)!=0){
temp=temp->next;
}
if(temp->next==NULL && strcmp(temp->ex,ex)==0){
free(temp);
temp=NULL;
head[hash_index]=NULL;
}

else if(temp->next!=NULL && strcmp(temp->ex,ex)==0){
node* temp2 = temp;
temp = temp->next;
temp = head[hash_index]->next;
free(temp2);
temp2=NULL;
}
}

Answer 1

您应该使用指向某个节点的指针，以便删除该节点，并更新指向该节点的指针以指向下一个节点，而不管该指针是节点中指针的头指针。

struct data* popCH(char ex[]){
int hash_index = Hash(ex);
node** temp = &head[hash_index];

if(*temp==NULL){
return NULL;
}

while(*temp!=NULL && strcmp((*temp)->ex,ex)!=0){
temp=&(*temp)->next;
}
if(*temp!=NULL){
node *temp2 = (*temp)->next;
free(*temp);
*temp=temp2;
}
/* return something not to let caller invoke undefined behavior by using the return value */
return NULL;
}

Answer 2

一种方法是使用指针对指针，这已经被一个优秀的答案所覆盖。

另一种方法是简单地跟踪指向前一个节点的指针，当没有前一节点时，指针为空：

node *prev = NULL;
while (temp != NULL && strcmp(temp->ex, ex) != 0) {
prev = temp;
temp = temp->next;
}
if (temp != NULL) { // found matching node
// retain data pointer to return before freeing
struct data *data = temp->data;
// two deletion cases: middle of chain or front
if (prev)
prev->next = temp->next;
else
head[hash_index] = temp->next;
free(temp);
return data;
}
// not found
return NULL;

如果我们给链一个代理父级，我们可以避免出现两个删除情况。也就是说，我们在列表的前面添加一个虚拟节点，作为第一个节点的前一个节点：

struct data* popCH(const char *ex){
int hash_index = Hash(ex);
// transfer chain into fake extra previous node:
struct node parent = { .next = head[hash_index] };
node *prev = &parent;
node *temp = prev->next;

while (temp != NULL && strcmp(temp->ex, ex) != 0) {
prev = temp;
temp = temp->next;
}
if (temp != NULL) { // found matching node
// retain data pointer to return before freeing
struct data *data = temp->data;
// splice temp out of list by getting
// the previous node to skip it
prev->next = temp->next;
// transfer updated chain back into table:
head[hash_index] = parent.next;
free(temp);
return data;
}
// not found
return NULL;
}

我们已经从代码中删除了一些测试，但还有一些不必要的内存写入。在返回之前，我们分配给head[hash_index]，无论这是否实际必要；则仅需要CCD_ 2已经改变。此外，我们已经分配了一个完整的node局部变量，并初始化了它的所有字段，即使我们只访问"。我们可以通过避免初始值设定项来避免这样做：

int hash_index = Hash(ex);
// transfer chain into fake extra previous node:
struct node parent;
node *prev = &parent;
node *temp = head[hash_index];
// initialize just parent.next member by assignment;
// other members are left uninitialized.
parent.next = temp;
// rest of code ...