首先要意识到的是从链表中删除一个元素涉及改变正好一个指针值:指针指向我们。这可以是外部head
指向第一个列表元素或其中一个的指针->next
列表内的指针。在这两种情况下那个指针需要改变;它的新值应该成为->next
待删除节点的指针。
为了更改某个对象(从函数内),我们需要一个指向它的指针。我们需要改变一个指针,所以我们需要一个指针到指针.
bool findAndRemove1(node **ptp, char *phrase)
{
node *del;
for( ;*ptp; ptp = &(*ptp)->next) {
if( !strcmp((*ptp)->entry, phrase) ) { break; } //found
}
/* when we get here, ptp either
** 1) points to the pointer that points at the node we want to delete
** 2) or it points to the NULL pointer at the end of the list
** (in the case nothing was found)
*/
if ( !*ptp) return false; // not found
del = *ptp;
*ptp = (*ptp)->next;
free(del);
return true;
}
的数量if
甚至可以通过在循环中执行脏工作并从循环返回来将条件减少到一个,但这会有点麻烦:
bool findAndRemove2(node **ptp, char *phrase)
{
for( ;*ptp; ptp = &(*ptp)->next) {
node *del;
if( strcmp((*ptp)->entry, phrase) ) continue; // not the one we want
/* when we get here, ptp MUST
** 1) point to the pointer that points at the node we want to delete
*/
del = *ptp;
*ptp = (*ptp)->next;
free(del);
return true;
}
return false; // not found
}
但如果列表是不独特,我们要删除all满足条件的节点?我们只需稍微改变一下循环逻辑并添加一个计数器:
unsigned searchAndDestroy(node **ptp, char *phrase)
{
unsigned cnt;
for( cnt=0 ;*ptp; ) {
node *del;
if( strcmp((*ptp)->entry, phrase) ) { // not the one we want
ptp = &(*ptp)->next;
continue;
}
/* when we get here, ptp MUST point to the pointer that points at the node we wish to delete
*/
del = *ptp;
*ptp = (*ptp)->next;
free(del);
cnt++;
}
return cnt; // the number of deleted nodes
}
更新:和一个驱动程序来测试它:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
typedef struct list {
struct list *next;
char entry[20];
} node;
void node_add( node **ptp, char *str)
{
node *new;
for ( ; *ptp; ptp = &(*ptp)->next) {
if (strcmp ((*ptp)->entry, str) < 0) continue;
}
new = malloc (sizeof *new);
strcpy(new->entry, str);
new->next = *ptp;
*ptp = new;
}
int main (void)
{
node *root = NULL;
unsigned cnt;
node_add (& root, "aaa" );
node_add (& root, "aaa" );
node_add (& root, "bbb" );
node_add (& root, "ccc" );
node_add (& root, "aaa" );
cnt = seachAndDestroy( &root, "bbb" );
printf("Cnt(bbb) := %u\n", cnt );
cnt = seachAndDestroy( &root, "ccc" );
printf("Cnt(ccc) := %u\n", cnt );
cnt = seachAndDestroy( &root, "aaa" );
printf("Cnt(aaa) := %u\n", cnt );
printf("Root now = %p\n", (void*) root );
return 0;
}
和输出:
plasser@pisbak:~/usenet$ ./a.out
Cnt(bbb) := 1
Cnt(ccc) := 1
Cnt(aaa) := 3
Root now = (nil)