c言語 片方向連結リスト

質問

c言語の片方向連結リストのプログラムについて質問があります．
下記のプログラムの関数int get_index(ListPtr l, int value)に以下のようなコードを書く．リストl において値value を持つセルの位置を返す．返り値は，最初のセルが値value を持っていれば0，次のセルが値value を持っていれば1，...，値value を持っているセルが存在しなければ–1とする．
また，関数void add(ListPtr l, int index, int value)に以下のようなコードを書く．リストl の位置index に値value を持つセルを挿入．挿入前のリストに対して：index が0 のときは先頭に挿入，index が1 のときは（0から数えて）1番目のセルの前に挿入，index が2 のときは（0から数えて）2番目のセルの前に挿入，...，index がリストのサイズと等しいときはリストの末尾に挿入，それ以外の場合は何もしなくてよい．
これらのコードはどのように書けばよいのでしょうか？

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* 連結リスト中のノードの構造体 */
struct node {
int val; /* 値 */
struct node *next; /* 次ノード */
};

/* セルとそのポインタの型 */
typedef struct node Node;
typedef Node *NodePtr;

/* セルを一つ生成 */
NodePtr create_node(int v) {
NodePtr n = NULL;

n = malloc(sizeof(Node));
n->val = v;
n->next = NULL;

return n;
}

/* セルを表示 */
void print_node(NodePtr n) {
if (n != NULL) {
printf("<%d>", n->val);
}
else {
printf("(null)");
}
}

/* 連結リストの構造体 */
struct list {
/* 先頭セルへのポインタ */
NodePtr head;
};

/* 連結リストとそのポインタの型 */
typedef struct list List;
typedef List *ListPtr;

/* 空の連結リストを生成 */
ListPtr create_list(void) {
ListPtr l = NULL;
l = malloc(sizeof(List));
l->head = NULL;
return l;
}

/* 連結リスト l が空かどうか判定 */
int is_empty(ListPtr l) {
return (l->head == NULL);
}

/* リスト l の内容を表示 */
void print_list(ListPtr l) {
NodePtr n = NULL;

if (is_empty(l)) {
printf("(empty)\n");
return;
}

n = l->head;
while (n != NULL) {
print_node(n);
n = n->next;
}
printf("\n");
}

/* リスト l の先頭にセルを挿入 */
void add_first(ListPtr l, int val) {
NodePtr n = NULL;
n = create_node(val);
n->next = l->head;
l->head = n;
}

/* リスト l の先頭セルを削除 */
int delete_first(ListPtr l) {
NodePtr n = NULL;
int v;

/* リストが空なら -1 を返す（負の値はリストに含まれないと仮定）*/
if (is_empty(l)) return -1;

v = l->head->val;
n = l->head;
l->head = l->head->next;
free(n);
n = NULL;

return v;
}

/* 連結リスト l のサイズを取得 */
int get_list_size(ListPtr l) {
NodePtr n = NULL;
int size;

size = 0;
n = l->head;
while (n != NULL) {
size++;
n = n->next;
}
return size;
}

/*
* 連結リスト l における index 番目のセルの値を取得
* （そのようなセルが存在しなければ -1 を返す）
*/
int get_value(ListPtr l, int index) {
NodePtr n = NULL;
if (index < 0) return -1;

n = l->head;
while (index > 0 && n != NULL) {
n = n->next;
index--;
}

return (n == NULL) ? -1 : n->val;
}

/* リスト l 中の全セルを削除（ループ版）*/
void delete_all(ListPtr l) {
NodePtr n = NULL, m = NULL;

n = l->head;
while (n != NULL) {
m = n;
n = n->next;
free(m);
}

l->head = NULL;
}

/* セル n 以降を全て削除（内部処理用の再帰関数）*/
void delete_rest(NodePtr n) {
if (n->next != NULL) delete_rest(n->next);
free(n);
}

/* リスト l 中の全セルを削除（再帰版）*/
void delete_all_recursively(ListPtr l) {
if (l->head == NULL) return;
delete_rest(l->head);
l->head = NULL;
}

/* リスト l 全体を削除 */
#define delete_list(l) (delete_list0(l),l=NULL)
void delete_list0(ListPtr l) {
delete_all(l);
free(l);
}

