Chinaunix首页 | 论坛 | 博客

bob_hu924的ChinaUnix博客yunliaohu.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

bob_hu924

  • 博客访问： 268760
  • 博文数量： 45
  • 博客积分： 930
  • 博客等级： 准尉
  • 技术积分： 553
  • 用 户 组： 普通用户
  • 注册时间： 2012-01-22 17:53
文章分类

全部博文（45）

文章存档

2013年（5）

2012年（40）

我的朋友
最近访客
推荐博文
相关博文
线性表的链表描述

分类： C/C++

2012-04-23 22:11:18


点击(此处)折叠或打开

  1. template <class T>
  2. class ChainNode{
  3.     friend Chain<T>;
  4.     private:
  5.     T data;
  6.     ChainNode<T> * link;
  7. };
  8. template<class T>
  9. class Chain {
  10.     public:
  11.         Chain() { first = 0; }
  12.         ~Chain();
  13.         bool IsEmpty() const { return first == 0;}
  14.         int Length() const;
  15.         bool Find(int k, T & x ) const;
  16.         int Search(const T & x) const;
  17.         Chain<T> & Delete(int k, T & x);
  18.         Chain<T> & Insert(int k, const T & x);
  19.         void Output(ostream & out ) const;
  20.     private:
  21.         ChainNode<T> * first;
  22. };

  24. template<class T>
  25. Chain<T>::~Chain()
  26. {
  27.     ChainNode<T> *next;
  28.     while (first){
  29.         next = first->link;
  30.         delete first;
  31.         first = next;
  32.     }
  33. }

  35. template<class T>
  36. int Chain<T>::Length() const
  37. {
  38.     ChainNode<T> * current = first;
  39.     int len = 0;
  40.     while (current)
  41.     {
  42.         len++;
  43.         current = current->link;
  44.     }
  45.     return len;
  46. }

  48. template<class T>
  49. bool Chain<T>::Find(int k, T & x) const
  50. {
  51.     if (k < 1) return false;
  52.     ChainNode<T> * current = first;
  53.     int index = 1;
  54.     while ( index < k && current)
  55.     {
  56.         current = current->link;
  57.         index++;
  58.     }
  59.     if (current)
  60.     {
  61.         x = current->data;
  62.         return true;
  63.     }
  64.     return false;
  65. }
  66. template<class T>
  67. int Chain<T>::Search(const T & x) const
  68. {
  69.     ChainNode<T> * current = first;
  70.     int index = 1;
  71.     while(current && current->data != x)
  72.     {
  73.         current = current->link;
  74.         index++;
  75.     }
  76.     if (currrent) return index;
  77.     return 0;
  78. }

  80. template<class T>
  81. void Chain<T>::Output(ostream & out) const
  82. {
  83.     ChainNode<T> * current;
  84.     for(current = first; current; current = current->link)
  85.     {
  86.         out<<current->data<<" ";
  87.     }
  88. }

  90. template<class T>
  91. ostream & operator<<(ostream & out,const Chain<T> & x)
  92. {
  93.     x.Output(out);
  94.     return out;
  95. }


点击(此处)折叠或打开

  1. template<class T>
  2. Chain<T> & Chain<T>::Delete(int k, T & x)
  3. {
  4.     if(k < 1 || !first)
  5.         throw OutOfBounds();//不存在第k个元素
  6.     ChainNode<T> *p = first;
  7.     if(k== 1)
  8.         first = first->link;
  9.     else {
  10.         ChainNode<T> * q = first;
  11.         for (int index = 1; index < k -1 && q; index++)
  12.             q = q->link;
  13.         if (!q || !q->link)
  14.             throw OutOfBounds();
  15.         p = q->link;
  16.         q->link = q->link;
  17.     }
  18.     x = p->data;
  19.     delete p;
  20.     return *this;
  21. }

  23. template<class T>
  24. Chain<T> & Chain<T>::Insert(int k, const T & x)
  25. {
  26.     if (k < 0)
  27.         throw OutOfBounds();
  28.     ChainNode<T> * p = first;
  29.     for (int index = 1; index < k && p; index++)
  30.         p = p->link;
  31.     if (k > 0 && !p)
  32.         throw OutOfBounds();
  33.     ChainNode<T> * y = new ChainNode<T>;
  34.     y->data = x;
  35.     if (k)
  36.     {
  37.         y->link = p->link;
  38.         p->link = y;
  39.     }
  40.     else
  41.     {
  42.         y->link = first;
  43.         first = y;
  44.     }
  45.     return *this;
  46. }

  48. template<class T>
  49. void Chain<T>::Erase()
  50. {
  51.     ChainNode<T> *next;
  52.     while(first){
  53.         next = first->link;
  54.         delete first;
  55.         first = next;
  56.     }
  57. }

  59. template<class T>
  60. Chain<T> & Chain<T>::Append(const T & x)
  61. {
  62.     ChainNode<T> * y;
  63.     y = new ChainNode<T>;
  64.     y->data = x;
  65.     y->link = 0;
  66.     if(first){
  67.         last->link = y;
  68.         last = y;
  69.     }
  70.     else //空链表
  71.         first = last = y;
  72.     return *this;
  73. }




阅读(1058) | 评论(0) | 转发(0) |
0

上一篇：没有了

下一篇：线性表的数组描述

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6