たまに、こういうところを勉強しておくのも、理解を深める意味でも悪くないので。
連結リストの操作を行うサンプルを作って見ました。
//**********************************************************
// メモリ操作のテスト
// 両方向リストの作成
//**********************************************************
//#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NAME_LENGTH 2048
#define TRUE 1
#define FALSE 0
typedef struct SDATA {
struct SDATA *back;
unsigned long source;
struct SDATA *next;
}_SDATA;
typedef struct NAMELIST {
struct NAMELIST *back;
char name[NAME_LENGTH];
struct SDATA sdata;
struct NAMELIST *next;
}_NAMELIST;
// 関数
struct NAMELIST *l_add(char *, struct NAMELIST *);
struct NAMELIST *l_insert(struct NAMELIST *, char *, int);
struct NAMELIST *l_delete(struct NAMELIST *);
struct NAMELIST *getStart(struct NAMELIST *);
struct NAMELIST *getLast(struct NAMELIST *);
struct NAMELIST *getPointer(struct NAMELIST *, int);
int record_count (struct NAMELIST *);
void print_list(struct NAMELIST *);
void free_list(struct NAMELIST *);
//=============================================================================
// メイン
//=============================================================================
int main(int argc, char *argv[]) {
int i = 0;
for(i = 0; i < argc; i++) {
printf("argv[%d] = %s\n", i, argv[i]);
}
char buf[NAME_LENGTH];
struct NAMELIST *p = NULL;
int cont = 1;
int record = 0;
while(cont) {
unsigned char select = 0;
printf("\n========================================\n");
printf("menu\n");
printf("========================================\n");
printf("1...追加(Add)\n");
printf("2...削除(Delete)\n");
printf("3...挿入(Insert)\n");
printf("4...表示(Print)\n");
printf("9...終了(Quit)\n");
printf("選択(1-4,9)? ");
if(scanf("%c%*c", &select) == EOF) {
break;
}
switch(select) {
case '1' :
case 'a' :
case 'A' :
printf("データを入力してください(end=EOF)\n");
if(scanf("%[^\n]%*c", buf) == EOF) {
break;
};
p = l_add(buf, p);
break;
case '2' :
case 'd' :
case 'D' :
printf("何レコード目を削除しますか(end=EOF)\n");
if(scanf("%d%*c", &record) == EOF) {
break;
};
if(getPointer(p, record) != NULL) {
p = l_delete(getPointer(p, record));
}
break;
case '3' :
case 'i' :
case 'I' :
printf("何レコード目に挿入しますか(end=EOF)\n");
if(scanf("%d%*c", &record) == EOF) {
break;
};
printf("データを入力してください(end=EOF)\n");
if(scanf("%[^\n]%*c", buf) == EOF) {
break;
};
p = l_insert(p, buf, record);
break;
case '4' :
case 'p' :
case 'P' :
printf("\nリストを表示します\n");
print_list(p);
break;
case '9' :
case 'q' :
case 'Q' :
cont = 0;
break;
default :
;
}
}
free_list(getLast(p));
return 0;
}
//=============================================================================
// データの追加
// 戻り値＝struct NAMELIST *追加したデータへのポインタ
//=============================================================================
struct NAMELIST *l_add(char *name, struct NAMELIST *name_last) {
struct NAMELIST *name_new;
name_last = getLast(name_last);
if((name_new = (struct NAMELIST *)malloc(sizeof(struct NAMELIST))) == NULL) {
printf("memory allocation failed. = malloc() error\n");
exit(EXIT_FAILURE);
}
// 確保したメモリに入力値を保存する
strncpy(name_new->name, name, (size_t)NAME_LENGTH);
// 今回のポインタのbackを前回のポインタにつなぐ
name_new->back = name_last;
// 今回のポインタのnextをNULLに
name_new->next = NULL;
// 前回のポインタのnextを今作成したメモリにつなぐ（NULLの時を除く）
if(name_last != NULL) {
name_last->next = name_new;
};
return name_new;
}
//=============================================================================
// データの削除
// 戻り値＝struct NAMELIST *追加したデータへのポインタ
//=============================================================================
struct NAMELIST *l_delete(struct NAMELIST *name) {
struct NAMELIST *name_before;
struct NAMELIST *name_after;
struct NAMELIST *p;
p = NULL;
// 当然データが何も入っていないポインタの削除依頼は無視する
if(name == NULL) {
return (struct NAMELIST *)NULL;
}
// つなぎ替え
// 前のデータと次のデータを取得する
name_before = name->back;
name_after = name->next;
if(name_before != NULL) {
// 前のデータが存在する場合
// 前のデータの、nextを削除するデータのnextに置き換える。
name_before->next = name->next;
p = name_before;
};
if(name_after != NULL) {
// 次のデータが存在する場合
// 次のデータの、backを削除するデータのbackに置き換える。
name_after->back = name->back;
p = name_after;
};
// つなぎ替えが終わったのでメモリを解放する
printf("メモリ %xを解放します。\n", (unsigned int)name);
free(name);
return p;
}
//=============================================================================
// データの挿入
// 戻り値＝struct NAMELIST *追加したデータへのポインタ
//=============================================================================
struct NAMELIST *l_insert(struct NAMELIST *p, char *name, int number) {
struct NAMELIST *name_new;
struct NAMELIST *name_before;
struct NAMELIST *name_after;
if(number <= 0) {
// 存在しないデータが指定されたので、挿入しない
return p;
}
if(number > record_count(p)) {
// 存在しないデータが指定されたので、新規で追加する
return l_add(name, p);
}
name_before = getPointer(p, number - 1);
name_after = getPointer(p, number);
if((name_new = (struct NAMELIST *)malloc(sizeof(struct NAMELIST))) == NULL) {
printf("memory allocation failed. = malloc() error\n");
exit(EXIT_FAILURE);
}
// 確保したメモリに入力値を保存する
strncpy(name_new->name, name, (size_t)NAME_LENGTH);
// 今回のポインタのbackを前のデータのポインタにつなぐ
name_new->back = name_before;
// 今回のポインタのnextを次のデータのポインタにつなぐ
name_new->next = name_after;
// 前のデータのポインタのnextを今作成したメモリにつなぐ（NULLの時を除く）
if(name_before != NULL) {
name_before->next = name_new;
};
// 次のデータのポインタのbackを今作成したメモリにつなぐ（NULLの時を除く）
if(name_after != NULL) {
name_after->back = name_new;
};
return name_new;
}
//=============================================================================
// 最初のデータへのポインタを求める
// 戻り値＝struct NAMELIST *最初のデータへのポインタ もしくは NULL
//=============================================================================
struct NAMELIST *getStart(struct NAMELIST *p) {
if(p == NULL) {
return (struct NAMELIST *)NULL;
}
while(p->back != NULL) {
p = p->back;
}
return p;
}
//=============================================================================
// 最後のデータへのポインタを求める
// 戻り値＝struct NAMELIST *最後のデータへのポインタ もしくは NULL
//=============================================================================
struct NAMELIST *getLast(struct NAMELIST *p) {
if(p == NULL) {
return (struct NAMELIST *)NULL;
}
while(p->next != NULL) {
p = p->next;
}
return p;
}
//=============================================================================
// データを検索する
// 戻り値＝struct NAMELIST *見つかったデータへのポインタ もしくは NULL
//=============================================================================
struct NAMELIST *getData(struct NAMELIST *p, unsigned char * name) {
struct NAMELIST *q;
if(p == NULL) {
return (struct NAMELIST *)NULL;
}
for (q = getStart(p); q < getLast(p); q++) {
if(strcmp(p->name, q->name)) {
printf("found!\n!");
return q;
}
}
printf("not found!\n");
return (struct NAMELIST *)NULL;
}
//=============================================================================
// 指定したレコードへのポインタを返す
// 戻り値＝struct NAMELIST *見つかったデータへのポインタ もしくは NULL
//=============================================================================
struct NAMELIST *getPointer(struct NAMELIST *namelist, int search) {
namelist = getStart(namelist);
int i = 1;
while(namelist != NULL) {
if (i == search) {
return namelist;
}
namelist = namelist->next;
i++;
}
return (struct NAMELIST *)NULL;
}
//=============================================================================
// レコードの件数を返す
// 戻り値＝int 登録されているレコードの件数
//=============================================================================
int record_count (struct NAMELIST *namelist) {
namelist = getStart(namelist);
int i = 0;
while(namelist != NULL) {
i++;
namelist = namelist->next;
}
return i;
}
//=============================================================================
// データをすべて表示する
//=============================================================================
void print_list(struct NAMELIST *namelist) {
namelist = getStart(namelist);
int i = 0;
while(namelist != NULL) {
i++;
printf("%d (%x) : %x -> %s -> %x\n", i, (unsigned int)namelist, (unsigned int)namelist->back, namelist->name, (unsigned int)namelist->next);
namelist = namelist->next;
}
printf("合計 %dレコードです。\n", i);
}
//=============================================================================
// データ用として確保したメモリをすべて解放する
//=============================================================================
void free_list(struct NAMELIST *p) {
struct NAMELIST *q;
while (p != NULL) {
q = p->back;
printf("メモリ %xを解放します。\n", (unsigned int)p);
free(p);
p = q;
}
}
実行結果はこんな感じ。
argv[0] = /test_list/build/Release/test_list
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? a
データを入力してください(end=EOF)
test data from
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? 1
データを入力してください(end=EOF)
console
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? a
データを入力してください(end=EOF)
STDIN
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? p
リストを表示します
1 (802000) : 0 -> test data from -> 802a00
2 (802a00) : 802000 -> console -> 803400
3 (803400) : 802a00 -> STDIN -> 0
合計 3レコードです。
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? d
何レコード目を削除しますか(end=EOF)
2
メモリ 802a00を解放します。
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? p
リストを表示します
1 (802000) : 0 -> test data from -> 803400
2 (803400) : 802000 -> STDIN -> 0
合計 2レコードです。
========================================
menu
========================================
1...追加(Add)
2...削除(Delete)
3...挿入(Insert)
4...表示(Print)
9...終了(Quit)
選択(1-4,9)? q
メモリ 803400を解放します。
メモリ 802000を解放します。
線形リスト（静的リスト）と比較して連結リストのよいところは、データ量が増えても都度メモリをアロケートするので、データ量に応じたメモリの消費量で済む点と、データの挿入が非常に簡単な点です。線形リストで途中にデータを追加する場合、追加するデータ以降はすべて一つずつ後にずらす処理が必要になりますので、データ量が増えた場合、その処理コストが高くなりますが、連結リストの場合、ポインタの付け替えで済みますので、処理コストが低く済みます。逆に線形リストが要素のどこかにアクセスしたい場合に簡単にアクセスできるのに対し、連結リストは各要素をたどってアクセスする必要があるため、一般的にランダムアクセス性能は線形リスト＞連結リストとなります。
とな。
メモリのアドレスを表示するようになっているので、一般的なCの入門書に比べて判りやすいかなと。
例えば
2 (802a00) : 802000 -> console -> 803400の部分は
前のデータが、８０２０００番地に格納されてて、格納されているデータは「console」で、次のデータは８０３４００番地に格納されている事を示しています。
データが入力される度にメモリが確保されている事、そして最初のデータの「前のアドレス」と最後のデータの「次のアドレス」がNULLになっている様子が分かると思います。
コメント