可変配列においてのメモリ取得、解放について

Question

###前提・実現したいこと
お世話になります・・・
いくつかの数字を入力して、隣り合う二数が連続した数であるならばその二数をぬいてその処理がなくなるまで行い、結果を出す。というプログラムを考えています。
構造体を勉強したため、何気なくで組んでみましたが、うまく動作せず、見にくいコードになってしまいました。
###発生している問題・エラーメッセージ
隣り合う二数の比較に構造体のメンバをそのまま使っているのですがわかりにくいコードであること。
処理後つなぎ合わせているため、メモリ解放するためにもう一度一からつながなければならないのか。

###該当のソースコード

#include<stdio.h>
#include<stdlib.h>
#define MAXLINE 11

void get_num(char ary[]);


typedef struct _number
{
	short int num;									//数字格納
	struct _number *prev;							//ひとつ前の構造体へのポインタを格納
	struct _number *next;							//次の構造体へのポインタを格納
}array;


int main()
{
	int i;											//配列の添え字
	array *p, *start;								//アドレスのp、構造体の先頭
	array *q;										//解放のアドレス
	char num[MAXLINE];								//getchar()の数字を格納
	short int cnt = 1;								//数列整理のカウンタ

	for (i = 0; i < 10; i++)
	{
		if (i == 0)
		{
			p = malloc(sizeof(array));				//構造体のメモリを確保
			if (p == NULL)
			{
				printf("memory allocattion error\n");
				return EXIT_FAILURE;
			}
			start = p;								//基準、始のアドレスを残しておく
			p->prev = NULL;

			get_num(num);
		}
		else
		{
			p->next = malloc(sizeof(array));		//次の構造体用のメモリ確保
			if (p == NULL)
			{
				printf("memory allocattion error\n");
				return EXIT_FAILURE;
			}
			p->next->prev = p;						//次の構造体の前へのポインタに現在のアドレス
			p = p->next;
		}
		p->num = num[i];							//構造体の数字格納メンバに数字を格納
	}
	p->next = NULL;									//終端NULL

/*数列の隣り合う要素を比較して連続数ならその二つの要素をとばす*/
	p = start;
	while (cnt != 0)
	{
		if (p->next==NULL)
			p = start;
		cnt = 0;
		if ((p->num + 1 == p->next->num) || (p->num == p->next->num + 1))
		{
			if (p == start) {
				p = p->next->next->next;
				cnt++;
			}
			else {
				p->prev->next = p->next->next;
				cnt++;
			}
		}
		p = p->next;
	}
	
	p = start;
	while (1)
	{
		printf("  %d", p->num);
		p = p->next;
		if (p->next == NULL)
			break;
	}


	
	/*動的確保したメモリの解放*/
	p = start;										//保存していた基準のアドレスに
	while (p != NULL)								//終端NULLになるまで
	{
		q = p;										//解放用でまわすqにp(pのメモリを消す為)
		p = p->next;								//次に移動
		free(q);									//解放
		
	}

	return 0;
}


void get_num(char ary[])							//数字の文字列を格納する関数
{
	short int k, c;
	for (k = 0; k <10 && (c = getchar()) != '\r'; k++)
		ary[k] = c - '0';
	ary[k] = '\0';

	while (getchar() != '\n');
}

今回聞きたくて該当になる部分はここになります。

/*数列の隣り合う要素を比較して連続数ならその二つの要素をとばす*/
	p = start;
	while (cnt != 0)
	{
		if (p->next==NULL)
			p = start;
		cnt = 0;
		if ((p->num + 1 == p->next->num) || (p->num == p->next->num + 1))
		{
			if (p == start) {
				p = p->next->next->next;
				cnt++;
			}
			else {
				p->prev->next = p->next->next;
				cnt++;
			}
		}
		p = p->next;
	}
	
	p = start;
	while (1)
	{
		printf("  %d", p->num);
		p = p->next;
		if (p->next == NULL)
			break;
	}

