構造体を使ったマージソートのプログラム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
chop.chop
記事: 36
登録日時: 9年前

構造体を使ったマージソートのプログラム

#1

投稿記事 by chop.chop » 9年前

こんばんは。

コマンドラインから入力されたファイルの各行を.で区切られた文字列ごとに辞書順でマージソートをするプログラムを作っているのですが、肝心のソートの部分を有効にするとバスエラーとなります…
コンパイル時にでる
--------------------------------------------------
sort.c: In function ‘sortlist’:
sort.c:237:23: warning: assignment from incompatible pointer type [enabled by default]
marge[little].dom=mow[little];
^
sort.c:249:8: warning: assignment from incompatible pointer type [enabled by default]
top=marge[0].dom;
^
sort.c:262:16: warning: assignment from incompatible pointer type [enabled by default]
now->next=marge[ii+1].dom;//次の文字の配列と連結
^
--------------------------------------------------
という警告文がありますが、自分的には構造体の型は合わせているつもりなので悪いのか分かりません

入力に使用しているファイル、inputは
--------------------------------------------------
abc.example.co.jp
abc.example.or.jp
info
example.JP
--------------------------------------------------
のようになっています。
後ろのラベルほど優先順位が高く、ソート後は
--------------------------------------------------
info
abc.example.co.jp
example.JP
abc.example.or.jp
--------------------------------------------------
のようになるのが望ましいです。

実行時は
./sort input
のように実行します

どなたかお助けください。
添付ファイル
sort.c
(6.79 KiB) ダウンロード数: 121 回

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#2

投稿記事 by chop.chop » 9年前

よく考えてみたらマージソートじゃなくてバケットソートでした…
すみませんゆるしてくださいなんでもしますから

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 構造体を使ったマージソートのプログラム

#3

投稿記事 by みけCAT » 9年前

とりあえず実行した所、255行目でnowがNULLだったためアクセス違反が発生しました。

コンパイラの警告

コード:

sort.c: In function 'sortlist':
sort.c:184:4: warning: implicit declaration of function 'sleep' [-Wimplicit-func
tion-declaration]
    sleep(1);
    ^
sort.c:237:23: warning: assignment from incompatible pointer type [enabled by de
fault]
      marge[little].dom=mow[little];
                       ^
sort.c:249:8: warning: assignment from incompatible pointer type [enabled by def
ault]
     top=marge[0].dom;
        ^
sort.c:262:16: warning: assignment from incompatible pointer type [enabled by de
fault]
       now->next=marge[ii+1].dom;//(文字化け省略)
  ^
sort.c:157:6: warning: unused variable 'temp' [-Wunused-variable]
  int temp;
      ^
sort.c:139:6: warning: unused variable 'pon' [-Wunused-variable]
  YJ *pon;
      ^
sort.c: In function 'main':
sort.c:301:11: warning: unused variable 'now' [-Wunused-variable]
  YJ *top,*now;
           ^
sort.c:298:14: warning: unused parameter 'argc' [-Wunused-parameter]
 int main(int argc,char *argv[])
              ^
sort.c: In function 'sortlist':
sort.c:225:12: warning: 'littlebefo' may be used uninitialized in this function
[-Wmaybe-uninitialized]
      little=littlebefo;
            ^
デバッガの出力

コード:

GNU gdb (GDB) 7.6.1
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "mingw32".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from D:\MyData\Documents\programs\_対質問\kouzoutaiwotukattamaaz
isootonopuroguramu\sort.exe...done.
(gdb) run input.txt
Starting program: D:\MyData\Documents\programs\_ホソ\kouzoutaiwotukattamaazisooton
opuroguramu/sort.exe input.txt
[New Thread 1120.0x1b94]
-1163005936,abc.example.co.jp
-1163005936,abc.example.or.jp
-1163005939,info
-1163005938,example.JP
max:0
@
Program received signal SIGSEGV, Segmentation fault.
0x004018a4 in sortlist (top=0x0) at sort.c:255
255                                             while(now->next!=NULL)
(gdb) where
#0  0x004018a4 in sortlist (top=0x0) at sort.c:255
#1  0x004019c5 in main (argc=2, argv=0x582e18) at sort.c:310
(gdb) print marge
$1 = {{dom = 0x0} <repeats 12 times>, {dom = 0x5819c8}, {
    dom = 0x0} <repeats 13 times>}
(gdb) print now
$2 = (YJ *) 0x0
(gdb) print little
$3 = -33
(gdb)
ここからパッと見で言えることは
・225行目でlittlebefoが初期化されないまま参照される可能性があります
・littleが負になり(ASCIIで'@'の文字コードは0x40 = 64)、233行目などで配列の範囲外を参照してしまいます
・yj構造体のnumメンバを初期化していないので、でたらめな値になっています
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#4

投稿記事 by chop.chop » 9年前

確かにlittlebefoがどこにも初期化されていなかったどころか@以外がでるまで遡る部分もめちゃくちゃでした…すみません
numメンバは別のところで初期化しているつもりなので、おそらく大丈夫かと(行の中にいくつドットがあるかをカウントするだけなので)


今設計を見なおしたらバケットソートなのに優先度の高い順からソートしようとしていたようです…もうめちゃくちゃなのでソート部分から書き直すことにします
丸々書き直すつもりなのですが、一つ構造体についてお聞きしたいことがあります

ある構造体の中に、別の構造体へのポインタをもたせることはできるのでしょうか?以下のような感じで

コード:

typedef struct num
{
        char word[256];
        struct num *nnext;
}NUM;

typedef struct gyo
{
        char word[256];
        struct gyo *gnext;
        struct num *nnext;
}GYO;
これで出来た構造体のメンバを例えば

コード:

GYO *gtop,*gnow,*gnew;
NUM *ntop,*nnow,*nnew;
gtop=newgyo();
ntop=newnum();
gnow=gtop;
gnow->nnext=ntop;
(gnow->nnext)->word[1]='a';

