数据布局练手02 双向链表实现
添加时间:2013-5-23 点击量:
双向链表实现
今天晚上用模板办法把双向链表实现了下，因为有点小粗心，在 中手抖了下，把tail->prev 打成了 tail->next，因为错误是产生在drop函数履行时，让我一向去调drop函数，调了半天还是一样错误，最后我体系在vs中把守了下值的变更，终于看到是失足了。 看来法度员离不开调试呀。
别的，昨天说的模板输出重载，我说要在友元的实现时加上 <>， 然则今天我在gcc中测试了下，居然说找不到匹配的函数，导致编译不经由过程，至心蛋疼，vs和g++的差别还至心大，看来改天要好好专研下模板输出重载，知道的伴侣可以或许告诉下。
对数据布局的实现，其实都很简单，思惟就是：
1、定义结点布局类，包含数据域和指针域
2、定义 链表（树，图）布局，此中封装包含几个结点，作为数据接口，因为节点定义指向自身类型的指针，是以而后所有的操纵都环绕这个数据接口进行。
对于双向链表来说，结点定义很简单，一个数据域，一个next指针，默示今后他将指向下一个结点； 一个prev指针，默示它将指向前一个结点。
template<typename T>
struct Node{
T datum;
Node next;
Node prev;
};
因为链式布局添加的结点都要new出来，且结点类包含了数据域，是以须要对结点类进行机关函数的编写，一般两个，带数据域的（今后new来做链表中结点），默认无参的（用于new给head和tail的）；析构函数就不消了，因为其指针域所指向的器材是由表布局new出来的，操纵应当留给表。
结点类定义好了后，我们定义下链表类，首要项目组就是要包含下 head 指针， tail 指针。
别的，所有的表（树，图布局）好包含个 “默示长度的数据”，如size， 如许求length（）操纵只要O（1）的错杂度，要不然就要遍历全部链表，错杂度就是O（n）了。
对于head指针，规定 head->next 指向第一个结点，head->prev 指向自身或NULL;
对于tail指针，规定 tail->prev 指向最后一个结点，tail->next指向自身或NULL; 如许规定了head，tail后，后面的操纵就会很顺畅，我们就可以next/prev到底了，哈哈。
空的前提为： size == 0 或者 head->next == NULL 或者 tail->prev == NULL ，看小我爱好。
剩下一些增删改查操纵，别手抖写错了指向关系就行，别的可以加上一个地位断定，看看是从头或从尾开端，哪边移动的少。
函数写法可以给的建议是:
若只是接见不批改，成员函数为const;
若须要操纵类类型，则用 & 或 const&;
好的，直接上代码：
先是头文件，重视最后一行；
1 ＃ifndef MY_CHAIN_H
2 ＃define MY_CHAIN_H
3 ＃include <ostream>
4 using namespace std;
5 template <class T>
6 struct Node{
7 T datum;
8 Node prev;
9 Node next;
10
11 Node（const T& x）;
12 Node（）;
13 };
14
15
16 template<class T>
17 class dList{
18 public:
19 dList（）;
20 ~dList（）;
21 bool find（int pos，T& hold） const;
22 int search（const T& x） const;
23 int length（） const;
24 bool isEmpty（） const;
25 dList<T>& drop（int pos， T& hold）;
26 dList<T>& （int pos， const T& x）;
27 dList<T>& push_back（const T& x）;
28 dList<T>& push_front（const T& x）;
29 T& operator[]（int pos）;
30 void show（std::ostream& os） const;
31 friend ostream& operator<< <>（ostream& os， const dList& d）;
32 protected:
33 Node<T> head;
34 Node<T> tail;
35 int size;
36 };
37 ＃endif
38
39 ＃include chain.cpp
View Code
接着是实现文件：
＃ifndef MY_CHAIN_CPP
＃define MY_CHAIN_CPP
＃include chain.h
＃include <ostream>
＃include <cassert>
using std::ostream;
// 节点类的机关
template<class T>
Node<T>::Node（const T& x） : datum（x）{
next = prev = NULL;
}
template<class T>
Node<T>::Node（）{
next = prev = NULL;
datum = 0;
}
// 双向链表类的机关
template<class T>
dList<T>::dList（）
{
head = new Node<T>（）;
// tail = new Node<T>（）;
head->next = NULL;
head->prev = head;
tail = head;
tail->next = tail;
tail->prev = NULL;
size = 0;
}
// 析构
template<typename T>
dList<T>::~dList（）
{
if（head）{ // 一个建议，若类中数据成员是指针类型，且指向是经由过程new出来的，那么好这里加上一个断定。 当然我这里是多余的，因为机关时必定new了。
Node<T> p = head->next;
Node<T> t;
while（p != NULL）{
t = p;
p = p->next;
t;
}
head;
head = NULL; // 好删除后指向空
tail = NULL;
}
}
template<class T>
bool dList<T>::isEmpty（） const
{
return size == 0;
}
template<class T>
bool dList<T>::find（int pos，T& hold） const // 接见不批改，成员函数const
{
if（pos < 1 || pos > size） return false;
Node<T> p;
if（pos <= （size>>1））{ // 从头开端斗劲快
p = head;
int count = pos;
while（count--）{p = p->next;} // next 给 head
}else{
p = tail; // 从尾开端斗劲快
int count = size - pos;
while（count--）{p = p->prev;} // 哈哈，中就是为什么把prev给tail， 代码是不是很顺畅？
}
hold = p->datum;
return true;
}
template<class T>
int dList<T>::search （const T& x） const
{
Node<T> p = head->next;
int count = 1;
while（（p!= NULL） && （p->datum != x））{
p = p->next;
count++;
}
if （p == NULL） {
return 0;
}
return count;
}
template<class T>
int dList<T>::length （）const
{
return size;
}
template<class T>
dList<T>& dList<T>::push_front （const T& x） // 前插
{
Node<T> p = new Node<T>（x）;
if （size == 0） {
head->next = p;
p->prev = NULL;
tail->prev = p;
p->next = NULL;
}else{
p->next = head->next;
head->next->prev = p;
p->prev = NULL;
head->next = p;
}
++size;
return this;
}
template<class T>
dList<T>& dList<T>::push_back （const T& x） // 尾插
{
Node<T> p = new Node<T>（x）;
if （tail->prev == NULL） {
head->next = p;
p->prev = NULL;
tail->prev = p;
p->next = NULL;
}else{
tail->prev->next = p;
p->prev = tail->prev;
p->next = NULL;
tail->prev = p;
}
++size;
return this;
}
template<class T>
dList<T>& dList<T>::（int pos， const T& x） // 指定地位插入，局限[1，size+1] 重视，我的代码中，1为下标开端；除了后边重载的[]操纵符。
{
if （pos == 1） {
return push_front （x）;
}
if （pos == （size+1）） {
return push_back （x）;
}
Node<T> in = new Node<T>（x）;
Node<T> p;
if （pos <= （size/2）） {
p = head;
int t = pos;
while（t--）{p = p->next;}
}else{
p = tail;
int t = size - pos;
while（t--）{p = p->prev;}
}
in->next = p;
in->prev = p->prev; // 哎，这里就是我万恶粗心的处所，Mark下，下次要心细点。
p->prev->next = in;
p->prev = in;
++size;
return this;
}
template<class T>
dList<T>& dList<T>::drop（int pos， T& hold）
{
if （pos < 1 || pos > size） {
exit（1）;
}
Node<T> d = NULL;
if（pos == 1）{
d = head->next;
hold = d->datum;
if（size == 1）{
tail->prev = NULL;
head->next = NULL;
}else{
head->next = d->next;
d->next->prev = NULL;
}
--size;
d;
d = NULL;
return this;
}
if（pos == size）{
d = tail->prev;
hold = d->datum;
tail->prev = d->prev;
d->prev->next = NULL;
size--;
d;
d = NULL;
return this;
}else{
if（pos <= （size/2））{
int c=pos;
d = head;
while（c--）{d = d->next;}
}else{
int c = size - pos;
d = tail;
while（c--）{d = d->prev;}
}
hold = d->datum;
d->prev->next = d->next;
d->next->prev = d->prev;
--size;
d;
d = NULL;
return this;
}
}
template<class T>
T& dList<T>::operator[]（int pos）
{
pos = pos + 1;
if（pos<1 || pos> size） {
exit（1）;
}
Node<T> p = NULL;
if （pos <= （size>>1）） {
int t = pos;
p = head;
while（t--）{p = p->next;}
}else{
int t = size - pos;
p = tail;
while （t--） { p = p->prev;}
}
return p->datum;
}
template<class T>
void dList<T>::show （ostream& os） const
{
Node<T> p = head->next;
int t = 0;
while（p != NULL）{
os << p->datum << ;
p = p->next;
t++;
}
assert（t==size）;
}
template<class T>
ostream& operator<< <>（ostream& out， const dList<T>& x）
{
x.show（out）;
return out;
}
＃endif
View Code
最后是测试文件：
1 ＃include chain.h
2 ＃include <iostream>
3 using namespace std;
4
5 int main（）
6 {
7 dList<int> dl;
8 int x=0;
9 dl. （1，5）;
10 cout << pos1 5: << dl << endl;
11 cout << length: << dl.length（） << endl;
12 dl.push_front （3）;
13 cout << push front 3: << dl << endl;
14 cout << length: << dl.length（） << endl;
15 dl.push_back （6）;
16 cout << push back 6: << dl << endl;
17 cout << length: << dl.length（） << endl;
18 dl.（4，8）;
19 cout << pos4 8: << dl << endl;
20 cout << length= << dl.length （） << endl;
21 dl.find （3，x）;
22 dl.drop（2，x）;
23 cout << drop pos 2: << dl << endl;
24 cout << length= << dl.length （） << endl;
25 cout << dl[0]= << dl[0] << endl;
26 dl[0] = 10;
27 cout << dl[0]= << dl[0] << endl;
28 cout << dl << endl;
29 }
View Code
成果如下图所示：
补充： 其实还可以重载更多的操纵符，有表情的伴侣可以本身添加下，比如++（int）， ++操纵等。甚至，可以参加个迭代器类，如许更便利应用，有时候可以实现下哦。
别的，心细，心细，手别抖。 自勉下！
无论对感情还是对生活，“只要甜不要苦”都是任性而孩子气的，因为我们也不完美，我们也会伤害人。正因为我们都不完美，也因为生活从不是事事如意，所以对这些“瑕疵”的收纳才让我们对生活、对他人的爱变得日益真实而具体。—— 汪冰《世界再亏欠你，也要敢于拥抱幸福》
双向链表实现
今天晚上用模板办法把双向链表实现了下，因为有点小粗心，在 中手抖了下，把tail->prev 打成了 tail->next，因为错误是产生在drop函数履行时，让我一向去调drop函数，调了半天还是一样错误，最后我体系在vs中把守了下值的变更，终于看到是失足了。 看来法度员离不开调试呀。
别的，昨天说的模板输出重载，我说要在友元的实现时加上 <>， 然则今天我在gcc中测试了下，居然说找不到匹配的函数，导致编译不经由过程，至心蛋疼，vs和g++的差别还至心大，看来改天要好好专研下模板输出重载，知道的伴侣可以或许告诉下。
对数据布局的实现，其实都很简单，思惟就是：
1、定义结点布局类，包含数据域和指针域
2、定义 链表（树，图）布局，此中封装包含几个结点，作为数据接口，因为节点定义指向自身类型的指针，是以而后所有的操纵都环绕这个数据接口进行。
对于双向链表来说，结点定义很简单，一个数据域，一个next指针，默示今后他将指向下一个结点； 一个prev指针，默示它将指向前一个结点。
template<typename T>
struct Node{
T datum;
Node next;
Node prev;
};
因为链式布局添加的结点都要new出来，且结点类包含了数据域，是以须要对结点类进行机关函数的编写，一般两个，带数据域的（今后new来做链表中结点），默认无参的（用于new给head和tail的）；析构函数就不消了，因为其指针域所指向的器材是由表布局new出来的，操纵应当留给表。
结点类定义好了后，我们定义下链表类，首要项目组就是要包含下 head 指针， tail 指针。
别的，所有的表（树，图布局）好包含个 “默示长度的数据”，如size， 如许求length（）操纵只要O（1）的错杂度，要不然就要遍历全部链表，错杂度就是O（n）了。
对于head指针，规定 head->next 指向第一个结点，head->prev 指向自身或NULL;
对于tail指针，规定 tail->prev 指向最后一个结点，tail->next指向自身或NULL; 如许规定了head，tail后，后面的操纵就会很顺畅，我们就可以next/prev到底了，哈哈。
空的前提为： size == 0 或者 head->next == NULL 或者 tail->prev == NULL ，看小我爱好。
剩下一些增删改查操纵，别手抖写错了指向关系就行，别的可以加上一个地位断定，看看是从头或从尾开端，哪边移动的少。
函数写法可以给的建议是:
若只是接见不批改，成员函数为const;
若须要操纵类类型，则用 & 或 const&;
好的，直接上代码：
先是头文件，重视最后一行；
1 ＃ifndef MY_CHAIN_H
2 ＃define MY_CHAIN_H
3 ＃include <ostream>
4 using namespace std;
5 template <class T>
6 struct Node{
7 T datum;
8 Node prev;
9 Node next;
10
11 Node（const T& x）;
12 Node（）;
13 };
14
15
16 template<class T>
17 class dList{
18 public:
19 dList（）;
20 ~dList（）;
21 bool find（int pos，T& hold） const;
22 int search（const T& x） const;
23 int length（） const;
24 bool isEmpty（） const;
25 dList<T>& drop（int pos， T& hold）;
26 dList<T>& （int pos， const T& x）;
27 dList<T>& push_back（const T& x）;
28 dList<T>& push_front（const T& x）;
29 T& operator[]（int pos）;
30 void show（std::ostream& os） const;
31 friend ostream& operator<< <>（ostream& os， const dList& d）;
32 protected:
33 Node<T> head;
34 Node<T> tail;
35 int size;
36 };
37 ＃endif
38
39 ＃include chain.cpp
View Code
接着是实现文件：
＃ifndef MY_CHAIN_CPP
＃define MY_CHAIN_CPP
＃include chain.h
＃include <ostream>
＃include <cassert>
using std::ostream;
// 节点类的机关
template<class T>
Node<T>::Node（const T& x） : datum（x）{
next = prev = NULL;
}
template<class T>
Node<T>::Node（）{
next = prev = NULL;
datum = 0;
}
// 双向链表类的机关
template<class T>
dList<T>::dList（）
{
head = new Node<T>（）;
// tail = new Node<T>（）;
head->next = NULL;
head->prev = head;
tail = head;
tail->next = tail;
tail->prev = NULL;
size = 0;
}
// 析构
template<typename T>
dList<T>::~dList（）
{
if（head）{ // 一个建议，若类中数据成员是指针类型，且指向是经由过程new出来的，那么好这里加上一个断定。 当然我这里是多余的，因为机关时必定new了。
Node<T> p = head->next;
Node<T> t;
while（p != NULL）{
t = p;
p = p->next;
t;
}
head;
head = NULL; // 好删除后指向空
tail = NULL;
}
}
template<class T>
bool dList<T>::isEmpty（） const
{
return size == 0;
}
template<class T>
bool dList<T>::find（int pos，T& hold） const // 接见不批改，成员函数const
{
if（pos < 1 || pos > size） return false;
Node<T> p;
if（pos <= （size>>1））{ // 从头开端斗劲快
p = head;
int count = pos;
while（count--）{p = p->next;} // next 给 head
}else{
p = tail; // 从尾开端斗劲快
int count = size - pos;
while（count--）{p = p->prev;} // 哈哈，中就是为什么把prev给tail， 代码是不是很顺畅？
}
hold = p->datum;
return true;
}
template<class T>
int dList<T>::search （const T& x） const
{
Node<T> p = head->next;
int count = 1;
while（（p!= NULL） && （p->datum != x））{
p = p->next;
count++;
}
if （p == NULL） {
return 0;
}
return count;
}
template<class T>
int dList<T>::length （）const
{
return size;
}
template<class T>
dList<T>& dList<T>::push_front （const T& x） // 前插
{
Node<T> p = new Node<T>（x）;
if （size == 0） {
head->next = p;
p->prev = NULL;
tail->prev = p;
p->next = NULL;
}else{
p->next = head->next;
head->next->prev = p;
p->prev = NULL;
head->next = p;
}
++size;
return this;
}
template<class T>
dList<T>& dList<T>::push_back （const T& x） // 尾插
{
Node<T> p = new Node<T>（x）;
if （tail->prev == NULL） {
head->next = p;
p->prev = NULL;
tail->prev = p;
p->next = NULL;
}else{
tail->prev->next = p;
p->prev = tail->prev;
p->next = NULL;
tail->prev = p;
}
++size;
return this;
}
template<class T>
dList<T>& dList<T>::（int pos， const T& x） // 指定地位插入，局限[1，size+1] 重视，我的代码中，1为下标开端；除了后边重载的[]操纵符。
{
if （pos == 1） {
return push_front （x）;
}
if （pos == （size+1）） {
return push_back （x）;
}
Node<T> in = new Node<T>（x）;
Node<T> p;
if （pos <= （size/2）） {
p = head;
int t = pos;
while（t--）{p = p->next;}
}else{
p = tail;
int t = size - pos;
while（t--）{p = p->prev;}
}
in->next = p;
in->prev = p->prev; // 哎，这里就是我万恶粗心的处所，Mark下，下次要心细点。
p->prev->next = in;
p->prev = in;
++size;
return this;
}
template<class T>
dList<T>& dList<T>::drop（int pos， T& hold）
{
if （pos < 1 || pos > size） {
exit（1）;
}
Node<T> d = NULL;
if（pos == 1）{
d = head->next;
hold = d->datum;
if（size == 1）{
tail->prev = NULL;
head->next = NULL;
}else{
head->next = d->next;
d->next->prev = NULL;
}
--size;
d;
d = NULL;
return this;
}
if（pos == size）{
d = tail->prev;
hold = d->datum;
tail->prev = d->prev;
d->prev->next = NULL;
size--;
d;
d = NULL;
return this;
}else{
if（pos <= （size/2））{
int c=pos;
d = head;
while（c--）{d = d->next;}
}else{
int c = size - pos;
d = tail;
while（c--）{d = d->prev;}
}
hold = d->datum;
d->prev->next = d->next;
d->next->prev = d->prev;
--size;
d;
d = NULL;
return this;
}
}
template<class T>
T& dList<T>::operator[]（int pos）
{
pos = pos + 1;
if（pos<1 || pos> size） {
exit（1）;
}
Node<T> p = NULL;
if （pos <= （size>>1）） {
int t = pos;
p = head;
while（t--）{p = p->next;}
}else{
int t = size - pos;
p = tail;
while （t--） { p = p->prev;}
}
return p->datum;
}
template<class T>
void dList<T>::show （ostream& os） const
{
Node<T> p = head->next;
int t = 0;
while（p != NULL）{
os << p->datum << ;
p = p->next;
t++;
}
assert（t==size）;
}
template<class T>
ostream& operator<< <>（ostream& out， const dList<T>& x）
{
x.show（out）;
return out;
}
＃endif
View Code
最后是测试文件：
1 ＃include chain.h
2 ＃include <iostream>
3 using namespace std;
4
5 int main（）
6 {
7 dList<int> dl;
8 int x=0;
9 dl. （1，5）;
10 cout << pos1 5: << dl << endl;
11 cout << length: << dl.length（） << endl;
12 dl.push_front （3）;
13 cout << push front 3: << dl << endl;
14 cout << length: << dl.length（） << endl;
15 dl.push_back （6）;
16 cout << push back 6: << dl << endl;
17 cout << length: << dl.length（） << endl;
18 dl.（4，8）;
19 cout << pos4 8: << dl << endl;
20 cout << length= << dl.length （） << endl;
21 dl.find （3，x）;
22 dl.drop（2，x）;
23 cout << drop pos 2: << dl << endl;
24 cout << length= << dl.length （） << endl;
25 cout << dl[0]= << dl[0] << endl;
26 dl[0] = 10;
27 cout << dl[0]= << dl[0] << endl;
28 cout << dl << endl;
29 }
View Code
成果如下图所示：
补充： 其实还可以重载更多的操纵符，有表情的伴侣可以本身添加下，比如++（int）， ++操纵等。甚至，可以参加个迭代器类，如许更便利应用，有时候可以实现下哦。
别的，心细，心细，手别抖。 自勉下！
无论对感情还是对生活，“只要甜不要苦”都是任性而孩子气的，因为我们也不完美，我们也会伤害人。正因为我们都不完美，也因为生活从不是事事如意，所以对这些“瑕疵”的收纳才让我们对生活、对他人的爱变得日益真实而具体。—— 汪冰《世界再亏欠你，也要敢于拥抱幸福》
