単行リストのソートのプログラムについて

質問

単行リストのソースでわからなくなったので質問させていただきます。
#include<stdio.h>

//----------------------------------------------------------
// InitBanpei
// 番兵の初期化
//----------------------------------------------------------
// input: struct pNode* pNode //番兵のアドレス
//----------------------------------------------------------

void InitBanpei(struct node* pStartNode,struct node* pEndNode);
//----------------------------------------------------------
// IsBanpei
// 番兵チェック
//----------------------------------------------------------
// input: struct pNode* pNode //番兵のアドレス
// out : true //成功
// false //失敗
//----------------------------------------------------------

int IsBanpei(struct node* pNode);
//構造体
struct node
{
char name[30];
int kokugo;
int suugaku;
int eigo;
int goukei;

struct node* pNext;
};
int main(void)
{
FILE* fp;
struct node useStart,useEnd;
struct node *p,*j,*max,*a;
int stich=0;

char work[256];

InitBanpei(&useStart,&useEnd);
IsBanpei(&useStart);
IsBanpei(&useEnd);
fp=fopen("data.txt","r");

if(fp==NULL)
{
printf("ファイルを開けません\n");
return 0;
}
while(feof(fp)==0)
{
fgets(work,256,fp);
stich++;
}
stich--;

printf("%d\n",stich);
if(stich==0)
{
printf("件数は0です\n");
return 0;
}
fclose(fp);
fp=fopen("data.txt","r");

if(fp==NULL)
{
printf("ファイルを開けません\n");
return 0;
}

j=NULL;
for(int i=0;i<stich;i++)
{

a=new struct node;
if(a==NULL)
{
printf("メモリが確保できません\n");
return 0;
}
fscanf(fp,"%s %d %d %d ",&(a->name),&(a->kokugo),&(a->suugaku),&(a->eigo));
a->goukei=a->kokugo+a->suugaku+a->eigo;
a->pNext=j;
j=a;

}
useStart.pNext=j;
max=&useStart;
p=max->pNext;
while(max->pNext!=NULL)
{
j=p;

while(j->pNext!=NULL)
{
if(max->goukei< j->goukei)
{
max=j->pNext;
p=j;
}
j=j->pNext;
}

p->pNext=max->pNext;
max->pNext=useStart.pNext;
max=max->pNext;
}
a=useStart.pNext;
while(a->pNext!=NULL)
{
printf("%7s %03d %3d %3d %3d点\n ",a->name,
a->kokugo,a->suugaku,
a->eigo,a->goukei);
a=a->pNext;
}
}
//----------------------------------------------------------
// InitBanpei
// 番兵の初期化
//----------------------------------------------------------
// input: struct pNode* pNode //番兵のアドレス
//----------------------------
//------------------------------

void InitBanpei(struct node* pStartNode,struct node* pEndNode)
{

pStartNode->pNext=pEndNode;
pEndNode->pNext=NULL;
}

//----------------------------------------------------------
// IsBanpei
// 番兵チェック
//----------------------------------------------------------
// input: struct pNode* pNode //番兵のアドレス
// out : true //成功
// false //失敗
//----------------------------------------------------------
int IsBanpei(struct node* pNode)
{
if( pNode->pNext!=NULL)
{
return -1;
}
return 0;
}
のソースなのですが、単行リストを使って大きい順に並び替えをしたいのですがうまくできません。どこを直せばいいのでしょうか？分かる方いらしたらソースを書いてくださると助かります。

回答No.7

prophetok · ベストアンサー

参考までに、単方向リストのまま、バブルソートするサンプルプログラムを作ってみた。
これと見比べれば、自分のコードのどこがまずいのか分かると思うけど。

#include<stdio.h>
struct Node
{
int point;
Node* next;
};

int main(void)
{
Node a,b,c,d;
Node* start;
start = &a;
a.point=0;
a.next=&b;
b.point=10;
b.next=&c;
c.point=20;
c.next=&d;
d.point=15;
d.next=NULL;

Node *p = start;
while(1)
{
int swap=0;
Node *prev = NULL;
while( p )
{
Node* now=p;
Node* next=p->next;
if( next && now->point < next->point )
{
swap=1;
now->next=next->next;
if( prev )
{
prev->next=next;
next->next=now;
}
else
{
start=next;
start->next=now;
}
}
prev=p;
p=p->next;
}
p=start;
if( !swap )
break;
}
p = start;
while( p )
{
printf( "%d\n", p->point );
p=p->next;
}
}

