前面完成了三個比較完整的鏈表程序。下面就是使用模板類來實現這個鏈表程序了。?

Code
??1#include?<iostream>
??2using?namespace?std;
??3
??4template<typename?T>
??5class?linkedlist;
??6
??7template<typename?T>
??8class?listnode
??9{
?10????friend?class?linkedlist<T>;
?11private:
?12????T?data;
?13????listnode<T>?*next;
?14
?15public:
?16????listnode(T?d,listnode<T>?*n=NULL):data(d),next(n)
?17????{
?18????}
?19????
?20????T?getdata()
?21????{
?22????????return?data;
?23????}
?24};
?25
?26template<typename?T>
?27class?linkedlist
?28{
?29public:
?30????linkedlist();
?31????~linkedlist();
?32????
?33????void?addNode(listnode<T>?*node,?int?pos);
?34????void?deleteNode(int?pos);
?35????void?reverselist();
?36????void?printlist();
?37????listnode<T>*?findNode(int?pos);
?38private:
?39????void?Destroy();
?40private:
?41????listnode<T>?*header;
?42????int?size;
?43};
?44
?45template<typename?T>
?46linkedlist<T>::linkedlist()
?47{
?48????header=NULL;
?49????size=0;
?50}
?51
?52template<typename?T>
?53linkedlist<T>::~linkedlist()
?54{
?55????if(header)
?56????????Destroy();
?57????header=NULL;
?58????size=0;
?59}
?60
?61template<typename?T>
?62void?linkedlist<T>::Destroy()
?63{
?64????listnode<T>*?p=header;
?65????while(p)
?66????{
?67????????listnode<T>?*q=p->next;
?68????????delete?p;
?69????????p=q;
?70????????size--;
?71????}
?72????header=NULL;
?73}
?74
?75template<typename?T>
?76void?linkedlist<T>::addNode(listnode<T>?*node,?int?pos)
?77{
?78????listnode<T>?*tmp=header;
?79????if(pos==0?||?tmp==NULL)
?80????{
?81????????node->next=tmp;
?82????????header=node;
?83????????size++;
?84????}
?85????else
?86????{
?87????????int?cnt=0;
?88????????while(tmp->next?&&?cnt<pos)
?89????????{
?90????????????tmp?=?tmp->next;
?91????????????cnt++;
?92????????}
?93????????node->next=tmp->next;
?94????????tmp->next=node;
?95????????size++;
?96????}
?97}
?98
?99template<typename?T>
100void?linkedlist<T>::deleteNode(int?pos)
101{
102????listnode<T>?*p,*q;
103????p=header;
104????if(p==NULL)
105????{
106????????return;
107????}
108????else?if(pos==0)
109????{
110????????q=p->next;
111????????delete?p;
112????????header=q;
113????????size--;
114????}
115????else
116????{
117????????int?cnt=0;
118????????while(cnt<pos-1?&&?p->next)
119????????{
120????????????p=p->next;
121????????????cnt++;
122????????}
123????????q=p->next;
124????????p->next=q->next;
125????????delete?q;
126????????size--;
127????}
128}
129
130template<typename?T>
131void?linkedlist<T>::printlist()
132{
133????listnode<T>?*tmp=header;
134????if(tmp==NULL)
135????{
136????????cout<<"empty?linked?list"<<endl;
137????????return;
138????}
139????else
140????{
141????????while(tmp)
142????????{
143????????????cout<<tmp->data<<"?";
144????????????tmp=tmp->next;
145????????}
146????????cout<<endl;
147????}
148}
149
150int?main()
151{
152????linkedlist<int>?ilist;
153
154????for(int?i=0;i<8;i++)
155????{
156????????listnode<int>?*node=new?listnode<int>(i);
157????????ilist.addNode(node,0);
158????}
159????ilist.printlist();
160
161????for(int?i=7;i>=0;i--)
162????{
163????????ilist.deleteNode(i);
164????????ilist.printlist();
165????}
166
167
168????return?0;
169}
170

?

看來現在對模板的支持比VC6要好多了。不過在使用模板時還是要小心。

?

在實現的時候，發現deleteNode的實現還是有問題。需要進行修改。

當處理超出范圍的pos時有問題。修改之后的

?

