下面就是我们双向链表的基本原理。
  |
 |
|
|
这里我们插入代码案例：头文件DoubleLink.h
#ifndef DOUBLE_LINK_HXX #define DOUBLE_LINK_HXX #include
using namespace std; //一个节点 template
struct DNode { public: T value; DNode *prev; DNode *next; public: DNode() { } DNode(T t, DNode *prev, DNode *next) { this->value = t; this->prev = prev; this->next = next; } }; //双向链表基本操作 template
class DoubleLink { public: DoubleLink(); ~DoubleLink(); int size();//大小 int is_empty();//判断是否为空 T get(int index);//获取节点 T get_first();//获取首节点 T get_last();//获取尾节点 int insert(int index, T t); int insert_first(T t); int append_last(T t); int del(int index); int delete_first(); int delete_last(); private: int count; DNode
*phead; private: DNode
*get_node(int index); }; template
DoubleLink
::DoubleLink() : count(0) { // 创建“表头”。注意：表头没有存储数据！ phead = new DNode
(); phead->prev = phead->next = phead; // 设置链表计数为0 //count = 0; } // 析构函数 template
DoubleLink
::~DoubleLink() { // 删除所有的节点 DNode
* ptmp; DNode
* pnode = phead->next; while (pnode != phead) { ptmp = pnode; pnode=pnode->next; delete ptmp; } // 删除"表头" delete phead; phead = NULL; } // 返回节点数目 template
int DoubleLink
::size() { return count; } // 返回链表是否为空 template
int DoubleLink
::is_empty() { return count==0; } // 获取第index位置的节点 template
DNode
* DoubleLink
::get_node(int index) { // 判断参数有效性 if (index<0 || index>=count) { cout << "get node failed! the index in out of bound!" << endl; return NULL; } // 正向查找 if (index <= count/2) { int i=0; DNode
* pindex = phead->next; while (i++ < index) { pindex = pindex->next; } return pindex; } // 反向查找 int j=0; int rindex = count - index -1; DNode
* prindex = phead->prev; while (j++ < rindex) { prindex = prindex->prev; } return prindex; } // 获取第index位置的节点的值 template
T DoubleLink
::get(int index) { return get_node(index)->value; } // 获取第1个节点的值 template
T DoubleLink
::get_first() { return get_node(0)->value; } // 获取最后一个节点的值 template
T DoubleLink
::get_last() { return get_node(count-1)->value; } // 将节点插入到第index位置之前 template
int DoubleLink
::insert(int index, T t) { if (index == 0) return insert_first(t); DNode
* pindex = get_node(index); DNode
* pnode = new DNode
(t, pindex->prev, pindex); pindex->prev->next = pnode; pindex->prev = pnode; count++; return 0; } // 将节点插入第一个节点处。 template
int DoubleLink
::insert_first(T t) { DNode
* pnode = new DNode
(t, phead, phead->next); phead->next->prev = pnode; phead->next = pnode; count++; return 0; } // 将节点追加到链表的末尾 template
int DoubleLink
::append_last(T t) { DNode
* pnode = new DNode
(t, phead->prev, phead); phead->prev->next = pnode; phead->prev = pnode; count++; return 0; } // 删除index位置的节点 template
int DoubleLink
::del(int index) { DNode
* pindex = get_node(index); pindex->next->prev = pindex->prev; pindex->prev->next = pindex->next; delete pindex; count--; return 0; } // 删除第一个节点 template
int DoubleLink
::delete_first() { return del(0); } // 删除最后一个节点 template
int DoubleLink
::delete_last() { return del(count-1); } #endif
接下来就放入DlinkTest.cpp
#include
#include "DoubleLink.h" using namespace std; // 双向链表操作int数据 void int_test() { int iarr[4] = {10, 20, 30, 40};//定义一个数组 cout << "\n开始测试 int数据" << endl; // 创建双向链表 DoubleLink
* pdlink = new DoubleLink
(); pdlink->insert(0, 20); // 将 20 插入到第一个位置 pdlink->append_last(10); // 将 10 追加到链表末尾 pdlink->insert_first(30); // 将 30 插入到第一个位置 // 双向链表是否为空 cout << "is_empty()=" << pdlink->is_empty() <
上面代码亲自敲的，并且运行成功。可复制直接使用。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/221637.html原文链接：https://javaforall.net
