データ構造とアルゴリズム——一方向チェーンテーブルADT(C++)
15426 ワード
この一方向チェーンテーブルクラス名はLinked_list.
1.Linked_Listクラスの基本データメンバー:
一方向チェーンテーブルクラスLinked_Listの基本データメンバーには、チェーンヘッダノードへのポインタheadと、チェーンテーブルのノード数sizeが含まれます.以下に示します.
ここで、チェーンテーブルノードノードノードノードノードのクラスは以下のように実装される.
2.Linked_Listクラスのメンバー関数:
Linked_Listクラスのメンバー関数は次のとおりです.
3.Linked_Listクラスメンバー関数の実装:
Linked_Listクラスメンバー関数の実装、実装の詳細、注意すべきポイントについては、コメントを参照してください.
4.ADTソースコード:
1.Linked_Listクラスの基本データメンバー:
一方向チェーンテーブルクラスLinked_Listの基本データメンバーには、チェーンヘッダノードへのポインタheadと、チェーンテーブルのノード数sizeが含まれます.以下に示します.
Node *head; //
int size; // ここで、チェーンテーブルノードノードノードノードノードのクラスは以下のように実装される.
struct Node
{
int data;
Node *next=NULL;
Node(int nums):data(nums),next(NULL)
{
}
};
2.Linked_Listクラスのメンバー関数:
Linked_Listクラスのメンバー関数は次のとおりです.
//
Linked_list(); // ：
Linked_list(int nums[],int size); // ：
Linked_list(const Linked_list &other); //
//
Linked_list operator= (const Linked_list &other); //
Linked_list operator+ (const Linked_list &other); // ：
//
Node *search_by_content(int target); //
int search_by_position(int pos); //
//
bool insert_by_position(int nums,int pos); //
void insert_back(int nums); //
//
bool delete_by_content(int nums); //
bool delete_by_position(int pos); //
//
void reverse(); //
void clean(); //
int count(); //
void print(); // 3.Linked_Listクラスメンバー関数の実装:
Linked_Listクラスメンバー関数の実装、実装の詳細、注意すべきポイントについては、コメントを参照してください.
Linked_list::Linked_list() // ：
{
size=0;
head=NULL;
}
Linked_list::Linked_list(int nums[],int isize) // ：
{
// insert_back ，
// insert_back ， head=NULL，size=0， insert_back
head=NULL;
size=0;
for(int i=0;idata); //
now=now->next;
}
}
Linked_list Linked_list::operator= (const Linked_list &other) //
{
// ，
if(size) // ， ，
(*this).clean();
Node *now=other.head;
while(now!=NULL)
{
(*this).insert_back(now->data);
now=now->next;
}
size=other.size;
return (*this);
}
Linked_list Linked_list::operator+ (const Linked_list &other) // ：
{
Node *now=other.head;
while(now!=NULL)
{
(*this).insert_back(now->data);
now=now->next;
}
size+=other.size;
return (*this);
}
Node *Linked_list::search_by_content(int target) //
{
Node *now=head;
while(now!=NULL)
{
if(now->data==target)
return now;
now=now->next;
}
return NULL;
}
int Linked_list::search_by_position(int pos) //
{
if(pos>=size)
return INT_MAX; // INT_MAX
if(pos<0)
return INT_MIN; // INT_MAX
Node *now=head;
for(int i=0;inext;
}
return now->data;
}
bool Linked_list::insert_by_position(int nums,int pos) //
{
//
if(pos>size||pos<0)
return false;
// ： pos=0， ，
else if(!pos)
{
Node *temp=head;
head=new Node(nums);
head->next=temp;
}
// ： pos=size，
else if(pos==size)
{
Node *now=head;
while(now->next)
{
now=now->next;
}
now->next=new Node(nums);
}
else
{
Node *back=head;
for(int i=0;inext;
}
Node *now=new Node(nums);
Node *next=back->next;
back->next=now;
now->next=next;
}
size++;
return true;
}
void Linked_list::insert_back(int nums) //
{
// ： ，
if(head==NULL)
{
head=new Node(nums);
}
else
{
Node *now=head;
while(now->next)
{
now=now->next;
}
now->next=new Node(nums);
}
size++;
}
bool Linked_list::delete_by_content(int nums) //
{
bool flag=false;
Node *now=head;
while(now)
{
if(now->data==nums)
{
flag=1;
//
if(now==head) // ：
{
Node *pre_del=head;
head=now;
size--;
delete pre_del;
}
else // ：
{
//
Node *back=head;
while(back->next!=now)
{
back=back->next;
}
//
back->next=now->next;
Node *pre_del=now;
size--;
delete pre_del;
}
}
now=now->next; // now=now->next
}
return flag;
}
bool Linked_list::delete_by_position(int pos) //
{
// ， ：
if(pos<0||pos>=size)
return false;
else if(pos==0) // ：
{
if(size==1) // ：
{
delete head;
head=NULL;
size=0;
}
else
{
Node *pre_del=head;
head=head->next;
size--;
delete pre_del;
}
}
else
{
Node *back=head;
Node *now=head->next;
for(int i=0;inext;
now=now->next;
}
back->next=now->next;
size--;
delete now;
}
return true;
}
void Linked_list::reverse() //
{
// ：
if(head==NULL) // ：
return;
Node *back=head;
Node *now=head->next;
while(now)
{
Node *temp=now->next; //
//
now->next=back;
//
back=now;
now=temp;
}
// ， back
// （ ） next
head->next=NULL;
head=back;
return;
}
void Linked_list::clean() //
{
Node *now=head;
while(now)
{
Node *temp=now;
now=now->next;
delete temp;
}
size=0;
head=NULL;
}
int Linked_list::count() //
{
return size;
}
void Linked_list::print() //
{
Node *now=head;
while(now)
{
cout<data<next;
}
cout< 4.ADTソースコード:
#include
#include
using namespace std;
struct Node
{
int data;
Node *next=NULL;
Node(int nums):data(nums),next(NULL)
{
}
};
class Linked_list
{
public:
//
Linked_list(); // ：
Linked_list(int nums[],int size); // ：
Linked_list(const Linked_list &other); //
//
Linked_list operator= (const Linked_list &other); //
Linked_list operator+ (const Linked_list &other); // ：
//
Node *search_by_content(int target); //
int search_by_position(int pos); //
//
bool insert_by_position(int nums,int pos); //
void insert_back(int nums); //
//
bool delete_by_content(int nums); //
bool delete_by_position(int pos); //
//
void reverse(); //
void clean(); //
int count(); //
void print(); //
private:
Node *head; //
int size; //
};
Linked_list::Linked_list() // ：
{
size=0;
head=NULL;
}
Linked_list::Linked_list(int nums[],int isize) // ：
{
// insert_back ，
// insert_back ， head=NULL，size=0， insert_back
head=NULL;
size=0;
for(int i=0;idata); //
now=now->next;
}
}
Linked_list Linked_list::operator= (const Linked_list &other) //
{
// ，
if(size) // ， ，
(*this).clean();
Node *now=other.head;
while(now!=NULL)
{
(*this).insert_back(now->data);
now=now->next;
}
size=other.size;
return (*this);
}
Linked_list Linked_list::operator+ (const Linked_list &other) // ：
{
Node *now=other.head;
while(now!=NULL)
{
(*this).insert_back(now->data);
now=now->next;
}
size+=other.size;
return (*this);
}
Node *Linked_list::search_by_content(int target) //
{
Node *now=head;
while(now!=NULL)
{
if(now->data==target)
return now;
now=now->next;
}
return NULL;
}
int Linked_list::search_by_position(int pos) //
{
if(pos>=size)
return INT_MAX; // INT_MAX
if(pos<0)
return INT_MIN; // INT_MAX
Node *now=head;
for(int i=0;inext;
}
return now->data;
}
bool Linked_list::insert_by_position(int nums,int pos) //
{
//
if(pos>size||pos<0)
return false;
// ： pos=0， ，
else if(!pos)
{
Node *temp=head;
head=new Node(nums);
head->next=temp;
}
// ： pos=size，
else if(pos==size)
{
Node *now=head;
while(now->next)
{
now=now->next;
}
now->next=new Node(nums);
}
else
{
Node *back=head;
for(int i=0;inext;
}
Node *now=new Node(nums);
Node *next=back->next;
back->next=now;
now->next=next;
}
size++;
return true;
}
void Linked_list::insert_back(int nums) //
{
// ： ，
if(head==NULL)
{
head=new Node(nums);
}
else
{
Node *now=head;
while(now->next)
{
now=now->next;
}
now->next=new Node(nums);
}
size++;
}
bool Linked_list::delete_by_content(int nums) //
{
bool flag=false;
Node *now=head;
while(now)
{
if(now->data==nums)
{
flag=1;
//
if(now==head) // ：
{
Node *pre_del=head;
head=now;
size--;
delete pre_del;
}
else // ：
{
//
Node *back=head;
while(back->next!=now)
{
back=back->next;
}
//
back->next=now->next;
Node *pre_del=now;
size--;
delete pre_del;
}
}
now=now->next; // now=now->next
}
return flag;
}
bool Linked_list::delete_by_position(int pos) //
{
// ， ：
if(pos<0||pos>=size)
return false;
else if(pos==0) // ：
{
if(size==1) // ：
{
delete head;
head=NULL;
size=0;
}
else
{
Node *pre_del=head;
head=head->next;
size--;
delete pre_del;
}
}
else
{
Node *back=head;
Node *now=head->next;
for(int i=0;inext;
now=now->next;
}
back->next=now->next;
size--;
delete now;
}
return true;
}
void Linked_list::reverse() //
{
// ：
if(head==NULL) // ：
return;
Node *back=head;
Node *now=head->next;
while(now)
{
Node *temp=now->next; //
//
now->next=back;
//
back=now;
now=temp;
}
// ， back
// （ ） next
head->next=NULL;
head=back;
return;
}
void Linked_list::clean() //
{
Node *now=head;
while(now)
{
Node *temp=now;
now=now->next;
delete temp;
}
size=0;
head=NULL;
}
int Linked_list::count() //
{
return size;
}
void Linked_list::print() //
{
Node *now=head;
while(now)
{
cout<data<next;
}
cout<data<data<