Chinaunix首页 | 论坛 | 博客
  • 博客访问: 264791
  • 博文数量: 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. };

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

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

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

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

  85. template<class T>
  86. ostream & operator<<(ostream & out,const Chain<T> & x)
  87. {
  88.     x.Output(out);
  89.     return out;
  90. }


点击(此处)折叠或打开

  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. }

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

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

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




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

上一篇:没有了

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

给主人留下些什么吧!~~