Code
?1void?linkedlist::deleteNode(int?pos)
?2{
?3????listnode?*p=header;
?4????listnode?*q;
?5????if?(p==NULL)
?6????{
?7????????return;
?8????}
?9????else?if(pos==0)
10????{
11????????size--;
12????????q=p->next;
13????????delete?p;
14????????header=q;
15????}
16????else
17????{
18????????int?cnt=0;
19??????while?(cnt<pos-1?&&?p->next->next)
20????????{
21????????????p=p->next;
22????????????cnt++;
23????????}
24????????size--;
25????????q=p->next;
26????????p->next=q->next;
27????????delete?q;
28????}
29}
30

?

模板可以使用typename和class兩個關鍵詞，我比較習慣使用typename。大家可以想一想為什么會使用class作為模板關鍵字？是否有什么隱含意義？

Code
??1#include?<iostream>
??2using?namespace?std;
??3
??4template?<typename?T>
??5class?linkedlist
??6{
??7public:
??8????linkedlist();
??9????~linkedlist();
?10
?11????void?addNode(T?data,?int?pos);
?12????void?deleteNode(int?pos);
?13????void?printlist();
?14private:
?15????void?Destroy();
?16private:
?17????template<typename?T>
?18????class?listnode
?19????{
?20????public:
?21????????T?data;
?22????????listnode<T>?*next;
?23
?24????????listnode(T?d,?listnode<T>?*n=NULL):data(d),next(n)
?25????????{}
?26????};
?27????listnode<T>?*header;
?28????int?size;
?29};
?30
?31template<typename?T>
?32linkedlist<T>::linkedlist()
?33{
?34????header=NULL;
?35????size=0;
?36}
?37
?38template<typename?T>
?39linkedlist<T>::~linkedlist()
?40{
?41????if(header)
?42????????Destroy();
?43????header=NULL;
?44????size=0;
?45}
?46
?47template<typename?T>
?48void?linkedlist<T>::Destroy()
?49{
?50????listnode<T>?*p=header;
?51????while(p)
?52????{
?53????????listnode<T>?*q=p->next;
?54????????delete?p;
?55????????p=q;
?56????????size--;
?57????}
?58????header=NULL;
?59}
?60
?61template<typename?T>
?62void?linkedlist<T>::addNode(T?data,?int?pos)
?63{
?64????listnode<T>?*node=new?listnode<T>(data);
?65????listnode<T>?*tmp=header;
?66????if(tmp==NULL?||?pos==0)
?67????{
?68????????node->next=tmp;
?69????????header=node;
?70????????size++;
?71????}
?72????else
?73????{
?74????????int?cnt=0;
?75????????while(tmp->next?&&?cnt<pos)
?76????????{
?77????????????tmp=tmp->next;
?78????????????cnt++;
?79????????}
?80????????node->next=tmp->next;
?81????????tmp->next=node;
?82????????size++;
?83????}
?84}
?85
?86template<typename?T>
?87void?linkedlist<T>::deleteNode(int?pos)
?88{
?89????listnode<T>?*p,*q;
?90????p=header;
?91????if(p==NULL)
?92????????return;
?93????else?if(pos==0)
?94????{
?95????????q=p->next;
?96????????delete?p;
?97????????header=q;
?98????}
?99????else
100????{
101????????int?cnt=0;
102????????while(cnt<pos-1?&&?p->next->next)
103????????{
104????????????p=p->next;
105????????????cnt++;
106????????}
107????????q=p->next;
108????????p->next=q->next;
109????????delete?q;
110????}
111????size--;
112}
113
114template<typename?T>
115void?linkedlist<T>::printlist()
116{
117????listnode<T>?*tmp=header;
118????if(tmp==NULL)
119????????cout<<"empty?linked?list."<<endl;
120????else
121????{
122????????while(tmp)
123????????{
124????????????cout<<tmp->data<<"?";
125????????????tmp=tmp->next;
126????????}
127????????cout<<endl;
128????}
129}
130
131int?main()
132{
133????linkedlist<int>?ilist;
134????
135????for(int?i=0;i<8;i++)
136????{
137????????ilist.addNode(i,0);
138????}
139
140????ilist.printlist();
141
142????return?0;
143}
144

?

關于嵌套類的模板函數，也一樣實現了，很奇怪的沒有出現什么問題。

當然，有一些函數重載沒有實現。不知道那些有沒有什么問題，不過從目前的實現說明VS對于模板的支持越來越好了。

到此為止，所有的具體實現都已經結束。下面是侯捷老師自己分析的STL源碼，從其網站上可以得到，我這里將其下載了下來。作為單獨一篇發表。

轉載于:https://www.cnblogs.com/cnyao/archive/2009/10/22/linkedlist13.html

總結

以上是生活随笔為你收集整理的穷究链表（十三）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。