/* ppps_int_clist.c [サンプルライブラリ] int型の双方向循環リスト author: K.Y (Programming Place Plus) version 1.0.2 '2019/9/16 ・Webサイト側が C99規格へ対応したことに合わせて、コードを修正。 コメントスタイルと、変数宣言位置を変えた。 bool型を使う。 1.0.1 '2018/3/19 ・ppps_int_clist_add_front関数内の余分な NULLチェックを削除。 ・ppps_int_clist_remove_elem_by_value関数内の余分な NULLチェックを削除。 1.0.0 '2015/1/11 */ #include "ppps_int_clist.h" #include #include #define PPP_SWAP(type,a,b) { type work = a; a = b; b = work; } /* リストを作成する */ PPPSIntClist ppps_int_clist_create(void) { struct PPPSIntClist_tag* head = malloc( sizeof(struct PPPSIntClist_tag) ); if( head == NULL ){ return NULL; } head->value = 0; head->next = head; // 循環するので nextポインタは自分自身を指す head->prev = head; // 循環するので prevポインタは自分自身を指す return head; } /* リストを破棄する */ void ppps_int_clist_delete(PPPSIntClist list) { ppps_int_clist_clear( list ); free( list ); } /* リストの末尾に要素を追加する */ bool ppps_int_clist_add_tail(PPPSIntClist list, int value) { // リストの末尾を得る PPPSIntClist tail = ppps_int_clist_get_tail( list ); // 追加する要素を作る PPPSIntClist elem = malloc( sizeof(struct PPPSIntClist_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = list; // 末尾に追加するので、次の要素は先頭 elem->prev = tail; // 末尾に追加するので、前の要素はこれまでに末尾だった要素 // これまで末尾だった要素は、末尾から2番目の位置になる。 // そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする tail->next = elem; // ダミーの先頭の前は、末尾の要素になる list->prev = elem; return true; } /* リストの先頭に要素を追加する */ bool ppps_int_clist_add_front(PPPSIntClist list, int value) { // 追加する要素を作る PPPSIntClist elem = malloc( sizeof(struct PPPSIntClist_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = list->next; elem->prev = list; // 追加する要素(elem) の次にある要素が、 // 手前の要素として、elem を指すようにポインタを付け替える elem->next->prev = elem; // ダミーの先頭要素の次は、追加した要素になる list->next = elem; return true; } /* リストに要素を挿入する */ bool ppps_int_clist_insert(PPPSIntClist list, int value, int pos) { // 追加位置を探す PPPSIntClist p = ppps_int_clist_search( list, pos ); if( p == NULL ){ return false; } // 追加する要素を作る PPPSIntClist elem = malloc( sizeof(struct PPPSIntClist_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = p->next; // p と p->next の隙間に挿入する elem->prev = p; // p と p->next の隙間に挿入する p->next = elem; // p の直後に挿入された elem->next->prev = elem; // elem->next にとっての prev は、挿入された elem return true; } /* 要素を削除する */ int ppps_int_clist_remove_elem_by_value(PPPSIntClist list, int value) { PPPSIntClist p = list->next; PPPSIntClist prev = list; int count = 0; while( p != list ){ if( p->value == value ){ // 削除する要素の1つ後ろの要素の prevメンバは、 // 削除する要素の1つ手前の要素を指すように書き換える。 p->next->prev = prev; // 削除する要素の1つ手前の要素の nextメンバを、 // 削除する要素の次の要素を指すように書き換える prev->next = p->next; // 要素は malloc関数で生成したので、free関数による解放が必要。 // 上記の prev->next = p->next よりも後で行わないと、不正なポインタが // prev->next に代入されてしまうことに注意。 free( p ); // 続行するなら、p を正しい要素を指すようにする p = prev->next; ++count; } else{ prev = p; p = p->next; } } return count; } /* 要素を削除する */ bool ppps_int_clist_remove_elem(PPPSIntClist elem) { if( elem->next == elem ){ // next が自分自身のときは空 return false; } elem->prev->next = elem->next; elem->next->prev = elem->prev; free( elem ); return true; } /* 要素を空にする */ void ppps_int_clist_clear(PPPSIntClist list) { PPPSIntClist p = list->next; while( p != list ){ // 削除する要素の1つ先の要素のポインタを保存 PPPSIntClist tmp = p->next; // 要素は malloc関数で生成したので、free関数による解放が必要。 // free関数を通すと p は不定になるので、その後の p->next は不正。 free( p ); // 保存しておいたポインタを復元 p = tmp; } list->next = list; list->prev = list; } /* 先頭の要素を返す */ PPPSIntClist ppps_int_clist_get_head(PPPSIntClist list) { return list->next; } /* 末尾の要素を返す */ PPPSIntClist ppps_int_clist_get_tail(PPPSIntClist list) { return list->prev; } /* 指定した値を持つ要素を探す */ PPPSIntClist ppps_int_clist_search(PPPSIntClist list, int value) { PPPSIntClist p = list->next; while( p != list ){ if( p->value == value ){ return p; } p = p->next; } return NULL; } /* 要素数をカウントする。 戻り値: リストに含まれる要素の個数。 */ int ppps_int_clist_count(PPPSIntClist list) { PPPSIntClist p = list->next; int count = 0; while( p != list ){ count++; p = p->next; } return count; } /* リストを逆順にする。 */ void ppps_int_clist_reverse(PPPSIntClist list) { PPPSIntClist p = list->next; PPPSIntClist work = NULL; while( p != list ){ // この後、p->next を書き換えるので退避しておく PPPSIntClist tmp = p->next; // next と prev を入れ替える PPP_SWAP(PPPSIntClist, p->next, p->prev); // 現在の注目要素を保存 work = p; // 最初に退避させておいた p->next を次の注目要素として復帰させる p = tmp; } // 最終的な work は、逆順になった後の先頭要素であるから、 // ダミーの先頭要素の nextポインタとして設定する list->next = work; // 逆順になった後の先頭要素には、手前の要素は存在しない list->prev = NULL; } /* 要素を出力する */ void ppps_int_clist_print(PPPSIntClist list) { PPPSIntClist p = list->next; if( p == list ){ puts( "リストは空です。" ); return; } while( p != list ){ printf( "%d\n", p->value ); p = p->next; } }