双向链表模板类
dlist.h
#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <string>
#include <stdexcept>
using namespace std;
template<typename T>
class DList
{
struct node{
T data;
node* next;
node* prev;
};
node *head = NULL;
node *tail = NULL;
int len;
public:
//缺省构造函数
DList(){
len = 0;
}
//拷贝构造函数
DList(const DList &l){
len = 0;
if(l.head!=NULL){
node *pHc = l.head; //链表l节点指针
head = new node(); //为新链表头节点申请空间
head->data = pHc->data; //新链表头结点赋值
node *pH = head; //新链表节点指针
len++;
while(pHc!=l.tail){
pHc = pHc->next;
pH->next = new node(); //为新节点分配内存,当前节点的next指针指向新节点
pH->next->prev = pH; //新节点的prev指针指向当前节点
pH = pH->next;
pH->data = pHc->data;
len++;
}
}
else{
head=tail=NULL;
}
}
//赋值运算符重载函数
DList& operator = (const DList &l){
len = 0;
if (this == &l){
return *this;
}
len = 0;
if(l.head!=NULL){
node *pHc = l.head; //链表l节点指针
head = new node(); //为新链表头节点申请空间
head->data = pHc->data; //新链表头结点赋值
node *pH = head; //新链表节点指针
len++;
while(pHc!=l.tail){
pHc = pHc->next;
pH->next = new node(); //为新节点分配内存,当前节点的next指针指向新节点
pH->next->prev = pH; //新节点的prev指针指向当前节点
pH = pH->next;
pH->data = pHc->data;
len++;
}
}
else{
head=tail=NULL;
}
return *this;
}
//析构函数
~DList(){
node *bgn = head;
while(head!=tail)
{
head = head->next;
delete bgn;//释放内存
bgn = head;
}
len = 0;
}
int size(){
return len;
}
void print(){
for(int i=0;i<len;i++){
cout<<at(i)<<" ";
}
cout<<endl;
}
//在尾部添加节点
void push_back(T data){
if(head==NULL){
head = new node();
head->data = data;
len++;
tail = head;
}
else{
tail->next = new node();
tail->next->data = data;
len++;
tail->next->prev = tail;
tail = tail -> next;
}
return;
}
//取出节点(按下标)
T at(int index){
node *p;
p = head;
if(index>=len)
throw out_of_range("in at(int index) index out of range");
else{
for(int i=0;i<index;i++)
p = p->next;
}
return p->data;
}
//查找节点
int indexOf(T _data){
int index = 0;
node *p = head;
while(p->data != _data){
p = p->next;
index++;
}
if(index >= len)
return -1;
else
return index;
}
//删除节点
void removeAt(int index){
node *p;
p = head;
if(index >= len)
throw out_of_range("in removeAt(int index) index out of range");
else{
//移动到要删除的节点处
for(int i=0;i<index;i++){
p = p->next;
}
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
p = NULL;
len--;
}
return;
}
void clear(){
node *bgn = head;
while(head!=tail)
{
head = head->next;
delete bgn;//释放内存
bgn = head;
}
len = 0;
}
//交换两节点(交换值)
void swap(int i, int j){
T vi = at(i);
T vj = at(j);
node *p;
p = head;
for(int k=0;k<i;k++)
p = p->next;
p->data = vj;
p = head;
for(int k=0;k<j;k++)
p = p->next;
p->data = vi;
}
//子表划分函数,返回枢轴值
int Partition(int low, int high){
T pivotkey;
pivotkey = at(low); //用子表的第一个记录作为枢轴记录
while(low < high){
while(low < high && at(high) >= pivotkey)
high--;
swap(low, high);
while(low < high && at(low) <= pivotkey)
low++;
swap(low, high);
}
return low;
}
//快速排序递归函数
void QSort(int low, int high){
int pivot;
if(low < high){
pivot = Partition(low,high);
QSort(low,pivot-1);
QSort(pivot+1,high);
}
}
//快速排序
void QuickSort(){
QSort(0,len-1);
}
};
#endif // DLIST_H
测试类型为 DList< std::string >
main.cpp
#include <iostream>
#include "dlist.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
try {
DList<string> list;
list.push_back("a");
list.push_back("b");
list.push_back("c");
list.push_back("d");
list.push_back("e");
list.push_back("f");
list.push_back("g");
list.push_back("h");
cout<<"【测试 push_back】 ";
list.print();
DList<string> list2(list);
cout<<"【测试 拷贝构造函数】 ";
list2.print();
DList<string> list3 = list;
cout<<"【测试 运算符重载函数】 ";
list3.print();
cout<<"【测试 indexOf()】 ";
cout<<list3.indexOf("c")<<endl;
cout<<"【测试 swap(0,1)】 ";
list3.swap(0,1);
list3.print();
cout<<"【测试 QuickSort】 ";
list3.QuickSort();
list3.print();
cout<<"【测试 removeAt(4)】 ";
list3.removeAt(4);
list3.print();
cout<<"【测试 clear】 ";
list3.clear();
list3.print();
}
catch (exception const& ex) {
cerr << "Exception: " << ex.what() <<endl;
return -1;
}
return 0;
}
运行结果
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200719214906433.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1bl90aWFu,size_16,color_FFFFFF,t_70)