線形リストのソートについて

質問

データ構造を線形リストとして、情報を管理するプログラムのソートについてです。
以下のプログラムはデータを入れ替えて、その後アドレスを入れ替えるようにしてソートを行っていますが、そうではなく線形リストなのでつなぎ替えるようにしてソートを行うプログラムを作成したいのですがわからないのでご教授をお願い致します。ソートは逐次決定で行ってます。
構造体の宣言として、nameとageとnextは氏名と年齢と次のポインタを指します。NAME_SORT、AGE_SORTはマクロです。

struct sortlist(struct PERSON *head) {
int menu;
struct PERSON person; /* 情報 */
struct PERSON move_person; /* 比較していく情報 */
struct PERSON work; /* 情報の一時的保存 */
struct PERSON temp; /* 作業用 */
struct PERSON temp_address; /* アドレス作業用 */
printf("ソート機能を選択：");
printf("%d:氏名\n",NAME_SORT);
printf("%d:年齢\n",AGE_SORT);
/* 交換処理 */
for(person = head; person -> next != NULL; person -> person -> next) {
work = person;
/* 交換データの探索 */
for(move_person = person -> next; move_person != NULL; move_person -> next) {
switch(menu) {
case NAME_SORT:
if(strcmp(work -> name, move_person -> name) > 0) {
work = move_person;
}
break;
case NAME_SORT:
if(work -> age > move_person -> age) {
work = move_person;
}
break;
default:
printf("機能以外が選択されました");
return head;
}
if(work != person) {
/* 情報の交換 */
temp = *person;
*person = *work;
*work = temp;
/* アドレスの交換 */;
temp_address = employee -> next;
person -> next = work -> next;
work -> next = temp_address;
}
}
}
}
printf(“ソート完了”);
}

回答No.6

BLUEPIXY · ベストアンサー

#5のようにいちいち先頭から検索してソートしてたんじゃ…と思ったので、
いったんポインタの配列にしてソートしてからリストを再構成する方法
----------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct person {
char *name;
int age;
struct person *next;
} PERSON ;

int listlen(PERSON *head){
int len=0;
PERSON *p;

for(p=head;p!=NULL;p=p->next)
len++;
return len;
}

void addlist(PERSON *head, PERSON *el){
//headが示すリストの最後に追加する
PERSON *p;

for(p=head;p->next!=NULL;p=p->next)
;
p->next=el;
}

void printlist(PERSON *head){
PERSON *p;

for(p=head;p!=NULL;p=p->next)
printf("氏名:%s\t年齢:%d\n", p->name, p->age);
}

#define NAME_SORT 1
#define AGE_SORT 2

int cmp1(const void *a, const void *b){
return (strcmp((*((PERSON**)a))->name, (*((PERSON**)b))->name));
}
int cmp2(const void *a, const void *b){
return ((*((PERSON**)a))->age - (*((PERSON**)b))->age);
}

void sortlist(PERSON **head) {
//リストを配列にしてソート、その結果でリストを再構成する
int menu=0;
int size;
int i;
PERSON **persons;
PERSON *p;

size=listlen(*head);
persons=(PERSON**)malloc(size*sizeof(PERSON*));
if(persons==NULL){
printf("メモリ不足のためソートできませんでした");
return ;
}
for(i=0,p=*head;p!=NULL;p=p->next)
persons[i++]=p; //ポインタの配列にする
redo:
printf("ソート機能を選択：\n");
printf("%d:氏名\n", NAME_SORT);
printf("%d:年齢\n", AGE_SORT);
printf("select:");
scanf("%d%*c", &menu);
if(menu != NAME_SORT && menu != AGE_SORT){
printf("機能以外が選択されました\n");
goto redo;
}
switch(menu){
case NAME_SORT:
qsort(persons, size, sizeof(PERSON*), cmp1);
break;
case AGE_SORT:
qsort(persons, size, sizeof(PERSON*), cmp2);
break;
}
*head=persons[0];//１つはデータがある？ホントに？
for(i=1;i<size;i++)
persons[i-1]->next=persons[i];
persons[size-1]->next=NULL;

free(persons);
printf("ソート完了\n");
}

void main(void){
PERSON *head;
PERSON a ={ "AKANE", 20, NULL };
PERSON b ={ "BLUE" , 25, NULL };
PERSON r ={ "RED" , 68, NULL };
PERSON g ={ "GREEN", 12, NULL };

head=&a;
addlist(head, &b);
addlist(head, &r);
addlist(head, &g);
printlist(head);//ソート前のリスト
sortlist(&head);//head自体が書き換わる可能性がある
printlist(head);
}

お礼

たびたびありがとうございます＾＾
こちらのほうも参考にさせて頂きます。
どうしたらよいのか困っていたんですが、本当に迅速かつ丁寧に対応して頂いて感謝致します。
こちらを参考にさせて頂き自分なりに考えてみます。
また、お願いします。

回答No.7

nofutureforyou

リストだと挿入ソートとかマージソートとかの方がいいんでないですかね。

