循環リスト
http://www.geocities.jp/ky_webid/algorithm/011.html
片方向の線形リストの最後の要素が、一番最初の要素を指すわけですね。
似たような実装になるんでしょうか。
とりあえず実装してみます。
#include <stdio.h> #include <stdlib.h> struct LIST { int data; int last; struct LIST *next; }; typedef struct LIST LIST; LIST *create_list(int data) { LIST *p; p = (LIST *)malloc(sizeof(LIST)); if ( p == NULL ) { // メモリ不足エラー return NULL; } p->next = NULL; p->data = data; p->last = 1; printf("create %p\n",p); return p; } LIST *add_list (LIST *p,int data) { LIST *add,*q; add = create_list(data); while( !p->last ){ p = p->next; } if ( p->next == NULL ) { q = p; } else { q = p->next; } p->last = 0; p->next = add; add->next = q; return add; } void free_list (LIST *p) { LIST *s = p; LIST *q; do { q = p; p = p->next; printf("free %p\n",q); free(q); q = NULL; } while ( s!=p ); } void delete_list (LIST *p,int data) { LIST *s = p; LIST *q; do { q = p; p = p->next; if ( p->data == data ) { q->next = p->next; printf("free %p\n",p); free(p); p = NULL; // まだ同じ値の要素があるかもしれないので引き続き検索する p = q->next; } } while ( s!=p ); } void show_list (LIST *p) { LIST *s = p; do{ printf("%d\n",p->data); p = p->next; }while( s!=p ); } int main (void) { LIST *head; LIST *p; head = create_list(100); p = add_list(head,200); add_list(head,300); add_list(p,200); add_list(p,500); delete_list(head,200); show_list(head); free_list(head); return 0; }
create 00383148 create 00383160 create 00383178 create 00383190 create 003831A8 free 00383160 free 00383190 100 300 500 free 00383148 free 00383178 free 003831A8
できました。
LIST構造体に最後の要素かどうかのlastフラグを持つようにしました。
これによりadd_listするときにちゃんと最後の要素の次にデータを追加するように実装できました。
show_listは逆に渡された位置から、そのひとつ手前の位置までを表示するように処理しています。