リストの削除

長いデータの中から一つだけデータを削除するときには、配列よりもリストの方が効率がよい

code: listremove1.c

typedef struct Node{

int data;

struct Node * next;

} Node;

Node * node_new();

void node_print(Node * np);

Node * node_search(Node *list, int data); //データ がある値dataのノードを探す

int main(void){

Node *head, *l, *s;

int i;

head = node_new(); // ヘッダーノード

s = head; // リスト全体

// 1から9までのリストを作る

for(i=1; i<10; i++){

l = node_new();

l->data = i;

s->next = l;

s = s->next;

}

node_print(head->next);

s = node_search(head, 5); //data が5のノードを探す

l = s->next; // 削除するノードをlに保存する

s->next = s->next->next; // この一行でリストからノードを削除している

free(l); // リストから削除したノードの存在自体を消す

node_print(head->next);

}

Node * node_new(){

Node *l;

l = malloc(sizeof(Node)); // 名前のない Node 一個分のメモリを確保して、そのポインタを l にしまう

l->data = 0;

l->next = NULL;

return l;

}

void node_print(Node * np){

while(1){

if(np == NULL) break;

printf("%d ", np->data);

np = np->next;

}

printf("\n");

}

Node * node_search(Node *list, int data){

while(1){

if(list->next == NULL) break; // なかった

if(list->next->next == NULL) break; // なかった

if(list->next->data == data) break; // みつけた

list = list->next;

}

return list;

}

比較のために、配列を使ったときの途中データの削除プログラム

code:arrayremove.c

int datanum;

void data_print(int data[]);

int data_search(int data[], int dat);//データがあるdataの引数を探す

int main(void){

int i, s;

// 1から9までのデータを作る

for(i=1; i<10; i++){

}

datanum=9;

data_print(data);

for(i=s+1; i<10-1; i++){//一個ずつデータの数だけ前に送る

}

datanum=datanum-1;

data_print(data);

}

void data_print(int data[]){

int i;

for(i=0; i<datanum; i++){

}

printf("\n");

}

int data_search(int data[], int num){

int i;

for(i=0; i<datanum; i++){

}

return i;

}

クイズ

データの数が増えたとき、削除にかかる計算時間は、リストと、配列でどう違うだろうか

ノードの削除の手順を図に書いてみよう

ノードを探すときに

if(list->next->data == data) break; // みつけた

演習

1) 1から10の数字をリストとして持って、一度表示してから、入力された1つの数字を取り除き出力するプログラムを書こう。リストに無い数字は無視する

2) 1から30の数字をリストとして持ち、リストから奇数を取り除いて出力するプログラムを書こう

kisu_search(..) を書くとよい