线性表的顺序表示实现－C++版

声明：本文内容属于本人原创，欢迎转载，请大家在转载时注明转贴地址

使用一个模板类实现了线性表的顺序表示，我对这个模板类进行了简单的测试，大家如果在使用过程中或看代码的过程中遇到错误请及时提出，谢谢！该代码已经在VS2005环境下编译通过

1. /**
2. *@fileListSqu.h
3. *@authorWangLiuqiang
4. *@version1.0
5. *@date2008-11-30
6. *@brief该类实现了线性表的顺序表示
7. */
9. #ifndefLISTSQU_H_
10. #defineLISTSQU_H_
12. #include<assert.h>
13. #include<iostream>
14. usingnamespacestd;
16. #defineLIST_INIT_SIZE100
17. #defineLISTINCREMENT10
19. #defineSQUSUCCEED0
20. #defineSQUERROR-1
21. #defineSQUOVERFLOW-2
23. /*
24. *定义了两个默认的函数，如果用户在调用LocalElem()函数时没有指定
25. *函数，则使用默认的equal()函数；如果指定了自己的比较函数，则将
26. *自己的函数指针赋给LocalElem()函数
27. */
28. template<classT>
29. boolequal(Te1,Te2)
30. {
31. if(e1==e2)
32. {
33. returntrue;
34. }
35. else
36. {
37. returnfalse;
38. }
39. }
41. /*
42. *定义了两个默认的函数，如果用户在调用Traverse()函数时没有指定
43. *函数，则使用默认的show()函数；如果指定了自己的比较函数，则将
44. *自己的函数指针赋给Traverse()函数
45. */
47. template<classT>
48. voidshow(Te)
49. {
50. cout<<e<<endl;
51. }
53. template<classT>
54. classListSqu
55. {
56. public:
57. /*
58. *name构造函数/析构函数
59. *@{
60. */
61. ListSqu();
62. ~ListSqu();
64. ListSqu(constListSqu<T>&ls);
65. ListSqu<T>&operator=(constListSqu<T>&ls);
66. /**@}*///构造函数/析构函数
68. public:
69. /*
70. *清空顺序表
71. *@return返回函数执行结果:
72. *-0表示执行成功
73. *-1表示执行出错
74. */
75. intClearList();
77. /*
78. *判断顺序表是否为空
79. *@return返回函数执行结果:
80. *-true表示顺序表为空
81. *-false表示顺序表不为空
82. */
83. boolIsEmpty();
85. /*
86. *返回顺序表中元素个数
87. *@return返回顺序表中元素个数
88. */
89. intLength();
91. /*
92. *返回线性表中第一个与e满足关系Compare()的数据元素的位序
93. *@param[in]e待判定的元素
94. *@param[in]Compare函数指针，指向判定元素的函数指针，默认为比较元素是否相等
95. *@return返回线性表中第一个与e满足关系Compare()的数据元素的位序
96. */
97. intLocalElem(constT&e,bool(*Compare)(T,T)=equal);
99. /*
100. *返回顺序表中第i个位置的元素
101. *@param[in]i需要获取元素的位置
102. *@param[out]e顺序表中第i个位置的元素值
103. *@return返回函数执行结果
104. *-SQUSUCCEED表示函数执行成功
105. *-SQUERROR表示函数执行失败
106. *@noteC++中数组的下标是从0开始，因此第i个位置的元素应该取下标为i-1的元素
107. */
108. intGetItem(inti,T&e);
110. /*
111. *在顺序表的第i个位置之前插入元素
112. *@param[in]元素的插入位置
113. *@param[in]插入元素值
114. *@return返回函数的执行结果
115. *-SQUSUCCEED表示函数执行成功
116. *-SQUERROR表示函数执行失败
117. */
118. intInsertItem(inti,T&e);
120. /*
121. *删除顺序表中第i个位置的元素
122. *@param[in]i待删除元素位置
123. *@param[out]e删除元素的值
124. *@return返回函数的执行结果
125. *-SQUSUCCEED表示函数执行成功
126. *-SQUERROR表示函数执行失败
127. */
128. intDeleteItem(inti,T&e);
130. /*
131. *显示顺序表中元素
132. *@return返回函数的执行结果
133. *-SQUSUCCEED表示函数执行成功
134. *-SQUERROR表示函数执行失败
135. */
136. intShow();//输出表中元素
138. /*
139. *遍历线性表中元素
140. *@param[in]vi函数指针，指向处理元素函数，默认为在屏幕打印元素
141. */
142. voidTraverse(void(*vi)(Te)=show);
144. private:
145. T*items;
146. intlength;
147. intlistsize;
148. };
150. template<classT>
151. ListSqu<T>::ListSqu()
152. {
153. items=newT[LIST_INIT_SIZE];
154. assert(items);
155. length=0;
156. listsize=LIST_INIT_SIZE;
157. }
159. template<classT>
160. ListSqu<T>::~ListSqu()
161. {
162. if(items!=NULL)
163. {
164. delete[]items;
165. items=NULL;
166. }
167. }
169. template<classT>
170. ListSqu<T>::ListSqu(constListSqu<T>&ls)
171. {
172. length=ls.length;
173. listsize=ls.listsize;
175. items=newT[listsize+1];
176. memcpy(items,ls.items,_msize(ls.items));
177. }
179. template<classT>
180. ListSqu<T>&ListSqu<T>::operator=(constListSqu<T>&ls)
181. {
182. if(this==&ls)
183. return*this;
185. if(items!=NULL)
186. {
187. delete[]items;
188. items=NULL;
189. }
191. length=ls.length;
192. listsize=ls.listsize;
194. items=newT[listsize+1];
195. memcpy(items,ls.items,_msize(ls.items));
196. return*this;
197. }
199. template<classT>
200. intListSqu<T>::ClearList()
201. {
202. length=0;
203. returnSQUSUCCEED;
204. }
206. template<classT>
207. boolListSqu<T>::IsEmpty()
208. {
209. returnlength==0;
210. }
212. template<classT>
213. intListSqu<T>::LocalElem(constT&e,bool(*Compare)(T,T))
214. {
215. inti=0;
216. T*p;
217. p=items;
218. while(i<length&&!Compare(*p++,e))
219. {
220. ++i;
221. }
223. if(i<length)
224. {
225. returni+1;
226. }
227. else
228. {
229. return0;
230. }
231. }
233. template<classT>
234. intListSqu<T>::GetItem(inti,T&e)
235. {
236. if((i<1)||(i>length))
237. {
238. cout<<"所给位置超出位置索引!"<<endl;
239. returnSQUERROR;
240. }
241. else
242. {
243. e=items[i-1];
244. returnSQUSUCCEED;
245. }
246. }
248. template<classT>
249. intListSqu<T>::InsertItem(inti,T&e)
250. {
251. if(i<1||i>length+1)
252. {
253. cout<<"所给位置出错！"<<endl;
254. returnSQUERROR;
255. }
256. else
257. {
258. if(length>=listsize)
259. {
260. T*pNew=newT[LISTINCREMENT];
261. memcpy(pNew,items,_msize(items));
262. items=pNew;
264. if(items==NULL)
265. {
266. cout<<"申请内存空间失败！"<<endl;
267. returnSQUOVERFLOW;
268. }
269. listsize+=LISTINCREMENT;
270. }
272. for(intk=length;k>=i-1;k--)
273. {
274. items[k+1]=items[k];
275. }
277. items[i-1]=e;
278. length++;
280. returnSQUSUCCEED;
281. }
282. }
284. template<classT>
285. intListSqu<T>::DeleteItem(inti,T&e)
286. {
287. if(i<1||i>length)
288. {
289. cout<<"所给删除位置出错！"<<endl;
290. returnSQUERROR;
291. }
293. e=items[i-1];
295. for(i=i-1;i<length;i++)
296. {
297. items[i]=items[i+1];
298. }
299. length--;
300. returnSQUSUCCEED;
301. }
303. template<classT>
304. intListSqu<T>::Show()
305. {
306. for(inti=0;i<length;i++)
307. {
308. cout<<items[i]<<endl;
309. }
310. returnSQUSUCCEED;
311. }
313. template<classT>
314. voidListSqu<T>::Traverse(void(*vi)(Te))
315. {
316. for(inti=0;i<length;i++)
317. {
318. vi(items[i]);
319. }
320. }
321. #endif

