学生番号，英語，数学，物理という順で一行にかかれたデータを読み込み，各

質問

学生番号，英語，数学，物理という順で一行にかかれたデータを読み込み，各自の合計点が大きい順にクイックソートで並び替えて，出力するプログラム

全体の流れは、
　　　　　　　・先頭を示すポインタを準備。
　　　　　　　・標準入力からデータをリンクドリスとに読み込む。
　　　　　　　・構造体に対するポインタを使ってデータをソートする。
　　　　　　　　->一覧を保持する「ポインタへのポインタ」の一覧を作る。
　　　　　　　　->データへのポインタのリストを作る。
　　　　　　　　->クイックソートで並び替える。
　　　　　　　・構造体に対するポインタを使って、データを表示する

このプログラムで、構造体に対するポインタを使ってクイックソートをするプログラムがわかりません。構造体に対するポインタを使って、left,right,pivotやwhile,ifの条件などをどう表現したらよいかが悩みの種です。
配列を使ったクイックソートのプログラムは出来ているので参考にしていますが。うまくいかない状況です。

どなたか教えていただけないでしょうか。

以下参考にしている配列を使ったクイックソートのプログラムの一部です。

void sort(int array[],int left, int right)
{
int pivot=0,i=0,j=0;
i=left;
j=right;
pivot=array[(left+right)/2];
while(1) {
while(array[i]<pivot) {
i++;
}
while (pivot<array[j]) {
j--;
}
if(i>=j) {
break;
}
swap(array,i,j);
i++;
j--;
}
if(left < i-1) {
sort(array,j+1,right);
}
if(j+1<right) {
sort(array,j+1,right);
}
}

void quickSort(int array[], int size)
{
int left=0, right=0;
left=0;
right=size-1;
sort(array,left,right);
return 1;
}

よろしくお願いします。

回答No.3

麻野 なぎ（@AsanoNagi）

そうですね。

sort=(Student **)malloc((count+1)*sizeof(Student *));
sortTop=sort;
tmp=top->next;
while (tmp!=NULL) {
*sort = tmp;
tmp=tmp->next;
sort++;
}
sort=NULL; // これ不要
sort=sortTop;

の直後で、sort は、size が、count の配列としても記述できます。
Student *sort[count]; と宣言されているように使用できます。
これで、配列版でも使えますね。

回答No.2

麻野 なぎ（@AsanoNagi）

構造体がたとえば、struct seiseki_type; なら、

void sort(int array[],int left, int right)

が、

void sort(struct seiseki_type *array[],int left, int right)

になるだけ。
当然、array[] とデータをやりとりする、povot も、strcut seiseki_type *

あと、未定義の関数、swap() も int 版が、

void swap(int a[], int i, int j)
{
int wk = a[i];
a[i] = a[j];
a[j] = wk;
}

とかになっているだろうから、同じく、
void swap(struct seiseki_type *a[], int i, int j)
{
struct seiseki_type *wk = a[i];
a[i] = a[j];
a[j] = wk;
}

でOK。

ここまでで、コンパイルは通ると思う。
ただし、このままでは、「ポインタの大小」でソートされてしまうから、要素の大小判定をしている部分を書き直す必要がある。

while(array[i]<pivot)
while (pivot<array[j])

の２カ所。（そのほかの場所はそのままで良いのはなぜか考えてみてください）

ここは、たとえば、
int lessThan(struct seiseki_type *a, struct seiseki_type *b)
{
int aSum = a->eigo + a->suugaku + a->butsuri;
int bSum = b->eigo + b->suugaku + b->butsuri;
return (aSum < bSum);
}
とすれば、それぞれ、

while (lessThan(array[i], pivot))
while (lessThan(pivot, array[j]))

と書き直し可能。

こんな感じです。

そうすると、比較すべきものの型を正しく合わせて、大小比較の部分を妥当な形で定義すれば、関数の中身は本質的には変わらないというところが見えてくると思います。

補足

詳しい回答ありがとうございます。とても参考にはなったのですが、問題のクイックソートのプログラムの記述では配列を使わないみたいです。

以下が問題のプログラムの全体で、バブルソートをクイックソートに変えて作りたいのです。

#include <stdio.h>
#include <stdlib.h>
struct student {
int number;
int math;
int eng;
int phy;
int sum;
struct student *next;
};
typedef struct student Student;
void swap(Student **x, Student **y);
void bubble(Student **t);
int main(void)
{

Student *top,**sort,**sortTop,*tmp;
char line[80];
int count=0;

top=(Student *)malloc(sizeof(Student));
top->number=-1; top->math=-1; top->eng=-1; top->phy=-1; top->sum=-1;
top->next=NULL;

while (fgets(line,sizeof(line),stdin)!=NULL) {
tmp=(Student *)malloc(sizeof(Student));
if (tmp==NULL) {
fprintf(stderr,"No more memory...\n");
return 1;
}
count++;
tmp->next = top->next;
top->next = tmp;
sscanf(line,"%d,%d,%d,%d",
&(tmp->number),
&(tmp->eng),
&(tmp->math),
&(tmp->phy));
tmp->sum = (tmp->eng) + (tmp->math) + (tmp->phy);
}

sort=(Student **)malloc((count+1)*sizeof(Student *));
sortTop=sort;
tmp=top->next;
while (tmp!=NULL) {
*sort = tmp;
tmp=tmp->next;
sort++;
}
sort=NULL;
sort=sortTop;

bubble(sort);

sort=sortTop;
while (*sort!=NULL) {
fprintf(stdout,"%8d\t%3d\t%3d\t%3d\t%3d\n",
(*sort)->number,
(*sort)->eng,
(*sort)->math,
(*sort)->phy,
(*sort)->sum);
sort++;
}
return 0;
}
void bubble(Student **sort)
{
Student **t1, **t2;
t1=sort;
while(*t1!=NULL) {
t2=sort;
while(*t2!=NULL) {
if(((*t1)->sum) > (((*t2)->sum))) {
swap(t1,t2);
}
t2++;
}
t1++;
}

return;
}

void swap(Student **x, Student **y)
{
Student *tmp;
tmp = *x;
*x = *y;
*y = tmp;
return;
}

回答No.1

t_nojiri

まず、ソートする単位は学生番号，英語，数学，物理という順でデータの入った構造体なんですよね？

で、ソート単位は合計値なんですよね？

普通、qsort()関数は
http://www.bohyoh.com/CandCPP/FAQ/FAQ00047.html
こんな感じなので、合計値の要素を構造体に含んで、そのまま比較関数作るのが簡単だと思いますけど。

補足

回答ありがとうございます。

学生番号、英語、数学、物理という順ではいった構造体です。
ソート単位は合計値で、
tmp->sum = (tmp->eng) + (tmp->math) + (tmp->phy);
このように合計値を求めています。

このプログラムではqsort()関数は使わずに、自分でクイックソートの関数をquickSort()として定義するので、その関数の記述で悩んでいます。