線形探索のエラーがでて困っています

質問

線形探索を用いて表を作るプログラムを作ったのですが、データの数が１００００ならば作動するのですが、それ以上になってしまうとセグメントエラーが起こります。なぜだが教えていただけないでしょうか？

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000000
#define M 10

typedef int Key;
typedef struct item{
Key key;
}Item;

struct table {
int n;
Item item[N];
};
typedef struct table *Table;
Item *lookup_item(Table table ,Key key){
int i=0;
while(1){
if(i==table->n)
return (0);
if(table->item[i].key==key)
return &(table->item[i]);
i++;
}
return 0;
}

int add_item(Table table, Item item){
int i;
int n=table->n;
if(lookup_item(table ,item.key)!=0)
return (0);
else {
table->item[n].key=item.key;
table->n++;
return (1);
}
}
Table new_table(){
Table table;
table = (Table)malloc(sizeof(table));
return table;
}
int remove_item(Table table, Key key){

int i=0;
int n=table->n;
if(lookup_item(table,key)!=0)
{
while(1){
if(table->item[i].key==key){
table->item[i].key=table->item[n-1].key;
table->n--;
return 1;
}
i++;
}
}
else return (0);
}
Key keys[N];

int main() {
Table table;
Item item;
clock_t t1, t2;
char buff[128];
int i, j, n;

/* ファイルからキーを読み込み keys[] に格納する。*/
for (n=0; n<N && fgets(buff, 128, stdin)!=NULL; n++) {
keys[n] = atoi(buff);
}

/* 表を用意する。*/
table = new_table();

/* 追加項目数と全項目の追加に必要な時間(秒単位)を印字する。*/
t1 = clock();
for (i=j=0; i<n; i++) {
item.key = keys[i];
j += add_item(table, item);
}
t2 = clock();
printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC);

/* 探索成功数と全項目の探索に必要な時間(秒単位)を印字する。*/
t1 = clock();
for (i=j=0; i<n; i++) {
if (lookup_item(table, keys[i])!=NULL) j++;
}
t2 = clock();
printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC);

/* 削除項目数と全項目の削除に必要な時間(秒単位)を印字する。*/
t1 = clock();
for (i=j=0; i<n; i++) {
j += remove_item(table, keys[i]);
}
t2 = clock();
printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC);
return 0;
}

よろしくお願いします。

回答No.3

buriburi3 · ベストアンサー

int add_item(Table table, Item item){
int i;
int n=table->n; // ★★　←　ココで参照されているtable->nは値が初期化されていない。
if(lookup_item(table ,item.key)!=0)
return (0);
else {
table->item[n].key=item.key;
table->n++;
return (1);
}
}

typedef struct table *Table;
Item *lookup_item(Table table ,Key key){
int i=0;
while(1){
if(i==table->n) // ★★　←　初期化していないからどんな値が入っているのかドキドキ
return (0);
if(table->item[i].key==key)
return &(table->item[i]);
i++;
}
return 0;
}

Table new_table(){
Table table;
table = (Table)malloc(sizeof(table)); // ★★　←領域を取っているが初期化していない
table->n = 0 ; // ●●　思うにコレが抜けてるんじゃ…
return table;
}

お礼

ありがとうございます！
指摘していただいたところを直したらプログラムが動きました。
自分はもう少しポインタを勉強すべきですね。

回答No.2

noocyte

> typedef struct table *Table;
> (中略)
> table = (Table)malloc(sizeof(table));

この２行しか見てませんが…(笑)，

上の２行目の左辺は struct table の配列を期待しているのに，
malloc() の引数はポインタのサイズになってます．

まぎらわしいので１行目は

typedef struct table Table;

とした方がいいと思います．

お礼

ご意見ありがとうございました。
やはりみなさん指摘したとおりこの初期化が間違ってるようですね。
プログラムは動きました。本当にありがとうございます。

回答No.1

sakusaker7

できればOSとかコンパイラ含めた環境も書いて欲しいのですが、

table = (Table)malloc(sizeof(table));
return table;

とりあえずここでメモリ確保に失敗してたりしませんか?

この関数でもその上でも tableが有効なポインタであるか
チェックしてませんよね。

お礼

確保に失敗していました・・
ご指摘ありがとうございます。プログラムは動きました。やはりほかの関数でもチェックを入れたほうがいいのですね。