チェーンテーブルの12種類の基本操作(C++実装)
9947 ワード
チェーンテーブルは動的データ構造であり、任意の記憶ユニット(連続的でも不連続的でもよい)のセットでデータ要素を格納することを特徴とする.チェーンテーブルの各要素は「ノード」となり、各ノードはデータドメインとポインタドメインからなり、各ノードのポインタドメインは次のノードを指します.Headは「ヘッダポインタ」であり、チェーンテーブルの開始を表し、最初のノードを指すために使用され、最後のポインタのポインタドメインはNULL(空のアドレス)であり、チェーンテーブルの終了を表す.チェーンテーブル構造はポインタを用いて実現されなければならないことが分かる.すなわち、次のノードのアドレスを格納するために、1つのノードにポインタ変数が含まれなければならない.実際には、チェーンテーブルの各ノードは、いくつかのデータといくつかのポインタを使用することができます.ノード内のポインタが1つしかないチェーンテーブルを単一チェーンテーブルと呼びます.これは最も簡単なチェーンテーブル構造です.さらにc++で単一チェーンテーブル構造を実現するのは比較的簡単である.たとえば、単一チェーンテーブル構造を定義できる最も簡単な形式は、struct Node{int Data;Node*next;}です.
ここでは構造体タイプを用いた.ここで、*nextはポインタドメインであり、そのノードの次のノードを指す.Dataは、ノード内のデータを格納する整形変数です.もちろん、Dataは、構造体タイプまたはクラスタイプを含む任意のデータ型であってもよい.これに基づいて、チェーンテーブルノードの挿入、削除、出力などの機能を含むメンバー関数を含むチェーンテーブルクラスlistを定義します.
C++はチェーンテーブルの12種類の基本操作を実現する:
積み重ねる.
ここでは構造体タイプを用いた.ここで、*nextはポインタドメインであり、そのノードの次のノードを指す.Dataは、ノード内のデータを格納する整形変数です.もちろん、Dataは、構造体タイプまたはクラスタイプを含む任意のデータ型であってもよい.これに基づいて、チェーンテーブルノードの挿入、削除、出力などの機能を含むメンバー関数を含むチェーンテーブルクラスlistを定義します.
C++はチェーンテーブルの12種類の基本操作を実現する:
C++ 2017-12-25 1 // .cpp: 。
//Author:kgvito
//Date: 2017.12.25
#include "stdafx.h"
#include
using namespace std;
typedef int DataType;
#define Node ElemType
#define ERROR NULL
//
class Node
{
public:
int data; //
Node * next; //
};
//
class LinkList
{
public:
LinkList(); // ;
~LinkList(); // ;
void CreateLinkList(int n); //
void TravalLinkList(); //
int GetLength(); //
bool IsEmpty(); //
ElemType * Find(DataType data); //
void InsertElemAtEnd(DataType data); //
void InsertElemAtIndex(DataType data,int n); //
void InsertElemAtHead(DataType data); //
void DeleteElemAtEnd(); //
void DeleteAll(); //
void DeleteElemAtPoint(DataType data); //
void DeleteElemAtHead(); //
private:
ElemType * head; //
};
//
LinkList::LinkList()
{
head = new ElemType;
head->data = 0; // 0
head->next = NULL; // NULL
}
//
LinkList::~LinkList()
{
delete head; //
}
//
void LinkList::CreateLinkList(int n)
{
ElemType *pnew, *ptemp;
ptemp = head;
if (n < 0) { // ，
cout << " " << endl;
exit(EXIT_FAILURE);
}
for (int i = 0; i < n;i++) { //
pnew = new ElemType;
cout << " " << i + 1 << " : " ;
cin >> pnew->data;
pnew->next = NULL; // NULL
ptemp->next = pnew; //
ptemp = pnew; //
}
}
//
void LinkList::TravalLinkList()
{
if (head == NULL || head->next ==NULL) {
cout << " " << endl;
}
ElemType *p = head; //
while (p->next != NULL) // ， p
{
p = p->next; //p p
cout << p->data << " ";
}
}
//
int LinkList::GetLength()
{
int count = 0; // count
ElemType *p = head->next; // p
while (p != NULL) // ，count+1
{
count++;
p = p->next; //p p
}
return count; // count
}
//
bool LinkList::IsEmpty()
{
if (head->next == NULL) {
return true;
}
return false;
}
//
ElemType * LinkList::Find(DataType data)
{
ElemType * p = head;
if (p == NULL) { // ，
cout << " " << endl;
return ERROR;
}
else
{
while (p->next != NULL) //
{
if (p->data == data) {
return p; //
}
p = p->next;
}
return NULL; //
}
}
//
void LinkList::InsertElemAtEnd(DataType data)
{
ElemType * newNode = new ElemType; // Node newNode
newNode->next = NULL; // newNode
newNode->data = data;
ElemType * p = head; // p
if (head == NULL) { // ， newNode
head = newNode;
}
else // ， newNode
{
while (p->next != NULL)
{
p = p->next;
}
p->next = newNode;
}
}
//
void LinkList::InsertElemAtIndex(DataType data,int n)
{
if (n<1 || n>GetLength()) //
cout << " " << endl;
else
{
ElemType * ptemp = new ElemType; //
ptemp->data = data; //
ElemType * p = head; //
int i = 1;
while (n > i) //
{
p = p->next;
i++;
}
ptemp->next = p->next; //
p->next = ptemp;
}
}
//
void LinkList::InsertElemAtHead(DataType data)
{
ElemType * newNode = new ElemType; // Node newNode
newNode->data = data;
ElemType * p = head; // p
if (head == NULL) { // ， newNode
head = newNode;
}
newNode->next = p->next; //
p->next = newNode;
}
//
void LinkList::DeleteElemAtEnd()
{
ElemType * p = head; //
ElemType * ptemp = NULL; //
if (p->next == NULL) { //
cout << " " << endl;
}
else
{
while (p->next != NULL) //
{
ptemp = p; // ptemp
p = p->next; //p
}
delete p; //
p = NULL;
ptemp->next = NULL;
}
}
//
void LinkList::DeleteAll()
{
ElemType * p = head->next;
ElemType * ptemp = new ElemType;
while (p != NULL) //
{
ptemp = p;
p = p->next;
head->next = p;
ptemp->next = NULL;
delete ptemp;
}
head->next = NULL; // NULL
}
//
void LinkList::DeleteElemAtPoint(DataType data)
{
ElemType * ptemp = Find(data); //
if (ptemp == head->next) { // ，
DeleteElemAtHead();
}
else
{
ElemType * p = head; //p
while (p->next != ptemp) //p
{
p = p->next;
}
p->next = ptemp->next; //
delete ptemp;
ptemp = NULL;
}
}
//
void LinkList::DeleteElemAtHead()
{
ElemType * p = head;
if (p == NULL || p->next == NULL) { // ，
cout << " " << endl;
}
else
{
ElemType * ptemp = NULL; //
p = p->next;
ptemp = p->next; //
delete p; //
p = NULL;
head->next = ptemp; //
}
}
//
int main()
{
LinkList l;
int i;
cout << "1. 2. 3. 4. 5.
";
cout << "6. 7. 8.
";
cout<> i;
switch (i)
{
case 1:
int n;
cout << " : ";
cin >> n;
l.CreateLinkList(n);
break;
case 2:
l.TravalLinkList();
break;
case 3:
cout << " " << l.GetLength() << endl;
break;
case 4:
if (l.IsEmpty() == 1)
cout << " " << endl;
else
{
cout << " " << endl;
}
break;
case 5:
DataType data;
cout << " : ";
cin >> data;
cout << " " << l.Find(data)->data << endl;
break;
case 6:
DataType endData;
cout << " : ";
cin >> endData;
l.InsertElemAtEnd(endData);
break;
case 7:
DataType pointData;
int index;
cout << " : ";
cin >> pointData;
cout << " : ";
cin >> index;
l.InsertElemAtIndex(pointData, index);
break;
case 8:
DataType headData;
cout << " : ";
cin >> headData;
l.InsertElemAtHead(headData);
break;
case 9:
l.DeleteElemAtEnd();
break;
case 10:
l.DeleteAll();
break;
case 11:
DataType pointDeleteData;
cout << " : ";
cin >> pointDeleteData;
l.DeleteElemAtPoint(pointDeleteData);
break;
case 12:
l.DeleteElemAtHead();
break;
default:
break;
}
}while (i != 0);
system("pause");
return 0;
} 積み重ねる.