雙向鏈表（C++實現）

雙向鏈表（C++實現）

List.h

//////////////////////////////////////////////////////////////////////////////////////
/////// 這裡建立兩個類，一個節點類和一個List類，與單鏈表不同的是雙向鏈表的節點要多一
////// 個前驅指針,相應的，雙向鏈表函數實現要與單鏈表實現有所差異

typedef int DataType;

//struct LinkNode //節點類（復合形態）
//{
// friend class SList;
//將SList設為友元，便於SList類可以訪問節點類的私有成員
//public:
// LinkNode(const DataType x);
//private:
// DataType _data; //節點的數據
// LinkNode* _next; //指向該節點的下一個節點
// LinkNode* _prev; //指向該節點的前一個節點
//};

//直接用struct定義LinkNode類，因為struct的成員默認為公有數據成員，所以可直接訪問
struct LinkNode //節點類(建議寫法)
{
LinkNode(const DataType x);
DataType _data; //節點的數據
LinkNode* _next; //後繼指針
LinkNode* _prev; //前驅指針
};

class List //鏈表類
{
public:
List(); //構造函數
List(const List& s); //拷貝構造
List &operator=(List& s); //賦值運算符的重載
~List();

public:
void Reverse();
void Swap(List& s);
void PrintSList(); //打印鏈表
void PushBack(const DataType& x); //在尾部插入一個節點
void Clear(); //鏈表置空
void PopBack();
void PushFront(DataType x); //頭插
void PopFront(); //刪除首節點
void Insert(LinkNode* pos, DataType x);//固定位置插入一個節點
void Erase(LinkNode* pos); //刪除某一節點
LinkNode* Find(DataType x); //查找節點並返回這個節點的地址
int Amount(); //計算鏈表節點的數目
void Remove(DataType x); //查找某節點並刪除

private:
LinkNode* _head; //指向頭結點
LinkNode* _tail; //指向尾節點
};

List.cpp

#include<iostream>
using namespace std;
#include<assert.h>
#include"List.h"

//節點類構造函數*
LinkNode::LinkNode(const DataType x)
:_data(x)
, _next(NULL)
, _prev(NULL)
{}

//鏈表類*
List::List() //構造函數
: _head(NULL)
, _tail(NULL)
{}

List::List(const List& s) //拷貝構造
: _head(NULL)
, _tail(NULL)
{
if (s._head == NULL)
{
return;
}
LinkNode* tmp = s._head;
while (tmp)
{
PushBack(tmp->_data);
tmp = tmp->_next;
}

}

//賦值運算符的重載（傳統方法）
//SList & SList::operator=(const SList& s)
//{
// if (this != &s)
// {
// _head = NULL;
// _tail = NULL;
// LinkNode* tmp = s._head;
// do{
// PushBack(tmp->_data);
// tmp = tmp->_next;
// } while (tmp != s._head);
// }
// return *this;
//}

//賦值運算符的重載（高效寫法）*
/*void SList::Swap(SList& s)
{
swap(_head, s._head);
swap(_tail, s._tail);

}
SList& SList::operator=(SList &s)
{
if (this != &s)
{
SList tmp(s);
Swap(tmp);
}
return *this;
}*/

List& List::operator=(List &s) //賦值運算符的重載再優化(推薦寫法)
{
if (this != &s)
{
swap(_head, s._head);
swap(_tail, s._tail);
}
return *this;
}
List::~List() //析構
{
Clear();
}

void List::Reverse() //鏈表逆置（利用頭插新節點的方法）
{
if (_head == NULL || _head== _tail)
{
return;
}
int ret = Amount();

/* // 方法一（相當於用頭插的方式重新建立鏈表）
_tail = new LinkNode(_head->_data);
LinkNode* begin = NULL;
LinkNode* tmp = _tail;
while (--ret)
{
LinkNode* del = _head;
_head = _head->_next;
delete del;
begin = new LinkNode(_head->_data);
begin->_next = tmp;
tmp->_prev = begin;
tmp = begin;
}
_head = begin;*/

////// 方法二（只是交換對稱位置節點的數據）**（高效）
LinkNode* begin = _head;
LinkNode* end = _tail;
while (ret)
{
if (end->_next == begin)
break;
ret /= 2;
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
}

/*// 方法三 交換前驅和後繼指針
swap(_head, _tail);
LinkNode* cur = _head;
while (cur)
{
swap(cur->_prev,cur->_next);
cur = cur->_next;
}
*/

}