お礼

回答ありがとうございます。
そうですね。挿入ソートやマージソートもあるんですが、自分がはじめに逐次決定でやったのでそのまま修正したかったんです。
また、挿入ソートやマージソートも勉強したいと思います。
ありがとうございます。

回答No.5

BLUEPIXY

とりあえず、文句を言っててもしょうがないので、サンプルを作ってみました。
（＃３の補足を見る前だったので、＃３の補足には合わせていません）
（他にもやりようがあるかもしれませんが、とりあえず動くもの）
----------------------------------------------------------------
#include <stdio.h>
#include <string.h>

typedef struct person {
char *name;
int age;
struct person *next;
} PERSON ;

void addlist(PERSON *head, PERSON *el){
//headが示すリストの最後に追加する
PERSON *p;

for(p=head;p->next!=NULL;p=p->next)
;
p->next=el;
}

void printlist(PERSON *head){
PERSON *p;

for(p=head;p!=NULL;p=p->next)
printf("氏名:%s\t年齢:%d\n", p->name, p->age);
}

#define NAME_SORT 1
#define AGE_SORT 2

int cmp(PERSON *a, PERSON *b, int kind){
switch(kind){
case NAME_SORT:
return (strcmp(a->name, b->name));
case AGE_SORT:
return (a->age > b->age);
}
return 0;//DUMMY
}

void swap(PERSON **head, PERSON *a, PERSON *b){
//headからのリストでａとｂを入れ替える
//リストの並びはａが先でｂが後
//head自体が書き換わる可能性がある
PERSON *p;

//リストの中のnext情報の書き換え
for(p=*head;p->next!=NULL;p=p->next){
if(p->next==b){
p->next=a;
break;
}
}
if(*head!=a){
for(p=*head;p->next!=NULL;p=p->next){
if(p->next==a){
p->next=b;
break;
}
}
} else {
//headの交換
*head=b;
}
//リンクの交換
p=a->next;
a->next=b->next;
b->next=p;
}

void sortlist(PERSON **head) {
int menu=0;
PERSON *person;
PERSON *move_person; /* 交換候補 */
PERSON *work;

redo:
printf("ソート機能を選択：\n");
printf("%d:氏名\n", NAME_SORT);
printf("%d:年齢\n", AGE_SORT);
printf("select:");
scanf("%d%*c", &menu);
if(menu != NAME_SORT && menu != AGE_SORT){
printf("機能以外が選択されました");
goto redo;
}

for(person=*head; person->next!=NULL; person=person->next) {
work=person;
for(move_person=person->next;move_person!= NULL;move_person=move_person->next){
if(cmp(work, move_person, menu)>0){
work=move_person;
}
}
if(work != person) {
/* 交換 */
swap(head, person, work);
person=*head;//リストの構成が変化したのでやり直し
}
}
printf("ソート完了\n");
}

void main(void){
PERSON *head;
PERSON a ={ "AKANE", 20, NULL };
PERSON b ={ "BLUE" , 25, NULL };
PERSON r ={ "RED" , 68, NULL };
PERSON g ={ "GREEN", 12, NULL };

head=&a;
addlist(head, &b);
addlist(head, &r);
addlist(head, &g);
printlist(head);//ソート前のリスト
sortlist(&head);//head自体が書き換わる可能性がある
printlist(head);
}

お礼

わざわざサンプルをお付けして頂いてありがとうございます。
是非参考にさせていただきます。
ありがとうございました。

補足

たびたび失礼します。
あと僕が書いたプログラムのソート関数の部分で構造体ポインタの宣言するところですべてにおいて＊をつけ忘れておりましたペコリ(o_ _)ｏ))
間違いが多くてすみません。

回答No.4

BLUEPIXY

