単方向リストの交換

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
mrte

単方向リストの交換

#1

投稿記事 by mrte » 4年前

リスト前半分と後ろ半分の要素を交換する関数halfchangeを完成させたいのですが、
考え方が分かりません。どなたかサンプルと解説をお願いしたいです。
ひな形は既に指定されています。

コード:

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

struct node{
    char element;
    struct node *next;
};

struct node *initlist() {    //リストの初期化
    struct node *n;
    n = (struct node *)malloc(sizeof(struct node *));
    n->next = NULL;
    return n;
}

void insert(struct node *p, char x) {  //要素の追加
    struct node *n;
    n = (struct node *)malloc(sizeof(struct node *));
    n->next = NULL;
    n->element = x;
    while(p->next != NULL){p = p->next; }
    p->next = n;
}

void printlist(struct node *p) {
    p = p->next;
    while (p) {
        putchar(p->element);
        p = p->next;
    }
    putchar('\n');
}

void halfchange(struct node *p) {   //ここが分からないです

}


int main(int argc, char *argv[]) {
    struct node *list, *head;
    char *p;

    if (argc<2)
        exit(-1);

    list = initlist();
    p = argv[1];
    for (; *p; p++) {
        insert(list, *p);
    }

    halfchange(list);
    printlist(list);

    for (; list; ) {
        head = list;
        list = list->next;
        free(head);
    }
    return 0;
}

例;
12345→34512
programing→amingprogr

かめのこにょこにょこ

Re: 単方向リストの交換

#2

投稿記事 by かめのこにょこにょこ » 4年前

アイデアとしては
・リストを半分に分けてしまう
・分けたリストの後半部分の最後と前半部分の先頭をくっつける
とするのが手っ取り早いと思われます。

そのために
・リストの先頭、中間、末尾をさすnode*型変数
が用意できればかなり解答に近づけると思います。

