C++チェーンテーブルのクラス定義

離散型の抽象データ型格納のデータ構造として,チェーンテーブルは使用率が高いといえる.チェーンテーブルは実は配列のように順番に格納されていますが、メモリには連続したデータではなく離散しています.データの接続はポインタの指向にかかっている.
本題に戻ると、ここでは簡単な単鎖表のクラス定義を紹介する.
チェーンテーブルは2つのクラスの複合方式で構成され、1つのクラスには2つの属性があり、1つのクラスにはチェーンテーブルに対する操作(増加、削除、検索、変更)がある.
 

class list
{
  private:
        int date;
        list *link;
};

 

class node
{
private:
	listnode *first,*last;
public:
	node();
	~node();
	void add(int x);
	void print();

};

1つ目のクラスには、データを格納するデータドメインと、次のノードを指すポインタドメインの2つの属性があります.
この2つのクラスの複合のためには,友元クラスを用いなければならない.class listではfriend nodeを定義し、友元を定義するのは主にnodeクラスでlistを使用できるプライベートメンバーのためです.
ここでintを例に挙げて整形チェーンテーブルを作成し、テンプレートを使用して抽象データ型ストレージを定義することができます.すべての操作の中で、最も難しいのはノードの確立と削除です.ここでは、新しいノードの2つの方法、頭挿入法と尾挿入法を紹介します.
ヘッドプラグ:
1つのfirstポインタだけで実現でき、具体的な機能はハンノタワーのモデルです.先に行ったのは尾で、後ろに入ったのは頭です.
firstは最初は空と定義されており、挿入が必要な場合は、新しいノード、newnode->link=first、first=newnodeと定義されています.この2つの言葉の意味は、新しいノードのポインタドメインがfirstを指し、firstをnewnodeに指すことで、ヘッダ挿入法が実現されます.転送されたxをdateに割り当てるだけでヘッダ挿入法の逆説記憶が実現できるのは、私たちが普段好きな順番とは少し違うのではないでしょうか.次に尾挿し法を紹介します.
テールプラグ法は離散したシーケンステーブルであり,配列のようにメモリが離散しているが,シーケンスストレージである.
テールプラグ法はfirstとlastの2つのポインタで実現する必要がある.
 

//       
	void add(int x)
	{
		listnode *p=new listnode;
		if(first==0)
		{
			p->date=x;
			p->link = NULL;
			first = last = p;
		}
		else
		{
			p->date=x;
			last->link = p;
			last = p;
			last->link = NULL;
		}

空のテーブルである場合、firstとlastは同時に新しいノードpを指し、空のテーブルでない場合、lastによってノードを接続する.
チェーンテーブルを書くときは絵の理解を補助したほうがいいです.