メモリの解放free()について

質問

メモリ解放についての質問です。
下の関数をループで呼び出すとき、new_itemのメモリ解放free()はどのように行えば良いでしょうか？

typedef struct _ITEM
{
int n,m;
void *right;
} item;

int data()
{
int i,j,k;
int n,m;
item *new_item,*last_item;

for (i = 0; i <= M-1; i++) {

...

last_item = &(list[i]);
k = 0;
for (j = 0; j <= num-1; j++) {
/* making new item */
if ((new_item = (item*)malloc(sizeof(item))) == NULL) {
fprintf(stderr,"Can't allocate memory.\n");
exit(-1);
}
new_item->m = i;
new_item->n = k;
new_item->right = NULL;
last_item->right = new_item;
last_item = new_item;
}
}
}

回答No.4

circuit · ベストアンサー

このタイプのリストだと、自分の右側しか見えないので、最初の要素を知っておく必要があります。
最初の要素から、順に右へ右へ解放していくのが通常の手段です。

最初の要素をダミーとして作っておきます。

// グローバル変数
item * first = NULL;

//
int data()
{
int i,j,k;
int n,m;
item *new_item,*last_item;

first = (item *)malloc(sizeof(item));
first->right = NULL;

last_item = first;

for (i = 0; i <= M-1; i++) {

...

//last_item = &(list[i]);
k = 0;
for (j = 0; j <= num-1; j++) {
/* making new item */
if ((new_item = (item*)malloc(sizeof(item))) == NULL) {
fprintf(stderr,"Can't allocate memory.\n");
exit(-1);
}
new_item->m = i;
new_item->n = k;
new_item->right = NULL;
last_item->right = new_item;
last_item = new_item;
}
}
}

// 解放部分
item * tmp;
while( first != NULL )
{
tmp = first->right;
free(first);
first = tmp;
}

＠補足
list 配列が何かわからないので無視しました。
もしなんらかの実装がされているなら、それにあわせて考え直す必要があります。

＃些細なことですが、right はリスト構造であることを示すためにも struct _ITEM * 型で定義したほうがいいと思います。
＃void * にすると何のポインタが入るのかわからないので、可読性が落ちます。

参考URL：

http://www.geocities.jp/ky_webid/algorithm/010.html

お礼

無事解決いたしました。
先頭アドレスはa->start_row_listが全部持ってました。
回答していただきありがとうございました。

補足

皆さんの意見を参考に色々修正して試してみてはいるのですが、なぜかメモリが解放されません。
色々試してみて（for文外にだしたりして）new_item以外は解放されていることを確認しましたので、やはりnew_itemが解放されていないんだと思います。
大変長々書いて申し訳ないですが、もしお暇でしたら見ていただると幸いです。

typedef struct _ITEM
{
int nn,mm;
struct _ITEM *right;
} item;

typedef struct _SPMATRIX
{
int N;
int M;
int* num_ones_in_col;
int* num_ones_in_row;
int biggest_num_ones_col;
int biggest_num_ones_row;
item* start_col_list;
item* start_row_list;
} sparce_matrix;

item *first = NULL;

int gaussian(FILE* fp, sparce_matrix* a)
{
int i,j,k,w,tmp;
int nn,mm;
item *new_item, *last_item;
item* p;
int* current_row;
int leader, eleader;
item *del;

fscanf(fp,"%d %d\n",&(a->N),&(a->M));
　if ((current_row = (int*)malloc(sizeof(int)*(a->N))) == NULL) {
fprintf(stderr,"Can't allocate memory\n");
exit(-1);
}
if ((a->num_ones_in_row = (int*)malloc(sizeof(int)*(a->M))) == NULL) {
fprintf(stderr,"Can't allocate memory\n");
exit(-1);
}
if ((a->num_ones_in_col = (int*)malloc(sizeof(int)*(a->N))) == NULL) {
fprintf(stderr,"Can't allocate memory\n");
exit(-1);
}
if ((a->start_row_list = (item*)malloc(sizeof(item)*(a->M))) == NULL) {
fprintf(stderr,"Can't allocate memory\n");
exit(-1);
}

first = (item *)malloc(sizeof(item));
first->right = NULL;
last_item = first;

for (i = 0; i <= a->M-1; i++) {
//略
last_item = &(a->start_row_list[i]);
k = 0;
for (j = 0; j <= a->num_ones_in_row[i]-1; j++) {
while ((current_row[k] == 0) && (k <= a->N-1)) k++;
if ((new_item = (item*)malloc(sizeof(item))) == NULL) {
fprintf(stderr,"Can't allocate memory\n");
exit(-1);
}
new_item->mm = i;
new_item->nn = k;
new_item->right = NULL;
last_item->right = new_item;
last_item = new_item;
k++;
}
}
free(current_row);
while( first != NULL )
{
del = first->right;
free(first);
first = del;
}
free(a->num_ones_in_row);
free(a->num_ones_in_col);
free(a->start_row_list);
return 0;
}

