【C++】双方向チェーンテーブル.cpp
双方向チェーンテーブルはデュアルチェーンテーブルとも呼ばれ、チェーンテーブルの一種であり、各データノードには2つのポインタがあり、それぞれ直接後続と直接前駆を指している.したがって,双方向チェーンテーブルのいずれかのノードから,その前駆ノードと後続ノードに容易にアクセスできる.
一般的に、双方向ループチェーンテーブルを構築します.双方向チェーンテーブルは一方向チェーンテーブルの不足と問題を解決しますが、単一チェーンテーブルは問題が多いので、面接ではよく単一チェーンテーブルの問題を試験します.
ここで、私は使います.cppは双方向チェーンテーブルの基本操作を実現する.
具体的なコードは以下の通りです.
List.hファイル:
List.cppファイル:(テスト)
私たちは、問題に遭遇したとき、直接手で書くことができないことに気づきました.なぜですか.バグではなくコードを書いているので、正しいプログラムは厳密な論理が必要であることを前提にしているので、コードを書く前に様々な臨界の状況と異常を慎重に考える必要があります.これは非常に重要です.
一般的に、双方向ループチェーンテーブルを構築します.双方向チェーンテーブルは一方向チェーンテーブルの不足と問題を解決しますが、単一チェーンテーブルは問題が多いので、面接ではよく単一チェーンテーブルの問題を試験します.
ここで、私は使います.cppは双方向チェーンテーブルの基本操作を実現する.
具体的なコードは以下の通りです.
List.hファイル:
#pragma once
typedef int DataType;
struct ListNode // struct, class
{ // class, public
DataType _data;
ListNode* _next; //
ListNode* _prev; //
ListNode(DataType x) //
:_data(x)
,_next(NULL)
,_prev(NULL)
{}
};
class List
{
public:
List()
:_head(NULL)
,_tail(NULL)
{}
~List()
{
Clear();
}
public:
void PushBack(DataType x)
{
if(_head == NULL)
{
_head = _tail = new ListNode(x);//
}
else
{
ListNode* tmp = new ListNode(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = tmp;
}
}
void PopBack()
{
//
//
//
if(_head == NULL)
{
return;
}
else if(_head == _tail)
{
delete _head;
_head = _tail = NULL;
}
else
{
ListNode* cur = _tail->_prev;
delete _tail;
_tail = cur;
cur->_next = NULL;
}
}
void PushFront(DataType x)
{
if(_head == NULL)
{
_head = _tail = new ListNode(x);
}
else
{
ListNode* tmp = new ListNode(x);
tmp->_next = _head;
_head = tmp;
}
}
void PopFront()
{
if(_head == NULL)//
{
return;
}
else if(_head == _tail)//
{
delete _head;
_head = _tail = NULL;
}
else //
{
ListNode* del = _head;
_head = _head->_next;
_head->_prev = NULL;
delete del;
}
}
void Insert(ListNode* pos,DataType x)
{
assert(pos);
if(pos == _tail)
{
PushBack(x);
}
else
{
/*
ListNode* tmp = new ListNode(x);
tmp->_next = pos->_next;
pos->_next->_prev = tmp; // ，
pos->_next = tmp; // pos ， pos->_next ， prev
tmp->_prev = pos;
*/
ListNode* tmp = new ListNode(x);// ，
ListNode* next = pos->_next;
tmp->_next = next;
next->_prev = tmp;
pos->_next = tmp;
tmp->_prev = pos;
}
}
ListNode* Find(DataType x)
{
if(_head == NULL)
{
return NULL;//
}
else
{
ListNode* cur = _head;
while(cur)
{
if(cur->_data == x)
{
return cur;
}
cur = cur->_next;
}
}
}
void Erase(ListNode* pos)
{
assert(_head);
assert(pos);
if(pos == _head)//
{
PopFront();
/*
ListNode* del = _head;
_head = _head->_next;
_head->_prev = NULL;
delete del;
*/
}
else if(pos == _tail)//
{
PopBack();
}
else //
{
/*
ListNode* cur = pos->_prev;
cur->_next = pos->_next;
pos->_next->_prev = cur;
delete pos;
*/
ListNode* prev = pos->_prev;
ListNode* next = pos->_next;
prev->_next = next;
next->_prev = prev;
delete pos;
}
}
void PrintList()// prev
{
ListNode* cur = _head;
while(cur)
{
cout<_data<";
cur = cur->_next;
}
cout<_next;
delete del;
}
}
//
void reverse()
{
/* ①.
ListNode* begin = _head;
ListNode* end = _tail;
while(begin != end && begin->_prev != end)//
{
swap(begin->_data , end->_data);
begin = begin->_next;
end = end ->_prev;
}
*/
//②.
ListNode* cur = _head;
while(cur)
{
swap(cur->_prev , cur->_next);//
cur = cur->_prev;
}
swap(_head,_tail);
}
private:
ListNode* _head;
ListNode* _tail;
};
void Test()
{
List l;
l.PushBack(1);
l.PushBack(2);
l.PushBack(3);
l.PushBack(4);
l.PushBack(5);
l.PrintList();
l.PopBack();
l.PrintList();
l.PushFront(0);
l.PrintList();
l.PopFront();
l.PrintList();
l.Insert(l.Find(1),0);
l.PrintList();
l.Erase(l.Find(1));
l.PrintList();
l.reverse();
l.PrintList();
} List.cppファイル:(テスト)
#include
#include
using namespace std;
#include "DoubleSList.h" //
int main()
{
Test();
return 0;
} 私たちは、問題に遭遇したとき、直接手で書くことができないことに気づきました.なぜですか.バグではなくコードを書いているので、正しいプログラムは厳密な論理が必要であることを前提にしているので、コードを書く前に様々な臨界の状況と異常を慎重に考える必要があります.これは非常に重要です.