スマホ環境でコードが打ちづらいので、コードが必要であれば返信ください。(その場合若干対応に時間かかります

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 単方向リストの交換

#3

投稿記事 by みけCAT » 4年前

かめのこにょこにょこ さんが書きました:
4年前
・リストの先頭、中間、末尾をさすnode*型変数
さらにヒントとして、最初は先頭を指しているnode*型変数a, bがあるとき、
「aを2回進めてbを1回進める」を繰り返せば、
aが末尾を指す時にbは中間を指しますね。
※何も考えず常に2回進めようとしてしまうと、末尾から飛び出してしまって危険なことがあるので注意
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

mrte

Re: 単方向リストの交換

#4

投稿記事 by mrte » 4年前

3つの変数を用意し繋ぎかえることで無事解決しました。
アドバイスありがとうございました!

かずま

Re: 単方向リストの交換

#5

投稿記事 by かずま » 4年前

mrte さんが書きました:
4年前
3つの変数を用意し繋ぎかえることで無事解決しました。
フォーラム(掲示板)ルールにあるように解決したコードを見せてください。
文字が 1文字の場合にも対応できていますか?

Math

Re: 単方向リストの交換

#6

投稿記事 by Math » 4年前

a, b のデータを交換するとき 作業用( temporary:一時的な )に 3つ目の temp を用意し
① a を temp に退避
② a,b を交換
③ b に temp を代入
が基本アルゴリズムですいよね。

かずま

Re: 単方向リストの交換

#7

投稿記事 by かずま » 4年前

Math さんが書きました:
4年前
a, b のデータを交換するとき 作業用( temporary:一時的な )に 3つ目の temp を用意し
① a を temp に退避
② a,b を交換
③ b に temp を代入
が基本アルゴリズムですいよね。
質問にある halfchange のコードを書いてみましたか?
コードも書かずに頓珍漢なことをいうのはやめてください。

質問は「リストの交換」であって、「データの交換」ではありません。
ポインタの付け替えになります。

データの個数が偶数の場合は、交換する個数が同数なので
データの交換でできないこともありませんが、
データの個数が奇数の場合は、とても面倒なことになります。

Math

Re: 単方向リストの交換

#8

投稿記事 by Math » 4年前

ん?
交換のアルゴリズムだよ
わかってならコード書いてあげたら
コードがすべてをかたるよ

Math

Re: 単方向リストの交換

#9

投稿記事 by Math » 4年前

リスト構造は何度もこたえてきたが これはリストの構造の問題かい

Math

Re: 単方向リストの交換

#10

投稿記事 by Math » 4年前

何の目的に使うんだろうこんなもの?
そこから知りたい

Math

Re: 単方向リストの交換

#11

投稿記事 by Math » 4年前

質問者様のコードは

コード:

main.c
main.c(16): error C3873: '0x3000': この文字を識別子の最初の文字にすることはできません
main.c(17): error C2065: ' ': 定義されていない識別子です。
main.c(17): error C2143: 構文エラー: ';' が '型' の前にありません。
となるから全角スペースがあるね

本当にためしたのかね

mrte

Re: 単方向リストの交換

#12

投稿記事 by mrte » 4年前

これは学校の授業の課題です。
解決したコードを載せ忘れていたので載せますね。

コード:

void halfchange(struct node *p) {
   struct node *head, *mid, *tail;
   int i = 0,j = 0;
   head = p;
   tail = p;
   for(i=0;tail->next != NULL;i++){tail = tail->next;}
   int k = i/2;
   mid = p;
   for(j=0;j<k;j++){mid = mid->next;}
   tail->next = head->next;
   head->next = mid->next;
   mid->next = NULL;
}

Math

Re: 単方向リストの交換

#13

投稿記事 by Math » 4年前

全角スペースを取り除き完成コードを入れると 動きました。(^^;

コード:

C:\19\19c\c2017>cl /TC main.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.21.27702.2 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

main.c
Microsoft (R) Incremental Linker Version 14.21.27702.2
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:main.exe
main.obj

C:\19\19c\c2017>dir main.exe
 ドライブ C のボリューム ラベルがありません。
 ボリューム シリアル番号は 7813-6100 です

 C:\19\19c\c2017 のディレクトリ

2019/06/29  19:41            96,768 main.exe
               1 個のファイル              96,768 バイト
               0 個のディレクトリ  95,188,013,056 バイトの空き領域

C:\19\19c\c2017>main.exe

C:\19\19c\c2017>pause
続行するには何かキーを押してください . . .
C:\19\19c\c2017>main.exe abcdefgh
efghabcd

C:\19\19c\c2017>

かずま

Re: 単方向リストの交換

#14

投稿記事 by かずま » 4年前

mrte さんが書きました:
4年前
解決したコードを載せ忘れていたので載せますね。
データが 1文字の場合には対応していませんね。

私なら次のように書きます。

コード:

void halfchange(struct node *p)
{
	if (p->next == NULL || p->next->next == NULL) return;
	struct node *q = p, *r = p;
	while (r->next) {
		r = r->next;
		if (r->next == NULL) break;
		r = r->next;
		q = q->next;
	}
	r->next = p->next;
	p->next = q->next;
	q->next = NULL;
}

かずま

Re: 単方向リストの交換

#15

投稿記事 by かずま » 4年前

「リストの交換」ではなく「データの交換」で実装すると
とても面倒になります。

コード:

void halfchange(struct node *p)
{
	if (!p->next || !p->next->next) return;
	struct node *q = p, *r = p;
	int n = 0;
	while (r->next) {
		r = r->next, n++;
		if (r->next == NULL) break;
		r = r->next, n++;
		q = q->next;
	}
	if (n % 1) {  // n は奇数
		n /= 2;
		char *t = malloc(n);  // 前半部分のデータの退避場所を確保
		r = p;
		for (int i = 0; i < n; i++)   // 前半部分のデータの退避
			r = r->next, t[i] = r->element;
		for (int i = 0; i <= n; i++)  // 後半部分を前半部分にコピー
			p = p->next, r = r->next, p->element = r->element;
		for (int i = 0; i < n; i++)   // 退避場所から後半部分にコピー
			p = p->next, p->element = t[i];
		free(t);
	}
	else {  // n は偶数
		while (q->next) {
			p = p->next, q = q->next;
			char t;                   // データの交換
			t = p->element, p->element = q->element, q->element = t;
		}
	}
}
ところで、次のコードが書けますか?

コード:

#include <stdio.h>

void swap(char s[], int n, int m)
{
	// 長さ n の文字列の左 m 文字と右(n-m)文字を交換する。
	// 補助関数を用意し、それを呼び出してもよい。
	// ただし malloc は使用しない。
}

int main(void)
{
	char s[] = "abcdefghijklmnopqrstuvwxyz";
	puts(s);
	swap(s, 26, 3);
	puts(s);  // "defghijklmnopqrstuvwxyzabc" と表示される
}

かずま

Re: 単方向リストの交換

#16

投稿記事 by かずま » 4年前

かずま さんが書きました:
4年前
「リストの交換」ではなく「データの交換」で実装すると
とても面倒になります。

コード:

	if (n % 1) {  // n は奇数
すみません。バグがありました。
if (n % 2) { または if (n & 1) { に訂正してください。

最初 if (n & 1) { と書いていたのですが、ビット演算は
分かりにくいだろうと考えて投稿時に % に書き換えてしまいました。
バグのままだと、12345 が 34512 ではなく 34521 になります。
なお、奇数偶数に分けなくても、奇数の方法だけでも処理できます。

だれもバグを指摘してくれないのは、皆さんあまり関心がないのでしょうね。
かずま さんが書きました:
4年前
ところで、次のコードが書けますか?

コード:

void swap(char s[], int n, int m)
{
	// 長さ n の文字列の左 m 文字と右(n-m)文字を交換する。
	// 補助関数を用意し、それを呼び出してもよい。
	// ただし malloc は使用しない。
}
面白い問題だと思うんですが、誰もやってみないのでしょうか?

アバター
usao
記事: 1887
登録日時: 11年前

Re: 単方向リストの交換

#17

投稿記事 by usao » 4年前

オフトピック
> 面白い問題だと思うんですが、誰もやってみないのでしょうか?

「面白い」とは何か?ってところが個人で違うでしょうし…
言わば「縛りプレイ」的なパズルですよね,コレ.

あえてごちゃごちゃとバグりそうな(あるいはバグっててもすぐにはわからないかもしれないような)処理を考えることを面白いと感じるかどうか.

私は頭使うの嫌いなタイプだから
「え? 配列内の並び替えをインプレースで…?」

「できらぁ!」

結果:バブルソート的なしょぼいコード

とかなっちゃうなぁ.

かずま

Re: 単方向リストの交換

#18

投稿記事 by かずま » 4年前

左の m文字と 右の (n-m)文字を交換するのは、
1文字ずつの左ローテートを m回実行すれば実現できます。
ローテートは、s[0] の値を退避し、残りを左にシフトし、
退避していた s[0] を s[n-1] にコピーすることです。
右側の方が短いときは、(n-m)回右ローテートすればよいでしょう。

コード:

void swap(char s[], int n, int m)
{
	if (m < n - m)
		while (--m >= 0) {
			char t = s[0];
			for (int i = 1; i < n; i++) s[i-1] = s[i];
			s[n-1] = t;
		}
	else 
		for (m = n - m; --m >= 0; ) {
			char t = s[n-1];
			for (int i = n; --i >= 0; ) s[i] = s[i-1];
			s[0] = t;
		}
}
でも、これは O(n2) のアルゴリズムで、あまりよくありません
swap("abcdefghijklmnopqrstuvwxyz", 26, 13); だと遅いです。

そこで私は、各文字の移動が 1回だけで済むやり方を考えてみました。
s[0] を退避し、s[0] に s[m] をコピー、s[m] に s[m*2] をコピー、
s[ i] = s[j]; の j が n以上になったら j -= n; で戻します。

このやり方は、n と m が互いに素の場合は、うまくいくんですが、
そうでない場合は、一部だけで循環し、移動が起こらない部分が残ります。
そこで、n と m の最小公倍数を求めておいて、その回数だけずらして
実行することで解決しました。

コード:

int gcd(int a, int b)
{
	int r;
	while (r = a % b) a = b, b = r;
	return b;
}

void swap(char s[], int n, int m)
{
	if (m == 0 || m == n) return;
	int g = gcd(n, m);
	for (int b = 0; b < g; b++) {
		char t = s[b];
		int i = b, k = b + n - m;
		do {
			int j = i + m;
			if (j >= n) j -= n;
			s[i] = s[j];
			i = j;
		} while (i != k);
		s[i] = t;
	}
}
ところが、この問題の解答は次のようなものでした。

コード:

void reverse(char s[], int n)
{
	char t;
	for (int m = 0; m < --n; m++)
		t = s[m], s[m] = s[n], s[n] = t;
}

void swap3(char s[], int n, int m)
{
	reverse(s, m);
	reverse(s + m, n - m);
	reverse(s, n);
}
驚きました。移動回数は多いのに速いのです。

「珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造」
Jon Bentley著 Programming Pearls Second Edition に載っています。
2014年に丸善出版から再発売されたものが 3672円になっていますが、
2000年にピアソンエデュケーションから出たものが中古で約1000円で買えます。
私はこれを持っています。

Second Edition ではないものの訳本「プログラム設計の着想」なら
中古で 500円程度で買えます。

かずま

Re: 単方向リストの交換

#19

投稿記事 by かずま » 4年前

かずま さんが書きました:
4年前
swap("abcdefghijklmnopqrstuvwxyz", 26, 13); だと遅いです。
char s[] = "abcdefghijklmnopqrstuvwxyz";
swap(s, 26, 13);
です。

アバター
usao
記事: 1887
登録日時: 11年前

Re: 単方向リストの交換

#20

投稿記事 by usao » 4年前

オフトピック
なるほど,最後のswap3の方法はinteresting

かずま

Re: 単方向リストの交換

#21

投稿記事 by かずま » 4年前

かずま さんが書きました:
4年前
そこで、n と m の最小公倍数を求めておいて、その回数だけずらして
すみません。最大公約数の間違いでした。
コードは間違っていません。

返信

“C言語何でも質問掲示板” へ戻る