双链表在单链表的基础上加上前驱指针，在创建时要多创建一个指针，在删除与插入元素时要处理更多指针，其它操作与单链表基本一样。
我们建立一个头文件用于建立结构体与函数等。
首先写上预备代码。。。
#include<iostream>
#include<string.h>
using namespace std;
struct dNode //用结构体建立双链表的节点
{
char data;
dNode* next, * prior;
};
void initList(dNode*& l)//初始化一个空表
{
l = (dNode*)malloc(sizeof(dNode));
l->next = l->prior = NULL;
}
void createListh(dNode*& l, char ass[]) //用ass中的数据给双链表赋值,头插法
{
l = (dNode*)malloc(sizeof(dNode));
l->next = NULL;
int i, n;
n = strlen(ass) / sizeof(ass[]);
dNode* s;
for (i = ; i < n; i++)
{
s = (dNode*)malloc(sizeof(dNode));
s->data = ass[i];
s->next = l->next;
if (l->next != NULL)
l->next->prior = s;
l->next = s;
s->prior = l;
}
}
void createListt(dNode*& l, char ass[]) //用ass中的数据给双链表赋值,尾插法
{
l = (dNode*)malloc(sizeof(dNode));
int i, n;
n = strlen(ass) / sizeof(ass[]);
dNode* s, * r = l;
for (i = ; i < n; i++)
{
s = (dNode*)malloc(sizeof(dNode));
s->data = ass[i];
s->prior = r;
r->next = s;
r = s;
}
r->next = NULL;
}
void destroyList(dNode*& l) //销毁双链表
{
dNode* pre, * p;
pre = l;
p = l->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
bool emptyList(dNode*& l) //确定双链表是否为空
{
return (l->next == NULL);
}
int lengthList(dNode*& l) //求双链表的长度
{
dNode* p = l;
int i = ;
while (p->next != NULL)
{
p = p->next;
i++;
}
return i;
}
void coutList(dNode*& l) //依次输出双链表所有元素
{
dNode* p = l;
int i = ;
while (p->next != NULL)
{
p = p->next;
cout << p->data;
}
}
void getiList(char& e, int i, dNode*& l)//获取第i个元素
{
dNode* p = l;
int j = ;
while (j < i && p->next != NULL)
{
p = p->next;
j++;
}
if (i != j)
cout << "超出顺序表范围";
else
e = p->data;
}
int findeList(char e, dNode*& l)//找到个元素e所在的位置
{
int i = 1;
dNode* p = l;
while (p->next != NULL && p->next->data != e)
{
i++;
p = p->next;
}
if (p->next == NULL)
{
cout << "未找到元素";
return ;
}
else
return i;
}
void insertList(char e, int i, dNode*& l) //将e插入第i个位置
{
dNode* p = l, * s;
s = (dNode*)malloc(sizeof(dNode));
int j = 1;
while (j < i && p->next != NULL)
{
j++;
p = p->next;
}
if (i == j)
{
s->data = e;
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;
}
else
cout << "指定的位置不存在";
}
void deleteList(int i, dNode*& l)//删除第i个元素
{
dNode* p = l, * s = l->next;
int j = 1;
while (j < i && s != NULL)
{
p = s;
s = s->next;
j++;
}
if (i != j)
cout << "超出范围";
else
{
p->next = s->next;
p->next->prior = p;
free(s);
}
}
下面是测试代码。
#include<iostream>
#include<math.h>
#include<string.h>
#include"shuanglianbiao.h"
using namespace std;
int main()
{
char x = '5', a[27] = "abcdefghijklmnopqrstuvwxyz";
dNode* list, * list2;
initList(list);
createListt(list, a);
cout << list->next->next->prior->data << endl;//测试前驱指针
cout << list->next->data << endl;
initList(list2);
createListh(list2, a);
cout << list2->next->data << endl;
destroyList(list2);
cout << emptyList(list) << endl;
cout << lengthList(list) << endl;
coutList(list);
int n = 3;
getiList(x, n, list);
cout << endl << x << endl;
cout << findeList('x', list) << endl;
insertList('y', 2, list);
coutList(list);
deleteList(2, list);
cout << endl;
coutList(list);
cout << endl << list->next->next->prior->data << endl;//再次测试前驱指针
destroyList(list);
}
