リスト

質問

アドレス：aa bb cc
head　→　３　→　１　→　２　→　NULL
　　　　　　　　　↓(1)
head　→　１　→　３　→　２　→　NULL
↓(2)
head　→　１　→　２　→　３　→　NULL

図がわかりにくいですが、リスト構造で上記のように昇順で交換を行うソート（逐次決定）処理を行う場合（この場合３つしかないので隣接交換にみえますが逐次のほうです）に、

(1)の処理では…３の要素と１の要素を交換するので、headの次のアドレスは１のアドレス（bb）にし、１の次のアドレスは３のアドレス（aa）にし、３の次のアドレスは２のアドレス（cc）

(2)の処理では…３の要素と２の要素を交換するので、１の次のアドレスは２のアドレス（cc）にし、２の次のアドレスは３のアドレス（aa）、３の次のアドレスはNULL

となりますよね？？
この(1)と(2)の処理を行うプログラムを作成したいのですがどなたかご教授をお願い致します。
またデータが多くなっても対応できるようにしたいです。
前日に下記のほうにも投稿しましたが、勉強不足のためあまり理解できなかったのでもう一度投稿しました。よろしくお願いします。
「http://okwave.jp/kotaeru.php3?q=1876998

回答No.4

BLUEPIXY · ベストアンサー

ＵＲＬの＃５のswapがそういう処理です。
＃１で言われているように、交換する要素同士だけでなく、要素の前の要素のリンクを変更する必要があるので、いちいち先頭から探して変更する処理をしています。
＃１で言われているようにすれば、リンク自体のつながりはそのままで、要素へのポインタを保持するようにしておけば、要素へのポインタを交換するだけで交換できます。
（つまり要素は、別に確保しておいて、リンクではその実体へのアドレスだけを保持するということです。）
（＃６でポインタでソートしているみたいなものです）
リストの構造を変えていいなら、そっちの方が楽です。
もしくは、
単方向リストでなくて、双方向リストにすると、ちょっと面倒が減ります。
一応＃５の解説をちょろっとしておくと
リンク（次のリンク）というような表記で質問文のリストを表すと
３（１）→１（２）→２（ＮＵＬＬ）
となります、＃５のｓｗａｐでは
３と１を交換する場合、まず、後にでてくる１を指している部分をリストから検索します。
３（１）、１（２）、２（ＮＵＬＬ）
３（１）でみつかりますので、これを３に置き換えます。
×３（３）、１（２）→２（ＮＵＬＬ）
×は、リンクが切れてしまっていることを表す
この場合、３は、ヘッダだったので、３を次に指しているリストはないので、ヘッダが指しているものを１にします。
１と３がそれぞれ指しているものを交換します。
するとリストは
１（３）→３（２）→２（ＮＵＬＬ）
になるので交換ができました。
この状態で３と２を交換する時は
同じ手順で
まず、２を指しているものを探します
３で見つかるので、３に変更します。
１（３）、３（３）、２（ＮＵＬＬ）
次に、３を指しているものを探します
１で見つかるので、２に変更します。
１（２）、３（３）、２（ＮＵＬＬ）
３と２のリンクを交換します
１（２）、３（ＮＵＬＬ）、２（３）
１（２）→２（３）→３（ＮＵＬＬ）
となって交換終了

お礼

回答のほうどうもありがとうございます。
丁寧に解説して頂けたこと感謝致します。
本日といっても昨日ですが、URLの＃５のプログラムのほう読ませて頂きました。ソートを分けてやればいいんですね。
でも元々のプログラムをBLUEPIXYさんがやったように書き換えようと考えていたんですが、僕の知識不足のためできませんでした＞＜
もう一度よく読みなおし、考え直してみます。
どうもありがとうございました。

補足

双方向リストというのは名前しか聞いたことがなかったので、解説して頂きありがたいです。
双方向は名前通り双方向に辿ることができるので、こちらのほうが面倒はなくなりますね。
でも今回は単方向でやる課題なんです＞＜
どちらもできるようになりたいですね。

回答No.5

nk2

