DoubleList.h
#pragma once
typedef struct DoubleListNode
{
int data; //数据
struct DoubleListNode *prior; //前驱
struct DoubleListNode *next; //后继
}DoubleListNode, *pDoubleListNode;
class DoubleList
{
public:
DoubleList();
~DoubleList();
//初始化双向链表
void DoubleList::CreateDouList(pDoubleListNode &head);
//打印双向链表
void DoubleList::PrintDouList(pDoubleListNode &head);
//逆序打印双向链表
void DoubleList::PrintDouReverseList(pDoubleListNode &head);
//求链表长度
int DoubleList::GetDouListLength(pDoubleListNode &head);
//判断链表是否为空
bool DoubleList::IsDouListEmpty(pDoubleListNode &head);
//把双向链表置空
void DoubleList::ClearDouList(pDoubleListNode &head);
//删除双向链表
void DoubleList::DeleteDouList(pDoubleListNode &head);
//在双向链表中第i个位置后面插入元素m
void DoubleList::InsertNodeAfter(pDoubleListNode &head);
// 在双向链表中第i个位置前面插入元素
void DoubleList::InsertNodeBefore(pDoubleListNode &head);
//删除双向链表中的第i个元素
void DoubleList::DeleteNode(pDoubleListNode &head);
};
3.对链表插入节点的理解
例如在节点i前插入一个新的节点(即上面代码中的InsertNodeBefore函数):
链表结构体为：
typedef struct DoubleListNode
{
int data; // 数据
struct DoubleListNode *prior; // 前驱
struct DoubleListNode *next; // 后继
}DoubleListNode, *pDoubleListNode;
假设该链表由五个节点构成,分别为A,B,C,D,E
图中假设了A,B,C,D,E的地址分别为:addressA,addressB,addressC,addressD,addressE。
下面将分析链表的前插的例子:
双链表的前插，下面这是在节点"D"前插入一个新的节点"S"的代码和分析
s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); // 申请一段内存空间，指针指向首地址为addressS s->data = data; // 给节点S的数据赋值data s->prior = p->prior; // p指向D节点, p->prior表示addressC，将它赋给s->prior,则s->prior里面的值是addressC，从而指向addressC这个地址即节点C，如下图S节点的蓝线 s->next = p; // p是addressD，将它赋给s->next，s->next中的值为addressD，也即s->next指向了D，如下图S节点的红线 p->prior->next = s; // p->prior 是addressC，即节点C，所以p->prior->next相当于没插入S之前的addressD，插入S后，将S的首地址即addressS赋给这个位置，所以此时，由C 到D的红线断裂，这个红线目标变成了S，如下图C节点的红线 p->prior = s; // 同理，p->prior也指向了S，即p->prior中addressC变成了addressS, D指向C的蓝线断裂。变成如下图D节点指向S节点的蓝线.