#2>コンパイル実行自体には問題がない
うそ！
目で見ただけでも、ポインタとポインタでないものがごっちゃになってる
例えば、
＞struct sortlist(struct PERSON *head) {
＞for(person = head; person -> next != NULL; person -> person -> next) {
で、
＞person = head
ポインタじゃないpersonにポインタであるheadを入れてる
＞person -> person -> next
参照できないはず
menuに値が設定されていない。
諸々
まともなコンパイラでまともにコンパイルできないはず

お礼

返信ありがとうございます。
確かにそうですね。ポインタじゃないのにポインタであるもの入れてありますね。
プログラム自体に問題がありますね＞＜すみませんです。

補足

あとすいません。
person = person -> nextの間違えでした＞＜
打ち間違えまいたぺこ <(＿ ＿)>

回答No.3

nk2

PERSON構造体の中身を見せろ。
お前の打ちかけソースより、元々もソースを見せろ。
返値にstructってなんだよ。

お礼

返信ありがとうございます。
すいません。質問の文字数が限られててソースが全部書けなかったのです。
なので絞って書きました。
今から補足のとこに書かさせていただきます。

補足

ソースが長すぎて収まりきらないので、メインとソート部分のみ書かさせてもらいました。
また、EMPLOYEE構造体に書き直しました。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* メニュー番号 */
#define REGIST 1/* 登録 */
#define LIST 2/* 一覧表示 */
#define DELETE 3/* 削除 */
#define SORT 4/* ソート */
/* 終了メニュー */
#define YES 1/* 終了する */
/* ソート番号 */
#define NAME_SORT 1/* 名前順 */
#define AGE_SORT 2/* 年齢順 */
#define ADDRESS_SORT 3/* 住所順 */
/* 配列の要素数 */
#define NAME_LENGTH 20/* 氏名 */
#define SECTION_LENGTH 10/* 所属 */
#define ADDRESS_LENGTH 255/* 住所 */

struct EMPLOYEE { /* 社員情報 */
int number; /* 登録番号 */
char name[NAME_LENGTH]; /* 氏名 */
int age; /* 年齢 */
char section[SECTION_LENGTH]; /* 所属 */
char address[ADDRESS_LENGTH]; /* 住所 */
struct EMPLOYEE * next; /* 次の情報 */
};
struct EMPLOYEE * list_regist(struct EMPLOYEE *, int *);
void list_print(struct EMPLOYEE *);
struct EMPLOYEE * list_delete(struct EMPLOYEE *);
struct EMPLOYEE * list_sort(struct EMPLOYEE *);
void list_free(struct EMPLOYEE *);

void main() {
struct EMPLOYEE * head; /* 社員情報 */
int menu; /* 入力された項目 */
int flag = 1; /* 継続フラグ */
int number = 1; /* 登録番号 */

head = NULL;

/* 処理を実行 */
while (flag) {
/* 行う処理の入力 */
printf("\n%d: 登録 %d: 一覧表示 %d: 削除 %d: ソート\n", REGIST, LIST, DELETE, SORT);
printf("（終了の場合は上の数字にない数字を押してEnter）\n");
printf("該当項目の入力 -> ");
scanf("%d", & menu);
/* 入力された文字から処理を判別 */
switch (menu) {
case REGIST:
head = list_regist(head, & number);
break;
case LIST:
list_print(head);
break;
case DELETE:
head = list_delete(head);
break;
case SORT:
head = list_sort(head);
break;
default:
printf("\n終了しますか？\n");
printf("%d: 終了する\n", YES);
scanf("%d", & menu);

/* 本当に終了するかの確認 */
if (menu == YES) {
flag = 0;
}
}
printf("\n");
}
printf("flag: %d\n", flag);
list_free(head);
}

/* ソーと関数 */
struct list_sort(struct EMPLOYEE *head) {
int menu;
struct ENPLOYEE employee; /* 情報 */
struct ENPLOYEE move_employee; /* 比較していく情報 */
struct ENPLOYEE work; /* 情報の一時的保存 */
struct ENPLOYEE temp; /* 作業用 */
struct ENPLOYEE temp_address; /* アドレス作業用 */

printf("ソート機能を選択：");
printf("%d:氏名\n",NAME_SORT);
printf("%d:年齢\n",AGE_SORT);
printf("%d:住所\n",ADDRESS_SORT);
/* 交換処理 */
for(employee = head; employee -> next != NULL; employee -> employee -> next) {
work = employee;
/* 交換データの探索 */
for(move_employee = employee -> next; move_employee != NULL; move_employee -> next) {

switch(menu) {
case NAME_SORT:
if(strcmp(work -> name, move_employee -> name) > 0) {
work = move_employee;
}
break;
case NAME_SORT:
if(work -> age > move_employee -> age) {
work = move_employee;
}
break;
case ADDRESS_SORT:
if(strcmp(work -> address, move_employee -> address > 0) {
work = move_employee;
}
break;
default:
printf("機能以外が選択されました");
return head;
}
if(work != employee) {
/* 情報の交換 */
temp = *employee;
*employee = *work;
*work = temp
/* アドレスの交換 */;
temp_address = employee -> next;
employee -> next = work -> next
work -> next = temp_address;
}
}
}
}
printf(“ソート完了”);
}

回答No.2

BLUEPIXY

これ、動いているプログラムじゃないよね？

お礼

返信ありがとうございます。

補足

機能としては、登録、一覧表示、削除、ソートを行うようにしています。
そこでソートでのプログラムで、コンパイル実行自体には問題がないのですが、このプログラムを単方向リストとなるかといったら、中身のデータを入れ替えて、次にアドレスを入れ替えてるだけなので、データ数が多くなればその分不都合であると思われるので、修正したいのですが、思いつかなくて・・・。
なので投稿してみたんですが＾＾

回答No.1

Trick--x--

employeeってナンダ？

一気に全部やろうとすると絶対に混乱する。
ので、問題を切り分けよう。
この場合だと……リストの並び替えだけするプログラムを書いてみてはどうだろう。

お礼

返信ありがとうございます。

補足

すいません。
employeeじゃなくてpersonでした。
リストの並び替えだけするプログラム・・・
並び替えは情報の交換のところでできると思うんですけどだめですか？？？