list_free() に関心がある場合は、ソースで削除チェーンを強化することをお勧めします。以下では、すべてが終了したら、*list を NULL にすることを前提としています (リスト全体が削除されたため)。
void list_free(list_t **list)
{
if (list && *list)
{
list_t* next = (*list)->next;
while (next && (next != *list))
{
list_t *tmp = next;
next = next->next;
free(tmp);
}
free(*list);
*list = NULL;
}
}
またはそのようなもの。外部リスト ポインターのアドレスを渡すことによって呼び出されます。
list_t *list = NULL;
.. initialize and use your list...
// free the list
list_free(&list);
編集OPがさらにコードを投稿した後、いくつかのことが目立ちます。
list_newnode()prevandの値を設定しないnextため、ガベージが含まれます。- ここでの他のすべての関数は、(1) next と prev が正しく初期化されていることを前提としています。率直に言って、これが 2 番目の追加の開始時に失敗しないことに驚いています。
循環リスト挿入では、挿入される新しいノードが初期リスト自体である可能性があると想定する必要があります。この努力を必要以上に難しくしているようです。循環リストは任意のノードをリスト ヘッドとして持つことができることを思い出してください。これは、現在のリスト 'head' が削除された場合よりも優れているとは言えません。これが発生したときに、呼び出し元に対して新しいリスト「ヘッド」を再確立するためのメカニズムが整っている必要があります。これと同じメカニズムにより、最後のノードが削除されたときにリスト ヘッドを NULL に設定できるようにする必要があります。
あなたのコードは、ポインターへのポインターを使用せずにこれを行うことを明白に試みているように見えますが、循環リンクリストのタスクを非常に簡単にします。コード内のその他の注意事項:
- あなたの関数のほとんどは、戻り値によってリストヘッドがどうあるべきかを呼び出し元に提案しようとしているようです。むしろ、in/out パラメータで強制する必要があります。
- 別のノードに関連する新しいノードを挿入する関数は、新しいノードを返す必要があります。
list_prepend()関数と関数は、リスト ヘッドに関連するコア挿入関数list_append()と見なす必要があります。他の API ( 、など) は、前または後に挿入する有効な既存のノードに対して完全に相対的である必要があり、上で述べたように、常に新しく挿入されたノードへのポインターを返します。非ルートベースの両方の挿入関数がリスト ヘッドを渡さなくなっていることがわかります。list_insert_before()list_insert_after()- 逆参照を実行する前に無効なポインターをチェックしないことを除けば、ほとんどのユーティリティ関数は正しかったです。そうでないものもありますが、少なくとも今は管理可能です。
以下は、ほとんどの関数を中心に構築されたコード ベッドです。実際のノード配置ルーチンはやり直したので、できる限りコメントしました。メインのテスト治具は至ってシンプル。ここに重大なバグがある場合、SO-watchtower がすぐに指摘してくれると確信していますが、コードのポイントはあなたのバグを修正することだけではありません。それは学習です：
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <assert.h>
// node structure
typedef struct list_t {
char *value;
struct list_t *next;
struct list_t *prev;
} list_t;
static void failed_allocation(void) {
fprintf(stderr, "Out of memory.\n");
abort();
}
// initialize a linked list header pointer. Just sets it to NULL.
void list_init(list_t** listpp)
{
if (listpp)
*listpp = NULL;
}
// return the value-field of a valid list node.
// otherwise return NULL if node is NULL.
const char *list_node_value(list_t *node)
{
return (node ? node->value : NULL);
}
// return the next pointer (which may be a self-reference)
// of a valid list_t pointer.
list_t *list_next(list_t *node)
{
return (node ? node->next : NULL);
}
// return the previous pointer (which may be a self-reference)
// of a valid list_t pointer.
list_t *list_previous(list_t *node)
{
return (node ? node->prev : NULL);
}
// return the same pointer we were passed.
list_t *list_first(list_t *headp)
{
return headp;
}
// return the previous pointer (which may be a self-reference)
// of the given list-head pointer.
list_t *list_last(list_t *headp)
{
return list_previous(headp);
}
// insert a new item at the end of the list, which means it
// becomes the item previous to the head pointer. this handles
// the case of an initially empty list, which creates the first
// node that is self-referencing.
list_t *list_append(list_t **headpp, const char* value)
{
if (!headpp) // error. must pass the address of a list_t ptr.
return NULL;
// allocate a new node.
list_t* p = malloc(sizeof(*p));
if (p == NULL)
failed_allocation();
// setup duplicate value
p->value = (value) ? strdup(value) : NULL;
// insert the node into the list. note that this
// works even when the head pointer is an initial
// self-referencing node.
if (*headpp)
{
(*headpp)->prev->next = p;
p->prev = (*headpp)->prev;
p->next = (*headpp);
(*headpp)->prev = p;
}
else
{ // no prior list. we're it. self-reference
*headpp = p;
p->next = p->prev = p;
}
return p;
}
// insert a new value into the list, returns a pointer to the
// node allocated to hold the value. this will ALWAYS update
// the given head pointer, since the new node is being prepended
// to the list and by-definition becomes the new head.
list_t *list_prepend(list_t **headpp, const char* value)
{
list_append(headpp, value);
if (!(headpp && *headpp))
return NULL;
*headpp = (*headpp)->prev;
return *headpp;
}
// insert a new node previous to the given valid node pointer.
// returns a pointer to the inserted node, or NULL on error.
list_t *list_insert_before(list_t* node, const char* value)
{
// node *must* be a valid list_t pointer.
if (!node)
return NULL;
list_prepend(&node, value);
return node;
}
// insert a new node after the given valid node pointer.
// returns a pointer to the inserted node, or NULL on error.
list_t *list_insert_after(list_t* node, const char* value)
{
// node *must* be a valid list_t pointer.
if (!node)
return NULL;
node = node->next;
list_prepend(&node, value);
return node;
}
// delete a node referenced by the node pointer parameter.
// this *can* be the root pointer, which means the root
// must be set to the next item in the list before return.
int list_remove(list_t** headpp, list_t* node)
{
// no list, empty list, or no node all return immediately.
if (!(headpp && *headpp && node))
return 1;
// validate the node is in *this* list. it may seem odd, but
// we cannot just free it if the node may be in a *different*
// list, as it could be the other list's head-ptr.
if (*headpp != node)
{
list_t *p = (*headpp)->next;
while (p != node && p != *headpp)
p = p->next;
if (p == *headpp)
return 1;
}
// isolate the node pointer by connecting surrounding links.
node->next->prev = node->prev;
node->prev->next = node->next;
// move the head pointer if it is the same node
if (*headpp == node)
*headpp = (node != node->next) ? node->next : NULL;
// finally we can delete the node.
free(node->value);
free(node);
return 0;
}
// release the entire list. the list pointer will be reset to
// NULL when this is finished.
void list_free(list_t **headpp)
{
if (!(headpp && *headpp))
return;
while (*headpp)
list_remove(headpp, *headpp);
}
// enumerate the list starting at the given node.
void list_foreach(list_t *listp, void (*function)(const char*))
{
if (listp)
{
list_t *cur = listp;
do {
function(cur->value);
cur = cur->next;
} while (cur != listp);
}
printf("\n");
}
// printer callback
void print_str(const char* value)
{
printf("%s\n", value);
}
// main entrypoint
int main(int argc, char *argv[])
{
list_t *listp;
list_init(&listp);
// insert some new entries
list_t* hello = list_append(&listp, "Hello, Bedrock!!");
assert(NULL != hello);
assert(listp == hello);
// insert Fred prior to hello. does not change the list head.
list_t* fred = list_insert_before(hello, "Fred Flintstone");
assert(NULL != fred);
assert(listp == hello);
// Hello, Bedrock!!
// Fred Flintstone
list_foreach(listp, print_str);
// insert Wilma priot to Fred. does not change the list head.
list_t* wilma = list_insert_before(fred, "Wilma Flintstone");
assert(NULL != wilma);
assert(list_next(wilma) == fred);
assert(list_previous(wilma) == hello);
// Hello, Bedrock!!
// Wilma Flintstone
// Fred Flintstone
list_foreach(listp, print_str);
list_t* barney = list_prepend(&listp, "Barney Rubble");
list_t* dino = list_insert_after(wilma, "Dino");
assert(barney != NULL);
assert(dino != NULL);
assert(listp == barney);
assert(list_previous(barney) == fred);
assert(list_next(barney) == hello);
// Barney Rubble
// Hello, Bedrock!!
// Wilma Flintstone
// Dino
// Fred Flintstone
list_foreach(listp, print_str);
// remove everyone, one at a time.
list_remove(&listp, fred); // will not relocate the list head.
// Barney Rubble
// Hello, Bedrock!!
// Wilma Flintstone
// Dino
list_foreach(listp, print_str);
list_remove(&listp, hello); // will not relocate the list head.
// Barney Rubble
// Wilma Flintstone
// Dino
list_foreach(listp, print_str);
list_remove(&listp, barney); // will relocate the list head.
// Wilma Flintstone
// Dino
list_foreach(listp, print_str);
assert(listp == wilma);
assert(list_next(wilma) == dino);
assert(list_previous(listp) == dino);
list_remove(&listp, wilma); // will relocate the list head.
// Dino
list_foreach(listp, print_str);
list_remove(&listp, dino); // will relocate the list head;
// generate a raft entries (a million of them)/
char number[32];
int i=0;
for (;i<1000000; i++)
{
sprintf(number, "%d", i);
list_append(&listp, number);
}
// now test freeing the entire list.
list_free(&listp);
return 0;
}
アサートとダンプの散らばりは、アルゴリズムの健全性の検証を支援するためのものです。この結果の出力は、コード内のコメントと一致する必要があります。
Hello, Bedrock!!
Fred Flintstone
Hello, Bedrock!!
Wilma Flintstone
Fred Flintstone
Barney Rubble
Hello, Bedrock!!
Wilma Flintstone
Dino
Fred Flintstone
Barney Rubble
Hello, Bedrock!!
Wilma Flintstone
Dino
Barney Rubble
Wilma Flintstone
Dino
Wilma Flintstone
Dino
Dino
最終的な考え: これを valgrind で実行しましたが、リークは見つかりませんでした。私はそれがあなたのニーズにすぐに適合しないことを確信しています** 。