线性表的C++实现代码

qq751220449

线性表的C++实现代码 [复制链接]

使用C++实现链表的操作。欢迎大家留言提问。

1. // 1.cpp : 定义控制台应用程序的入口点。
   
2. // 16.线性表.cpp : 定义控制台应用程序的入口点。
   
3. //
   
4. 
   
5. #include "stdafx.h"
   
6. 
   
7. 
   
8. //enum bool{false,true};
   
9. template<class T>
   
10. class LinearList
    
11. {
    
12. public:
    
13.         LinearList(){}
    
14.         ~LinearList(){}
    
15.         virtual int Size() const =0;          //表的最大长度
    
16.         virtual int Length() const =0;                        //表的长度
    
17.         virtual int Search(T &x) const =0;
    
18.         virtual int Locate(int i) const =0;
    
19.         virtual bool getData(int i,T &x) const =0;
    
20.         virtual void setData(int i,T &x) =0;
    
21.         virtual bool Insert(int i,T &x) =0;
    
22.         virtual bool Remove(int i,T &x) =0;
    
23.         virtual bool IsEmpty() const =0;
    
24.         virtual bool IsFull() const =0;
    
25.         virtual void Sort() =0;
    
26.         virtual void input()=0;
    
27.         virtual void output()=0;
    
28.         virtual LinearList<T>operator=(LinearList<T>& L)=0;
    
29. };
    
30. 
    
31. template<class T>
    
32. struct LinkNode
    
33. {
    
34.         T data;
    
35.         LinkNode<T> * link;
    
36.         LinkNode(LinkNode<T> *ptr=NULL)
    
37.         {
    
38.                 link=ptr;
    
39.         }
    
40.         LinkNode(const T&item,LinkNode<T> *ptr=NULL)
    
41.         {
    
42.                 data=item;
    
43.                 link=ptr;
    
44.         }
    
45. };
    
46. template<class T>
    
47. class List
    
48.         //class List:public LinearList<T>
    
