C言語関係掲示板

過去ログ

No.261.リストの削除

[戻る] [ホームページ]
No.1569

再びリスト
投稿者---yusuke(2002/05/21 23:59:32)


どうも。前回の「リストについて」で質問させていただいたyusukeです。
同じような内容なのですが、ツリーが大きくなってしまうので新規投稿させていただきました。
今回は、リストの削除についてです。キーボードから予算を受け取り、その金額以上の商品リストを削除し、残りのリストを表示するというものです。皆さんのアドバイスも参考にさせてもらいながら作ってみたのですが、どうしてもうまく実行されません。読み込んでいるデータは次のようなものです。

JZK-30 Jizake_tsumeawase 4500
BSP-15 Body_soap_set 3000
BT-200 Bath_towel_set 2500
TEA-20 Koutya_tsumeawase 5000
THY-55 Koutya_hachimitsu_tsumeawase 3000
SPO-22 Tyoumiryo_variety_set 4000

これで、予算に4000と入力するとうまくいくんですが、それ以外では予算以上のものも出力されたり、途中でプログラムが止まってしまいます。

struct vertex{
	char code[10];
	char name[40];
	int price;
	struct vertex *next;
};

main()
{
	struct vertex *new_data, *top, *old, *copy;
	FILE *fp;
	char infile[20];
	int nedan=0;

	printf("Input filename : ");
	scanf("%s", infile);

	fp=fopen(infile, "r");

	top=malloc(sizeof(struct vertex));   /* ダミーノード */
	old=top;

	new_data=malloc(sizeof(struct vertex));
	while(fscanf(fp, "%s %s %d", new_data->code, new_data->name, &new_data->price)!=EOF){
		old->next=new_data;
		old=new_data;
		new_data=malloc(sizeof(struct vertex));
	}
	old->next=NULL;
	new_data=top;

	printf("Input price : ");   /* 予算を受け取る */
	scanf("%d", &nedan);

	while(new_data!=NULL){
		if(nedan<=(new_data->next->price)){   /* 予算以上の商品があれば */
			new_data->next=new_data->next->next;    /* ポインタのつなぎ換え(リストの削除) */
		}
		new_data=new_data->next;
	}

	new_data=top->next;
	copy=new_data;   /* copyにnew_dataをコピーしておく */
	while(new_data!=NULL){                 /* 削除した結果を出力 */
		printf("%s %s %d\n", new_data->code, new_data->name, new_data->price);
		new_data=new_data->next;
	}

	while(copy!=NULL){
		free(copy);
		copy=copy->next;
	}


	fclose(fp);
	free(top);
}


free()の使い方等に問題があるのでしょうか?


No.1593

Re:再びリスト
投稿者---snow(2002/05/23 17:09:20)


こんにちは、snowです。
誰も回答がなさそうなんで私でよければ。
問題の意味が微妙に読み取れなかったんで、私の解釈でやりました。

>free()の使い方等に問題があるのでしょうか?

freeの使い方とかではないですね。
ただ、1つ問題があり、最後のほうのfreeでメモリを開放した後に、そのアドレスのnextにアクセスしているところがあります。
これはだめです。
開放した領域の値は当然保証されません。
そのため、本編の例題でも、ポインタをもう1つ用意していたと思います。

また、mallocについてキャストをしていませんが、やったほうがいいと思います。
自分で書いといてあれですが、参考書によってはキャストしていたり、していなかったりと、まちまちだったりします。
そして載っていない本には、大概その意味が書いてなかったりするので、参考までに、との意味で書きました。
混乱させてしまうような書き込みでごめんなさい。