nnow=newnum();
(gnow->nnext)->nnext=nnow;
みたいな記述はできるのでしょうか?これができたらバケットソートするのに相当楽になるのですが…

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 構造体を使ったマージソートのプログラム

#5

投稿記事 by みけCAT » 9年前

chop.chop さんが書きました:numメンバは別のところで初期化しているつもりなので、おそらく大丈夫かと(行の中にいくつドットがあるかをカウントするだけなので)
デバッグにおいて「つもりなので、おそらく大丈夫」は禁句です。
実際、変な値が出ています。すなわち初期化されておらず、大丈夫ではありません
こっちはきちんと出力結果(やソースコード)に基づいて指摘しました。
chop.chop さんが書きました:一つ構造体についてお聞きしたいことがあります

ある構造体の中に、別の構造体へのポインタをもたせることはできるのでしょうか?以下のような感じで

コード:

typedef struct num
{
        char word[256];
        struct num *nnext;
}NUM;

typedef struct gyo
{
        char word[256];
        struct gyo *gnext;
        struct num *nnext;
}GYO;
これで出来た構造体のメンバを例えば

コード:

GYO *gtop,*gnow,*gnew;
NUM *ntop,*nnow,*nnew;
gtop=newgyo();
ntop=newnum();
gnow=gtop;
gnow->nnext=ntop;
(gnow->nnext)->word[1]='a';

nnow=newnum();
(gnow->nnext)->nnext=nnow;
みたいな記述はできるのでしょうか?
はい。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#6

投稿記事 by chop.chop » 9年前

すみません、一応こちらの出力では
---------------------------------------------
3,abc.example.co.jp
3,abc.example.or.jp
0,info
1,example.JP
---------------------------------------------
のようにはなっていたもので…

mklist関数の以下の部分でnumメンバは初期化されてないでしょうか?

コード:

        while((c=fgetc(fp))!=EOF)
        {
                if(c!='\n')
                {
                        if(c=='.')
                        {
                                (now->num)++;
                        }
                        now->word[i]=c;
                        i++;
                }
                else if(c=='\n')
                {
                        now->word[i]='\0';
                        new=newyj();//新しい領域確保
                        now->next=new;//これにより、現在のnowの指す領域のnextは上で確保した領域となる
                        now=new;//次のループに向け、nowを上で確保した領域に再指定

                        /*---------------ここらへんは全部ループのための再設定-------------------*/
                        i=0;
                }

        }

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 構造体を使ったマージソートのプログラム

#7

投稿記事 by みけCAT » 9年前

chop.chop さんが書きました:mklist関数の以下の部分でnumメンバは初期化されてないでしょうか?
はい、初期化されていません。
謎の値にその値に依存しない数を足しても、謎の値のままですね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#8

投稿記事 by chop.chop » 9年前

ループ始めにnow->numの部分を0にいったんする必要があるということですね
言われるまで気づきませんでした。ありがとうございます

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#9

投稿記事 by chop.chop » 9年前

こんばんは。
この前の続きとなるのですが、やはり構造体のメンバ変数として、別の構造体へのポインタを指定するときの書き方に問題があるらしくコンパイル時にエラーが出まくりです。
またある関数内で宣言したポインタの配列を、他の関数に参照渡しすることもうまくできません…
またアドバイスをいただけないでしょうか

コード:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>

//構造体YJの定義
typedef struct yj
{
        int numdot;
	int lastdot;
	int nextdot;
        char word[256];
        struct yj *next;
}YJ;


//領域確保用の関数
YJ *newyj()
{
        YJ *p;
        p=(YJ *)malloc(sizeof(YJ));

        if(p==NULL)
        {
                fputs("malloc failedn\n",stderr);
                exit(1);
        }
        else
        {
                return p;
        }
}

//この構造体を配列にしてマージソートに使いたい
typedef struct list
{
        struct YJ *dom;//すでに上で定義した構造体型のポインタ
}LIST;


//ファイルの中身からリストを作るだけの関数
YJ *makelist(char filename[256])
{

        FILE *fp;
        fp=fopen(filename,"r");//ファイル開く
        //エラー処理
	if(fp==NULL)
        {
                printf("file open failed(%s)\n",filename);
        }

	int c;//ファイルから読み取った文字を格納
	int i=0;
	YJ *top,*now,*new;
	//入力順にリスト作成開始
	new=newyj();
	now=new;
	top=now;

	now->numdot=0;//初期化
	now->lastdot=-1;//文字列の最初の1つ前ににdotがあると仮定
	while((c=fgetc(fp))!=EOF)
	{
		if(c!='\n')
		{
			if(c=='.')
			{
				(now->numdot)++;
			}
			now->word[i]=c;
			i++;
		}
                else if(c=='\n')
                {
		        now->word[i]='\0';
                        new=newyj();//新しい領域確保
                        now->next=new;//これにより、現在のnowの指す領域のnextは上で確保した領域となる
                        now=new;//次のループに向け、nowを上で確保した領域に再指定

                        i=0;
			now->numdot=0;//初期化
			now->lastdot=-1;//最初の1つ前にdotがあると仮定
                }

	}
        now->next=NULL;
        fclose(fp);
	return top;
}

//メンバをNULLに初期化する関数
void resetdom(LIST *margepri,LIST *marge)
{
	int i;
	(*margepri).dom=NULL;
	for(i=0;i<26;i++)
	{
		(marge[i]).dom=NULL;
	}
}

//行ごとにいくつのdotがあるかを見つける関数
void findmaxdot(YJ *top,int *maxdot)
{
	YJ *now;
        now=top;
        while(now->next!=NULL)
        {
                if(*maxdot<(now->numdot))
                {
                        *maxdot=now->numdot;
                }
                now=now->next;
        }
        printf("Maxdot:%d\n",*maxdot);

}

