連結リスト 要素の入れ替え

質問

自分には、難しい内容なので、色々教えていただけると嬉しいです。

リスト構造で、データの入れ替え・ポインタの付け替えを行っているのですが、どこのサイトを見てもどれが、参考になるのか分かりませんでした。

例えば、宣言でgFront→a1→a2→a3→a4→a5→NULLのすでに連結されたリストがあります。
先頭には、ダミー（gFront）のセルがあり、そこからたどって入れ替えていくというものです。
a1からa5の中には、数字が入っているものとします。

a２とa5の入れ替えを行うと仮定して話します。
そして、a２をpreとして、a5をnewとして、preの一つ前をprepreとし、newの１つ前をprenewとして、ひとつ前のnextを調べてポインタの付け替えを行います。

4か所のポインタの付け替え後の結果を、gFront→a1→a5→a3→a4→a2→NULLとしたいです。
swapを使ったリストの中身入れ替えではなく、ポインタの付け替えでリスト自体の入れ替えを行いたいと考えています。

この付け替えの部分がいまいちプログラムの書き方と言いますか、よく理解できていないので、教えていただけないでしょうか？
文章だけでは、分かりにくいところが多々あるかとは思いますが、宜しくお願いいたします。

回答No.11

Tacosan

「入れ替え→表示」ということがしたい, って言われてもなぁ.
「入れ替え」ってことは, その対象が (複数) 存在するんだよね. その対象はどこで誰が指定するの? それがわからないとプログラムなんか組みようがありません.
これは #7 あたりで既に指摘されていて「あなたがどう思っているのか」が問われているんだけど, わかってる?

補足

どう思っているのかというと、
例えば、a2とa5の入れ替えならば、

a1->next=a5;
a5->pre=a1;
a5->next=a3;
a2->pre=a4;
a2->next=NULL;

このようにソースを書いてしまうと、

a2とa5の入れ替えしかできません。

これだと、入れ替え処理ごとにプログラムの
量が増えますよね？

入れ替え対象は、ソース上で指定しておきます。

入れ替え処理をkと仮定します。

---------------------------------------

k(a2,a5);
printf("入れ替え前：gFront→a1→a2→a3→a4→a5→NULL");
printf("入れ替え後：gFront→a1→a5→a3→a4→a2→NULL",a2,a5);

k(a1,a5);
printf("入れ替え前：gFront→a1→a5→a3→a4→a2→NULL");
printf("入れ替え後：gFront→a5→a1→a3→a4→a2→NULL",a1,a5);

k(a3,a4);
printf("入れ替え前：gFront→a1→a5→a3→a4→a2→NULL");
printf("入れ替え後：gFront→a5→a1→a4→a3→a2→NULL",a3,a4);

k(a2,a1);
printf("入れ替え前：gFront→a1→a5→a3→a4→a2→NULL");
printf("入れ替え後：gFront→a5→a2→a4→a3→a1→NULL",a2,a1);
・
・
・

-------------------------------------------

このように行っても、入れ替え処理の書き換え（変更）をしないで済むようにしたいんです。

プログラムの書き方は変ですが、伝えやすいイメージだと思うので、このようなプログラムを書いたことをお許しください・・・

回答No.10

asuncion

＞双方向リストとして考えないでも不可能なのでしょか？

今回の話は、単方向にしろ双方向にしろ、リスト構造を使うことが前提なのですよね？

リスト構造を使うからには、次のノードや前のノードを指すためのポインタを必ず使うことになります。
そういうポインタを使わずにリスト構造を使うことは、できません。

質問者さんが本当にしたいことは何なのか、よくわからなくなってきました。

補足

リスト構造は使用します。

最終的に求める結果は、

入れ替え→表示

さらに入れ替え→表示

さらに入れ替え→表示

さらに入れ替え→表示

さらに入れ替え→表示

終了としたいんです…

回答No.9

asuncion

＞ループで何回か処理を行いたいのですが、a1.prev=...といったやり方ではないやり方はありますでしょうか？

ポインタを付け替えるということは、双方向リスト上で、
付け替え対象となっているデータの前後を指すポインタ（prevとnext）を
別の値に変更する、ということです。

