/* ppps_int_slist.c [サンプルライブラリ] int型の単方向線形リスト author: K.Y (Programming Place Plus) version 1.0.2 '2019/9/16 ・成否を返す関数の戻り値に、bool型を使うようにした 1.0.1 '2019/9/13 ・Webサイト側が C99規格へ対応したことに合わせて、コードを修正。 コメントスタイルと、変数宣言位置を変えた。 1.0.0 '2012/1/4 */ #include "ppps_int_slist.h" #include #include /* リストを作成する */ PPPSIntSlist ppps_int_slist_create(void) { struct PPPSIntSlist_tag* head = malloc( sizeof(struct PPPSIntSlist_tag) ); if( head == NULL ){ return NULL; } head->value = 0; head->next = NULL; return head; } /* リストを破棄する */ void ppps_int_slist_delete(PPPSIntSlist list) { ppps_int_slist_clear( list ); free( list ); } /* リストの末尾に要素を追加する */ bool ppps_int_slist_add_tail(PPPSIntSlist list, int value) { // リストの末尾を探す PPPSIntSlist tail = ppps_int_slist_search_tail( list ); // 追加する要素を作る PPPSIntSlist elem = malloc( sizeof(struct PPPSIntSlist_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = NULL; // 末尾に追加するので、次の要素は無い // これまで末尾だった要素は、末尾から2番目の位置になる。 // そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする tail->next = elem; return true; } /* リストの先頭に要素を追加する */ bool ppps_int_slist_add_front(PPPSIntSlist list, int value) { // 追加する要素を作る PPPSIntSlist elem = malloc( sizeof(struct PPPSIntSlist_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = list->next; // ダミーの先頭要素の次は、追加した要素になる list->next = elem; return true; } /* リストに要素を挿入する */ bool ppps_int_slist_insert(PPPSIntSlist list, int value, int pos) { // 追加位置を探す PPPSIntSlist p = ppps_int_slist_search( list, pos ); if( p == NULL ){ return false; } // 追加する要素を作る PPPSIntSlist elem = malloc( sizeof(struct PPPSIntSlist_tag) ); if( elem == NULL ){ return false; } elem->value = value; elem->next = p->next; // p と p->next の隙間に挿入する p->next = elem; return true; } /* 要素を削除する */ int ppps_int_slist_delete_elem(PPPSIntSlist list, int value) { PPPSIntSlist p = list->next; PPPSIntSlist prev = list; int count = 0; while( p != NULL ){ if( p->value == value ){ // 削除する要素の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; } /* 要素を空にする */ void ppps_int_slist_clear(PPPSIntSlist list) { PPPSIntSlist p = list->next; while( p != NULL ){ // 削除する要素の1つ先の要素のポインタを保存 PPPSIntSlist tmp = p->next; // 要素は malloc関数で生成したので、free関数による解放が必要。 // free関数を通すと p は不定になるので、その後の p->next は不正。 free( p ); // 保存しておいたポインタを復元 p = tmp; } } /* 末尾の要素を探す */ PPPSIntSlist ppps_int_slist_search_tail(PPPSIntSlist list) { PPPSIntSlist p = list; while( p->next != NULL ){ p = p->next; } return p; } /* 指定した値を持つ要素を探す */ PPPSIntSlist ppps_int_slist_search(PPPSIntSlist list, int value) { PPPSIntSlist p = list->next; while( p != NULL ){ if( p->value == value ){ return p; } p = p->next; } return NULL; } /* 要素数をカウントする。 戻り値: リストに含まれる要素の個数。 */ int ppps_int_slist_count(PPPSIntSlist list) { PPPSIntSlist p = list->next; int count = 0; while( p != NULL ){ count++; p = p->next; } return count; } /* リストを逆順にする。 */ void ppps_int_slist_reverse(PPPSIntSlist list) { PPPSIntSlist p = list->next; PPPSIntSlist work = NULL; while( p != NULL ){ // この後、p->next を書き換えるので退避しておく PPPSIntSlist tmp = p->next; // 1つ前の要素を p->next に設定 // "1つ前の要素" とは先頭から末尾へ向かう流れの中でのことを言っており、 // 逆順になった後のことを考えると、"次の要素" のことを言っている。 // 初回は何もないので NULL になっている p->next = work; // 現在の注目要素を保存 // これは、次のループにおいては "1つ前の要素" になる work = p; // 最初に退避させておいた p->next を次の注目要素として復帰させる p = tmp; } // 最終的な work は、逆順になった後の先頭要素であるから、 // ダミーの先頭要素の nextポインタとして設定する list->next = work; } /* 要素を出力する */ void ppps_int_slist_print(PPPSIntSlist list) { PPPSIntSlist p = list->next; if( p == NULL ){ puts( "リストは空です。" ); return; } while( p != NULL ){ printf( "%d\n", p->value ); p = p->next; } }