//打印鏈表*
void List::PrintSList()
{
//頭結點為空時，無需打印鏈表
if (_head == NULL)
{
cout << "This SList is Empty !" << endl;
return;
}
else
{
LinkNode* tmp = _head;
while (tmp)
{
cout << tmp->_data << "-->";
tmp = tmp->_next;
}
cout <<"NULL"<< endl;
}
}

void List::PushBack(const DataType& x) //在尾部插入一個節點*
{
//如果鏈表為空，插入節點後只有一個節點，此時_head=_tail
if (_head == NULL)
{
_head = new LinkNode(x);
_tail = _head;
}
else
{
_tail->_next = new LinkNode(x);
_tail->_next->_prev=_tail;
_tail = _tail->_next;
}
}

void List::Clear() //鏈表置空*
{
LinkNode* begin = _head;
while (begin != _tail)
{
_head = _head->_next;
delete begin;
begin = _head;
}
_head = NULL;
_tail = NULL;
}

void List::PopBack() //尾刪
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
}
else if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = NULL;
}
else
{
LinkNode* cur = _head;
while (cur->_next != _tail)
{
cur = cur->_next;
}
delete _tail;
_tail = cur;
_tail->_prev = cur->_prev;
_tail->_next = NULL;
}
}

void List::PushFront(DataType x) //頭插*
{
if (_head == NULL)
{
PushBack(x);
}
else
{
LinkNode* tmp = _head;
_head = new LinkNode(x);
_head->_next = tmp;
tmp->_prev = _head;
}
}

void List::PopFront() //刪除首節點
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return;
}
LinkNode* tmp = _head;
_head = _head->_next;
_head->_prev = NULL;
delete tmp;
}

//固定位置插入一個節點（這個函數需和Find函數搭配使用）
//先用Find函數找到新節點需要插入的位置
//（將Find函數的返回值傳給Insert函數的參數pos），再在pos節點後面插入新節點x
void List::Insert(LinkNode* pos, DataType x) //*
{
assert(pos);
if (pos == _tail)
{
PushBack(x);
}
else
{
LinkNode* tmp = new LinkNode(x);
tmp->_next = pos->_next;
pos->_next = tmp;
tmp->_next->_prev = tmp;
tmp->_prev = pos;
}
}

//刪除某一節點，同樣，要先找到該節點並傳參給Erase函數
void List::Erase(LinkNode* pos)
{
assert(pos);
if (pos == _tail)
{
PopBack();
}
else if (pos == _head)
{
PopFront();
}
else
{
pos->_prev->_next = pos->_next;
pos->_next->_prev = pos->_prev;
delete pos;
}
}

//查找節點並返回這個節點的地址
LinkNode* List::Find(DataType x)
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return NULL;
}
else
{
LinkNode* tmp = _head;
while (tmp != NULL)
{
if (tmp->_data == x)
{
return tmp;
}
tmp = tmp->_next;
}
return NULL;
}
}

int List::Amount() //計算鏈表節點的數目
{
if (_head == NULL)
{
return 0;
}
else
{
int count = 0;
LinkNode* cur = _head;
while (cur != _tail)
{
count++;
cur = cur->_next;
}
return ++count;
}
}

void List::Remove(DataType x) //查找某節點並刪除
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
}
else
{
LinkNode* tmp = Find(x);
if (tmp != NULL)
{
Erase(tmp);
}
}
}

Test.cpp

#include"List.h"
#include<stdlib.h>
#include<iostream>
using namespace std;

void Test1()
{
List list1;
list1.PushBack(1);
list1.PushBack(2);
list1.PushBack(3);
list1.PushBack(4);
list1.PushBack(5);
list1.PushBack(6);
list1.PrintSList();

/* List list2(list1);
list2.PrintSList();*/

List list2=list1;
list2.PrintSList();
//list2.PopBack();
//list2.Clear();
//list2.PushFront(0);
//list2.PopFront();

//////檢驗Find函數
////LinkNode* ret=list2.Find(4);
////if (ret != NULL)
////{
//// cout << "ret:" << ret << " " << ret->_data << endl;
////}
////else
////{
//// cout << "Not exit !" << endl;
////}

/* int ret=list2.Amount();
cout << ret << endl;*/

//list2.Erase(list2.Find(5));
//list2.Insert(list2.Find(2), 0);
//list2.Remove(3);
list2.Reverse();
list2.PrintSList();
}

int main()
{
Test1();
system("pause");
}