お礼

なんとか出来るようになりました。回答ありがとうございました！

回答No.6

prophetok

ソートは、基本的に比較と要素並び替えの繰り返しです。
リストの場合、要素並び替えとは、要素の削除と挿入になります。
単方向リストの場合、自分の後への挿入は簡単ですが、自分の削除と自分の前への挿入は、簡単ではありません。
理由は分かりますよね、操作が必要な自分の前のノードを知るには、先頭から調べる必要があるからです。
この処理が、まったくないので、#1でソートとリストは理解していますか？と聞いたのです。
どういう意図で単方向リストでソートさせる課題なのかよく分かりませんが、もし自分がやるとしたらノードポインタの配列を作ってqsortで並び替え、リンクを張り直します。
qsortのようなライブラリを使わないという制限があっても、いったんノードポインタの配列を作ってソートするほうが、簡単で効率的でしょう。

お礼

回答ありがとうございます。単方向リストで難しいと言うことでしょうか？先頭から調べたのですがこれではだめということでしょうか？
a=p;
max=a;
j=a;
while(j->pNext!=NULL)
{
if(max->goukei<j->pNext->goukei)
{
a=j;
max=j->pNext;
}
j=j->pNext;
}
　　　　　・
　　　　　・　
　　　　　・　
}のaのところなのですが・・・

回答No.5

prophetok

自分の書いたコードが、どのようにしてソートしているのか、言葉で説明できますか？

お礼

回答ありがとうございます。はい。拙いですけど、
1.PがNULLになるまで繰り返して
2.a=p,j=a,max
3.jがNULLまで繰り返す。
4.if(max->goukei<j->pNext->goukei)
5.maxよりj->pNextのほうが大きい場合、a=j;max=j->pNext；
6.j=j->pNext
7.3を繰り返す
8.maxとaとがｐ、ｐ重ねるといけないのでif(p!=a && p!=max && p->pNext!=a && p->pNext!=max)
9.c=>pNext; a->pNext>pNext;max=useStart.pNext;useStart.pNext=max
10.if(p!=a && p!=max && p->pNext!=a && p->pNext!=max)でない場合
11.if(p->pNext==max || p->pNext==a) の場合c=p>pNext->pNext;a->pNext=max->pNext;max->pNext;max->pNext=NULL;max-Next=useStart.pNext;useStart.pNext=max;
12.cをｐに代入
13.1に戻る
です。

回答No.4

Tacosan

#2 に
しょせんは連結リストなので, 絵を描いてひたすら「ここでこうなってこれがあ～なって...」と追っていけば, たぶんそのうちわかるだろう.
と書いておいたんだけどやってみましたか?
たぶん, 何パターンか試してみれば「動作がおかしい」ことだけは分かるはず. 少なくとも, 「C のインタプリタになったつもり」で雑念を払って丹念にコードを追っていけば分かります.
手元でちょろちょろ実験して怪しいところは見つけたんだけど.... ごめん, どう直していいかわからないや. とりあえず場所だけ言うと
・a = p->pNext;
・最後の p = p->pNext;
の 2つは「このままではだめ」です.

お礼

書いてみました。これでも結構直したと思うのですが、
//テキストファイル
No1 90 81 95
104さん 5 64 63
No9 58 100 73
No3 77 79 95
No4 77 90 82
No8 74 70 89
No7 60 100 77
No6 78 67 99
No2 74 86 96

while(IsBanpei(p)!=NULL)
{
a=p;
max=a;
j=a;
while(j->pNext!=NULL)
{
if(max->goukei<j->pNext->goukei)
{
a=j;
max=j->pNext;
}
j=j->pNext;
}
if(p!=a && p!=max && p->pNext!=a && p->pNext!=max)
{
c=p->pNext;
a->pNext=max->pNext;
max->pNext=NULL;
max->pNext=useStart.pNext;
useStart.pNext=max;

}
else
{
if(p->pNext==max || p->pNext==a)
{
c=p->pNext->pNext;
a->pNext=max->pNext;
max->pNext=NULL;
max->pNext=useStart.pNext;
useStart.pNext=max;

}
}
p=c;
}
と変えてみたのですが、
この
while(j->pNext!=NULL)
{
if(max->goukei<j->pNext->goukei)
{
a=j;
max=j->pNext;
}
j=j->pNext;
}
のところが繰り返してブレークポイントでやっていると、
No6 78 67 99
No7 60 100 77
No8 74 70 89
No4 77 90 82
No3 77 79 95
No9 58 100 73
104さん 5 64 63
No1 90 81 95
　　　　　　　・
　　　　　　　・
　　　　　　　・
と繰り返されされるのですが、なぜこいうう結果になるのでしょうか？

