[セットトップ]シーケンステーブル&チェーン(List)の基礎操作
説明:
順序表とチェーンはデータ構造の基礎構造の一つであり、面接の基礎でもあります.初心者はSeqlistとListの添削の基礎練習について、その後のTree、HashTable、Binary Linked List、Trigeinal linked listなどのデータ構造に対して堅固な基礎を打ち立てます.
C言語のSeqlist:
C++の下のSeqlist:
Cの下のList:
C++の下のList:
最後に、順序表とチェーンの違いをまとめます.
★シーケンス表の特徴:論理的にデータ要素が隣接しており、物理的な格納位置も隣接しており、記憶空間はあらかじめ割り当てられている必要がある.
利点: (1)方法は簡単で、各種の高級言語には配列があり、実現しやすいです.
(2)ノード間の論理関係を示すために追加の記憶オーバヘッドを追加する必要はない.
(3)シーケンステーブルは要素番号によってランダムにアクセスする特徴がある.
短所: (1)シーケンステーブルに挿入、削除操作をすると、移動テーブルの半分の要素が平均されているため、nに対して大きなシーケンステーブルの効率が低い.
(2)十分な記憶空間をあらかじめ分配しておく必要があり、大きすぎると、順序表の後部に大量の空きが生じる可能性がある.小さな分配をしておくと、また溢れ出すことがあります.
★シングルチェーン表の特徴:チェーンテーブルに論理的に隣接するデータ要素は、物理的な格納位置が必ずしも隣接していないため、ポインタを使って要素間の論理関係を実現します.そして記憶空間は動的に割り当てられている.
利点:
チェーンの最大の特徴は: 演算を挿入、削除するのに便利です.
短所:
(1)追加の記憶空間記憶要素間の関係を占用するには、記憶密度が低下します.記憶密度とは、ノード内のデータ要素が占める記憶ユニットと、ノード全体が占める記憶リストのことです. 元の比
(2)チェーンテーブルはランダム記憶構造ではなく、ランダムアクセス要素ではありません.
★2つの構造の適用シーン: (1)シーケンステーブルの格納空間は静的に割り当てられており、プログラム実行前にその記憶規模を明確に規定しなければならない.つまり事前に「MaxuSize」に対して適切な設定が必要であり、大会設定により記憶空間の無駄が発生し、オーバーフローを起こしてしまう.したがって、線形表の長さや記憶規模の推定が困難な場合は、順序表を採用するべきではない.
(2)チェーンの動的配分はこの欠点を克服することができる.チェーンテーブルは記憶空間を残しておく必要がありません.表の長さがどう変化するかを知る必要もありません.メモリの空間が空きさえあれば、プログラムを実行する時にいつでもダイナミックに空間を割り振りできます.必要でない時にはダイナミックに回収できます.したがって、線形テーブルの長さが大きく変化したり、記憶規模を推定することが困難な場合は、動的チェーンテーブルを記憶構造として用いることが望ましい.
(3)チェーンテーブルには、データ範囲の他に、各ノードにポインタを追加する必要がある.ノードのデータが占有する空間が小さい場合、チェーンテーブルの構造オーバーヘッドは記憶空間全体の大部分を占める.シーケンステーブルが満たされている場合は、構造オーバーヘッドがない.この場合、シーケンステーブルの空間効率はより高い.ポインタ領域の設定額が外部にあるため、一定の記憶空間がかかり、記憶密度の観点からチェーンの記憶密度は1より小さい.したがって、線形テーブルの長さが大きく変化していない、かつ、その大きさが予め決定されやすい場合は、格納空間を節約するために、順序表を記憶構造として用いるのが好ましい.
(4)演算に基づく考慮(時間):順序格納はランダムアクセスの構造であり、チェーンテーブルは順序アクセス構造であるため、それらは様々な動作に対して全く異なるアルゴリズムと時間複雑さを有する.例えば、線形表のi番目の要素を検索するには、シーケンステーブルに対してa(i)のアドレスを直接計算することができ、その時間の複雑さは0(1)であり、チェーンテーブルはチェーンテーブルの先頭から順に後方に検索する必要があり、平均的に0(n)の時間が必要である.したがって、頻繁に行われる演算がシリアル番号でデータ要素にアクセスする場合、明らかにリストのほうがチェーンより優れています. 逆に、順序表に挿入し、削除するときは、平均移動表の半分の要素が、データ要素の情報量が大きく、表が比較的長いときは無視してはいけない.チェーンで挿入、削除します.挿入位置を探しますが、操作は比較操作です.この角度から見れば前者より優れています.
(5)環境に基づく考慮(言語) 順序表は簡単に実現できます.任意の高度な言語には配列タイプがあります.チェーンの操作は針に基づいています.したがって、順序表の適応範囲はより広く、前者がより簡単であり、ユーザーが考慮する要素でもある.
▲とにかく、二つの記憶構造にはそれぞれ優劣があります.どちらを選ぶかは実際の問題の主要な要素によって決められます.一般的に「安定している」線形テーブル、すなわち、主な動作はルックアップ動作の線形テーブルであり、順序記憶を選択するのに適している.挿入削除演算を頻繁に行う線形表は、チェーン記憶を選択するのに適しています.
順序表とチェーンはデータ構造の基礎構造の一つであり、面接の基礎でもあります.初心者はSeqlistとListの添削の基礎練習について、その後のTree、HashTable、Binary Linked List、Trigeinal linked listなどのデータ構造に対して堅固な基礎を打ち立てます.
C言語のSeqlist:
<span style="font-size:18px;">#include<stdio.h>
#include<stdlib.h>
#include<cassert>
#include<string.h>
#define Max_Size 10
typedef int Datatype;
typedef struct Seqlist
{
Datatype arr[Max_Size];//
size_t size;//
Datatype x;
}Seqlist;
void Init(Seqlist* ptr)
{
assert(ptr);
memset(ptr->arr, 0, sizeof(Datatype)*Max_Size);
ptr->size = 0;
}
void PushBack(Seqlist* ptr,Datatype x)
// ， size +1， x
{
assert(ptr);
if (ptr->size >= Max_Size)
{
printf("Seqlist is Full!
");
return;
}
ptr->arr[ptr->size++] = x;
}
void PopBack(Seqlist* ptr)
// ， size -1，
{
assert(ptr);
if (ptr->size <= 0)
{
printf("Seqlist is Empty!
");
return;
}
--ptr->size;
}
void PushFront(Seqlist* ptr,Datatype x)
// ， size +1， ， ， ， x 。 ： ， 。
{
assert(ptr);
int i = ptr->size - 1;
if (ptr->size >= Max_Size)
{
printf("Seqlist is Full!
");
return;
}
ptr->size++;
for (; i >= 0; --i)
{
ptr->arr[i + 1] = ptr->arr[i];
}
ptr->arr[0] = x;
}
void PopFront(Seqlist* ptr)
// ， ， size -1
{
assert(ptr);
size_t i = 0;
if (ptr->size <= 0)
{
printf("Seqlist is Empty!
");
return;
}
for (; i < ptr->size;++i)
{
ptr->arr[i] = ptr->arr[i+1];
}
--ptr->size;
}
void Erase(Seqlist* ptr, size_t pos)
// ， ， pos 。 ： 0 ， pos-1
{
assert(ptr);
size_t i = pos - 1;
if (ptr->size <= 0)
{
printf("Seqlist is Empty!
");
return;
}
for (; i < ptr->size; ++i)
{
ptr->arr[i] = ptr->arr[i + 1];
}
--ptr->size;
}
void Insert(Seqlist* ptr, Datatype x, size_t pos)
// ， Erase ，
{
assert(ptr);
assert(pos);
if (ptr->size >= Max_Size)
{
printf("Seqlist is Full!
");
return;
}
if (pos > ptr->size)
{
printf("Illegal Insert!
");
return;
}
size_t i = ptr->size++;
for (; i >= pos - 1; i--)
{
ptr->arr[i] = ptr->arr[i - 1];
}
ptr->arr[pos - 1] = x;
}
int Find_One(Seqlist* ptr,Datatype x)
//
{
assert(ptr);
size_t i = 0;
for (; i < ptr->size; i++)
{
if (ptr->arr[i] == x)
{
return i;
}
}
return -1;
}
void Display(Seqlist* ptr)
//
{
assert(ptr);
size_t i = 0;
if (ptr->size == 0)
{
printf("Seqlist is Empty!
");
return;
}
for (; i < ptr->size; i++)
{
printf("%d ", ptr->arr[i]);
}
printf("
");
}</span>C++の下のSeqlist:
<span style="font-size:18px;">#include<iostream>
using namespace std;
SeqList::SeqList()
:_array(NULL)
, _size(0)
, _capacity(0)
{}
//
//
SeqList(const SeqList& s)
:_array(new DataType[s._size])
,_size(s._size)
,_capacity(s._capacity)
memcpy(_array, s._array, sizeof(DataType)*(_size));
}
SeqList& operator=(const SeqList& s)
{
if (this != &s)
{
DataType* tmp = new DataType[s._size];
delete[] _array;
_array = tmp;
_size = s._size;
_capacity = s._capacity;
memcpy(_array, s._array, sizeof(DataType)*(_size));
}
return *this;
}
//
SeqList::SeqList(DataType* array, const size_t size)
:_array(new DataType[size])
, _size(size)
, _capacity(size)
{
memcpy(_array, array, sizeof(DataType)*size);
}
SeqList::SeqList(const SeqList& s)
:_array(NULL)
{
SeqList tmp(s._array, s._size);
swap(_array, tmp._array);
_size = s._size;
_capacity = s._size; // _size,
}
SeqList& SeqList::operator=(SeqList& s)
{
if (this != &s)
{
swap(_array, s._array);
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
SeqList::~SeqList()
{
if (_array)
{
delete[] _array;
}
}
void SeqList::_CheckCapacity()//
{
if (_size >= _capacity)
{
_capacity = 2 * _capacity + 3;//_capacity 0
_array = (DataType*)realloc(_array, _capacity*sizeof(DataType));//realloc ，
}
}
void SeqList::PrintSepList()//
{
for (int i = 0; i < (int)_size; i++)
{
cout << _array[i] << "-";
}
cout << "NULL" << endl;
}
void SeqList::PushBack(DataType x)//
{
_CheckCapacity();
_array[_size++] = x;
}
void SeqList::PopBack()//
{
if (_size > 0)
{
_array[_size--] = NULL;
}
else
cout << "SeqList is empty" << endl;
}
void SeqList::PushFront(DataType x)////
{
_CheckCapacity();
for (int i = (int)_size; i >0 ; i--)
{
_array[i] = _array[i - 1];
}
_array[0] = x;
_size++;
}
void SeqList::PopFront()//
{
if (_size > 0)
{
_array[0] = NULL;
for (int i = 0; i < (int)_size; i++)
{
_array[i] = _array[i + 1];
}
_size--;
}
else
cout << "SeqList is empty" << endl;
}
void SeqList::Insert(size_t pos, DataType x)//
{
if (pos <= 0 || pos > _size + 1)
{
cout << "position is error!" << endl;
}
else if (pos == _size)
SeqList::PushBack(x);
else
{
for (int i = (int)(++_size); i > ((int)pos - 1); i--)
{
_array[i] = _array[i - 1];
}
_array[pos - 1] = x;
}
}
void SeqList::Erase(size_t pos)//
{
if (pos <= 0 || pos > _size + 1)
{
cout << "position is error!" << endl;
}
else if (pos == _size)
SeqList::PopBack();
else
{
_array[pos - 1] = NULL;
for (int i = pos - 1; i < (int)_size; i++)
{
_array[i] = _array[i + 1];
}
_size--;
}
}
size_t SeqList::Find(DataType x)//
{
int i;
for (i = 0; i < (int)_size; i++)
{
if (x == _array[i])
return i + 1;
}
if (i == (int)_size)
return 0;
return -1;
}</span>Cの下のList:
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Datatype;
typedef struct ListNode
{
Datatype data;//
struct ListNode *next;// ，
}ListNode;
ListNode* createNode(Datatype x)//
{
ListNode *tmp = (ListNode*)malloc(sizeof(ListNode));
if (tmp != NULL)
{
tmp->data = x;
tmp->next = NULL;
}
return tmp;
}
void pushFront(ListNode*& pHead, Datatype x)//
{
if (pHead == NULL)
{
pHead = createNode(x);
}
else
{
ListNode*tmp = createNode(x);
tmp->next = pHead;
pHead = tmp;
}
}
void PopFront(ListNode*& pHead)//
{
if (pHead == NULL)
{
printf("empty LinkedList
");
return;
}
else if (pHead->next == NULL)
{
free(pHead);
pHead = NULL;
}
else
{
ListNode* tmp = pHead;
pHead = pHead->next;
free(tmp);
}
}
void Insert(ListNode* pos, Datatype x)//
{
assert(pos);
ListNode*tmp = createNode(x);
ListNode*cur = pos->next;
pos->next = tmp;
tmp->next = cur;
}
void Erase(ListNode*pHead, ListNode* pos)//
{
assert(pos);
if (pos->next == NULL)
{
free(pos);
}
else
{
ListNode*cur = NULL;
ListNode*tail = pos;
while (pHead->data != tail->data)
{
cur = pHead;
pHead = pHead->next;
}
ListNode*tmp = pos->next;
cur->next = tmp;
free(pos);
}
}
ListNode* Find(ListNode* pHead, Datatype x)//
{
assert(pHead);
ListNode* tail = pHead;
while (tail->next)
{
if (tail->data == x)
{
return tail;
}
tail = tail->next;
}
if (tail->next == NULL)
{
return tail;
}
return NULL;
}
void print(ListNode *pHead)//
{
ListNode* cur = pHead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
printf("
");
}<span style="color:#ff0000;font-weight: bold;">
</span>C++の下のList:
<span style="font-size:18px;">#include<iostream>
using namespace std;
template<class T>
struct ListNode
{
ListNode(const T& x)
:_next(NULL)
, _prev(NULL)
, _data(x)
{}
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
};
template<class T>
class List
{
public:
List()
:_head(NULL)
, _tail(NULL)
{}
List(const List<T>& l)
{
ListNode<T>* cur = l._head;
while (cur)
{
this->PushBack(cur->_data);
cur = cur->_next;
}
}
List<T>& operator=(const List<T>& l)
{
// ，
if (&s != this)
{
ListNode<T>* pcur = _head;
while (pcur)
{
ListNode<T>* del = pcur;
pcur = pcur->_next;
delete del;
del = NULL;
}
ListNode<T>* cur = _head;
while (cur)
{
this->PushBack(cur->_data);
cur = cur->_next;
}
}
return *this;
}
~List()//
{
ListNode<T>* cur = _head;
while (cur)
{
ListNode<T>* del = cur;
cur = cur->_next;
delete del;
del = NULL;
}
}
void PushBack(const T& x);//
void PopBack();//
void Unique();//
void PrintList();//
void Reverse();//
int Length();//
void Sort();//
protected:
ListNode<T>* _head;
ListNode<T>* _tail;
};
//
template<class T>
void List<T>::PushBack(const T& x)
{
// ： ： 、
if (_head == NULL)
{
_head = _tail = new ListNode<T>(x);
}
else
{
ListNode<T>* cur = new ListNode<T>(x);
_tail->_next = cur;
cur->_prev = _tail;
_tail = cur;
_tail->_next = NULL;
}
}
//
template<class T>
void List<T>::PopBack()
{
// ： ： 、 、
if (_head == _tail)
{
if (_head == NULL)
{
return;
}
else
{
delete _head;
_head = _tail = NULL;
}
}
else
{
ListNode<T>* prev = _tail->_prev;
delete _tail;
_tail = NULL;
_tail = prev;
_tail->_next = NULL;
}
}
// :
template<class T>
void List<T>::Unique()
{
// ： ： （ ）、 、
if (_head == _tail)
{
return;
}
else
{
ListNode<T>* pcur = _head;
ListNode<T>* pnext = _head->_next;
if (pnext->_next == NULL) //
{
if (pcur->_data == pnext->_data)
{
delete pnext;
pnext = NULL;
_tail = _head = pcur;
return;
}
else
{
return;
}
}
else
{
//
ListNode<T>* cur = _head;
while (cur->_next)
{
ListNode<T>* next = cur->_next;
ListNode<T>* nextnext = next->_next;
if (cur->_data == next->_data)
{
cur->_next = nextnext;
nextnext->_prev = cur;
delete next;
next = NULL;
}
cur = cur->_next;
}
}
}
}
//
template<class T>
void List<T>::Reverse()
{
// ： , （ ）
ListNode<T>* begin = _head;
ListNode<T>* end = _tail;
while (!((begin == end) || end->_next == begin))
{
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
}
}
//
template<class T>
int List<T>::Length()
{
ListNode<T>* cur = _head;
int count = 0;
while (cur)
{
count++;
cur = cur->_next;
}
return count;
}
//
template<class T>
void List<T>::Sort()
{
// ,
ListNode<T>* i = _head;
while (i != _tail)
{
ListNode<T>* j = _head;
ListNode<T>* end = _tail;
while (j != end)
{
if (j->_data >(j->_next)->_data)
{
swap(j->_data, (j->_next)->_data);
}
j = j->_next;
}
end = end->_prev;
i = i->_next;
}
}
//
template<class T>
void List<T>::PrintList()
{
ListNode<T>* cur = _head;
while (cur)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}</span>最後に、順序表とチェーンの違いをまとめます.
★シーケンス表の特徴:論理的にデータ要素が隣接しており、物理的な格納位置も隣接しており、記憶空間はあらかじめ割り当てられている必要がある.
利点: (1)方法は簡単で、各種の高級言語には配列があり、実現しやすいです.
(2)ノード間の論理関係を示すために追加の記憶オーバヘッドを追加する必要はない.
(3)シーケンステーブルは要素番号によってランダムにアクセスする特徴がある.
短所: (1)シーケンステーブルに挿入、削除操作をすると、移動テーブルの半分の要素が平均されているため、nに対して大きなシーケンステーブルの効率が低い.
(2)十分な記憶空間をあらかじめ分配しておく必要があり、大きすぎると、順序表の後部に大量の空きが生じる可能性がある.小さな分配をしておくと、また溢れ出すことがあります.
★シングルチェーン表の特徴:チェーンテーブルに論理的に隣接するデータ要素は、物理的な格納位置が必ずしも隣接していないため、ポインタを使って要素間の論理関係を実現します.そして記憶空間は動的に割り当てられている.
利点:
チェーンの最大の特徴は: 演算を挿入、削除するのに便利です.
短所:
(1)追加の記憶空間記憶要素間の関係を占用するには、記憶密度が低下します.記憶密度とは、ノード内のデータ要素が占める記憶ユニットと、ノード全体が占める記憶リストのことです. 元の比
(2)チェーンテーブルはランダム記憶構造ではなく、ランダムアクセス要素ではありません.
★2つの構造の適用シーン: (1)シーケンステーブルの格納空間は静的に割り当てられており、プログラム実行前にその記憶規模を明確に規定しなければならない.つまり事前に「MaxuSize」に対して適切な設定が必要であり、大会設定により記憶空間の無駄が発生し、オーバーフローを起こしてしまう.したがって、線形表の長さや記憶規模の推定が困難な場合は、順序表を採用するべきではない.
(2)チェーンの動的配分はこの欠点を克服することができる.チェーンテーブルは記憶空間を残しておく必要がありません.表の長さがどう変化するかを知る必要もありません.メモリの空間が空きさえあれば、プログラムを実行する時にいつでもダイナミックに空間を割り振りできます.必要でない時にはダイナミックに回収できます.したがって、線形テーブルの長さが大きく変化したり、記憶規模を推定することが困難な場合は、動的チェーンテーブルを記憶構造として用いることが望ましい.
(3)チェーンテーブルには、データ範囲の他に、各ノードにポインタを追加する必要がある.ノードのデータが占有する空間が小さい場合、チェーンテーブルの構造オーバーヘッドは記憶空間全体の大部分を占める.シーケンステーブルが満たされている場合は、構造オーバーヘッドがない.この場合、シーケンステーブルの空間効率はより高い.ポインタ領域の設定額が外部にあるため、一定の記憶空間がかかり、記憶密度の観点からチェーンの記憶密度は1より小さい.したがって、線形テーブルの長さが大きく変化していない、かつ、その大きさが予め決定されやすい場合は、格納空間を節約するために、順序表を記憶構造として用いるのが好ましい.
(4)演算に基づく考慮(時間):順序格納はランダムアクセスの構造であり、チェーンテーブルは順序アクセス構造であるため、それらは様々な動作に対して全く異なるアルゴリズムと時間複雑さを有する.例えば、線形表のi番目の要素を検索するには、シーケンステーブルに対してa(i)のアドレスを直接計算することができ、その時間の複雑さは0(1)であり、チェーンテーブルはチェーンテーブルの先頭から順に後方に検索する必要があり、平均的に0(n)の時間が必要である.したがって、頻繁に行われる演算がシリアル番号でデータ要素にアクセスする場合、明らかにリストのほうがチェーンより優れています. 逆に、順序表に挿入し、削除するときは、平均移動表の半分の要素が、データ要素の情報量が大きく、表が比較的長いときは無視してはいけない.チェーンで挿入、削除します.挿入位置を探しますが、操作は比較操作です.この角度から見れば前者より優れています.
(5)環境に基づく考慮(言語) 順序表は簡単に実現できます.任意の高度な言語には配列タイプがあります.チェーンの操作は針に基づいています.したがって、順序表の適応範囲はより広く、前者がより簡単であり、ユーザーが考慮する要素でもある.
▲とにかく、二つの記憶構造にはそれぞれ優劣があります.どちらを選ぶかは実際の問題の主要な要素によって決められます.一般的に「安定している」線形テーブル、すなわち、主な動作はルックアップ動作の線形テーブルであり、順序記憶を選択するのに適している.挿入削除演算を頻繁に行う線形表は、チェーン記憶を選択するのに適しています.