これは新しいリストを構成しているので、
”要素数0または1のリストはいかなるときも整列済みのリストである”
ということを利用し、初期化した要素数1のリストに挿入ソートでソートしながらリストを構成する方法を提示します。
これの面白い所は外部からソートする必要がないことです。
いつどこでソートのオーバーヘッドがかかるのかが分からないことが難点ですが、
常に整列済みのリストが取得できるため、プログラムは簡潔になります。
//----------------------------------------------------------
#include <iostream>
#include <string>
using namespace std;
//----------------------------------------------------------
typedef struct element
{
　int v;
　struct element* next;
}E,Element;
//----------------------------------------------------------
class MyList
{
　E* Head;
　E* Current;

　bool IsNotFirst;

　public:
　　MyList(E &e):IsNotFirst(false){ Head = &e; }

　　add(E &A)
　　{
　　　E* P = Head;
　　　E* Back;

　　　while(P)
　　　{
　　　　if(P->v > A.v) break;

　　　　Back = P;
　　　　P = P->next;
　　　}

　　　if(Back)
　　　{
　　　　Back->next = &A;
　　　　A.next = P;
　　　}

　　　Current = Head;
　　}

　　bool hasNext()
　　{
　　　return Current && Current->next;
　　}

　　E* next()
　　{
　　　if(!IsNotFirst)
　　　{
　　　　IsNotFirst = true;
　　　　return Current;
　　　}

　　　E* Result = Current->next;
　　　Current = Current->next;
　　　return Result;
　　}
};
//----------------------------------------------------------
int main(int argc,char* arg[])
{
　E A = {1,NULL};
　E B = {2,NULL};
　E C = {3,NULL};
　E D = {4,NULL};

　MyList L(A);

　L.add(C);
　L.add(D);
　L.add(B);

　while(L.hasNext())
　　cout << L.next()->v << endl;

　return 0;
}
//----------------------------------------------------------

お礼

回答ありがとうございます。
挿入ソートで行う方法もあるのですね。
ご丁寧に解説やソースを掲示していただき感謝致します。
是非参考にさせて頂きます。
ソートについていろいろ勉強させて頂いてるので、どれも扱えるようになりたいです。
どうもありがとうございました。

回答No.3

επιστημη（@episteme）

> 要素そのものではなく、要素へのポインタ・・・
> 私が勉強不足なものであまりイメージがつきません。

[ご参考]
要素のポインタを交換することによる単純選択ソート
コメントはあえて一切つけません/メモリ開放していません。

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

typedef struct link_t {
　struct link_t* next;
　int* data;
} link;

void sort(link* l) {
　link* begin = l;
　while ( begin ) {
　　link* min_position = begin;
　　int* min_value = begin->data;
　　link* cursor = begin->next;
　　while ( cursor ) {
　　　if ( *min_value > *cursor->data ) {
　　　　min_position = cursor;
　　　　min_value = cursor->data;
　　　}
　　　cursor = cursor->next;
　　}
　　min_position->data = begin->data;
　　begin->data = min_value;
　　begin = begin->next;
　}
}

int main() {
　link* head = 0;
　int i;
　for ( i = 0; i < 10; ++i ) {
　　link* node = (link*)malloc(sizeof(link));
　　int* data = (int*)malloc(sizeof(int));
　　*data = rand() % 10;
　　node->data = data;
　　node->next = head;
　　head = node;
　}
　sort(head);

　{
　　link* pos;
　　for ( pos = head; pos; pos = pos->next ) {
　　　printf("%d ", *pos->data);
　　}
　}
　return 0;
}

お礼

回答ありがとうございます。
選択ソートで行ってるんですね。
是非参考にさせていただきます。
ありがとうございますm(._.*)mペコッ

回答No.2

επιστημη（@episteme）

> 要素そのものではなく、要素へのポインタ・・・
> 私が勉強不足なものであまりイメージがつきません。

だとすれば、ポインタに関して勉強不足です。
リストを自在に扱うには時期尚早ではないでしょうか。
この場で解説を試みても"その場しのぎ"に終わるように思います。

お礼

回答ありがとうございます。
次の要素へのポインタを利用するということでいいんですよね？
構造体ポインタを利用して、それを入れ替えてからアドレスを入れ替えるという方法でやったのですがこれがあまりよくない方法と言われまして。
それをどう修正しようかと悩んでいたので再度今回のようにやりたくて投稿させていただきました。
ありがとうございました。考えてみます。

回答No.1

επιστημη（@episteme）

正直面倒です。
2つのlinkを交換するにはそれぞれの手前のlinkを書き換えなくてはなりません。

struct link {
struct link* next;
void* data;
};
のように、linkが保持するのが要素そのものでなく、
要素へのポインタであれば、それを交換するだけで交換できます。
この方が楽じゃありませんか?

お礼

ご回答ありがとうございます。
面倒ですか＞＜
要素そのものではなく、要素へのポインタ・・・
私が勉強不足なものであまりイメージがつきません。
もう少しヒントを頂けると幸いです。
すみませんがお願いします。