ページ 1 / 1
単方向リストの交換
Posted: 2019年6月29日(土) 00:59
by mrte
リスト前半分と後ろ半分の要素を交換する関数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: 単方向リストの交換
Posted: 2019年6月29日(土) 01:23
by かめのこにょこにょこ
アイデアとしては
・リストを半分に分けてしまう
・分けたリストの後半部分の最後と前半部分の先頭をくっつける
とするのが手っ取り早いと思われます。
そのために
・リストの先頭、中間、末尾をさすnode*型変数
が用意できればかなり解答に近づけると思います。
スマホ環境でコードが打ちづらいので、コードが必要であれば返信ください。(その場合若干対応に時間かかります
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 03:03
by みけCAT
かめのこにょこにょこ さんが書きました: ↑4年前
・リストの先頭、中間、末尾をさすnode*型変数
さらにヒントとして、最初は先頭を指しているnode*型変数a, bがあるとき、
「aを2回進めてbを1回進める」を繰り返せば、
aが末尾を指す時にbは中間を指しますね。
※何も考えず常に2回進めようとしてしまうと、末尾から飛び出してしまって危険なことがあるので注意
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 08:58
by mrte
3つの変数を用意し繋ぎかえることで無事解決しました。
アドバイスありがとうございました!
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 09:11
by かずま
mrte さんが書きました: ↑4年前
3つの変数を用意し繋ぎかえることで無事解決しました。
フォーラム(掲示板)ルールにあるように解決したコードを見せてください。
文字が 1文字の場合にも対応できていますか?
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 13:04
by Math
a, b のデータを交換するとき 作業用( temporary:一時的な )に 3つ目の temp を用意し
① a を temp に退避
② a,b を交換
③ b に temp を代入
が基本アルゴリズムですいよね。
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 16:06
by かずま
Math さんが書きました: ↑4年前
a, b のデータを交換するとき 作業用( temporary:一時的な )に 3つ目の temp を用意し
① a を temp に退避
② a,b を交換
③ b に temp を代入
が基本アルゴリズムですいよね。
質問にある halfchange のコードを書いてみましたか?
コードも書かずに頓珍漢なことをいうのはやめてください。
質問は「リストの交換」であって、「データの交換」ではありません。
ポインタの付け替えになります。
データの個数が偶数の場合は、交換する個数が同数なので
データの交換でできないこともありませんが、
データの個数が奇数の場合は、とても面倒なことになります。
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 18:39
by Math
ん?
交換のアルゴリズムだよ
わかってならコード書いてあげたら
コードがすべてをかたるよ
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 18:45
by Math
リスト構造は何度もこたえてきたが これはリストの構造の問題かい
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 18:49
by Math
何の目的に使うんだろうこんなもの?
そこから知りたい
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 19:15
by Math
質問者様のコードは
コード:
main.c
main.c(16): error C3873: '0x3000': この文字を識別子の最初の文字にすることはできません
main.c(17): error C2065: ' ': 定義されていない識別子です。
main.c(17): error C2143: 構文エラー: ';' が '型' の前にありません。
となるから全角スペースがあるね
本当にためしたのかね
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 19:27
by mrte
これは学校の授業の課題です。
解決したコードを載せ忘れていたので載せますね。
コード:
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;
}
Re: 単方向リストの交換
Posted: 2019年6月29日(土) 19:47
by Math
全角スペースを取り除き完成コードを入れると 動きました。(^^;
コード:
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: 単方向リストの交換
Posted: 2019年6月29日(土) 19:50
by かずま
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: 単方向リストの交換
Posted: 2019年6月30日(日) 12:29
by かずま
「リストの交換」ではなく「データの交換」で実装すると
とても面倒になります。
コード:
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: 単方向リストの交換
Posted: 2019年6月30日(日) 19:39
by かずま
かずま さんが書きました: ↑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 は使用しない。
}
面白い問題だと思うんですが、誰もやってみないのでしょうか?
Re: 単方向リストの交換
Posted: 2019年7月01日(月) 10:56
by usao
オフトピック
> 面白い問題だと思うんですが、誰もやってみないのでしょうか?
「面白い」とは何か?ってところが個人で違うでしょうし…
言わば「縛りプレイ」的なパズルですよね,コレ.
あえてごちゃごちゃとバグりそうな(あるいはバグっててもすぐにはわからないかもしれないような)処理を考えることを面白いと感じるかどうか.
私は頭使うの嫌いなタイプだから
「え? 配列内の並び替えをインプレースで…?」
↓
「できらぁ!」
↓
結果:バブルソート的なしょぼいコード
とかなっちゃうなぁ.
Re: 単方向リストの交換
Posted: 2019年7月02日(火) 10:12
by かずま
左の 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(n
2) のアルゴリズムで、あまりよくありません
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: 単方向リストの交換
Posted: 2019年7月02日(火) 10:36
by かずま
かずま さんが書きました: ↑4年前
swap("abcdefghijklmnopqrstuvwxyz", 26, 13); だと遅いです。
char s[] = "abcdefghijklmnopqrstuvwxyz";
swap(s, 26, 13);
です。
Re: 単方向リストの交換
Posted: 2019年7月02日(火) 12:12
by usao
オフトピック
なるほど,最後のswap3の方法はinteresting
Re: 単方向リストの交換
Posted: 2019年7月02日(火) 14:07
by かずま
かずま さんが書きました: ↑4年前
そこで、n と m の最小公倍数を求めておいて、その回数だけずらして
すみません。最大公約数の間違いでした。
コードは間違っていません。