自己写的个有序的双向链表:
#include
using namespace std;
template
class dNode
{
public:
dNode* pre;
dNode* next;
T content;
};
template
dNode* insertNode(dNode *&head ,const T &n)
{
dNode *newNode = new dNode;
newNode->content = n;
dNode *move = head;
if(head == NULL)//////////////////链表为空
{
head = newNode;
head->pre = NULL;
head->next = NULL;
return head;
}
else
{
if(n<=head->content)//////////////表头插入
{
newNode->pre = 0;
newNode->next = head;
head->pre = newNode;
head = newNode;
return head;
}
else
{
while(n>move->content&&move->next!=NULL)
{
move=move->next;
}
if(n>move->content)///////插入链表末端
{
newNode->pre = move;
newNode->next = 0;
move->next = newNode;
}
else ////////////////表中间插入
{
newNode->pre = move ->pre;
newNode->next = move;
move->pre->next = newNode;
move->pre = newNode;
}
return newNode;
}
}
}
template
void displayLink(const dNode *const head)
{
const dNode *move = head ;
while(move!=0)
{
cout<content< move=move->next;
}
}
template
dNode* searchNode(dNode *&head ,const T &n)
{
dNode *move = head ;
while(n>move->content&&move->next!=0)
{
move = move->next;
}
if(n==move->content)
{
return move;
}
else
{
return NULL;
}
}
template
void find(dNode *&head ,const T &n)
{
dNode *key = searchNode(head ,n);
if(key==0)
{
cout<<"无此记录"< }
else
{
cout<content< }
}
template
dNode* deleteNode(dNode *&head ,const T &n)
{
dNode *move = searchNode(head ,n);
if(move!=0)
{
if(move->pre == 0)/////////////////////删除表头
{
move->next->pre = 0;
head = head->next;
delete move;
move = 0;
return head;
}
else if(move->next== 0)/////////////删除链表尾部
{
move->pre->next = 0;
}
else/////////////////////////////删除中间元素
{
move->pre->next = move->next;
move->next->pre = move->pre;
}
move = move->pre;
return move;
}
else
{
return NULL;
}
}
int main()
{
dNode *head = 0;
//dNode *head=new dNode;
int a = 6;
insertNode(head,a);
insertNode(head,4);
insertNode(head,5);
insertNode(head,7);
// cout<pre->content< displayLink(head);
dNode *k = searchNode(head,1);
deleteNode(head ,7);
find(head,7);
displayLink(head);
// cout<content< return 1;
}
阅读(504) | 评论(0) | 转发(0) |