C++实现双链表（使用模板类）
双链表
结点定义
template
class DNode
{
public:
T data;
DNode* next,* pre;
};
方法定义
template
class DLink_List
{
private:
DNode* head;
public:
int size;
DLink_List();
bool isEmpty();
bool Insert(int pos, T elem);
bool Delete(int pos, T& elem);
bool Find(int pos, T& elem);
void show();
~DLink_List();
};
总体实现
//双链表
#include
#include "DLink_List.h"
using namespace std;
template
DLink_List::DLink_List()
{
head = new DNode;
head->next = NULL;
head->pre = NULL;
this->size = 0;
}
template
bool DLink_List::isEmpty()
{
return this->size == 0;
}
template
bool DLink_List::Insert(int pos, T elem)
{
if (pos < 0 || pos > this->size)
return false;
DNode* p = new DNode;
p->data = elem;
p->pre = p->next = NULL;
DNode* temp = head;
if (pos == 0)
{
if (head->next == NULL)
{
p->pre = head;
head->next = p;
}
else
{
p->next = head->next;
head->next->pre = p;
p->pre = head;
head->next = p;
}
}
else if (pos == this->size)
{
while (temp->next != NULL)
temp = temp->next;
temp->next = p;
p->pre = temp;
}
else
{
while (pos-- > 0)
temp = temp->next;
p->next = temp->next;
p->pre = temp;
temp->next->pre = p;
temp->next = p;
}
this->size++;
return true;
}
template
bool DLink_List::Delete(int pos, T& elem)
{
if (pos <= 0 || pos > this->size || isEmpty())
return false;
DNode* p = head;
if (pos == 1)
{
if (head->next->next == NULL)
{
p = p->next;
elem = p->data;
head->next = NULL;
delete p;
}
else
{
p = p->next;
elem = p->data;
head->next = p->next;
p->next->pre = head;
}
}
else if (pos == this->size)
{
while (p->next != NULL)
p = p->next;
elem = p->data;
p->pre->next = NULL;
delete p;
}
else
{
while (pos-- > 0)
p = p->next;
elem = p->data;
p->pre->next = p->next;
p->next->pre = p->pre;
delete p;
}
this->size--;
return true;
}
template
bool DLink_List::Find(int pos, T& elem)
{
if (pos <= 0 || pos > this->size || isEmpty())
return false;
DNode* p = head;
while (pos-- > 0)
p = p->next;
elem = p->data;
return true;
}
template
void DLink_List::show()
{
DNode* p = head;
while (p->next != NULL)
{
p = p->next;
cout << p->data << " ";
}
cout << endl;
}
template
DLink_List::~DLink_List()
{
delete head;
}
分块
初始化
template
DLink_List::DLink_List()
{
head = new DNode;
head->next = NULL;
head->pre = NULL;
this->size = 0;
}
判空
template
bool DLink_List::isEmpty()
{
return this->size == 0;
}
插入
template
bool DLink_List::Insert(int pos, T elem)
{
if (pos < 0 || pos > this->size)
return false;
DNode* p = new DNode;
p->data = elem;
p->pre = p->next = NULL;
DNode* temp = head;
if (pos == 0)
{
if (head->next == NULL)
{
p->pre = head;
head->next = p;
}
else
{
p->next = head->next;
head->next->pre = p;
p->pre = head;
head->next = p;
}
}
else if (pos == this->size)
{
while (temp->next != NULL)
temp = temp->next;
temp->next = p;
p->pre = temp;
}
else
{
while (pos-- > 0)
temp = temp->next;
p->next = temp->next;
p->pre = temp;
temp->next->pre = p;
temp->next = p;
}
this->size++;
return true;
}
删除
template
bool DLink_List::Delete(int pos, T& elem)
{
if (pos <= 0 || pos > this->size || isEmpty())
return false;
DNode* p = head;
if (pos == 1)
{
if (head->next->next == NULL)
{
p = p->next;
elem = p->data;
head->next = NULL;
delete p;
}
else
{
p = p->next;
elem = p->data;
head->next = p->next;
p->next->pre = head;
}
}
else if (pos == this->size)
{
while (p->next != NULL)
p = p->next;
elem = p->data;
p->pre->next = NULL;
delete p;
}
else
{
while (pos-- > 0)
p = p->next;
elem = p->data;
p->pre->next = p->next;
p->next->pre = p->pre;
delete p;
}
this->size--;
return true;
}
按位序查找
template
bool DLink_List::Find(int pos, T& elem)
{
if (pos <= 0 || pos > this->size || isEmpty())
return false;
DNode* p = head;
while (pos-- > 0)
p = p->next;
elem = p->data;
return true;
}
遍历
template
void DLink_List::show()
{
DNode* p = head;
while (p->next != NULL)
{
p = p->next;
cout << p->data << " ";
}
cout << endl;
}
销毁
template
DLink_List::~DLink_List()
{
delete head;
}
测试代码
#include
#include "DLink_List.h"
#include "DLink_List.cpp"
using namespace std;
int main()
{
DLink_List dll;
for (int i = 0; i < 5; i++)
{
dll.Insert(0, i + 1);
cout << "头插：" << i + 1 << "：";
dll.show();
}
for (int i = 0; i < 5; i++)
{
dll.Insert(dll.size, i + 11);
cout << "尾插：" << i + 11 << "：";
dll.show();
}
for (int i = 0; i < 3; i++)
{
dll.Insert(2, i + 101);
cout << "在第2个位置插入" << i + 101 << "：";
dll.show();
}
getchar();
system("cls");
cout << "当前剩余：";
dll.show();
int val;
cout << "头删：";
dll.Delete(1, val);
cout << val << endl;
dll.show();
cout << "头删：";
dll.Delete(1, val);
cout << val << endl;
dll.show();
cout << "头删：";
dll.Delete(1, val);
cout << val << endl;
dll.show();
cout << "尾删：";
dll.Delete(dll.size, val);
cout << val << endl;
dll.show();
cout << "尾删：";
dll.Delete(dll.size, val);
cout << val << endl;
dll.show();
cout << "尾删：";
dll.Delete(dll.size, val);
cout << val << endl;
dll.show();
cout << "在第2个位置删除：";
dll.Delete(2, val);
cout << val << endl;
dll.show();
cout << "在第2个位置删除：";
dll.Delete(2, val);
cout << val << endl;
dll.show();
getchar();
system("cls");
cout << "当前剩余：";
dll.show();
dll.Find(3, val);
cout << "3号位置为：" << val << endl;
return 0;
}
暑期编程PK赛
得CSDN机械键盘等精美礼品！