//現在の区画中の最大文字数を特定する,次のdot特定
void findmaxword(YJ *top,int *maxw,int i)
{
	YJ *now;
	now=top;
	int l;
	int maxtemp;
	while(now->next!=NULL)
	{
		maxtemp=0;
		l=(now->lastdot)+1;
		while(1)
		{
			printf("%c",now->word[l]);
			//行の区画数が不足の時
			if((now->numdot)<i)
			{
				break;
			}

			//行の端ordotまで読んだ時
			if(((now->word[l])=='\0')||((now->word[l])=='.'))
			{
	                	now->nextdot=l;//現在の区画の終了の添字
				break;	
			}
			else
			{
				maxtemp++;
				l++;
			}
		}
		printf("@");
		//大小比較
		if(maxtemp>(*maxw))
		{
			(*maxw)=maxtemp;
		}
		now=now->next;
		printf("maxw:%d\n",*maxw);
	}	
}

//lastdot置き換え
void setlastdot(YJ *top,int i)
{
	YJ *now;
	now=top;
	while(now->next!=NULL)
	{
	        if((now->numdot)<i)
        	{
        		//区画数が足りない場合はそのまま
        	}
		else
		{
			now->lastdot=now->nextdot;//置き換え
		}
		now=now->next;
	}
}

void putin(YJ *now,LIST *margepri,LIST *marge,int asc,YJ *lastmpri,YJ *lastm[26])
{	//文字が足りないとき
	if(asc=='@')
	{
		if((*margepri).dom==NULL)//何もリストが連結されていないとき
		{
			(*margepri).dom=now;
			lastmpri=now;
			lastmpri->next=NULL;
		}
		else
		{
			lastmpri->next=now;
			lastmpri=now;
			lastmpri->next=NULL;
		}
		
	}//アルファベットの時
	else
	{
		asc=asc-97;//これでascは0~25になる
		if((marge[asc]).dom==NULL)//何もリストが連結されていないとき
                {
                        (marge[asc]).dom=now;
                        lastm[asc]=now;
                        lastm[asc]->next=NULL;
                }
                else
                {
                        lastm[asc]->next=now;
                        lastm[asc]=now;
                        lastm[asc]->next=NULL;
                }

	}
	
}

void joint(YJ *top,LIST *margepri,LIST *marge,YJ *lastmpri,YJ *lastm[26])
{
	int i;
	YJ *now;
	now=top;
	if(((*margepri).dom)!=NULL)//文字なしのところの処理
	{
		now->next=(*margepri).dom;
		now=lastmpri;
	}
	for(i=0;i<=25;i++)
	{
		if(((marge[i]).dom)!=NULL)
		{
			now->next=(marge[i]).dom;
			now=lastm[i];
		}

	}
	
}

void listmarge(YJ *top,LIST *margepri,LIST *margem,int i,int maxw,YJ *lastmpri,YJ *lastm[26])
{
	YJ *now,*temp;
	int j;
	int asc;
	int l;
	
	for(j=maxw;j>=1;j--)
	{
		now=top;
		l=(now->lastdot)+j;
		while(now->next!=NULL)
		{	//文字が足りない時
			if(l>=(now->nextdot))
			{
				asc='@';
			}//大文字
			else if((65<=(now->word[l]))&&((now->word[l])<=90))
			{
				asc=(now->word[l])+32;
			}//小文字
			else if((97<=(now->word[l]))&&((now->word[l])<=122))
                        {
                                asc=now->word[l];
                        }
			//marge配列に格納
			temp=now->next;//退避
			putin(now,&margepri,margem,asc,lastmpri,lastm);
			now=temp;//退避したやつ戻す
		}
		//この時点ですべての行はバケットソート用の配列にリストとして格納されているため、ここからまたtopから辿れるように戻す
		(top,&margepri,margem,lastmpri,lastm);

		//デバッグ
		printf("\n\n");
	        now=top;
	        while(now->next!=NULL)
	        {
	                printf("%d,%s\n",now->numdot,now->word);
	                now=now->next;
	        }
		
	}	
	
	
}

//ソート用の関数
void sortlist(YJ *top)
{
	YJ *now;
	
	//とりあえずデバッグのために表示
	now=top;
        while(now->next!=NULL)
        {
                printf("%d,%s\n",now->numdot,now->word);
                now=now->next;
        }

	//ソート用のリスト
	LIST margepri;//@文字の時に収納される配列(@の時は文字不足)
	YJ *lastmpri;//ソート用のリストの最後の要素を指すポインタ
	LIST marge[26];//アルファベット用
	YJ *lastm[26];//ソート用のリストの最後の要素を指すポインタ(アルファベット用)
	//構造体のメンバのdomをNULLに初期化
	resetdom(&margepri,marge);
	
	//各行の中のdotの数を見つける
	int maxdot=0;
	findmaxdot(top,&maxdot);

	printf("\n");
	//ここからdotで区切られた文字列ごとにソートをかけていく
	int i,j;
	int maxw=0;//現在の区画の中で最大の文字数
	for(i=maxdot;i>=0;i--)
	{
		now=top;
		//現在の区画でどの行の文字列が一番多いのかを特定,次のdot特定
		findmaxword(top,&maxw,i);

		//入れ替え
		listmarge(top,&margepri,marge,i,maxw,lastmpri,lastm);








		//置き換え
		setlastdot(top,i);
		printf("\n\n");
	}

}



int main(int argc,char *argv[])
{

	YJ *top,*now;

	top=makelist(argv[1]);

        if(top==NULL)
        {
                return -1;
        }
	
	sortlist(top);

	return 0;
}

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#10

投稿記事 by chop.chop » 9年前

273行目は引数だけで、joint関数を記述することを忘れていました…

