ポプラ nano ( BTOスリムタワーPC ) オリジナル ベアボーン Intel Celeron G530 Windows7 Professional (64bit) 搭載モデル 新品価格 |
PCワンズBTOパソコンG-spirit i73770K GX670-ZDA 新品価格 |
インテル Celeron G540 2.50GHz 2M LGA1155 SandyBridge BX80623G540 新品価格 |
インテル Celeron G530 2.40GHz 2M LGA1155 SandyBridge BX80623G530 新品価格 |
インテル Atom Onboardマザーボード BOXDN2800MT 【Mini-ITX】 新品価格 |
インテル Atom Onboardマザーボード BOXD2700DC 【Mini-ITX】 新品価格 |
インテル Atom Onboardマザーボード BOXD2500HN 【Mini-ITX】 新品価格 |
ECS Mini-ITXマザーボード Atom D2700搭載 CDC-I 日本正規代理店品 (MB1848) CDC-I 新品価格 |
ASRock H61 Micro-ATX SATA3 USB3 HDMI DVI H61M/U3S3 新品価格 |
ASRock Intel H61チップセット搭載 LGA1155対応microATXマザーボード H61M-HVS 新品価格 |
GIGABYTE microATX Intel H61 GA-H61M-DS2 REV2.X 新品価格 |
ASRock マザーボード H61 Mini-ITX H61M-ITX 新品価格 |
ANTEC デザインと冷却性に優れた小型Mini-ITXケース ISK-100 新品価格 |
GIGABYTE intel H61 micro-ATX LGA1155 GA-H61M-DS2H 新品価格 |
■これからやる事。
C言語 連結リスト(2014年12月11日)で実装した連結リストを改造して双方向リストを実装します。
そのためにまずリストの構造体に前(pre)を追加します。
リストの構造体に前(pre)を追加しました。
コレにより構造体でリストの次の構造体だけでなく、前の構造体を保持することになります。
メリットとして構造体の削除が連結リストより高速になります。
デメリットは削除以外の操作が若干重くなります。確保されるメモリが多くなります。
頻繁にリストの追加削除がある場合は、双方向リストの方が高速でしょう(未検証)
■リストの構造体
#define MACHINEID_MAX 6 typedef struct _CELL { struct _CELL *pre; struct _CELL *next; char id[MACHINEID_MAX+1]; int data; } CELL;
addListにpreの処理を追加
前の構造体になるポインタをセット
/********************************************************/ /* \fn int addList(CELL* p, int data) */ /* \param *p 挿入したいセルのポインタ */ /* (この直後にセルを挿入する) */ /* \param data データ */ /* \return -1の時はデータのセットができなかった時、 */ /* 正常時は0を返す */ /* */ /********************************************************/ int addList(CELL* p, int data) { CELL *tmp; tmp = (CELL*)malloc(sizeof(CELL)); if(tmp == NULL) { return(-1); } tmp->pre = p; tmp->next = NULL; tmp->data = data; p->next = tmp; return(0); } |
addList2にpreの処理を追加
前の構造体になるポインタをセット
->初めて追加する場合は、start_cellのアドレス
->それ以降に追加する場合は、end_cellのアドレスがセットされる
/********************************************************/ /* \fn int addList2(int data) */ /* \param data データ */ /* \return -1の時はデータのセットができなかった時、 */ /* 正常時は0を返す */ /* */ /********************************************************/ int addList2( char *name, int data ) { CELL *tmp; int length = 0; tmp = (CELL*)malloc(sizeof(CELL)); if(tmp == NULL) { return(-1); } memset( tmp->id , 0x0 , MACHINEID_MAX+1 ); tmp->next = NULL; length = strlen( name ); if ( length > 6 ) { length = 6; } // name[length] = '\0'; memcpy( tmp->id, name, length ); tmp->data = data; if ( start_cell.next == NULL ) { start_cell.next = tmp; tmp->pre = &start_cell; } else { end_cell->next = tmp; tmp->pre = end_cell; } end_cell = tmp; return (0); } |
名前でリスト検索する関数
/********************************************************/ /* void searchList() */ /* データの検索 */ /* return None */ /* */ /********************************************************/ CELL *searchList( char *name ) { CELL *tmp; int ct = 0; tmp = start_cell.next; while (tmp != NULL) { if ( !strcmp( name, tmp->id ) ) { printf("%d[%s]\n", tmp, tmp->id); printf("%d[%d]\n", ct, tmp->data); return tmp; break; } tmp = tmp->next; ct++; } return 0; } |
指定したリストの前のリストを検索する関数
名前指定でリストを削除するために必要。後述
/********************************************************/ /* void searchList2() */ /* データの検索 */ /* return None */ /* */ /********************************************************/ CELL *searchList2( CELL *p ) { CELL *tmp; int ct = 0; tmp = start_cell.next; while (tmp != NULL) { if ( p == tmp->next ) { printf("%d[%s]\n", tmp, tmp->id); printf("%d[%d]\n", ct, tmp->data); return tmp; break; } tmp = tmp->next; ct++; } return 0; } |
指定した名前のリストの直後にリストを挿入する関数
searchList関数を使用
/********************************************************/ /* int insertList(int data) */ /* data データ */ /* return -1の時はデータのセットができなかった時、 */ /* 正常時は0を返す */ /* */ /********************************************************/ int insertList( char *name2, char *name, int data ) { CELL *tmp; CELL *tmp2; int length = 0; tmp = (CELL*)malloc(sizeof(CELL)); if(tmp == NULL) { return(-1); } memset( tmp->id , 0x0 , MACHINEID_MAX+1 ); // tmp->next = NULL; length = strlen( name ); if ( length > 6 ) { length = 6; } // name[length] = '\0'; memcpy( tmp->id, name, length ); tmp->data = data; tmp2 = searchList( name2 ); if ( tmp2 == 0 ) { return -1; } tmp->next = tmp2->next; tmp2->next= tmp; return (0); } |
削除関数
preの処理を追加。削除する構造体の次の構造体の前が削除する構造体の前の構造体になる
/********************************************************/ /* \fn int deleteList(CELL* p) */ /* \brief 引数で受け取ったセルの */ /* 次のポインタのデータを削除 */ /* \param *p 削除したいセルを指しているポインタ */ /* \return -1:エラー 0:正常終了 */ /* */ /********************************************************/ int deleteList(CELL* p) { CELL *tmp; if(p->next == NULL) { return(-1); } tmp = p->next; p->next = tmp->next; tmp->next->pre = p; free(tmp); return(0); } |
全削除する関数
未変更
/********************************************************/ /* \fn void allDeleteList(CELL *p) */ /* \brief データの全削除 */ /* \param *p 先頭のセルのポインタ */ /* \return None */ /* */ /********************************************************/ void allDeleteList(CELL *p) { CELL *tmp; while (p->next != NULL) { tmp = p->next; p->next = tmp->next; free(tmp); } } |
データの全表示する関数
未変更
/********************************************************/ /* \fn void showAllList() */ /* \brief データの全表示 */ /* \return None */ /* */ /********************************************************/ void showAllList() { CELL *tmp; int ct = 0; tmp = start_cell.next; while (tmp != NULL) { printf("%d[%s]\n", ct, tmp->id); printf("%d[%d]\n", ct, tmp->data); tmp = tmp->next; ct++; } } |
データの検索
未変更
/********************************************************/ /* \fn void searchList() */ /* \brief データの検索 */ /* \return None */ /* */ /********************************************************/ CELL *searchList( char *name ) { CELL *tmp; int ct = 0; tmp = start_cell.next; while (tmp != NULL) { if ( !strcmp( name, tmp->id ) ) { printf("%d[%s]\n", tmp, tmp->id); printf("%d[%d]\n", ct, tmp->data); return tmp; break; } tmp = tmp->next; ct++; } return 0; } |
データの検索する関数2
未変更
/********************************************************/ /* \fn void searchList2() */ /* \brief データの検索 */ /* \return None */ /* */ /********************************************************/ CELL *searchList2( CELL *p ) { CELL *tmp; int ct = 0; tmp = start_cell.next; while (tmp != NULL) { if ( p == tmp->next ) { printf("%d[%s]\n", tmp, tmp->id); printf("%d[%d]\n", ct, tmp->data); return tmp; break; } tmp = tmp->next; ct++; } return 0; } |
指定した名前のリストの次に挿入する関数
preの処理を追加
/********************************************************/ /* \fn int insertList(int data) */ /* \param data データ */ /* \return -1の時はデータのセットができなかった時、 */ /* 正常時は0を返す */ /* */ /********************************************************/ int insertList( char *name2, char *name, int data ) { CELL *tmp; CELL *tmp2; int length = 0; tmp = (CELL*)malloc(sizeof(CELL)); if(tmp == NULL) { return(-1); } memset( tmp->id , 0x0 , MACHINEID_MAX+1 ); // tmp->next = NULL; length = strlen( name ); if ( length > 6 ) { length = 6; } // name[length] = '\0'; memcpy( tmp->id, name, length ); tmp->data = data; tmp2 = searchList( name2 ); if ( tmp2 == 0 ) { return -1; } tmp->next = tmp2->next; tmp2->next= tmp; tmp->pre = tmp2; tmp2->next->pre= tmp; return (0); } |
指定した名前のリストを削除する関数
変更前はsearchList関数,searchList2関数を使用。
削除する構造体とその前の構造体を検索してその構造体の次を削除する構造体の次に変更していた。
変更後は、
削除する構造体の前の次を削除する構造体の次。
削除する構造体の次の前を削除する構造体の前。
に修正。
変更前 | 変更後 |
/********************************************************/ /* \fn int insertList(int data) */ /* \param data データ */ /* \return -1の時はデータのセットができなかった時、 */ /* 正常時は0を返す */ /* */ /********************************************************/ int deleteList2( char *name ) { CELL *tmp; CELL *tmp2; int length = 0; tmp = searchList( name ); if ( tmp == 0 ) { return -1; } tmp2 = searchList2( tmp ); tmp2->next= tmp->next; free(tmp); return (0); } | /********************************************************/ /* \fn int insertList(int data) */ /* \param data データ */ /* \return -1の時はデータのセットができなかった時、 */ /* 正常時は0を返す */ /* */ /********************************************************/ int deleteList2( char *name ) { CELL *tmp; int length = 0; tmp = searchList( name ); if ( tmp == 0 ) { return -1; } tmp->pre->next = tmp->next; tmp->next->pre = tmp->pre; free(tmp); return (0); } |