c++単一チェーンテーブルの基本操作を実現

程序媛はコードを書くことをよく勉強することにした.
チェーンテーブルは物理記憶ユニット上の非連続、非順序の記憶構造であり、データ要素の論理順序はチェーンテーブル内のポインタリンク順序によって実現される.チェーンテーブルは、実行時に動的に生成できる一連のノード(チェーンテーブルの各要素をノードと呼ぶ)から構成されます.各ノードには、データ要素を格納するデータドメインと、次のノードアドレスを格納するポインタドメインの2つのセクションがあります.線形テーブルの順序構造に比べて、操作が複雑です.順番に格納する必要がないため、チェーンテーブルは挿入時にO(1)の複雑さに達し、別の線形テーブルの順序テーブルよりもずっと速いが、1つのノードを検索したり、特定の番号のノードにアクセスしたりするにはO(n)の時間が必要であり、線形テーブルと順序テーブルの対応する時間複雑さはそれぞれO(logn)とO(1)である.
チェーンテーブル構造を使用すると、配列チェーンテーブルが予めデータサイズを知る必要があるという欠点を克服することができ、チェーンテーブル構造はコンピュータのメモリ空間を十分に利用し、柔軟なメモリ動態管理を実現することができる.しかし,チェーンテーブルは配列ランダム読み出しの利点を失い,同時にチェーンテーブルはノードのポインタドメインを増加させるため,空間オーバーヘッドが大きい.チェーンテーブルの最も明らかな利点は、従来の配列が関連項目を配列する方法が、メモリまたはディスク上のこれらのデータ項目とは順序が異なり、データのアクセスが異なる配列順序で変換されることが多いことです.チェーンテーブルでは、テーブル上の任意の場所のノードの挿入と削除は許可されますが、ランダムアクセスは許可されません.チェーンテーブルには、一方向チェーンテーブル、双方向チェーンテーブル、ループチェーンテーブルなど、さまざまなタイプがあります.チェーンテーブルは、複数のプログラミング言語で実現できます.LispやSchemeのような言語の組み込みデータ型には,チェーンテーブルへのアクセスと操作が含まれている.C,C+,Javaなどのプログラム言語またはオブジェクト向け言語は,可変ツールによってチェーンテーブルを生成する.
ここで、データ要素情報を格納するドメインをデータドメイン(ドメイン名をdataとする)と呼び、直接後続の格納位置を格納するドメインをポインタドメイン(ドメイン名をnextとする)と呼ぶ.ポインタドメインに格納されている情報は、ポインタまたはチェーンとも呼ばれます.
それぞれ表示,,,…,のN個のノードが順次相鎖で構成されるチェーンテーブルを線形テーブルと呼ぶチェーン格納表現は,このようなチェーンテーブルの各ノードに1つのポインタドメインしか含まれていないため,単鎖テーブルまたは線形チェーンテーブルとも呼ばれる.
linkedlist.h//ヘッダファイル、ノードとチェーンテーブル情報の定義、宣言作成、挿入、削除などの基本関数

/*     ，    、  、     */
#include 
using namespace std;

struct StuInfo
{
	int id;  //  
	string name;   //  
};

struct Node
{
	StuInfo info;
	Node *next;
	Node(){}
	Node(StuInfo x){ info = x; next = NULL; }
};

class LinkedList
{
public:
	LinkedList(); //    
	~LinkedList(); //    
	void insert(StuInfo info, int pos);
	void remove(int id);  //          
	int find(int id); //        ，      
	int getLength(); //      
	void print();  //      
private:
	Node *head;
	int length;

};

次に、対応するソースファイル、linkedlistの作成を続行します.cpp//具体的な関数の内容を実現する

#include 
#include "linkedlist.h"
using namespace std;

//    
LinkedList::LinkedList()
{
	head = NULL;
	length = 0;
}

//    
LinkedList::~LinkedList()
{
	Node* temp;
	for (int i = 0; i < length; i++)
	{
		temp = head;
		head = head->next;
		delete temp;
	}

}

void LinkedList::insert(StuInfo info, int pos)
{
	if (pos < 0)
	{
		cout << "          " << endl;
	}
	int index = 1;
	Node *temp = head;
	Node *node = new Node(info);
	if (pos == 0)
	{
		node->next = temp;
		head = node;
		length++;
		return;
	}
	while (index < pos && temp != NULL)
	{
		temp = temp->next;
		index++;
	}
	if (temp == NULL)
	{
		cout << "    ，          " << endl;
		return;
	}
	node->next = temp->next;
	temp->next = node;
	length++;
	return;
}

void LinkedList::remove(int id)
{
	int pos = find(id);
	if (pos == -1)
	{
		cout << "        ，        " << endl;
		return;
	}
	if (pos == 0)
	{
		head = head->next;
		length--;
		return;
	}
	int index = 1;
	Node *temp = head;
	while (index < pos)
	{
		temp = temp->next;
	}
	temp->next = temp->next->next;
	length--;
	return;
}

int LinkedList::find(int id)
{
	Node *temp = head;
	int index = 0;
	while (temp != NULL)
	{
		if (temp->info.id == id)
		{
			return index;
		}
		temp = temp->next;
		index++;
	}
	return -1;
}

int LinkedList::getLength()
{
	return length;
}

void LinkedList::print()
{
	if (head == NULL)
	{
		cout << "    ，    " << endl;
		return;
	}
	Node *temp = head;
	while (temp != NULL)
	{
		cout << temp->info.id << "," << temp->info.name << endl;
		temp = temp->next;
	}
	cout << endl;
	return;
}

最後に、テスト用main関数の作成

#include 
#include 
#include "linkedlist.h"
using namespace std;
int main()
{
	LinkedList head;
	StuInfo info1, info2, info3, info4, info5;
	info1.id = 1001, info1.name = "  ", info2.id = 1002, info2.name = "  ", info3.id = 1003, info3.name = "  ", info4.id = 1004, info4.name = "  ", info5.id = 1005, info5.name = "  ";

	//      
	cout << "    ：" << endl;
	head.insert(info1, 0);
	head.print();
	head.insert(info2, 1);
	head.print();
	head.insert(info3, 4);
	head.print();
	head.insert(info4, 0);
	head.print();
	head.insert(info5, 2);
	head.print();
	//      
	cout << "    ：" << endl;
	cout << "     ：" << head.getLength() << endl;
	head.remove(1004);
	head.print();
	cout << "     ：" << head.getLength() << endl;
	head.remove(1004);
	head.print();
	return 0;
}