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

Question

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;

}

Answer 1

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

双方向リスト：Ｃ言語入門

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

Wikipedia:双方向リスト

Answer 2

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

では、本題です。
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は先頭データをもらっているので、末尾のデータを貰うこと。

末尾のデータをどうやって指定するのかを考えましょう。

• 次のデータに向かっていくのではなく、前のデータに戻るようにする。

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