49. {
    
50. protected:
    
51.         LinkNode<T> *first;
    
52. public:
    
53.         List()
    
54.         {
    
55.                 first=new LinkNode<T>;
    
56.         }
    
57.         List(const T& x)
    
58.         {
    
59.                 first=new LinkNode<T>(x);
    
60.         }
    
61.         List(List<T> &L)
    
62.         {
    
63.                 T value1;
    
64.                 LinkNode<T>*srcptr=L.getHead();
    
65.                 LinkNode<T>*destptr=first=new LinkNode<T>;
    
66.                 while(srcptr->link!=NULL)
    
67.                 {
    
68.                         value1=srcptr->link->data;
    
69.                         destptr->link=new LinkNode<T>(value1);
    
70.                         destptr=destptr->link;
    
71.                         srcptr=srcptr->link;
    
72.                 }
    
73.                 destptr->link=NULL;
    
74.         }
    
75.         ~List(){makeEmpty();}
    
76.         void makeEmpty()
    
77.         {
    
78.                 LinkNode<T>* q;
    
79.                 while(first->link!=NULL)
    
80.                 {
    
81.                         q=first->link;
    
82.                         first->link = q->link;
    
83.                         delete q;       
    
84.                 }
    
85.         }
    
86.         int Length()const
    
87.         {
    
88.                 LinkNode<T>* p;
    
89.                 int count=0;
    
90.                 p=first->link;
    
91.                 while(p!=NULL)
    
92.                 {
    
93.                         p=p->link;
    
94.                         count++;
    
95.                 }
    
96.                 return count;
    
97.         }
    
98.         LinkNode<T>* getHead()const
    
99.         {
    
100.                 return first;
     
101.         }
     
102.         bool IsEmpty()const
     
103.         {
     
104.                 return first->link==NULL?true:false;
     
105.         }
     
106.         bool IsFull()const
     
107.         {
     
108.                 return false;
     
109.         }
     
110.         LinkNode<T> * search(T x)
     
111.         {
     
112.                 LinkNode<T>* current;
     
113.                 current=first->link;
     
114.                 while(current!=NULL)
     
115.                 {
     
116.                         if(current->data==x)
     
117.                         {
     
118.                                 break;
     
119.                         }
     
120.                         else
     
121.                         {
     
122.                                 current=current->link;
     
123.                         }
     
124.                 }
     
125.                 return current;
     
126.         }
     
127.         LinkNode<T>* Locate(int i)
     
128.         {
     
129.                 LinkNode<T>* current;
     
130.                 current=first;
     
131.                 int k=0;
     
132.                 for (;k<i;k++)
     
133.                 {
     
134.                         if (current==NULL)
     
135.                         {
     
136.                                 break;       
     
137.                         }
     
138.                         current=current->link;
     
139.                 }
     
140.                 return current;
     
141.         }
     
142.         bool getData(int i,T &x)const
     
143.         {
     
144.                 if (i<=0)
     
145.                 {
     
146.                         return NULL;
     
147.                 }
     
148.                 LinkNode<T>*current=Locate(i);
     
149.                 if (current==NULL)
     
150.                 {
     
151.                         return false;
     
152.                 }
     
153.                 else
     
154.                 {
     
155.                         x=current->data;
     
156.                         return true;
     
157.                 }
     
158.         }
     
159.         void setData(int i,T &x)
     
160.         {
     
161.                 if (i<=0)
     
162.                 {
     
163.                         return;
     
164.                 }
     
165.                 LinkNode<T>*current=Locate(i);
     
166.                 if (current==NULL)
     
167.                 {
     
168.                         return;
     
169.                 }
     
170.                 else
     
171.                 {
     
172.                         current->data=x;
     
173.                 }
     
174.         }
     
175.         bool Insert(int i,T &x)
     
176.         {
     
177.                 if(i<0)
     
178.                 {
     
179.                         return false;
     
180.                 }
     
181.                 LinkNode<T>*current=Locate(i);
     
182.                 if (current==NULL)
     
183.                 {
     
184.                         return false;
     
185.                 }
     
186.                 LinkNode<T>*newNode=new LinkNode<T>(x);
     
187.                 if (newNode==NULL)
     
188.                 {
     
189.                         cerr<<"存储器空间分配错误"<<endl;
     
190.                         exit(1);
     
191.                 }
     
192.                 newNode->link=current->link;
     
193.                 current->link=newNode;
     
194.                 return true;
     
195.         }
     
196.         bool Remove(int i,T &x)
     
197.         {
     
198.                 LinkNode<T>*current=Locate(i-1);
     
199.                 if (current==NULL||current->link==NULL)
     
200.                 {
     
201.                         return false;
     
202.                 }
     
203.                 LinkNode<T>*del=current->link;
     
204.                 current->link=del->link;
     
205.                 x=del->data;
     
206.                 delete del;
     
207.                 return true;
     
208.         }
     
209.         void output()
     
210.         {
     
211.                 LinkNode<T>*current=first->link;
     
212.                 while (current!=NULL)
     
213.                 {
     
214.                         cout<<current->data<<endl;
     
215.                         current=current->link;
     
216.                 }
     
217.         }
     
218.         LinkNode<T>& operator=(List<T>&L)
     
219.         {
     
220.                 T value1;
     
221.                 LinkNode<T>*srcptr=L.getHead();
     
222.                 LinkNode<T>*destptr=first=new LinkNode<T>;
     
223.                 while(srcptr->link!=NULL)
     
224.                 {
     
225.                         value1=srcptr->link->data;
     
226.                         destptr->link=new LinkNode<T>(value1);
     
227.                         destptr=destptr->link;
     
228.                         srcptr=srcptr->link;
     
229.                 }
     
230.                 destptr->link=NULL;
     
231.                 return *this;
     
232.         }
     
233. 
     
234. };
     
235. int _tmain(int argc, _TCHAR* argv[])
     
236. {
     
237.         List<int> a(1);
     
238.         int c=10;
     
239.         int d=20;
     
240.         a.Insert(0,c);
     
241.         a.Insert(1,d);
     
242.         int b=0;
     
243.         b=a.Length();
     
244.         cout<<b<<endl;
     
245.         a.output();
     
246.         List<int> h(a);
     
247. //        h=a;
     
248.         d=1000;
     
249.         h.setData(1,d);
     
250.         h.output();
     
251.         return 0;
     
252. }
     
253. 输出结果如下:

复制代码