双方向リストについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ラビット
記事: 1
登録日時: 2ヶ月前

双方向リストについて

#1

投稿記事 by ラビット » 2ヶ月前

ソート済みの双方向リスト2つを併合して3つ目のソートした双方向リストを作るにはどうすれば良いか教えてください!

アバター
usao
記事: 1541
登録日時: 6年前

Re: 双方向リストについて

#2

投稿記事 by usao » 2ヶ月前

どうすればも何も,単にそれを実現するだけなら
単に2つのリストの全要素を持つリストを作って,それをソートすりゃ良いであろうことは火を見るよりも明らか.

リスト1:{ 1, 3, 5 }
リスト2:{ 2, 4, 6 }
 ↓てきとーに合体
リスト3:{ 1, 3, 5, 2, 4, 6 }
 ↓ソートする
リスト3:{ 1, 2, 3, 4, 5, 6 }


「てきとーに合体」ではなく,元のリストがソート済みであるという制約条件を利用した合体を行えば
最後のソートが要らないだろうこともまた自明に思える.

かずま

Re: 双方向リストについて

#3

投稿記事 by かずま » 2ヶ月前

まずは C++ で書いてみます。

コード:

#include <iostream>
#include <list>
#include <algorithm>  // merge
#include <iterator>   // back_inserter
using namespace std;

int main()
{
	list<int> a = { 1, 3, 5 };
	list<int> b = { 2, 4, 6 };
	list<int> c;

	merge(begin(a), end(a), begin(b), end(b), back_inserter(c));

	for (int i : c) cout << ' ' << i;
	cout << endl;
}
merge を使わないようにすると、

コード:

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int> a = { 1, 3, 5 };
	list<int> b = { 2, 4, 6 };
	list<int> c;

	auto a1 = a.begin(), a2 = a.end(), b1 = b.begin(), b2 = e.end();
	while (a1 != a2 && b1 != b2) c.push_back(*a1 < *b1 ? *a1++ : *b1++);
	while (a1 != a.end()) c.push_back(*a1++);
	while (b1 != b2) c.push_back(*b1++);

	for (int i : c) cout << ' ' << i;
	cout << endl;
}
C++ を C に変換すると、

コード:

#include <stdio.h>   // printf, putchar
#include <stdlib.h>  // malloc, free

typedef struct Node {
	struct Node *prev, *next;
	int data;
} Node;

void push_back(Node *p, int data)
{
	Node *q = malloc(sizeof(Node));
	q->data = data;
	q->prev = p->prev, q->next = p;
	p->prev->next = q, p->prev = q;
}

void release(Node *p)
{
	for (Node *r, *q = p->next; q != p; q = r) r = q->next, free(q);
}

int main(void)
{
	Node a = { &a, &a }, b = { &b, &b }, c = { &c , &c }; 
	push_back(&a, 1), push_back(&a, 3), push_back(&a, 5);
	push_back(&b, 2), push_back(&b, 4), push_back(&b, 6);

	Node *a1 = a.next, *b1 = b.next;
	while (a1 != &a && b1 != &b)
		if (a1->data < b1->data)
			push_back(&c, a1->data), a1 = a1->next;
		else
			push_back(&c, b1->data), b1 = b1->next;
	while (a1 != &a) push_back(&c, a1->data), a1 = a1->next;
	while (b1 != &b) push_back(&c, b1->data), b1 = b1->next;

	for (const Node *p = &c; (p = p->next) != &c; ) printf(" %d", p->data);
	putchar('\n');
	release(&a), release(&b), release(&c);
}
分からないところは質問してください。

Math

Re: 双方向リストについて

#4

投稿記事 by Math » 2ヶ月前

双方向リスト(doubly-linked list)は、双方向の連結リストです。各ノードには2つのリンクがあり、1つが次のノード(前方リンク)、もう1つが後ろのノード(後方リンク)を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。

http://www.cs.shinshu-u.ac.jp/Lecture/P ... ist-2.html を参照。

ソート済みの双方向リスト2つを読み出しながら順次比較して 新しく双方向リストを作れば
3つ目のソートした双方向リストになります。

返信

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