通过编写这段代码，觉得以下几点需要特别注意：

1. 需要特别注意内存越界的情况，对于动态申请的内存指针，如果对其进行越界操作，在使用delete操作释放该指针时会造成程序崩溃。在编写上面的程序时就将

template <class T> ListSqu<T>& ListSqu<T>::operator=(const ListSqu<T>& ls)

函数中items = new T[listsize + 1];错误的写成了items = new T[length + 1];而造成内存越界，详细解释如下：

template <class T>
ListSqu <T>& ListSqu <T>::operator=(const ListSqu <T>& ls)
{
if( this == &ls )
return *this;

delete[] items;
items = NULL;

length = ls.length;
listsize = ls.listsize;

items = new T[length + 1];
memcpy(items, ls.items, _msize(ls.items));
return *this;
}

items = new T[length + 1];
这里应该是
items = new T[listsize + 1];
listsize是我在类的构造函数中初始化分配的内存数，而length是当前线性表中存放的元素个数，这里用length+1分配内存，而在memcpy(items, ls.items, _msize(ls.items)); 又将sizeof(T)*listsize长的字节拷贝给items该处发生越界了

2. 注意模板类的复制构造函数和赋值操作符的声明方法

3. 注意如何把函数指针当作形参并对其使用默认参数的方法