[C言語]単連結リストにおける着目ノードの操作

質問

http://www.bohyoh.com/Books/CalgoA/EX/ALGOEX0901.html

上の線形リストのプログラムにおいて、着目ノードを１個次にずらす操作と、１個前にずらす操作を追加したいのですが、単連結リストでは後者の実現は少しばかりややこしく、困っています。
おそらく先頭ノードから後続ノードへのポインタを辿って行って、着目ノードを探索すれば良いのでしょうが……。
尚、前者において着目ノードが末尾ノードだった場合、後者において着目ノードが先頭ノードだった場合は考えないものとします。

皆様にご教授頂けると幸いです。

/* 着目ノードを一個次のノードにする */
void NextCrnt(List *list)
{
if (list->crnt == NULL){
puts("着目要素はありません。");
}
else {
list->crnt = list->crnt->next;
}
}

回答No.7

Tacosan · ベストアンサー

「明白に質問者を置き去りにしている」としか思えないので「先頭ノードから後続ノードへのポインタを辿っていく」バージョンも書いてみる... けど, 本質的に「next が『着目しているノード』であるようなノード」をひたすら探すだけなので構造的には SearchNode と変わりません:
void PrevCrnt(List *list)
{
if (list->crnt == NULL) {
puts("着目要素はありません。");
} else if (list->crnt != list->head) {
Node *p = list->head;
while (p != NULL) {
if (p->next != list->crnt) {
list->crnt = p;
return;
}
p = p->next;
}
}
}
本当に正しいことまでは保証できないので確認はお願いしますね.

それにしても「crnt」はどうしても「クルント」って読んじゃうなぁ. こんな無理して縮めずとも「current」でいいのに. NO とか NAME とかも, シフト使えば... いやいや, こんなところであら捜ししてもしょうがないんだ....