joint(top,&margepri,margem,lastmpri,lastm);

となります。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 構造体を使ったマージソートのプログラム

#11

投稿記事 by みけCAT » 9年前

chop.chop さんが書きました:この前の続きとなるのですが、やはり構造体のメンバ変数として、別の構造体へのポインタを指定するときの書き方に問題があるらしくコンパイル時にエラーが出まくりです。
gcc 4.8.1でコンパイルしたところ、エラーは一件も出ませんでした(273行目未修正)。

コード:

YUKI.N>gcc --version
gcc (GCC) 4.8.1
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


YUKI.N>gcc -Wall -Wextra -g3 -static -o raw9.exe raw9.c
raw9.c: In function 'putin':
raw9.c:188:19: warning: assignment from incompatible pointer type [enabled by de
fault]
    (*margepri).dom=now;
                   ^
raw9.c:205:41: warning: assignment from incompatible pointer type [enabled by de
fault]
                         (marge[asc]).dom=now;
                                         ^
raw9.c: In function 'joint':
raw9.c:227:12: warning: assignment from incompatible pointer type [enabled by de
fault]
   now->next=(*margepri).dom;
            ^
raw9.c:234:13: warning: assignment from incompatible pointer type [enabled by de
fault]
    now->next=(marge[i]).dom;
             ^
raw9.c: In function 'listmarge':
raw9.c:269:4: warning: passing argument 2 of 'putin' from incompatible pointer t
ype [enabled by default]
    putin(now,&margepri,margem,asc,lastmpri,lastm);
    ^
raw9.c:182:6: note: expected 'struct LIST *' but argument is of type 'struct LIS
T **'
 void putin(YJ *now,LIST *margepri,LIST *marge,int asc,YJ *lastmpri,YJ *lastm[26
])
      ^
raw9.c:273:7: warning: left-hand operand of comma expression has no effect [-Wun
used-value]
   (top,&margepri,margem,lastmpri,lastm);
       ^
raw9.c:273:17: warning: left-hand operand of comma expression has no effect [-Wu
nused-value]
   (top,&margepri,margem,lastmpri,lastm);
                 ^
raw9.c:273:24: warning: left-hand operand of comma expression has no effect [-Wu
nused-value]
   (top,&margepri,margem,lastmpri,lastm);
                        ^
raw9.c:273:33: warning: left-hand operand of comma expression has no effect [-Wu
nused-value]
   (top,&margepri,margem,lastmpri,lastm);
                                 ^
raw9.c:273:3: warning: statement with no effect [-Wunused-value]
   (top,&margepri,margem,lastmpri,lastm);
   ^
raw9.c:242:56: warning: unused parameter 'i' [-Wunused-parameter]
 void listmarge(YJ *top,LIST *margepri,LIST *margem,int i,int maxw,YJ *lastmpri,
YJ *lastm[26])
                                                        ^
raw9.c: In function 'sortlist':
raw9.c:316:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
raw9.c: In function 'main':
raw9.c:346:11: warning: unused variable 'now' [-Wunused-variable]
  YJ *top,*now;
           ^
raw9.c:343:14: warning: unused parameter 'argc' [-Wunused-parameter]
 int main(int argc,char *argv[])
              ^
raw9.c: In function 'sortlist':
raw9.c:325:12: warning: 'lastmpri' may be used uninitialized in this function [-
Wmaybe-uninitialized]
   listmarge(top,&margepri,marge,i,maxw,lastmpri,lastm);
            ^

YUKI.N>
chop.chop さんが書きました:またある関数内で宣言したポインタの配列を、他の関数に参照渡しすることもうまくできません…
具体的に、どういうことがしたいのでしょうか?

[hr]
実行すると不自然に多くの出力がなされてしまいますが、とりあえずインデントを整え、gccの警告を全て潰してみました。
まだ解読はしていないです。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>

//構造体YJの定義
typedef struct yj
{
	int numdot;
	int lastdot;
	int nextdot;
	char word[256];
	struct yj *next;
}YJ;


//領域確保用の関数
YJ *newyj()
{
	YJ *p;
	p=(YJ *)malloc(sizeof(YJ));

	if(p==NULL)
	{
		fputs("malloc failedn\n",stderr);
		exit(1);
	}
	else
	{
		return p;
	}
}

//この構造体を配列にしてマージソートに使いたい
typedef struct list
{
	//struct YJ *dom;//すでに上で定義した構造体型のポインタ
	YJ *dom;//すでに上で定義した構造体型のポインタ
}LIST;


//ファイルの中身からリストを作るだけの関数
YJ *makelist(char filename[256])
{

	FILE *fp;
	fp=fopen(filename,"r");//ファイル開く
	//エラー処理
	if(fp==NULL)
	{
		printf("file open failed(%s)\n",filename);
	}

	int c;//ファイルから読み取った文字を格納
	int i=0;
	YJ *top,*now,*new;
	//入力順にリスト作成開始
	new=newyj();
	now=new;
	top=now;

	now->numdot=0;//初期化
	now->lastdot=-1;//文字列の最初の1つ前ににdotがあると仮定
	while((c=fgetc(fp))!=EOF)
	{
		if(c!='\n')
		{
			if(c=='.')
			{
				(now->numdot)++;
			}
			now->word[i]=c;
			i++;
		}
		else if(c=='\n')
		{
			now->word[i]='\0';
			new=newyj();//新しい領域確保
			now->next=new;//これにより、現在のnowの指す領域のnextは上で確保した領域となる
			now=new;//次のループに向け、nowを上で確保した領域に再指定

			i=0;
			now->numdot=0;//初期化
			now->lastdot=-1;//最初の1つ前にdotがあると仮定
		}

	}
	now->next=NULL;
	fclose(fp);
	return top;
}

