基于C++类的双向链表

前言链表linked list)是一种这样的数据结构其中的各对象按线性排列。数组的线性顺序是由数组下标决定的然而于数组不同的是链表的各顺序是由链表中的指针决定的。双向链表也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。双向链表的定义双链表doubly linked list)的每一个元素都是一个对象每一个对象都有一个数据域和两个指针front和tail。对象中还可以包含其他辅助数据。设L为链表的一个元素L.front指向他在链表中的后继元素L.tail指向他的前继元素。我们可以定义一个结构体封装这些数据typedef struct Node { int data; struct Node* front; struct Node* tail; }NODE, * LPNODE;双向链表的创建在C中我们以类的形式封装了双向链表。在类中我们定义了两个指针一个是指向链表的头部 frontNode一个是指向了链表的尾部 tailNode另外我们还加入了 curSize属性记录节点的个数。在对象创建的过程就是链表创建的过程我们只需要在类的构造函数中初始化参数即可。class duplexHead { public: duplexHead() { frontNode NULL; tailNode NULL; curSize 0; } LPNODE createNode(int data); LPNODE seachNode(int data); void push_front(int data); void push_back(int data); void push_appoin(int posData, int data); void pop_front(); void pop_back(); void pop_appoin(int posData); void printByFront(); void printByTail(); protected: LPNODE frontNode; LPNODE tailNode; int curSize; };节点的创建在上面我们已经知道双向链表的单体长啥样了我们只需要给他的单体分配空间然后初始化他的参数即可。LPNODE duplexHead::createNode(int data) { LPNODE newNode new NODE; assert(newNode); newNode-front nullptr; newNode-tail nullptr; newNode-data data; return newNode; }双向链表节点查找链表的查找我们可以定义一个函数LPNODE seachNodeint data)当满足查找条件时我们就返回当前节点的链表。在实际操作过程中链表的数据域可能会有多个数据可能要比较int 类型可能要比较string类型等多种变化这是我们可以在参数列表预留一个函数指针 (int) (*comparData)(LPNODE data),以应对多种需求。当然在这里为了演示方便我们就用一个int 类型的数据代替了。LPNODE duplexHead::seachNode(int data) { if (!curSize) { printf(链表为空无法查找); return; } LPNODE preNode frontNode; LPNODE curNode frontNode; while (curNode ! NULL curNode-data ! data) { preNode curNode; curNode preNode-tail; } if (curNode nullptr) { printf(链表中没有该数据); return nullptr; } return curNode; }双向链表的插入插入节点我们分为头部插入和尾部插入以及指定位置插入。而这三种插入都可分为3步。1创建新节点2找到插入位置3插入我们就以制定位置插入为例如图所示我们只需把原来相连的两个节点断开然后再分别用指针拼接起来当然我们也可以调用我们的seachNode来查找位置这样就更方便一些了。void duplexHead::push_appoin(int posData, int data) { if (curSize 0) return; if (frontNode-data posData) { push_front(data); } else { LPNODE preNode frontNode; LPNODE curNode frontNode; while (curNode ! NULL curNode-data ! posData) { preNode curNode; curNode preNode-tail; } if (curNode NULL) { printf(未找到指定位置无法插入\n); } else { LPNODE newNode createNode(data); preNode-tail newNode; newNode-tail curNode; curNode-front newNode; newNode-front preNode; curSize; } } }双向链表的节点删除删除节点我们也可以分为头部删除尾部删除指定数据删除。他与插入节点几乎是一样的1找到删除位置2记录删除的位置将节点从链表中移出3释放删除节点的内存我们就以指定数据删除为例我们通过while或者seachNode来查找到要删除的节点然后把他的front 指向的位置和tail指向的位置记住就可以直接删除节点了。删除完了节点要记得把前后段的链表连接上即可。void duplexHead::pop_appoin(int posData) { if (frontNode NULL || curSize 0) { printf(链表为空无法删除); return; } if (frontNode-data posData) { pop_front(); return; } LPNODE preNode frontNode; LPNODE curNode frontNode; while (curNode ! NULL curNode-data ! posData) { preNode curNode; curNode preNode-tail; } if (curNode NULL) { printf(未找到指定位置无法删除\n); } else { if (tailNode curNode) { pop_back(); } else { preNode-tail curNode-tail; //curNode-tail是不是不空 //当删除的表尾时候curNode-tail等于空 curNode-tail-front preNode; free(curNode); curNode NULL; curSize--; } } }双向链表的删除于双向链表的创建一样我们可以把双向链表的删除放在析构函数中实现创建和删除自动化当对象被创建双向链表就被创建当对象消亡双向链表就删除了。duplexHead::~duplexHead() { if (!frontNode)return; LPNODE pmove ; while (!pmove) { pmove frontNode-tail; delete frontNode-tail; frontNode pmove; } }