回答No.3

prophetok

まず、頭でコードを追っかけて、自分の方針通りコーディングされいるかを確かめる。しつこいぐらいコメントをつけるのも吉。
間違いないことが分かったら、デバッガでステップ実行し、
・方針通り動かない
・方針通りうごくけど、実行結果がおかしい
前者なら、方針通り動くようコーディングしなおす
後者なら、方針が間違っているので、再検討
もちろん、どの実行結果が正しいかどうか判断できるのは大前提
これらを繰り返せば、ちゃんと動作するプログラムになるはず。

その他アドバイス
変数名は、長くてもいいから何を表しているのか明確に
>struct node *p,*j,*max,*a;
jが構造体のポインタ変数なんてのは、プロの世界ではあり得ない。

#2の方もアドバイスしているとおり
行数のカウントなんかも全くの無駄

せっかく定義したIsBanpei()
使ってあげようよ。（コールしてるけど、無意味なコールだよね）

基本が分かっていれば、極簡単な課題なので、自分でやってみましょう。

回答No.2

Tacosan

そう, その辺一帯が怪しい. 怪しいが, 残念ながら「どこがどうおかしくてどう直せばいいのか」をなかなか言いにくい. まあ, しょせんは連結リストなので, 絵を描いてひたすら「ここでこうなってこれがあ～なって...」と追っていけば, たぶんそのうちわかるだろう.
1点だけ挙げておくと,
if(max->goukei< j->goukei)
はおかしい.
はっきり言って「動作には影響ないんだけどプログラムの表現としては怪しい」ところがいくつも見受けられる. っつ～か, 連結リストを使ってるのになんで「行数を数えている」の?
あと, 1つ言わせてもらうと「うまくいかない」といわれてもあなた以外には「何がどうなっているので『うまくいかない』のか」が分からないんだよね. だから, #1 でも言われているんだけど
・どのようなデータを与えたときに
・どのような出力を期待して
・実際の出力がどうであったのか
ということもきちんと書いてほしい. このくらいの問題ならいいんだけど, 「実はプログラムは正しい結果を出しているんだけど『それが正しい』と認識できていない」ということも考えられるので.

お礼

回答ありがとうございます。テストの点をファイルを読み込んで、それを構造体に入れて大きい順に並び替えたいんですけど、一位と二位を繰り返していて終了しません。どこがいけないのでしょうか？後、
p=&useStart;
while(p->pNext!=NULL)
{
a=p->pNext;
max=p->pNext;
j=p->pNext;
while(j->pNext!=NULL)
{
if(max->goukei<j->pNext->goukei)
{
a=j;
max=j->pNext;
}
j=j->pNext;
}
a->pNext=max->pNext;
max->pNext=useStart.pNext;
useStart.pNext=max;
p=p->pNext;
}
は間違いで、
p=&useStart;
while(p->pNext!=NULL)
{
a=p->pNext;
max=p->pNext;
j=p->pNext;
while(j->pNext!=NULL)
{
if(max->goukei<j->pNext->goukei)
{
a=j;
max=j->pNext;
}
j=j->pNext;
}
a->pNext=max->pNext;
max->pNext=useStart.pNext;
useStart.pNext=max;
p=p->pNext;
}
です。

回答No.1

prophetok

単行リストって何？
初めて聞くタームなんだけど、単方向リストの間違い？

うまくいかないって、どこをどうしたのに、うまくできないのか。
そこを追加して、具体的に質問しなよ。
基本的な処理なので、ソートとリストが理解できていれば、簡単な問題ですよ。
まずは、ソートとリストは理解できていますか？

お礼

回答ありがとうございます。
単方向リストの間違いでした。
リストとソートはわかっているつもりなのですが・・・
p=max->pNext;
while(max->pNext!=NULL)
{
j=p;

while(j->pNext!=NULL)
{
if(max->goukei< j->goukei)
{
max=j->pNext;
p=j;
}
j=j->pNext;
}

p->pNext=max->pNext;
max->pNext=useStart.pNext;
max=max->pNext;
のところだと思うのですが、この辺りがおかしいと思うのですがよくわかりません。ご教授おねがいします。