我发个用C++写的双向链表（自己做的）：
程序代码：
程序代码：
#ifndef _LIST_H
#define _LIST_H
#include <windows.h>
//////////////////////////////////////////////////////////////////////////
//节点的结构
struct node
{
void *data;
node *last;
node *next;
};
//////////////////////////////////////////////////////////////////////////
//链表类
class CList
{
public:
//////////////////////////////////////////////////////////////////////////
//初始化链表
CList()
{
m_curNode = NULL; //为NULL则说明没有节点
m_curPos = -1; //为-1也说明没有节点
}
//////////////////////////////////////////////////////////////////////////
//在当前节点的左边插入一个新节点
void *insertLeft(void *dat)
{
node *newNode = new node;
newNode->data = dat;
newNode->last = NULL;
newNode->next = NULL;
if(!m_curNode)
{
m_curNode = newNode;
m_curPos = 0;
}
else
{
node *oldNode = m_curNode->last;
if(oldNode) oldNode->next = newNode;
newNode->last = oldNode;
newNode->next = m_curNode;
m_curNode->last = newNode;
m_curNode = newNode;
}
return m_curNode->data;
}
//////////////////////////////////////////////////////////////////////////
//在当前节点的右边插入一个新节点
void *insertRight(void *dat)
{
node *newNode = new node;
newNode->data = dat;
newNode->last = NULL;
newNode->next = NULL;
if(!m_curNode)
{
m_curNode = newNode;
m_curPos = 0;
}
else
{
node *nextNode = m_curNode->next;
if(nextNode) nextNode->last = newNode;
newNode->last = m_curNode;
newNode->next = nextNode;
m_curNode->next = newNode;
m_curNode = newNode;
m_curPos ++;
}
return m_curNode->data;
}
//////////////////////////////////////////////////////////////////////////
//删除当前节点
short deleteNode()
{
if(!m_curNode)return 0;
else
{
node *last = m_curNode->last;
node *next = m_curNode->next;
if(last) last->next = next;
if(next) next->last = last;
delete m_curNode;
m_curNode = NULL;
if(last)
{
m_curNode = last;
m_curPos --;
return 1;
}
else if(next)
{
m_curNode = next;
return 2;
}
else
{
m_curNode = NULL;
m_curPos = -1;
return 0;
}
}
}
//////////////////////////////////////////////////////////////////////////
//删除所有节点
int delAllEx()
{
int cnt = 0;
moveFirst();
node *tmp = m_curNode;
do
{
deleteNode();
cnt++;
} while (tmp = moveRight());
deleteNode();
m_curPos = -1;
cnt++;
return cnt;
}
//////////////////////////////////////////////////////////////////////////
//删除所有节点（最快）
int delAll()
{
int cnt = 0;
do cnt ++;
while (deleteNode());
return cnt;
}
//////////////////////////////////////////////////////////////////////////
//当前节点往左移动
node *moveLeft()
{
if(!m_curNode)
{
m_curPos = -1;
return NULL;
}
else
{
node *tmp = m_curNode->last;
if(tmp)
{
m_curNode = tmp;
m_curPos --;
return m_curNode;
}
else return NULL;
}
}
//////////////////////////////////////////////////////////////////////////
//当前节点往右移动
node *moveRight()
{
if(!m_curNode)
{
m_curPos = -1;
return NULL;
}
else
{
node *tmp = m_curNode->next;
if(tmp)
{
m_curNode = tmp;
m_curPos ++;
return m_curNode;
}
else return NULL;
}
}
//////////////////////////////////////////////////////////////////////////
//当前节点移动到最前
node *moveFirst()
{
while(moveLeft())
{}
return m_curNode;
}
//////////////////////////////////////////////////////////////////////////
//当前节点移动到最后
node *moveEnd()
{
while(moveRight())
{}
return m_curNode;
}
//////////////////////////////////////////////////////////////////////////
//循环移动当前节点，v为正则往右，负则往左，0则不移动
void loopMove(int v)
{
int idx = 0;
if(v < 0)
{
idx = abs(v);
for(int i = 0; i < idx; i++)
moveLeft();
}
else if(v > 0)
{
idx = abs(v);
for(int i = 0; i < idx; i++)
moveRight();
}
}
//////////////////////////////////////////////////////////////////////////
//当前节点移动到idx位置
void moveTo(int idx)
{
int a = idx - m_curPos;
loopMove(a);
}
//////////////////////////////////////////////////////////////////////////
//获得当前节点
node *getCurNode()
{
return m_curNode;
}
//////////////////////////////////////////////////////////////////////////
//获得当前节点的位置
int getCurPos()
{
return m_curPos;
}
//////////////////////////////////////////////////////////////////////////
//获得当前节点的data指针
void *getCurData()
{
if(!m_curNode) return NULL;
else return m_curNode->data;
}
//////////////////////////////////////////////////////////////////////////
//重载等于运算符，把另一个链表复制到此链表
void operator = (CList lst)
{
lst.moveFirst();
do insertRight(lst.getCurData());
while (lst.moveRight());
moveFirst(); //置于最前
}
//////////////////////////////////////////////////////////////////////////
//获得链表中总共有多少个节点
//这个会把curPos改变，但是速度更快
int getNumEx()
{
moveEnd();
return m_curPos + 1;
}
//////////////////////////////////////////////////////////////////////////
//这个能保持curPos，但是速度较慢
int getNum()
{
int oldCur = m_curPos;
moveEnd();
int ret = m_curPos + 1;
moveTo(oldCur);
return ret;
}
private:
node *m_curNode; //当前节点
int m_curPos; //当前节点的位置
};
#endif
天之道,损有余而补不足.人之道则不然,损不足以奉有余.孰能有余以奉天下,唯有道者.