###試したこと
当初は配列で考えたのですが、処理後配列の長さが変わるということで可変型が言いと思い、構造体にしました。
このコードで 0123456789 と入力すると 01236 となるため、まだ変数の扱いが間違っているのは把握してます。

うまい表現方法などがあれば教えていただけると幸いです。

Answer 1

当初は配列で考えたのですが、処理後配列の長さが変わるということで可変型が言いと思い、構造体にしました。

この文では読んだ人は「？？？」となります、正しくは構造体ではなくリスト構造ですね。

やりたい事は連続した数を抜くということなので、データとしては増える事はなく減る一方の処理ですね。
それならばリスト構造ではなく配列(文字列）で扱った方がシンプルになると思います。

このプログラムではリスト構造を用いる必要もなければ、メリットもありません。
配列（文字列）のまま扱うべきでしょう。

---

書いてみました。

#include<stdio.h>
#include<stdlib.h>
#define MAXLINE 11

int main()
{
    int i, j;
    char num[MAXLINE];
    char work[MAXLINE];

    strcpy(num, "2563579015");

    while(1){
        j = 0;
        for(i = 0; i <= strlen(num); i++) {
            if( num[i+1] == '\0' || num[i] + 1 != num[i+1]) {
                work[j] = num[i];
                j += 1;
            } else {
                i += 1;
            }
        }
        work[j] = '\0';
        if(strcmp(num, work) == 0) break;
        strcpy(num, work);
    }
    
    printf(num);  // 5795
}

Comments

[yowashi]

回答ありがとうございます。そうですね。言われて、調べて確認しました。リスト構造体というものですね。
配列で扱ってみたいのですが、配列は要素を削ったりすることができるのでしょうか。
それとも配列（文字列）とおっしゃられている意味というのは、数字の並びを文字列と考えstr○○関数を駆使して分解、再構成するということでしょうか。
無知で申し訳ないですが、足りない部分がありましたらそのテーマ、単元でも教えていただけると幸いです。

[pashango2]

要素を削るというのは適当ではありません、配列の範囲内ならば増減はできます。
文字列の範囲はヌルターミネートといって\0がきたら終了となります、配列の範囲内(MAX_VALUE)であれば要素を削る（正確には配列の範囲内で終端を短くする）ことはできます。

[pashango2]

ちなみに私がやるのであればstr○○関数は一つも使いません。

[yowashi]

なるほど、配列で確保した範囲の増減ですね。
その方法のときに、メモリ管理に重きを置く場合、たとえば要素数が千以上などの膨大な桁になった時、使用メモリは大きくなりますよね、処理速度はおそらく配列の方が速いのだと思いますが、処理とメモリを並べたときに、その使用メモリの多さというのは目をつぶれる範疇にあるのでしょうか。
うまく伝えられずにすみません。

[pashango2]

まず要素をどのようにアクセスするかによります。
シーケンシャルなアクセスであれば、リスト構造でも良いでしょう。
ランダムアクセスが何回も発生する場合はリスト構造は非常に遅くなります。

処理に見合ったデータ構造を選択することが重要です。
銀の弾丸はありませんので、メリットデメリットを熟知している技術者が判断を下すべきです。
コード組むだけなら誰でも出来ます、逆に言えばその判断のバランス感覚こそが技術者の手腕といっても良いでしょう。

[pashango2]

あと普通にリスト構造の作成時にバグがありますよ。

p->next = malloc(sizeof(array)); //次の構造体用のメモリ確保

とありますが、この後の

if (p == NULL)

は意味がありません。
コピペをしているからだと思いますが、あまり良くないコードですね。

[yowashi]

勉強になります。ケースバイケースを念頭においてどのアルゴリズムをするか考えるようにします。

コードについては、こちらでまだまともに動いていなくバグがあるのは承知です。
なるほど、確かに　次の　なのにpがNULLなはずがないですね。
p->next = malloc(sizeof(array))でp->nextのarray構造体の箱がとられて、そのメンバのprevに現在のpの値が入ると思っていたのですが、まだ値が決まっていないんですね。

[pashango2]

すみません、質問なのですが0123456789 と入力されたら正しい答えは何ですか？
012345678と入力したときの答えもお願いします。

[yowashi]

問題定義があやふやですみません。隣り合う二数を比較して連続なら抜く、この作業を繰り返して、この作業がなくなったら表示。というものなので、
自分の想定している答えは0123456789ですと、何も表示されずに終了。です。
もうひとつ、2563579015ですと、5795　と表示されて終了するものを作成するつもりです。

[yowashi]

012345678ですと8と表示で終了の予定です。

[pashango2]

あまり答えは書くべきではないかと思いましたが、リスト構造をやめるとこんなにスッキリするという事で・・・
処理にあったデータ構造にすることが肝心です。

[yowashi]

解答ありがとうございます。すごいスッキリするんですね。
ただ、今回自分の中で標準入力からの不特定な数字であること、構造体を理解するということを自己課題にしてやっているので、もう少し自分で考えて見ます。

Answer 2

連続する二整数が現れたら，現れた時点でリストを繋ぎなおして，その後すぐにfree()してしまうべきでしょうね。
このままではメモリリークを起こしてしまいます。
一度リストから外れた要素は(別に記録しておかない限りは)もう二度と参照する方法がありませんから，後でまとめて削除することもできません。

また，このようなリストの場合，敢えて先頭にはデータを持たせないでダミーとするのもありかもしれません。
今は先頭を削除するときはstartを書き換えなければならないので先頭と途中とで場合分けをしなければなりませんが，もし先頭をダミーの要素にしておけば，データの先頭も途中と同じように見なせます。表示するときはデータは start->next から読み始めればよいですし。

それで質問に関係のない部分なのですが少し。

main() 内でのfor文が10回回されていることから考えて，入力は10文字固定なんですよね。

• 9文字しか来ない等の不正な入力を考えなくてよいならば，

get_num() 関数内では単純に for を 10 回回せばよいと思います。getchar()を使って判定する必要はないかと。
ついでに，配列をNULL終端させる意味はないと思います。

• 不正な入力を考えるならば，

get_num() 関数の中の (c = getchar()) != '\r'に関してですが，(バイナリファイルなら別として)入力は勝手にCRLF(\r\n)をLF(\n)に変換してくれる場合がほとんどだと思うので，チェックしたいなら(c = getchar()) != '\n'にするべきなのではないでしょうか？
また，配列を初期化しておかないと，10文字に満たなかった場合に，配列の後ろの残りが不正値になります。
さらに，チェックを'\n'に変更した場合は，最後のwhile(getchar() != '\n')を常に実行させると困ったことが起こります。10文字に満たなかった場合に，入力の'\n'がfor文の中で消費されてしまっていますので，もう一度改行を入力する羽目になります。

また，最後に表示させている部分の while なのですが，このままではリストの中身が全て無くなってしまった場合に落ちます。

Comments

[yowashi]

なるほど、ダミーをいれるのはしっくりきました。試してみます。
そうですね、getchar()の判定はLFでした。おっしゃるとおり、while文でまた入力することになったため消しました。
残りの配列部分は￥0で終端決めて、と考えていましたがfor文の１０回固定では初期化必要ですね。考え直します。
表示させているwhileもおっしゃるとおり落ちました、startの値を適宜変えて、要素がない時、nullの時以外の実行でまわすようにします。

Answer 3

処理の後にそれぞれfreeで解放することでおそらくメモリ解放は解決すると思います。
処理後のstartのポインタの中身等、まだ穴だらけではありますが、考えていきます。

ケースバイケースを改めて知ることができました。ありがとうございます。