どうやってC++を使って双方向循環チェーン表を実現しますか?
双方向循環チェーンテーブル、すなわち、各ノードは前の2つのポインタを有しており、最後の相互チェーンのチェーンテーブルを持っています。各チェーンの簡単な違いは次の通りです。一方通行のチェーンは基本チェーンです。一方向循環チェーン表:一方向チェーン表とは違って、NULLでチェーンテーブルの末尾を判断し、一方向循環チェーン表の末尾がヘッダにリンクされているため、反復操作が先頭の前にすなわち末尾になる。双方向チェーン表:一方向チェーンテーブルより前のノードに向けたポインタが多いですが、実際には双方向チェーンを使う時にはあまり使われません。双方向循環チェーン表:一方向循環チェーンテーブルに対して、双方向循環チェーンテーブルは頭から逆に反復してもよく、これはチェーンテーブルの長さが大きく、チェーンの尾に近い要素を取得、挿入または削除する必要がある時に非常に効率的である。一方向循環リストは、表頭から順方向に反復するだけであり、逆反復から実行する時間はより大きい。node.h
/*
* 。 : , , 。
*/
class Node {
public:
int element;
Node *next;
Node *previous;
Node(int element, Node *next, Node *previous) {
this->element = element;
this->next = next;
this->previous = previous;
}
};
linkedlist.h:
#include "node.h“
struct LinkedList {
LinkedList();
void addFirst(int);
void addLast(int);
void add(int index, int element);
int getFirst();
int getLast();
int get(int);
int removeFirst();
int removeLast();
int remove(int);
void iterate();
private:
Node *header;
int size;
};
linkedlist.cpp:
#include "linkedlist.h"
#include <iostream>
using std::cout;
/*
* 。
* , 。
*/
LinkedList::LinkedList() {
header = new Node(NULL, NULL, NULL);
header->next = header;
header->previous = header;
size = 0;
}
/*
* 。
* , , , 。
* , 。
*/
void LinkedList::addFirst(int i) {
header->next = new Node(i, header->next, header);
header->next->next->previous = header->next;
++size;
}
/*
* 。
* , , , 。
* , 。
*/
void LinkedList::addLast(int i) {
header->previous = new Node(i, header, header->previous);
header->previous->previous->next = header->previous;
++size;
}
/*
* 。0 <= <= 。
* , ( ) , ( )。
* , , 。
* , 。
* ( )
*/
void LinkedList::add(int index, int i) {
if(index > size || index < 0) {
cout << "Exception in add(): Index out of bound." << '
';
return;
}
Node *entry;
if(index < size / 2) {
entry = header->next;
for(int i = 0; i < index; ++i)
entry = entry->next;
}
else {
entry = header;
for(int i = size; i > index; --i)
entry = entry->previous;
}
entry->previous->next = new Node(i, entry, entry->previous);
entry->previous = entry->previous->next;
++size;
}
/*
* 。
* 。
*/
int LinkedList::getFirst() {
if(!size)
cout << "Exception in getFirst(): List is empty." << '
';
return header->next->element;
}
/*
* 。
* 。
*/
int LinkedList::getLast() {
if(!size)
cout << "Exception in getLast(): List is empty." << '
';
return header->previous->element;
}
/*
* 。
* , 。
*/
int LinkedList::removeFirst() {
int remove = header->next->element;
header->next->next->previous = header;
header->next = header->next->next;
--size;
return remove;
}
/*
* 。
* , 。
*/
int LinkedList::removeLast() {
int remove = header->previous->element;
header->previous->previous->next = header;
header->previous = header->previous->previous;
--size;
return remove;
}
/*
* 。
*/
void LinkedList::iterate() {
if(!size) {
cout << "Exception in iterate(): List is empty." << '
';
return;
}
for(Node *entry = header->next; entry != header; entry = entry->next)
cout << entry->element << " ";
cout << '
';
}