//メンバをNULLに初期化する関数
void resetdom(LIST *margepri,LIST *marge)
{
	int i;
	(*margepri).dom=NULL;
	for(i=0;i<26;i++)
	{
		(marge[i]).dom=NULL;
	}
}

//行ごとにいくつのdotがあるかを見つける関数
void findmaxdot(YJ *top,int *maxdot)
{
	YJ *now;
	now=top;
	while(now->next!=NULL)
	{
		if(*maxdot<(now->numdot))
		{
			*maxdot=now->numdot;
		}
		now=now->next;
	}
	printf("Maxdot:%d\n",*maxdot);

}

//現在の区画中の最大文字数を特定する,次のdot特定
void findmaxword(YJ *top,int *maxw,int i)
{
	YJ *now;
	now=top;
	int l;
	int maxtemp;
	while(now->next!=NULL)
	{
		maxtemp=0;
		l=(now->lastdot)+1;
		while(1)
		{
			printf("%c",now->word[l]);
			//行の区画数が不足の時
			if((now->numdot)<i)
			{
				break;
			}

			//行の端ordotまで読んだ時
			if(((now->word[l])=='\0')||((now->word[l])=='.'))
			{
				now->nextdot=l;//現在の区画の終了の添字
				break;	
			}
			else
			{
				maxtemp++;
				l++;
			}
		}
		printf("@");
		//大小比較
		if(maxtemp>(*maxw))
		{
			(*maxw)=maxtemp;
		}
		now=now->next;
		printf("maxw:%d\n",*maxw);
	}	
}

//lastdot置き換え
void setlastdot(YJ *top,int i)
{
	YJ *now;
	now=top;
	while(now->next!=NULL)
	{
		if((now->numdot)<i)
		{
			//区画数が足りない場合はそのまま
		}
		else
		{
			now->lastdot=now->nextdot;//置き換え
		}
		now=now->next;
	}
}

void putin(YJ *now,LIST *margepri,LIST *marge,int asc,YJ *lastmpri,YJ *lastm[26])
{	//文字が足りないとき
	if(asc=='@')
	{
		if((*margepri).dom==NULL)//何もリストが連結されていないとき
		{
			(*margepri).dom=now;
			lastmpri=now;
			lastmpri->next=NULL;
		}
		else
		{
			lastmpri->next=now;
			lastmpri=now;
			lastmpri->next=NULL;
		}

	}//アルファベットの時
	else
	{
		asc=asc-97;//これでascは0~25になる
		if((marge[asc]).dom==NULL)//何もリストが連結されていないとき
		{
			(marge[asc]).dom=now;
			lastm[asc]=now;
			lastm[asc]->next=NULL;
		}
		else
		{
			lastm[asc]->next=now;
			lastm[asc]=now;
			lastm[asc]->next=NULL;
		}

	}

}

void joint(YJ *top,LIST *margepri,LIST *marge,YJ *lastmpri,YJ *lastm[26])
{
	int i;
	YJ *now;
	now=top;
	if(((*margepri).dom)!=NULL)//文字なしのところの処理
	{
		now->next=(*margepri).dom;
		now=lastmpri;
	}
	for(i=0;i<=25;i++)
	{
		if(((marge[i]).dom)!=NULL)
		{
			now->next=(marge[i]).dom;
			now=lastm[i];
		}

	}

}

void listmarge(YJ *top,LIST *margepri,LIST *margem,int i,int maxw,YJ *lastmpri,YJ *lastm[26])
{
	YJ *now,*temp;
	int j;
	int asc;
	int l;
	(void)i; // 未使用の警告避け

	for(j=maxw;j>=1;j--)
	{
		now=top;
		l=(now->lastdot)+j;
		while(now->next!=NULL)
		{	//文字が足りない時
			if(l>=(now->nextdot))
			{
				asc='@';
			}//大文字
			else if((65<=(now->word[l]))&&((now->word[l])<=90))
			{
				asc=(now->word[l])+32;
			}//小文字
			else if((97<=(now->word[l]))&&((now->word[l])<=122))
			{
				asc=now->word[l];
			}
			//marge配列に格納
			temp=now->next;//退避
			//putin(now,&margepri,margem,asc,lastmpri,lastm);
			putin(now,margepri,margem,asc,lastmpri,lastm);
			now=temp;//退避したやつ戻す
		}
		//この時点ですべての行はバケットソート用の配列にリストとして格納されているため、ここからまたtopから辿れるように戻す
		//joint(top,&margepri,margem,lastmpri,lastm);
		joint(top,margepri,margem,lastmpri,lastm);

		//デバッグ
		printf("\n\n");
		now=top;
		while(now->next!=NULL)
		{
			printf("%d,%s\n",now->numdot,now->word);
			now=now->next;
		}

	}	


}

//ソート用の関数
void sortlist(YJ *top)
{
	YJ *now;

	//とりあえずデバッグのために表示
	now=top;
	while(now->next!=NULL)
	{
		printf("%d,%s\n",now->numdot,now->word);
		now=now->next;
	}

	//ソート用のリスト
	LIST margepri;//@文字の時に収納される配列(@の時は文字不足)
	YJ *lastmpri;//ソート用のリストの最後の要素を指すポインタ
	LIST marge[26];//アルファベット用
	YJ *lastm[26];//ソート用のリストの最後の要素を指すポインタ(アルファベット用)
	//構造体のメンバのdomをNULLに初期化
	resetdom(&margepri,marge);
	lastmpri=NULL; // 未初期化の警告避け

	//各行の中のdotの数を見つける
	int maxdot=0;
	findmaxdot(top,&maxdot);

	printf("\n");
	//ここからdotで区切られた文字列ごとにソートをかけていく
	int i,j;
	int maxw=0;//現在の区画の中で最大の文字数
	for(i=maxdot;i>=0;i--)
	{
		now=top;
		//現在の区画でどの行の文字列が一番多いのかを特定,次のdot特定
		findmaxword(top,&maxw,i);

		//入れ替え
		listmarge(top,&margepri,marge,i,maxw,lastmpri,lastm);








		//置き換え
		setlastdot(top,i);
		printf("\n\n");
	}
	(void)j; // 未使用の警告避け

}



