「数据结构」: 链表的实现

此次实现的数据结构仍为线性表，物理结构上采用链表结构，与顺序表相比有以下特点：

优点：不再有存储空间上的限制（主要取决了机器的存储能力，不会提前分配一定量的空间）

缺点：失去了随机存储特性，若只用简单的链表则查找、插入、删除都将占用O(K)的时间(K为操作位置)

使用C＋＋语言实现。

代码如下：

  1 //linkList.h
  2 #ifndef __LINKLIST__
  3 #define __LINKLIST__
  4 #include <iostream>
  5 #include "excp.h"
  6 using namespace std;
  7 
  8 template<class T>
  9 class linkList;
 10 
 11 template<class T>
 12 class Node {
 13 public:
 14     Node(const T& newData) 
 15     {
 16         data = newData;
 17         next = NULL;
 18     }
 19     friend class linkList<T>;
 20 private:
 21     T data;
 22     Node<T> *next;
 23 };
 24 
 25 template<class T>
 26 class linkList{
 27 public:
 28     linkList(Node<T>* first){head = first;}
 29     linkList(){head = 0;}
 30     ~linkList();
 31     bool isEmpty() const {return head == 0;}
 32     int Length() const;
 33     bool findElement(int k, T& x) const;
 34     int searchElement(const T& x) const;
 35     linkList<T>& deleteElement(int k, T& x);
 36     linkList<T>& insertElement(int k, const T& x);
 37     void output(ostream& out) const;
 38 private:
 39     Node<T> *head;
 40 };
 41 
 42 //deconstructor
 43 template<class T>
 44 linkList<T>::~linkList()
 45 {
 46     Node<T> *next;
 47     while (head)
 48     {
 49         next = head->next;
 50         delete head;
 51         head = next;
 52     }
 53 }
 54 
 55 //get the length of the linkList
 56 template<class T>
 57 int linkList<T>::Length() const
 58 {
 59     Node<T> *cur = head;
 60     int len = 0;
 61     while (cur)
 62     {
 63         len++;
 64         cur = cur->next;
 65     }
 66     return len;
 67 }
 68 
 69 //find function, x carry the value of the index-k
 70 template<class T>
 71 bool linkList<T>::findElement(int k, T& x) const
 72 {
 73     if (k<1)
 74         return false;
 75     Node<T> *cur = head;
 76     int index = 1;
 77     while (index<k && cur)
 78     {
 79         index++;
 80         cur = cur->next;
 81     }
 82     if (cur)
 83     {
 84         x = cur->data;
 85         return true;
 86     }
 87     return false;
 88 }
 89 
 90 
 91 //search function
 92 template<class T>
 93 int linkList<T>::searchElement(const T& x) const
 94 {
 95     Node<T> *cur = head;
 96     int index = 1;
 97     while (cur)
 98     {
 99         if (x == cur->data)
100             return index;
101         index++;
102         cur = cur->next;
103     }
104     return 0;
105 }
106 
107 //call the override function later
108 template<class T>
109 void linkList<T>::output(ostream& out) const
110 {
111     Node<T> *cur = head;
112     while (cur)
113     {
114         out<<cur->data<<" ";
115         cur = cur->next;
116     }
117     out<<endl;
118 }
119 
120 //override
121 template<class T>
122 ostream& operator<<(ostream& out, const linkList<T>& x)
123 {
124     x.output(out);
125     return out;
126 }
127 
128 //delete operation
129 template<class T>
130 linkList<T>& linkList<T>::deleteElement(int k, T& x)
131 {
132     if (k<1 || !head)
133         throw OutOfBounds();
134     Node<T> *cur = head;
135     if (k == 1)
136     {
137         head = head->next;
138         x = cur->data;
139         delete cur;
140         return *this;
141     }
142     else
143     {
144          int index = 1;
145          //find the prior fo the kth node
146          while (index<k-1 && cur)
147          {
148              index++;
149              cur = cur->next;
150          }
151          if (!cur || !(cur->next))
152              throw OutOfBounds();
153          Node<T> *de = cur->next;
154          cur->next = de->next;
155          x = de->data;
156          delete de;
157          return *this;
158     }
159 }
160 
161 //insert operation
162 template<class T>
163 linkList<T>& linkList<T>::insertElement(int k, const T& x)
164 {
165     if (k<=0)
166         throw OutOfBounds();
167     Node<T> *newNode = new Node<T>(x);
168     if (k==1)
169     {
170         newNode->next = head;
171         head = newNode;
172     }
173     else
174     {
175         Node<T> *cur = head;
176         for (int index=1; index<k-1; index++)
177             cur = cur->next;
178         if (!cur)
179         {
180             delete newNode;
181             throw OutOfBounds();
182         }
183         newNode->next = cur->next;
184         cur->next = newNode;
185     }
186     return *this;
187 }
188 #endif

 1 //excep.h异常类
 2 #ifndef _EXCP_
 3 #define _EXCP_
 4 #include <new>
 5 using namespace std;
 6 
 7 class OutOfBounds {
 8 public:
 9     OutOfBounds(){}
10 };
11 
12 class FullMemery {
13 public:
14     FullMemery(){}
15 };
16 
17 void my_new_handler()
18 {
19     throw FullMemery();
20 }
21 
22 new_handler old_handler = set_new_handler(my_new_handler);
23 #endif

 1 //linkList.cpp测试主函数
 2 #include <iostream>
 3 #include "linkList.h"
 4 #include "excp.h"
 5 using namespace std;
 6 int main()
 7 {
 8     try{
 9         linkList<int> L;
10         cout<<"Length = "<<L.Length()<<endl;
11         cout<<"IsEmpty = "<<L.isEmpty()<<endl;
12         L.insertElement(1 ,2).insertElement(2, 6).insertElement(2, 3).
13         insertElement(3, 6);
14         cout<<"List is "<<L<<endl;
15         cout<<"IsEmpty ="<<L.isEmpty()<<endl;
16         int c;
17         L.findElement(1, c);
18         cout<<"First element is "<<c<<endl;
19         cout<<"Length = "<<L.Length()<<endl;
20         L.deleteElement(1, c).deleteElement(3, c);
21         cout<<"Delete element is "<<c<<endl;
22         cout<<"List is "<<L<<endl;
23     }
24     catch(...)
25     {
26         cerr<<"This is a error"<<endl;
27     }
28     return 0;
29 }

总结：

1、对于表的下标起始位置要统一，本次程序采用起始下标为1。

2、利用友元类的访问权限，但要适度。

3、注意处理内存垃圾。