双方向リストについて

[ラビット]

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

[usao]

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

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


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

[かずま]

まずは 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]

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

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

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