int main(int argc,char *argv[])
{

	YJ *top,*now;
	(void)argc; // 未使用の警告避け
	(void)now; // 未使用の警告避け

	top=makelist(argv[1]);

	if(top==NULL)
	{
		return -1;
	}

	sortlist(top);

	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#12

投稿記事 by chop.chop » 9年前

具体的には、
ある関数で宣言した構造体方のポインタの配列を、他の関数でも参照できるようにしたいのです。
バケットソートでアルファベットに対応した構造体型の配列に、別の構造体をリストとしてつなげ、そのすべてを連結する際に、すべての配列に一つづつリストの最終要素を指しているようなポインタを使いたいのです。

コード:

typedef struct yj
{
    struct yj *next;
}YJ;

//newyj()は省略

typedef struct list
{
    YJ *dom;//すでに上で定義した構造体型のポインタ
}LIST;

void a(LIST *marge,LIST *lastm//ここの書き方がわからない)
{
    YJ *now;
    now=newyj();
    (marge[0]).dom=now;//(marge[0])->dom=nowと書いたほうがいいのかわからない
    lastm[0]=now;
    lastm[0]->next=NULL;
}

void b()
{
    LIST marge[26];/
    YJ *lastm[26];//上の構造体型の配列が各々持ってるYJ型のリストの最後尾を指させたい.YJ型のポインタ、の配列
    a(marge,lastm//ここの書き方がわからない);
}

やりたいことはこんな感じになります

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 構造体を使ったマージソートのプログラム

#13

投稿記事 by みけCAT » 9年前

chop.chop さんが書きました:具体的には、
ある関数で宣言した構造体方のポインタの配列を、他の関数でも参照できるようにしたいのです。
バケットソートでアルファベットに対応した構造体型の配列に、別の構造体をリストとしてつなげ、そのすべてを連結する際に、すべての配列に一つづつリストの最終要素を指しているようなポインタを使いたいのです。
すいません、やっぱりよくわからないですが…
chop.chop さんが書きました:

コード:

typedef struct yj
{
    struct yj *next;
}YJ;

//newyj()は省略

typedef struct list
{
    YJ *dom;//すでに上で定義した構造体型のポインタ
}LIST;

void a(LIST *marge,LIST *lastm//ここの書き方がわからない)
{
    YJ *now;
    now=newyj();
    (marge[0]).dom=now;//(marge[0])->dom=nowと書いたほうがいいのかわからない
    lastm[0]=now;
    lastm[0]->next=NULL;
}

void b()
{
    LIST marge[26];/
    YJ *lastm[26];//上の構造体型の配列が各々持ってるYJ型のリストの最後尾を指させたい.YJ型のポインタ、の配列
    a(marge,lastm//ここの書き方がわからない);
}

やりたいことはこんな感じになります
素直に渡したい型を書けばいいと思います。
C言語では、「普通」に配列を渡すと参照渡しっぽくなります。

コード:

typedef struct yj
{
    struct yj *next;
}YJ;

//newyj()は省略

typedef struct list
{
    YJ *dom;//すでに上で定義した構造体型のポインタ
}LIST;

void a(LIST *marge,YJ *lastm[])
{
    YJ *now;
    now=newyj();
    // margeとlastmを事前に初期化してif(marge[0].dom!=NULL)marge[0].dom->next=lastm[0];みたいなことをしないと、
    // このaを複数回呼び出した時にメモリリークを起こすかもしれない
    // が、そもそも元のコードでも全くfreeを呼び出していないので、関係無かった。
    (marge[0]).dom=now;//(marge[0])->dom=nowと書いてはいけません。(hoge->fugaは(*hoge).fugaのような意味です。型を合わせましょう)
    lastm[0]=now;
    lastm[0]->next=NULL;
}

void b()
{
    LIST marge[26];//
    YJ *lastm[26];//上の構造体型の配列が各々持ってるYJ型のリストの最後尾を指させたい.YJ型のポインタ、の配列
    a(marge,lastm);
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#14

投稿記事 by chop.chop » 9年前

そのように書けばよかったのですね…すぐ試してみます

たぶんやりたいことはこちらを見ていただけるとわかりやすいかと思います。
http://www.dotup.org/uploda/www.dotup.org286085.png

ひとつ教えていただきたいのですが
みけCATさんにいただいた最後のコードの29行目の a(marge,lastm)
これはmargeのほうが配列の先頭アドレスを渡しているのは分かるのですが、lastmのほうはどうなっているのでしょうか?
YJ *lastm[26]として宣言したはずですから、これはYJ型のポインタが配列として宣言されているはずです
同じ関数内で使うなら、YJ型の構造体をnewyj()で確保したものを、lastm[0]=newyj()のようにしてやれば使えると思うのですが、lsatmだけの場合はどのような意味合いになるのでしょうか?

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 構造体を使ったマージソートのプログラム

#15

投稿記事 by みけCAT » 9年前

chop.chop さんが書きました:たぶんやりたいことはこちらを見ていただけるとわかりやすいかと思います。
http://www.dotup.org/uploda/www.dotup.org286085.png
なるほど、わかりました。
chop.chop さんが書きました:ひとつ教えていただきたいのですが
みけCATさんにいただいた最後のコードの29行目の a(marge,lastm)
これはmargeのほうが配列の先頭アドレスを渡しているのは分かるのですが、lastmのほうはどうなっているのでしょうか?
YJ *lastm[26]として宣言したはずですから、これはYJ型のポインタが配列として宣言されているはずです
同じ関数内で使うなら、YJ型の構造体をnewyj()で確保したものを、lastm[0]=newyj()のようにしてやれば使えると思うのですが、lsatmだけの場合はどのような意味合いになるのでしょうか?
lsatmは見当たりません。
lastmは書かれている通りの意味で、bのローカル変数はYJ型へのポインタを要素とする26要素の配列、aの仮引数はYJ型へのポインタへのポインタです。
宣言せず、本当にlastmまたはlsatmだけ書いた場合は、未定義の識別子としてコンパイルエラーになるかもしれません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#16

投稿記事 by chop.chop » 9年前

lsatmではなくlastmでした…

lastmは上のコードでいうと、関数aの仮引数としては、YJ型へのポインタへのポインタ、ということですが、これは参照渡しなのでしょうか?
自分が望む動作は、関数b内で既にとあるYJ型構造体(0とします)へのポインタとして機能している状態のlastmを、関数aに参照渡しした後関数a内でlastmを別の領域(1とします)を指させる、というものです。
この動作後は関数bでもlastmは(1)の方の領域を指していなければなりません。

もし関数b内での宣言が
YJ *lastm[26];
のようなポインタの配列ではなく単なるポインタ
YJ *lastm;
でしたらaを
a(LIST *marge,YJ **lastm)
としてやり、b内での記述は
a(marge,&lastm);
としてやればいいのですが、lastmはYJ型へのポインタの配列となっているため、どう書けばいいのか混乱している状態です。
margeの方はb内ではポインタではなく配列として宣言しているため、margeで先頭アドレスを渡す参照渡しになっているため関数a内でも指す領域を自由に変えれるとは思いますが。

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#17

投稿記事 by chop.chop » 9年前

とりあえず先ほどの書き方で参照渡しができているという前提で書いたコードです。
sort関数の中で、iがdotに区切られた区画を、jが区画内の文字列を参照するために使用されています。
putin関数では得られたascを元にmarge配列から辿れる各リストの最後尾に現在の構造体をつなげています。
joint関数ではmarge配列の各リストをmarge[0]からmarge[26]まで全て連結し、YJ 型のポインタを返すようになっています。

しかしjoint関数でコアダンプが起きてしまいます。

入力ファイル:hello
----------------------
abc.example.co.jp
abc.example.or.jp
info
example.JP
----------------------

./asort hello
の様に実行します


ps.
直接コードを貼り付けるとインデントがずれるのはなぜでしょうか…?
当方はvimで作業をしています
添付ファイル
asort.c
(7.23 KiB) ダウンロード数: 112 回

chop.chop
記事: 36
登録日時: 9年前

Re: 構造体を使ったマージソートのプログラム

#18

投稿記事 by chop.chop » 9年前

上で言うようなポインタの配列を参照渡しする方法がわからなかったため、それ無しで書いたコードです。
期待している動作はできましたが、これでは使用するメモリは少ないですが、実行時間はソート対象(n行のテキスト)に依存してO(n^2)かかってしまいます(全ての文字に対しtillnull関数で毎回先頭から最後尾までnow->next!=NULLまでたどっているため)
なのでできれば上で言うような動作をしたいのですが、とりあえずプログラム自体は完成したため、コードを載せておきます。
ぐだぐだなコードにも関わらず、アドバイスを下さったみけCATさん、ありがとうございます。
ポインタの配列を参照渡しする方法はまだ理解できていないため、どなたか教えていただけるとありがたいです。

./sort hello
の様に実行してください

入力ファイル:hello
-------------------------------
abc.example.co.jp
abc.example.or.jp
xy.example.JP
example.org
info
abc.example.com
example.co.jp
XY.Example.com
xy.example.ac.jp
-------------------------------

コード:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>

//構造体YJの定義
typedef struct yj
{
        int numdot;
        int lastdot;
        int nextdot;
        char word[256];
        struct yj *next;
}YJ;


//領域確保用の関数
YJ *newyj()
{
        YJ *p;
        p=(YJ *)malloc(sizeof(YJ));

        if(p==NULL)
        {
                fputs("malloc failedn\n",stderr);
                exit(1);
        }
        else
        {
                return p;
        }
}

//この構造体を配列にしてマージソートに使いたい
typedef struct list
{
        YJ *dom;//すでに上で定義した構造体型のポインタ
}LIST;

void printlist(YJ *top)
{
	printf("printlist-------\n");
	YJ *now;
	now=top;
        now=top;
        while(now->next!=NULL)
        {
                printf("%d,%s\n",now->numdot,now->word);
                now=now->next;
        }
	printf("/printlist--------\n");

}

YJ *tillnull(YJ *temp)
{
	YJ *now,*past;
	now=temp;
	printf("IN:%s\n",now->word);
	while(now->next!=NULL)
	{
		past=now;
		now=now->next;
	}
	now=past;
	printf("OUT:%s\n",now->word);
	return now;
}

YJ *makelist(char filename[256])
{

        FILE *fp;
        fp=fopen(filename,"r");//ファイル開く
        //エラー処理
        if(fp==NULL)
        {
                printf("file open failed(%s)\n",filename);
        }

        int c;//ファイルから読み取った文字を格納
        int i=0;
        YJ *top,*now,*new;
        //入力順にリスト作成開始
        new=newyj();
        now=new;
        top=now;

        now->numdot=0;//初期化
        now->lastdot=-1;//文字列の最初の1つ前ににdotがあると仮定
        while((c=fgetc(fp))!=EOF)
        {
                if(c!='\n')
                {
                        if(c=='.')
                        {
                                (now->numdot)++;
                        }
                        now->word[i]=c;
                        i++;
                }
                else if(c=='\n')
                {
                        now->word[i]='\0';
                        new=newyj();//新しい領域確保
                        now->next=new;//これにより、現在のnowの指す領域のnextは上で確保した領域となる
                        now=new;//次のループに向け、nowを上で確保した領域に再指定

                        i=0;
                        now->numdot=0;//初期化
                        now->lastdot=-1;//最初の1つ前にdotがあると仮定
                }
        }
        now->next=NULL;
        fclose(fp);
        return top;
}

void resetdom(LIST *marge)
{
	int i;
        for(i=0;i<27;i++)
        {
                (marge[i]).dom=NULL;
        }
}

void findmaxdot(YJ *top,int *maxdot)
{
        YJ *now;
        now=top;
        while(now->next!=NULL)
        {
                if(*maxdot<(now->numdot))
                {
                        *maxdot=now->numdot;
                }
                now=now->next;
        }
        printf("Maxdot:%d\n",*maxdot);
}

void findmaxword(YJ *top,int *maxw,int i)
{
        YJ *now;
        now=top;
        int l;
        int maxtemp;
	*maxw=0;
        while(now->next!=NULL)
        {
                maxtemp=0;
                l=(now->lastdot)+1;
                while(1)
                {
                        printf("%c",now->word[l]);
                        //行の区画数が不足の時
                        if((now->numdot)<i)
                        {
                                break;
                        }

                        //行の端ordotまで読んだ時
                        if(((now->word[l])=='\0')||((now->word[l])=='.'))
                        {
                                now->nextdot=l;//現在の区画の終了の添字
                                break;
                        }
                        else
                        {
                                maxtemp++;
                                l++;
                        }
                }
                printf("@");
                //大小比較
                if(maxtemp>(*maxw))
                {
                        (*maxw)=maxtemp;
                }
                now=now->next;
                printf("maxw:%d\n",*maxw);
        }
}

void setlastdot(YJ *top,int i)
{
        YJ *now;
        now=top;
        while(now->next!=NULL)
        {
                if((now->numdot)<i)
                {
                        //区画数が足りない場合はそのまま
                }
                else
                {
                        now->lastdot=now->nextdot;//置き換え
                }
                now=now->next;
        }
}

void putin(YJ *now,LIST *marge,YJ *lastm[27],int j)
{
	printf("putin----------------------------\n");
	int asc;
	int l;
	YJ *temp,*temp2,*new;
	while(now->next!=NULL)
	{
		l=(now->lastdot)+j;	
        	if(l>=(now->nextdot))
        	{
        		asc=96;
        	}//大文字
        	else if((65<=(now->word[l]))&&((now->word[l])<=90))
        	{
        		asc=(now->word[l])+32;
        	}//小文字
        	else if((97<=(now->word[l]))&&((now->word[l])<=122))
        	{
        		asc=now->word[l];
        	}
		printf("\n");
		printf("@@@%c@@@\n",asc);

		temp=now->next;//退避
		//バケットソート用配列に入れる操作---------------------------------------
	        asc=asc-96;//これでascは0~26になる
	        if((marge[asc]).dom==NULL)//何もリストが連結されていないとき
	        {
                        printf("-------------\n");
                        printf("%s\n",now->word);
	                (marge[asc]).dom=now;
			new=newyj();
			now->next=new;
			new->next=NULL;//構造として、最後に一つ余計なものをつける必要がある
                        printf("---------------\n");

	        }
                else
	        {
			printf("-------------\n");
			printf("%s\n",now->word);
			temp2=(marge[asc]).dom;
			temp2=tillnull(temp2);
			now->next=temp2->next;//最後に余計なものをつける
			temp2->next=now;//余計なものの一個前に滑りこませる感じ
			printf("---------------\n");
	        }
		//--------------------------------------------------------------------

		now=temp;
	}
	printf("/putin----------------------------\n");
}

YJ *joint(LIST *marge,YJ *lastm[27])
{
	printf("joint-----------------------------------\n");
	int i;
	int temp;
	YJ *now,*top;
	top=NULL;
	for(i=0;i<=26;i++)
	{
		if(((marge[i]).dom)!=NULL)//LISt型配列の最初のYJ型リストへのポインタがNULLでない場合
		{	
			//表示させる
			temp=i+96;//
			printf("joint:::%c\n",temp);

			if(top==NULL)//まだtopが見つかってない時
			{
				
				now=(marge[i]).dom;
				top=now;
			}
			else//もう以前のループでtopが見つかった時
			{
				now->next=(marge[i]).dom;
			}
			printf("@@@@@@@@@@@@@\n");
			now=tillnull(((marge[i]).dom));
			printf("/@@@@@@@@@@@@\n");
		}
	}
	now=now->next;
	now->next=NULL;
	return top;
        printf("/joint-----------------------------------\n");
}

void sort(char filename[256])
{
	YJ *top,*now;
	top=makelist(filename);
	now=top;
        //とりあえずデバッグのために表示
        printlist(top);

	//バケットソート用配列
        LIST marge[27];//アルファベット用
        YJ *lastm[27];//ソート用のリストの最後の要素を指すポインタ(アルファベット用)
	resetdom(marge);

	int maxdot=0;
	findmaxdot(top,&maxdot);

	printf("\n");
	int i,maxw;
	int j,asc;
	YJ *temp;
	for(i=maxdot;i>=0;i--)
	{
		findmaxword(top,&maxw,i);
		printf("maxw:%d\n",maxw);	
		for(j=maxw;j>=1;j--)
		{
			now=top;
			printf("i:%d,j:%d\n",i,j);
			putin(now,marge,lastm,j);//各配列にリストとしてつなげる
			top=joint(marge,lastm);//各配列からtopから辿れるように繋げなおす
			resetdom(marge);//各配列のYJ型リストへのポインタをNULLとする
			printlist(top);
		}
		printf("\n");
		setlastdot(top,i);
	}
}

int main(int argc,char *argv[])
{
	sort(argv[1]);
	return 0;
}

閉鎖

“C言語何でも質問掲示板” へ戻る