/* ppps_int_list.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_list_insert関数で、挿入位置がリストの末尾だった場合に、 ハングアップするバグを修正。 1.0.0 '2015/1/10 */ #include "ppps_int_list.h" #include #include #define PPP_SWAP(type,a,b) { type work = a; a = b; b = work; } /* リストを作成する */ PPPSIntList ppps_int_list_create(void) { struct PPPSIntList_tag* head = malloc( sizeof(struct PPPSIntList_tag) ); if( head == NULL ){ return NULL; } head->value = 0; head->next = NULL; head->prev = NULL; return head; } /* リストを破棄する */ void ppps_int_list_delete(PPPSIntList list) { ppps_int_list_clear( list ); free( list ); } /* リストの末尾に要素を追加する */ bool ppps_int_list_add_tail(PPPSIntList list, int value) { // リストの末尾を探す PPPSIntList tail = ppps_int_list_search_tail( list ); // 追加する要素を作る PPPSIntList elem = malloc( sizeof(struct PPPSIntList_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = NULL; // 末尾に追加するので、次の要素は無い elem->prev = tail; // 末尾に追加するので、前の要素はこれまでに末尾だった要素 // これまで末尾だった要素は、末尾から2番目の位置になる。 // そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする tail->next = elem; return true; } /* リストの先頭に要素を追加する */ bool ppps_int_list_add_front(PPPSIntList list, int value) { // 追加する要素を作る PPPSIntList elem = malloc( sizeof(struct PPPSIntList_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = list->next; elem->prev = list; // 追加した要素の次の要素があれば、前の要素として追加した要素を設定 if( elem->next != NULL ){ elem->next->prev = elem; } // ダミーの先頭要素の次は、追加した要素になる list->next = elem; return true; } /* リストに要素を挿入する */ bool ppps_int_list_insert(PPPSIntList list, int value, int pos) { // 追加位置を探す PPPSIntList p = ppps_int_list_search( list, pos ); if( p == NULL ){ return false; } // 追加する要素を作る PPPSIntList elem = malloc( sizeof(struct PPPSIntList_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = p->next; // p と p->next の隙間に挿入する elem->prev = p; // p と p->next の隙間に挿入する // p の直後に追加するので、p->next を付け替える p->next = elem; // elem->next にとっての prev を、挿入される elem を指すように付け替える。 // 挿入位置がリストの末尾だった場合、elem->next は NULL であることに注意。 if( elem->next != NULL ){ elem->next->prev = elem; } return true; } /* 要素を削除する */ int ppps_int_list_remove_elem_by_value(PPPSIntList list, int value) { PPPSIntList p = list->next; PPPSIntList prev = list; int count = 0; while( p != NULL ){ if( p->value == value ){ // 削除する要素の1つ後ろの要素の prevメンバは、、 // 削除する要素の1つ手前の要素を指すように書き換える。 // ただし、1つの後ろの要素が存在しない可能性を考慮しなければならない。 if( p->next != NULL ){ 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_list_remove_elem(PPPSIntList elem) { if( elem == NULL ){ return false; } if( elem->prev != NULL ){ elem->prev->next = elem->next; } if( elem->next != NULL ){ elem->next->prev = elem->prev; } free( elem ); return true; } /* 要素を空にする */ void ppps_int_list_clear(PPPSIntList list) { PPPSIntList p = list->next; while( p != NULL ){ // 削除する要素の1つ先の要素のポインタを保存 PPPSIntList tmp = p->next; // 要素は malloc関数で生成したので、free関数による解放が必要。 // free関数を通すと p は不定になるので、その後の p->next は不正。 free( p ); // 保存しておいたポインタを復元 p = tmp; } list->next = NULL; } /* 先頭の要素を返す */ PPPSIntList ppps_int_list_get_head(PPPSIntList list) { return list->next; } /* 末尾の要素を探す */ PPPSIntList ppps_int_list_search_tail(PPPSIntList list) { PPPSIntList p = list; while( p->next != NULL ){ p = p->next; } return p; } /* 指定した値を持つ要素を探す */ PPPSIntList ppps_int_list_search(PPPSIntList list, int value) { PPPSIntList p = list->next; while( p != NULL ){ if( p->value == value ){ return p; } p = p->next; } return NULL; } /* 要素数をカウントする。 戻り値: リストに含まれる要素の個数。 */ int ppps_int_list_count(PPPSIntList list) { PPPSIntList p = list->next; int count = 0; while( p != NULL ){ count++; p = p->next; } return count; } /* リストを逆順にする。 */ void ppps_int_list_reverse(PPPSIntList list) { PPPSIntList p = list->next; PPPSIntList work = NULL; while( p != NULL ){ // この後、p->next を書き換えるので退避しておく PPPSIntList tmp = p->next; // next と prev を入れ替える PPP_SWAP(PPPSIntList, p->next, p->prev); // 現在の注目要素を保存 work = p; // 最初に退避させておいた p->next を次の注目要素として復帰させる p = tmp; } // 最終的な work は、逆順になった後の先頭要素であるから、 // ダミーの先頭要素の nextポインタとして設定する list->next = work; // 逆順になった後の先頭要素には、手前の要素は存在しない list->prev = NULL; } /* 要素を出力する */ void ppps_int_list_print(PPPSIntList list) { PPPSIntList p = list->next; if( p == NULL ){ puts( "リストは空です。" ); return; } while( p != NULL ){ printf( "%d\n", p->value ); p = p->next; } }