回答No.5

noname#20242

circuitさんの意見とダブるかもしれませんが、#1の考えで全部開放できると思いますよ。
オリジナルに多少手を加えてしまいましたが、以下のコードでどうでしょうか？

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

typedef struct _ITEM
{
int n,m;
struct _ITEM *right;
} item;

#define M 2
#define num 3
item **list;
item **top;

int data(void)
{
int i,j,k;
int n,m;
item *new_item,*last_item;

for (i = 0; i <= M-1; i++) {
last_item = list[i];
k = 0;
for (j = 0; j <= num-1; j++) {
/* making new item */
if ((new_item = (item*)malloc(sizeof(item))) == NULL) {
fprintf(stderr,"Can't allocate memory.\n");
exit(-1);
}
k = j;
new_item->m = i;
new_item->n = k;
new_item->right = NULL;
if (top[i] == NULL) {
top[i] = new_item;
}else{
last_item->right = new_item;
}
last_item = new_item;
}
}
return 0;
}

int main(int argc, char* argv[])
{
int i, size;
item *top_item, *del_item;

size = sizeof(void*) * M;
list = (item**)malloc(size);
top = (item**)malloc(size);
memset(list, '\0', size);
memset(top, '\0', size);

data();

//free
for (i = 0; i < M; i++) {
top_item = top[i];
while (top_item != NULL) {
del_item = top_item;
top_item = top_item->right;
free(del_item);
}
}

free(list);
free(top);
return 0;
}

お礼

無事解決いたしました。
先頭アドレスはa->start_row_listが全部持ってました。
回答していただきありがとうございました。

補足

回答ありがとうございます。
やはりうまくいきませんでした。
非効率ですが、for前で大きめにmallocすしてfreeするしかないのかなとも思い始めています。

回答No.3

t_nojiri

あ、良く見たら、
last_item = new_item;
で、更新してるからアドレスは全て入ってますね。

でもなー。この
malloc(sizeof(item))
は、サイズ変わらないじゃないですか？

オート変数で固定値切るか、ループに入る前に(M-1)*(num-1)分itemのmallocしといて、最後にfree()を先頭アドレスだけやる方が速いですよ。
まあ、リスト管理の最後ちゃんとNULLになってるから、iのループとrightのアドレスNULLになるまでfreeしても構いませんが。

お礼

無事解決いたしました。
先頭アドレスはa->start_row_listが全部持ってました。
回答していただきありがとうございました。

補足

回答ありがとうございます。
質問上固定長にしましたが、numの部分は実際のプログラムでは固定長ではないので困っています。

回答No.2

t_nojiri

last_item->right = new_item;
で一つ前のリストにmallocしたアドレス管理してるのかな？

でも、この
for (j = 0; j <= num-1; j++) {
内のループで
last_item->right
のアドレス書き潰してるから、全部開放出来ませんよ。

補足

回答ありがとうございます。
関数自体を変更するしかないのでしょうか？

回答No.1

noname#20242

一番先頭のポインタはどこかで覚えておく必要があると思います。
そして開放時に下記のような処理でいいのではないでしょうか？

item* del_item;
top_item = 先頭;
while (top_item != NULL) {
del_item = top_item;
top_item = top_item->right;
free(del_item);
}

一番先頭のポインタを覚えたくない場合は、item構造体に void* left; を追加して、逆にたどっていけるようにする方法もあります。

item* del_item;
while (new_item != NULL) {
del_item = new_item;
new_item = new_item->left;
free(del_item);
}

補足

回答ありがとうございます。
試してみましたが、メモリが増え続けています。
No.2の回答者がおっしゃる通り、全部解放は出来ないんでしょうか。