「数据结构」:顺序表的实现

使用c++实现一下常用的数据结构，参考书为《数据结构、算法与应用－c++语言描述》。

此次代码为顺序表，为了保证通用性采用模板机制，算法本身没有什么难度，毕竟是基础算法，但是长时间不用c++，一些高级特性和陷阱着实让人难受。

此次代码共分三个文件：

1、Sq_list.h ：实现顺序表的结构和基本操作。

2、excp.h ：实现异常类，关于命名空间的问题，直接将异常类加入到std空间内。

3、sq.cpp ：主函数，简单测试，可稍加简单修改，转为交互式程序。

 1 Sq_list.h
 2 //construct the sq_list with template 
 3 #ifndef _sqList_ 
 4 #define _sqList_
 5 #include <iostream>
 6 #include "excp.h"
 7 using namespace std;
 8 
 9 template<class T>
10 class sqList {
11 public:
12     sqList(int maxSizel = 10);
13     ~sqList(){delete [] data;}
14     bool isEmpty() const{return length == 0;}
15     template<class Type>
16     friend ostream& operator<<(ostream& out, const sqList<Type>& x);
17     int getLength() const{return length;}
18     bool findElement(int k, T& x) const;//get the kth value in the var x
19     int searchElement(T& x) const;//return the index of the var x
20     sqList<T>& deleteElement(int k, T& x);//remove the kth element and return it by x
21     sqList<T>& insertElement(int k, const T& x);//Insert x
22     T* getData() const {return data;}
23 private:
24     T *data;
25     int length;
26     int maxSize;
27 };
28 
29 template<class T>
30 sqList<T>::sqList(int maxSizel)
31 {
32     maxSize = maxSizel;
33     data = new T[maxSize];
34     length = 0;
35 }
36 
37 template<class T>
38 bool sqList<T>::findElement(int k, T& x) const
39 {
40     if (k<1 || k>length)
41         return false;
42     x = data[k-1];
43     return true;
44 }
45 
46 template<class T>
47 int sqList<T>::searchElement(T& x) const
48 {
49     for (int i=0; i<length; i++)
50         if (data[i] == x)
51             return i+1;
52     return 0;
53 }
54 
55 template<class T>
56 sqList<T>& sqList<T>::deleteElement(int k, T& x)
57 {
58     if (findElement(k, x))
59     {
60         for (int i=k; i<length; i++)
61             data[i-1] = data[i];
62         length--;
63         return *this;
64     }
65     else
66         throw OutOfBounds();
67 }
68 
69 template<class T>
70 sqList<T>& sqList<T>::insertElement(int k, const T& x)
71 {
72     if (k<1 || k>length+1)
73         throw OutOfBounds();
74     if (length >= maxSize)
75         throw FullMemery();
76     for (int i=length-1; i>=k-1; i--)
77         data[i+1] = data[i];
78     data[k-1] = x;
79     length++;
80     return *this;
81 }
82 
83 template<class Type>
84 ostream& operator<<(ostream& out, const sqList<Type>& x)
85 {
86     Type* t = x.getData();
87     for (int i=0; i<x.getLength(); i++)
88         out<<t[i]<<" ";
89     out<<endl;
90     return out;
91 }
92 #endif

 1 excp.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 sq.cpp
 2 #include <iostream>
 3 #include "Sq_list.h"
 4 #include "excp.h"
 5 using namespace std;
 6 int main()
 7 {
 8     try{
 9         sqList<int> L(5);
10         cout<<"Length = "<<L.getLength()<<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.getLength()<<endl;
20         L.deleteElement(1, 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、在模板类中重载操作符，稳妥的一种方法就是像程序中这样在外层模板中（类模板）对于友元重载函数声名成另一模板，否则会提示basic_ostream找不到匹配函数什么的，估计是编译器在定义ostream的时候把所有可用的查了一遍，结果没找到合适的。

2、对于异常，使用自定义的异常，方便定制。

3、良好的编程习惯，遵循最小权限原则，对于公有函数要进行一定的限制。

4、写代码要小心，错将#ifndef写成#ifdef浪费了大量时间。