以下にとりあえず動くもの作ってみました。
自分のものと何がおかしかったのか比較してみてください。
また、絵に描いて見ると、意外と理解できたりします。
メモリの開放に関しては・・・
だれかhelp(笑

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


struct base{
char code[10];
char name[40];
int price;
};
struct vertex{
struct base data;
struct vertex *next;
};

main()
{
struct vertex *new_data; //領域確保に使用
struct vertex *top=NULL; //データのヘッダ
struct vertex *old; //削除対象のアドレスをnextに持っているポインタ
struct vertex *del=NULL; //削除用ヘッダ
struct vertex *dammy; //削除対象になるポインタ
struct vertex *temp; //削除対象のnextに入っているアドレスを持つポインタ

struct base *wk; //ファイル入力用ワーク領域
FILE *fp;
char infile[20];
int nedan=0;
wk=(struct base *)malloc(sizeof(struct base));
fp=fopen("gifts.txt", "r");


while(fscanf(fp, "%s %s %d", wk->code, wk->name, &wk->price)!=EOF){
new_data=(struct vertex *)malloc(sizeof(struct vertex));
new_data->data=*wk;
new_data->next=top;
top=new_data;

}
dammy=top;
while(dammy!=NULL){
printf("%-10s %-40s %8d\n", dammy->data.code, dammy->data.name, dammy->data.price);
dammy=dammy->next;
}
scanf("%d",&nedan);
old=temp=top;


while(temp!=NULL){ //リストの最後まで回す

if(temp->data.price >= nedan){ //入力された値とリストの値を比較

if(top==temp){ //対象がリストの先頭のとき

top=temp->next; //リストの2番目を先頭ヘッダに渡す
temp=temp->next; //tempを次のリストに進める
old->next=del; //削除対象をdelリストに連結
del=old; //削除対象をdelリストに連結
old=temp; //tempの持つアドレスをoldにコピー
}
else
{
dammy=temp; //削除対象となるアドレスをdammyにコピー
temp=temp->next; //tempを次のリストに進める
old->next=temp; //削除対象をさしていたnextに次のリストのアドレスを渡す
dammy->next=del; //削除対象をdelリストに連結
del=dammy; //削除対象をdelリストに連結
}
}
else{

old=temp; //oldを1つ進める
temp=temp->next; //tempを1つ進める
}
}

//以下ただの表示です

printf("\n削除対象データ\n");
while(del!=NULL){
printf("%-10s %-40s %8d\n", del->data.code, del->data.name, del->data.price);
del=del->next;
}
printf("\n残ったデータ\n");
while(top!=NULL){
printf("%-10s %-40s %8d\n", top->data.code, top->data.name, top->data.price);
top=top->next;
}
}
</pre>

No.1599

Re:再びリスト
投稿者---shelly(2002/05/24 16:40:54)


うーん。発想を変えてもいいでしょうか?
ファイルを読み込む前に予算を受け取っておいて、
予算以上のデータは読み込まない。
確保するメモリも少なくて済むし、処理が簡潔になるように思うのですが。

こんな感じでどうでしょうか。

struct vertex{
	char code[10];
	char name[40];
	int price;
	struct vertex *next;
};
typedef struct vertex vertex;

main()
{
	vertex work;
	vertex *datalist = NULL, *tmp = NULL, *current = NULL;
	char infile[20];
	int nedan = 0;
	FILE *fp = NULL;

	memset(&work, 0x00, sizeof(work));

	printf("Input filename : ");
	scanf("%s", infile);

	/* ファイルからデータ取得 */
	if (!(fp = fopen(infile, "r"))) {
		printf("file open error\n");
		goto end;
	}
	/* [先に]予算を受け取る */
	printf("Input price : ");
	scanf("%d", &nedan);

	while (fscanf(fp, "%s %s %d", work.code, work.name, &work.price) != EOF) {
		/* 予算オーバーなデータは読み飛ばす */
		if (work.price >= nedan) {
			continue;
		}
		/* 新しくメモリ確保 */
		if (!(tmp = (vertex *)calloc(1, sizeof(vertex)))) {
			printf("allocate error\n");
			goto end;
		}
		strcpy(tmp->code, work.code);
		strcpy(tmp->name, work.name);
		tmp->price = work.price;
		if (!datalist) {
			datalist = tmp;
			current = datalist;
		} else {
			current->next = tmp;
			current = current->next;
		}
	}
	/* 順に表示 */
	for (current = datalist; current; current = current->next) {
		printf("%-10s %-40s %8d\n", current->code, current->name,
			current->price);
	}

end:
	/* ファイルクローズ */
	if (fp) {
		fclose(fp);
	}
	/* 領域解放 */
	current = datalist; 
	while (current) {
		tmp = current;
		current = current->next;
		free(tmp);
	}
}


No.1600

Re:再びリスト
投稿者---yusuke(2002/05/24 20:29:12)


snowさん、shellyさん、どうもありがとうございました。大変参考になりました。プログラムの組み方は本当に人それぞれで、十人十色なんだなぁって感じです。


No.1601

Re:再びリスト
投稿者---かずま(2002/05/25 12:24:43)


> プログラムの組み方は本当に人それぞれで、十人十色なんだなぁって感じです。

リストの要素を削除するには双方向リストが便利だと思ってこんなのを書いてみました。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct vertex vertex;
struct vertex {
    char code[10];
    char name[40];
    int  price;
    vertex *prev, *next;
};

void initialize(vertex *vp)
{
    vp->prev = vp->next = vp;
}

void cleanup(vertex *vp)
{
    vertex *p = vp;
    while (p != vp) {
        vertex *t = p;
        p = p->next;
        free(t);
    }
    vp->prev = vp->next = vp;
}

void add(vertex *vp, const vertex *v)
{
    vertex *p = malloc(sizeof(vertex));
    if (p == NULL) fprintf(stderr, "out of memory\n"), exit(1);
    strcpy(p->code, v->code);
    strcpy(p->name, v->name);
    p->price = v->price;
    p->prev = vp->prev;
    p->next = vp;
    vp->prev->next = p;
    vp->prev = p;
}

void erase(vertex *v)
{
    v->prev->next = v->next;
    v->next->prev = v->prev;
    free(v);
}

int main()
{
    char   infile[100];
    FILE   *fp;
    vertex data, *vp;
    int    nedan;

    printf("Input filename : ");
    scanf("%99s", infile);

    fp = fopen(infile, "r");
    if (fp == NULL) return fprintf(stderr, "can't open %s\n", infile), 1;

    initialize(&data);
    while (fscanf(fp, "%9s%29s%d", data.code, data.name, &data.price) == 3)
        add(&data, &data);

    printf("Input price : ");
    if (scanf("%d", &nedan) != 1)
        return fprintf(stderr, "can't get price\n"), 1;

    for (vp = data.next; vp != &data; ) {
        vertex *t = vp;
        vp = vp->next;
        if (t->price >= nedan)
            erase(t);
    }

    for (vp = data.next; vp != &data; vp = vp->next)
        printf("%8s%8d   %s\n", vp->code, vp->price, vp->name);

    cleanup(&data);
    return 0;
}


No.1603

Re:再びリスト
投稿者---かずま(2002/05/25 12:54:25)


>リストの要素を削除するには双方向リストが便利だと思ってこんなのを書いてみました。

バグがありました。訂正します

void cleanup(vertex *vp) の最初は、vertex *p = vp; ではなく、
vertex *p = vp->next; です。


No.1605

Re:再びリスト
投稿者---かずま(2002/05/26 10:16:08)


> バグがありました。訂正します。

また、バグ発見。vertex で、char name[40]; と宣言しているのに、
while (fscanf(fp, "%9s%29s%d", data.code, data.name, &data.price) == 3)

%29s は、当然 %39s です。

入力文字列が、用意した文字配列の範囲外に書き込みを行うことを避けるため、
scanf の "%s" は、"%39s" のように読み込み文字数を制限したほうがよいと私は
考えています。gets よりも fgets を使うほうがよいと言われるのも同じですね。

C++ なら string型があるので、C のように char配列を使わずに済みます。
list もありますから、今回のプログラムも簡単にかけます。
free し忘れなんてことは考える必要がありません。
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <list>
using namespace std;

struct vertex {
    string code;
    string name;
    int    price;
};

class price_greater_equal {
    int price;
public:
    price_greater_equal(int nedan) : price(nedan) { }
    bool operator()(const vertex &v) const { return v.price >= price; }
};

int main()
{
    string infile;
    cout << "Input filename : ";
    cin >> infile;

    ifstream fp(infile.c_str());
    if (!fp) return cerr << "can't open " << infile << endl, 1;

    list<vertex> data;
    vertex v;
    while (fp >> v.code >> v.name >> v.price)
        data.push_back(v);

    int nedan;
    cout << "Input price : ";
    cin >> nedan;
    if (!cin) return cerr << "can't get price\n", 1;

    data.remove_if(price_greater_equal(nedan));

    for (list<vertex>::iterator i = data.begin(); i != data.end(); ++i)
        cout << setw(8) << i->code << setw(8) << i->price
            << "   " << i->name << endl;
}

このプログラムですが、g++ や Borland C++ 5.5 では問題ありませんが、
Visual C++ 6 だと、data.remove_if(price_greater_equal(nedan)); でエラーに
なるようです。これを次のように書き直すと、コンパイルできますが、ちょっとね。
list<vertex>::iterator i;
i = remove_if(data.begin(), data.end(), price_greater_equal(nedan));
data.erase(i, data.end());