つまり、prevとnextにアクセスしないでポインタを付け替える方法は、ありません。

補足

双方向リストとして考えないでも不可能なのでしょか？

何かいい方法はないでしょうか？

回答No.8

asuncion

＞入れ替え(ポインタの付け替え)の処理を繰り返し行えるようにしたいんです。

もしかして、
「どれを入れ替えるかを手で入力して、入れ替えた結果を出力する」
ことを繰り返したいのでしょうか？

補足

手入力ではなく、プログラム上に記述し、例えば、

a1とa2
a3とa5
a4とa2
a1とa3
a2とa5

をそれぞれ入れ替えたいとします。
入れ替える回数をプログラム上で指定、もしくはなんらかの終了条件を入力して画面に表示したいんです。

回答No.7

asuncion

＞入れ替え(ポインタの付け替え)の処理を繰り返し行えるようにしたいんです。

繰り返した結果、最初の
＞gFront→a1→a2→a3→a4→a5→NULL
がどうなることを期待していますか？

また、どのポインタを入れ替えるかを、どのように指定するのですか？

補足

繰り返した結果を入れ替えごとに表示し、繰り返したいと考えています。

回答No.6

asuncion

＞ループで何回か処理を行いたい

何の処理を行ないたいのですか？

補足

入れ替え(ポインタの付け替え)の処理を繰り返し行えるようにしたいんです。

回答No.5

redfox63

struct cell {
　　int nData;
　　struct cell *prev;
　　struct cell *next;
};
といった具合の構造体でいいように思いますよ

a1ならば a1.prevがNULL、a1.nextが &a2
a2ならば a2.prevが&a1、a2.nextが &a3
a5ならば a5.prevが&a4、a2.nextが NULL
といった具合になっています

a2とa5の入れ替えならば
struct cell* temp;
temp = a2.prev;　　　// &a3(a3のポインタ)をtemp
a2.prev = a5.prev;　// &a4をa2のprevへ
a5.prev = temp;　　　// tempを a5のprev … つまりa3のポインタ
で a2,a5が指している前の要素の入れ替えができます
tmp = a2.next;
a2.next = a5.next;
a5.next = tmp;
で a2,a5が指している後ろの要素の入れ替えができます

補足

ループで何回か処理を行いたいのですが、a1.prev=...といったやり方ではないやり方はありますでしょうか？

回答No.4

asuncion

＞どうなっているとは、どういう事でしょうか？

当該の構造体の定義内容を見せてください、ということです。
struct 何とか、という部分がありますよね？
これで伝わりますか？

補足

typedef struct *cell{
struct cell *pre;/*入れ替え要素*/
struct cell *prepre;/*preの１つ前の要素*/
struct cell *new;/*入れ替え要素*/
struct cell *prenew;/*newの一つ前の要素*/
struct cell *next; /*次のcellへのポインタ*/
}LIST_CELL;
LIST_CELL *p1;

多分めちゃくちゃだと思います。
わけわからなかったら、無視してください・・・

回答No.3

osamuy

「ひとつ前のnext」が、リストの次要素を指し示す構造体メンバーのことなら、

1)prepreとprenewのnextを交換。
2)preとnewのnextを交換。

でいけるかと。

図にするとこんな感じ。
// 図を既に書いてみたけど分からないというなら、ごめんなさい。

補足

osamuyさん　回答ありがとうございます。
osamuyさんのように書いた図は、かなり書いていて、プログラムも書いているんですが、リストプログラムの記述の順番かコード自体が間違っていて、うまく動作しません。
入れ替え（ポインタの付け替え）なので、２つだけの処理じゃ足りないんじゃないでしょうか？；；
また、a1とa5の入れ替えをする場合、つながらないですよね？

回答No.2

asuncion

そもそも、当該の構造体の定義はどうなっているのですか？＞質問者さん

#1さんの回答は双方向リストを前提としています（メンバーpre, nextが存在）が、
その前提が崩れれば回答が成り立たなくなります。

補足

どうなっているとは、どういう事でしょうか？