で蛇足タイム (笑):
ウケ狙いで
#define defStruct(tag) typedef struct tag tag; struct tag
とかやると #3 の最初の 2行が
typedef struct Node Node;
struct Node {
から
defStruct(Node) {
に変わるのでちょっと見やすい... か?

祝 gets消滅 (謎)

回答No.8

LongSecret

>defStruct(Node) {

おお、なんとｗ
これはC++に近くなってますねｗ

では私は確認済みのやつを提供するために
自分のコードへの拡張、という形で示しますが

こんなの思いつきましたよ

「入れ替えなしで、numを逆順に表示する！」

void PrintAll_Reversed( CPNODE p ){
if ( !p ) return;
PrintAll_Reversed( p->next );
printf( "%d\r\n", p->num );
}

スタックを使ってprevポインタを疑似的に作り出す、って言う考え方です。

もちろん、ここまでくると
こいつは魔術の一種に近いんで、極力不必要に真似しないでくださいｗ
（もちろん、再帰が必要な構造だったら再帰は使うべきでしょうが、線形リストなら普通ループでかかないとスタック無駄に使っちまう危険があります。）

puts( "\r\n逆順表示\r\n" );
PrintAll_Reversed( head );

こんなコードで確認できるかと。

回答No.6

LongSecret

フムフム、そういうことですね
OKです。

＞struct __node
＞は危険です.

それなんですね
#3言われたとこで気づいたんですが
仮に「あの時点」までで、私が「完全に0から書いてたら」struct node_こうなった可能性が高いですが（後ろについてるのは基本だいじょぶですから）

なんでうっかりこうなってたかって言うと、「リンク先のコピペ」が原因だったんですよねｗ

元

typedef struct __node {
Data data; /* データ */
struct __node *next; /* 後続ノードへのポインタ */
} Node;

で、下のサンプルではint型一個あれば十分と思ったので
そこからさらに、後の拡張があった場合にアラインメント的に無駄が少なくなる可能性が高いであろう、となるように、配置逆にして（ポインタの方がサイズが大きくなる可能性高いと思うので）

typedef struct __node {
struct __node *next;
int num;
} Node;

こうなったわけですが

※なお、アラインメントについては
http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html
辺りを参照していただくとして

下のサンプルを仮に直すとしたら

typedef struct Node Node, *PNODE;
struct Node {
PNODE next;
int num;
};

ぐらいでよさそうって感じですね。（もっとも、10文字以内程度の差ぐらいですが）

なお、ポインタのポインタについてですが

もうちょっと詳しく言うと

普通に全体に特定の処理かけるだけとかなら、単なるポインタの方が簡単だし、表記上も処理上も無駄がない可能性高いですが

「挿入や削除、追加などをはじめとする、付け替えの時」にポインタのポインタ使うと非常にすっきりとして、便利な可能性が高いです。

回答No.5

Tacosan

そういえば #3 では本題について全く触れていなかったのでそっちについてちょっとだけ書いておこう.

#1 でも書かれていますが, 単方向リストを作るときに「ポインタのポインタ」を使うと便利なことがしばしばあります (これは 2文木でも同様). なので, 探索なども含めてすべて「ポインタのポインタ」をベースに関数を作っていくとプログラムが書きやすくなる傾向があります. たとえば, 現状探索関数は
Node *SearchNode(List *list, Data x, int equal(Data x, Data y))
{
Node *ptr = list->head;
/* 以下は略 */
}
で始まっているんだけど, これを
Node **pp = &list->head;
としちゃう (もちろん返り値も Node **) とあとがちょっとだけ楽かもしれません.

以下は蛇足:

まず, typedef では不完全型に別名をつけることもできます. なので, 構造体 Foo を定義しなくても
typedef struct Foo Bar;
は合法です.

さらに, 構造体タグ (もちろん共用体および列挙型のタグを含む) と「ふつ～の識別子」とは異なる名前空間 (≠ C++ の namespace) に属し, その間では同じ識別子を使っても問題ありません (ついでにいうとラベルもまた別の名前空間になる). なので
typedef struct Node Node;
struct Node {
Node *next;
int num;
};
typedef Node *PNode;
は文法的に正しいです (C++ でも正しい) し,
typedef struct __node {
struct __node* next;
int num;
} Node;
という typedef ができる以上
typedef struct Node Node;
typedef struct Node {
Node *next;
int num;
} *PNode;
も OK です. まあ, 現実的にはこうするくらいなら
typedef struct Node Node, *PNode;
struct Node {
Node *next;
int num;
};
(あるいは PNode next; とする) ですけどね.

あ, 今気づいた. #3 を書く時点では見えなかったんだけど, 「_+大文字」や「__」で始まる識別子はすべての用途において処理系に予約されているので
struct __node
は危険です.

回答No.4

LongSecret

＞typedef struct Node Node;
＞struct Node {
＞Node *next;
＞int num;
＞};
＞typedef Node *PNode;

なるほど、これもOKなんですねｗ
Cの深淵に対する理解度はまだまだあまっちょろいですね～ｗ（←自分に対して）

ついでに、Cではこれっておｋでしたっけ？
（うちんとこでは動くっぽいですが）

typedef struct Node Node;
typedef struct Node {
Node *next;
int num;
} *PNode;

んでもまぁ、C++なら、「メンバ関数抜き」にしても、さらに1行減って、いきなり

typedef struct Node {
Node *next;
int num;
} *PNode;

これぐらいのことが出来ちゃうし、ローカル変数の宣言位置はC99みたいに「ブロック先頭じゃなくてもいい」→ for(int i=0;i<NUM_;++i){～} とかC++03でも普通に可能

ですし、メンバ関数持てますし、テンプレートあって継承あってアクセス修飾子まであって、C++11も固まった、ということで

Cを使うなら、どうせなら「C++も読み書きできるようになる」ってことはやはりとてもお勧めですね。

回答No.3

Tacosan

どうせ typedef するなら, 構造体タグにも同じものを使えばいいんじゃないでしょうか＞#2.

typedef struct Node Node;
struct Node {
Node *next;
int num;
};
typedef Node *PNode;
でも動きますし.

回答No.2

LongSecret

そうですか。

プログラムってのは不必要な機能は書かない方がいいです（コンパイル時間も犠牲になる）
が、知的好奇心を満たすために
やってみるというのも面白いかもしれません。

ただ、Cの長いソース読み切るのは結構辛いので
もうちょっと機能が少ない（最後尾をさすポインタはないなど）バージョンを「別途0から書いて」みました。
（最近C++漬なので、Cだと出来ない表記が入っちゃってるかもしれませんが
てかやっぱCとC++ではC++の方が読みやすいと思うので、それをご希望される場合はそっちで書きなおせます。）

単方向の線形リストでは
実用的に前後のポインタの情報がいると便利と思われるのは
「挿入」
「順番入れ替え」
などなどぐらいなものですから

前者をInsert（先頭からNodeの「num」が昇順になるように挿入）
後者をPlacement_Reversed（逆順にポインタを総付け替え）

として、ポインタのポインタを有効活用しつつ実現してみました。

（教えてgooだとインデントがなくなるので余計読み辛いかもしれませんがｗ　コピペして正常に動いたら、その辺修正しつつ読み解いて見てください。どうにも分からない箇所あったら聞いてください）

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

typedef struct __node {
struct __node* next;
int num;
} Node;

typedef const Node* CPNODE;
typedef Node* PNODE;

int GetCount( CPNODE p ){
int i = 0;
for ( ; p ; p = p->next ) ++i;
return i;
}

void PrintAll( CPNODE p ){ for ( ; p ; p = p->next ) printf( "%d\r\n", p->num ); }

void Placement_Reversed( PNODE* head_ ){ //逆順に並び変える

PNODE p = *head_;
const int num_of_nodes = GetCount( p );
PNODE* pp = (PNODE*)malloc( sizeof(p) * num_of_nodes );

int i = 0;
for ( ; p ; p = p->next ) pp[i++] = p; //先に順番に入れておく.

//i == num_of_nodes; になってる

for ( ;i; head_ = &(*head_)->next ) *head_ = pp[--i]; //逆順につけかえ
pp[0]->next = NULL;

free( pp );

}

void Insert( PNODE const newnode, PNODE* pp ){
PNODE p;
for ( ; p = *pp ; pp = &p->next ){ if ( newnode->num <= p->num ) break; }
newnode->next = *pp;
*pp = newnode;
}

int main(void){

const int numbers[] = { 4, 3, 8, 6, 0, -1, 0 };

enum { NUM_ = sizeof(numbers) / sizeof( numbers[0] ) };
PNODE head = NULL, p;
Node nodes[NUM_];
int i;

for ( i = 0; i < NUM_ ; ++i ){
p = nodes + i;
p->next = NULL;
p->num = numbers[i];
Insert( p, &head );
}

PrintAll(head);

Placement_Reversed( &head );
puts( "\r\n順番入れ替え後\r\n" );
PrintAll(head);

getchar(); //一瞬で終わらないようにするためだけ

return 0;

}

回答No.1

LongSecret

（こうしてみるとCとC++（どっちもものすごく練られているコードと仮定して）では読みやすさに雲泥の差があるなぁ。柴田さん達のコードでこれですからね…まぁもうちょっと読みやすくは出来るだろうけども。あと構造体はポインタ渡しのが良いと思いますが、まぁそこはおいといて）

単方向連結リスト
って言うのは、通常一方向の操作だけで簡単に済むような場合に使うものです。

着目ノードの前後移動を自由に行いたいのならば、通常は双方向連結リスト(nextとprevをもつ）を使います。

ただし
よほどの場合で
単方向連結リストでごく稀にだけ
そうしたい場合は

＞おそらく先頭ノードから後続ノードへのポインタを辿って行って、着目ノードを探索すれば良いのでしょうが……。

そうすることでも出来ますし（スマートでない可能性は高い）
もう一個だけポインタあればいいのならもう一個用意すればできますし

ポインタのポインタを使えばちょー楽勝なこともありますし

よっぽど連続でごしゃごしゃいじる場合は
作業前に先にポインタ配列作っといてそっちに順番に移し替えたりしといて…とかでもできます。

もちろんそれぞれに一長一短ありますが

「単方向連結リストを使うのが適切な構造では」ほとんどの場合
ポインタ２つとか、ポインタポインタで十分解決できると思います。

具体的にはどういう用途がお望みですか？

お礼

回答ありがとうございます。
用途は特に想定していません。こういった場合双連結リストを使うべきなのは承知しておりますが、ひねくれた性分でして…。
授業で習ったプログラムをどうにかして弄くり回そうと、いろいろやってみたくなるんです。まぁ、テスト勉強も兼ねていますが。
ご提案いただいた方法でも試してみますね。