/* リスト l において値 val を持つセルの位置を返す */
int get_index(ListPtr l, int value) {

return -1;
}

/* リスト l の位置 index に値 val を持つセルを挿入 */
void add(ListPtr l, int index, int value) {

}

/* 連結リストの使用例 */
int main(void) {
FILE *fp = NULL;
char buf[10];
int age;
ListPtr l = NULL;

l = create_list();

add_first(l, 28);
add_first(l, 40);
add_first(l, 33);
add_first(l, 15);

print_list(l);

delete_first(l); print_list(l);
delete_first(l); print_list(l);
delete_first(l); print_list(l);
delete_first(l); print_list(l);

return 0;
}

回答No.1

POMPUG · ベストアンサー

修正した関数：add_first
実装した関数：get_index, add
星印が付いているところが修正箇所です。

/* ★リスト l の先頭にセルを挿入 */
void add_first(ListPtr l, int val) {
NodePtr n = NULL;

/* ★今の先頭セルの次があるならそれを覚えておく */
NodePtr next = NULL;
if(l && l->head) next = l->head;

n = create_node(val);

/* ★nの次はNULLまたは先頭であったノードなのでnextを入れる */
/* n->next = l->head; ←間違い */
n->next = next;

l->head = n;
}

/* ★リスト l において値 val を持つセルの位置を返す */
int get_index(ListPtr l, int value) {
int i;
int len = get_list_size(l);
for(i = 0 ; i < len ; i++)
{
if(get_value(l, i) == value)
{
return i;
}
}
return -1;
}

/* ★リスト l の位置 index に値 val を持つセルを挿入 */
void add(ListPtr l, int index, int value) {
int len = get_list_size(l);

/* リストの先頭に追加する場合はここで処理をして抜ける */
if(index == 0)
{
add_first(l, value);
return;
}

/* indexが1以上の場合は挿入する位置を探す。pは挿入する位置であり、p_prev_nodeはpの一つ手前のノードである */
NodePtr p = l->head;
NodePtr p_prev_node = NULL;
while(index > 0)
{
if(p == NULL)
{
/* 挿入する位置が無い場合で且つindexが0になっていない場合は指定された位置に正しく入れることができない。よって仕様では無視する事になっているためここで戻る。 */
return;
}
p_prev_node = p;
p = p->next;
index--;
}

/* 新しいノードを作る */
NodePtr new_node = create_node(value);

/* 挿入する位置のひとつ前のノード(p_prev_node)の次に今作ったノードをつなぐ */
p_prev_node->next = new_node;

/* 今作ったノードの次に、挿入する位置にあったノード(p)をつなぐ。pはNULLでもよい。その場合は最後のノードという意味である。 */
new_node->next = p;
}

/* 連結リストの使用例 */
int main(void) {
FILE *fp = NULL;
char buf[10];
int age;
ListPtr l = NULL;

l = create_list();

add_first(l, 28);
add_first(l, 40);
add_first(l, 33);
add_first(l, 15);
/* ★重複する場合のテストのため同じ値を追加 */
add_first(l, 33);

print_list(l);

/* ★ get_indexのテスト */
printf("値15の位置は%dです。\n", get_index(l, 15));
printf("値33の位置は%dです。複数ある場合は先に見つかった方。\n", get_index(l, 33));
printf("値40の位置は%dです。\n", get_index(l, 40));
printf("値28の位置は%dです。\n", get_index(l, 28));

/* ★ addのテスト1 */
printf("\nindex=0に値0をaddした結果\n");
add(l, 0, 0);
print_list(l);

/* ★ addのテスト2 */
printf("\nindex=99に値99をaddした結果(無視される)\n");
add(l, 99, 99); /* 無視される */
print_list(l);

/* ★ addのテスト3 */
printf("\nindex=2に値2をaddした結果\n");
add(l, 2, 2);
print_list(l);

/* ★ addのテスト4 */
printf("\nindex=7に値7をaddした結果(最後のノードとして追加できることの検証)\n");
add(l, 7, 7);
print_list(l);

delete_first(l); print_list(l);
delete_first(l); print_list(l);
delete_first(l); print_list(l);
delete_first(l); print_list(l);

/* ★ 削除 */
delete_list(l);

return 0;
}

お礼

遅れてすみません．解答ありがとうございました！