Chinaunix首页 | 论坛 | 博客
  • 博客访问: 963876
  • 博文数量: 335
  • 博客积分: 10287
  • 博客等级: 上将
  • 技术积分: 3300
  • 用 户 组: 普通用户
  • 注册时间: 2005-08-08 15:29
文章分类

全部博文(335)

文章存档

2015年(4)

2014年(15)

2013年(17)

2012年(11)

2011年(12)

2010年(96)

2009年(27)

2008年(34)

2007年(43)

2006年(39)

2005年(37)

我的朋友

分类: C/C++

2010-02-03 16:59:46

自己写的个有序的双向链表:
#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) |
给主人留下些什么吧!~~