0

前提
c言語のリスト構造の問題を行っていて、わからない問題に直面したため質問しました。

実現したいこと
受け取ったリストの後半半分を前半に、前半半分を後半につなぎなおす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 -> element = x;
  n -> next = NULL;
  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) {
  struct node *q;
  int i = 0;
  int j;
  int k;
  q = p;
  while(p){
    p = p -> next;
    i++;
  }
  i--;
  p = q;
  for(j=1; j<=i/2; j++){
    delete(p);
  }
}
void delete ( struct node *p ) {
  if ( p -> next != NULL ) {
    p -> next = p -> next -> next;
  }
}

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;
}

正しい出力結果

[]$ ./q5-2 tokyo
kyoto
[]$ ./q5-2 yuyakekoyake
koyakeyuyake

自分の出力結果

[]$ ./q5-2 tokyo
kyo
[]$ ./q5-2 yuyakekoyake
koyake
2

1 件の回答 1

0

コメントで示された参照先記事の内容で解決していますが、一応解説。

質問のソースコードの主な問題は、以下の部分でリストの先頭から始まる前半部分をdelete(p)しているからですね。

  for(j=1; j<=i/2; j++){
    delete(p);
  }

データを削除してしまっては失われてしまうので繋ぎ直すことはできません。

それから作業用のポインタに渡されたパラメータを使っていたり、ノード数や後半位置計算の処理が微妙に冗長です。

質問のソースコードとコメントで示された参照先記事を合わせつつ大まかな解説をソースコメントに入れると以下のようになります。

void halfchange(struct node* p) {
    // NULLを指す無効なパラメータまたはノード数=1ならリターン
    if (!p || !p->next || !p->next->next) return;

    // *q は一時退避では無く最終ノード取得作業用, *r は新しい最終ノード取得作業用
    struct node *q, *r;
    int i, j, k;

    // 現在の最終ノードとノード数を取得
    q = p;
    for (i = 0; q->next != NULL; i++) {
        q = q->next;
    }

    // 処理後の新しい最終ノードを取得
    k = i / 2;
    r = p;
    for (j = 0; j < k; j++) {
        r = r->next;
    }

    // リストを半分で切って前後を付け替える
    q->next = p->next; // 現最終ノードに現先頭ノードを接続
    p->next = r->next; // 新先頭ノードを新最終ノードの次に設定
    r->next = NULL;    // 新最終ノードの次ポインタをクリアして最終ノードに
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。