質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.64%

単方向連結リストから双方向連結リスト

受付中

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 805

ldangol

score 4

C言語についての質問です。
以下のソースコードは単方向連結リストです。
これを双方向連結リストに改編し、リストを逆順に表示する ListRevPrintAll 関数を実装したいのですが、わかりません。
どなたか解説付きで教えてくださらないでしょうか。
自分で勉強しての変更点は、
struct cell *prev;
を追加し、
ListInsert関数を
PCELL ListInsert(PCELL pos, const char *string)
{
PCELL pNewCell;
pNewCell = calloc(1, sizeof(CELL));

if (pNewCell != NULL) {
// 新しいセルへの文字列をコピーおよび
// ポインタの付け替えを行う
strcpy(pNewCell->string, string);
pNewCell->next = pos->next;
pNewCell->next->prev = pNewCell;
pos->next = pNewCell;
pNewCell->prev = pos;
}
return pNewCell;
}
とし、ListDelete関数は
void ListDelete(PCELL pos)
{
PCELL P0;
P0 = pos->prev->next = pos->next;
pos->next->prev = pos->prev;
pos->prev = pos->next = pos;
free(P0);

}
と変更しました。
ほかにどのように改編すればよいでしょうか。

include <stdio.h>

include <string.h>

include <stdlib.h>

include <assert.h>

include <crtdbg.h>

typedef struct cell {
char string[8];
struct cell *next;
} CELL, *PCELL;

PCELL ListCreate()
{
return calloc(1, sizeof(CELL));
}

PCELL ListGetPrevPos(PCELL header, const char *str)
{
while (header->next) {
if (strcmp(header->next->string, str) == 0) {
return header;
}
header = header->next;
}
return NULL;
}

PCELL ListNext(PCELL pos)
{
return pos->next;
}

void ListPrintAll(PCELL header)
{
puts("-  addr  --  next  -:string");
printf("[%08x][%08x]:HEADER\n", header, header->next);
header = header->next;
while (header) {
printf("[%08x][%08x]:<%s>\n", header, header->next, header->string);
header = header->next;
}
puts("------");
}

PCELL ListInsert(PCELL pos, const char *string)
{
PCELL pNewCell;
pNewCell = calloc(1, sizeof(CELL));

if (pNewCell != NULL) {
strcpy(pNewCell->string, string);
pNewCell->next = pos->next;
pos->next = pNewCell;
}
return pNewCell;
}

void ListDelete(PCELL pos)
{
PCELL P0;
P0 = pos->next;
pos->next = pos->next->next;
free(P0);

}

void ListDestroy(PCELL header)
{
PCELL P, PC;
PC = header;
while (PC != NULL) {
P = PC->next;
free(PC);
PC = P;
}

}

define BUFSIZE 20

int main()
{
static char buf[BUFSIZE];
PCELL header;

header = ListCreate();

for (;;) {
printf(">>");
gets(buf);
switch (*buf) {
case 'A': case 'a':
printf("先頭に挿入する文字列を入力:");
gets(buf);
ListInsert(header, buf);
break;
case 'I': case 'i':
{
PCELL pos;
printf("挿入位置の文字列を入力:");
gets(buf);
pos = ListGetPrevPos(header, buf);
if (pos == NULL) {
printf("\"%s\"は見つかりません\n", buf);
}
else {
printf("挿入する文字列を入力:");    gets(buf);
ListInsert(ListNext(pos), buf);
}
}
break;
case 'D': case 'd':
{
PCELL pos;
printf("削除する文字列を入力:");
gets(buf);
pos = ListGetPrevPos(header, buf);
if (pos == NULL) {
printf("\"%s\"は見つかりません\n", buf);
}
else {
ListDelete(pos);
}
}
break;
case 'P': case 'p':
ListPrintAll(header);
break;
case 'E': case 'e':
ListDestroy(header);
exit(0);
break;
default:
printf("(A)dd, (I)nsert, (D)elete, (P)rint, (E)xit\n");
}
}
return 0;
}

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+1

双方向リストで検索してみてください

双方向リスト:C言語入門

といったページが見つかると思います。言語が異なっても考え方が重要ですので上記のサイト以外にも色々探してみてください。自分はwikipediaの説明が図入りで分かりやすいと思いました。

Wikipedia:双方向リスト

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

最初に、初めてこのサイトを利用するようなので厳しいことを書きます。
今後はもう少し具体的に直面している問題について記載してください。
「どうしたらいいか?」という漠然とした質問の仕方はこの場では不適切です。
どこに躓いたかをきちんと書きましょう。

では、本題です。
ListInsertとListDeleteの二つの変更は双方向リストとしてやりたいことができてて、良い感じだと思います。
※不具合はまだあるかもしれないけどね …というか あります。

あとはListRevPrintAllを実装するだけですよね。
せっかくListPrintAllメソッドがあるので、これを参考にどのような変更が必要か考えてみてはどうでしょうか。

void ListPrintAll(PCELL header) 
{ 
    puts("-  addr  --  next  -:string"); 
    printf("[%08x][%08x]:HEADER\n", header, header->next); 
    header = header->next; 
    while (header) { 
        printf("[%08x][%08x]:<%s>\n", header, header->next, header->string); 
        header = header->next; 
    } 
    puts("------"); 
}


この関数は、先頭のデータを受け取って、次のデータがなくなるまで画面に文字列を表示しています。
ということは、必要なのは…

  • ListPrintAllは先頭データをもらっているので、末尾のデータを貰うこと。
    末尾のデータをどうやって指定するのかを考えましょう。
  • 次のデータに向かっていくのではなく、前のデータに戻るようにする。

こんな感じでどうでしょう。作っていけそうですか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.64%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる