启迪思维：顺序存储

　参加工作快三年，兴趣和生存压力促使自己在业余时间学习一些底层知识，慢慢发现这些看似用不上的东东，很好锻炼我逻辑思维，也大大提升我工作效率。在这里和大家分享我用C++写一个简易版STL，仅供参考和学习使用，想更好更全面学习数据结构请参考官方STL源码。

　　在阅读本片代码的时候注意一下几点(请参考Effective C++)：　　

　　1、用了泛型技术：templeate <class T>　　

　　2、const 引用　　

　　3、auto_ptr智能指针

一、概念

　　在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向明上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表，如下图(我画的图比土，在网上找几张好看便于理解)

单向链表：

二、使用范围

链表许多其它数据结构基础，如堆栈，队列和他们的派生。

三、实现操作(顺序存储)

1、类的属性、方法

 1 private:
 2     int length;//链表元素个数
 3     int size;//链表实存储大小
 4     T *elem;//链表节点元素
 5 void Clear(){
 6     length = 0;
 7 }
 8 
 9 bool IsEmpty() const{
10     return length == 0;
11 }
12 
13 int Length() const{
14     return length;
15 }

2、初始化和销毁：在项目中要多关注一个对象从初始化和销毁过程，一般优化都从这里开始，这个过程最好都是显式操作，拒绝编译器自动生产构造方法。

 1 /**
 2  *以前写程序总是喜欢给一个默认值
 3  *(然而从设计角度来看，这样做并不恰当。默认值应该符合大多数情况下的要求，
 4  *给指定链表一个默认值，例如k=100，并不符合一个「通用型 链表」的需求。
 5  *更好的作法是让使用者指定这两个参数的值，并在文件中说明它们的意义)
 6  */
 7 ArrayList(int k):length(0),size(k),elem(new T[k]) {
 8 }
 9 ~ArrayList() {
10     //这种删除内存很危险，更多请参考boost里shared_array
11     delete[] elem;
12 }

3、插入一个元素：

 1 /**
 2  *把e元素插入链表i的位置
 3  */
 4 bool Insert(const int &i,const T &e){
 5     if(i < 1 || i > length+1)
 6         return false;
 7 
 8     T *newSpace,*p,*q;
 9 
10     //如果当前链表位置已经满，动态扩展链表长度为原链表2倍
11     if(length == size){
12         newSpace = new T[size*2];
13         //复制原空间的数据到新创建空间
14         for(int j = 0; j < length; j++){
15             *(newSpace + j) = *(elem + j);
16         }
17 
18         //删除原空间内存
19         delete[] elem;
20         elem = newSpace;
21         //更长存储容量
22         size = size*2;
23     }
24 
25     q = elem + i -1;
26 
27     //插入之前,插入点后面元素都向后移动一位,这里就体现静态链表在大量插入元素时候效率会很低
28     for(p = elem + length -1; p >= q ; --p){
29         *(p + 1) = *p;
30     }
31     *q = e;
32     ++length;
33     return true;
34 }

4、删除一个元素：

 1 /**
 2  *根据i的值删除链表中的元素
 3  */
 4 bool Delete(const int &i){
 5 
 6     if(i < 1 || i > length)
 7         return false;
 8 
 9     T *p,*q;
10     p =  elem + i - 1;
11 
12     q = elem + length -1;
13     //插入之前,插入点后面元素都向前移动一位,这里就体现静态链表在大量删除元素时候效率会很低
14     for(++p; p <= q; ++p){
15         *(p-1) = *p;
16     }
17     --length;
18     return true;
19 }

5、获取一个元素：

 1 /**
 2  *根据i获取链表元素值
 3  */
 4 T& GetElem(const int &i) const{
 5 
 6     if(i < 1 || i > length){
 7         T t = T();
 8         return t;
 9     }
10 
11     return *(elem+i-1);
12 
13 }
14 /**
15  * 获取元素和e元素相对的元素位置
16  */
17 int GetElemByValue(const T &e) const{
18 
19     int i = 0;
20     while(i <= length && *(elem + i -1) == e){
21         i++;
22     }
23 
24     if(i < length){
25         return i;
26     }else{
27         return 0;
28     }
29 
30 }

完整代码

View Code

  1 #ifndef ARRAYLIST_H_
  2 #define ARRAYLIST_H_
  3 template<typename T>
  4 class ArrayList{
  5 private:
  6     int length;//链表元素个数
  7     int size;//链表实存储大小
  8     T *elem;//链表节点元素
  9 public:
 10     /**
 11      *以前写程序总是喜欢给一个默认值
 12      *(然而从设计角度来看，这样做并不恰当。默认值应该符合大多数情况下的要求，
 13      *给指定链表一个默认值，例如k=100，并不符合一个「通用型 链表」的需求。
 14      *更好的作法是让使用者指定这两个参数的值，并在文件中说明它们的意义)
 15      */
 16     ArrayList(int k):length(0),size(k),elem(new T[k]) {
 17     }
 18     ~ArrayList() {
 19         //这种删除内存很危险，更多请参考boost里shared_array
 20         delete[] elem;
 21     }
 22 
 23     void Clear(){
 24         length = 0;
 25     }
 26 
 27     bool IsEmpty() const{
 28         return length == 0;
 29     }
 30 
 31     int Length() const{
 32         return length;
 33     }
 34     /**
 35      * 获取元素和e元素相对的元素位置
 36      */
 37     int GetElemByValue(const T &e) const{
 38 
 39         int i = 0;
 40         while(i <= length && *(elem + i -1) == e){
 41             i++;
 42         }
 43 
 44         if(i < length){
 45             return i;
 46         }else{
 47             return 0;
 48         }
 49 
 50     }
 51 
 52     /**
 53      *根据i的值删除链表中的元素
 54      */
 55     bool Delete(const int &i) const{
 56 
 57         if(i < 1 || i > length)
 58             return false;
 59 
 60         T *p,*q;
 61         p =  elem + i - 1;
 62 
 63         q = elem + length -1;
 64         //插入之前,插入点后面元素都向前移动一位,这里就体现静态链表在大量删除元素时候效率会很低
 65         for(++p; p <= q; ++p){
 66             *(p-1) = *p;
 67         }
 68 
 69         return true;
 70     }
 71 
 72     /**
 73      *把e元素插入链表i的位置
 74      */
 75     bool Insert(const int &i,const T &e){
 76         if(i < 1 || i > length+1)
 77             return false;
 78 
 79         T *newSpace,*p,*q;
 80 
 81         //如果当前链表位置已经满，动态扩展链表长度为原链表2倍
 82         if(length == size){
 83             newSpace = new T[size*2];
 84             //复制原空间的数据到新创建空间
 85             for(int j = 0; j < length; j++){
 86                 *(newSpace + j) = *(elem + j);
 87             }
 88 
 89             //删除原空间内存
 90             delete[] elem;
 91             elem = newSpace;
 92             //更长存储容量
 93             size = size*2;
 94         }
 95 
 96         q = elem + i -1;
 97 
 98         //插入之前,插入点后面元素都向后移动一位,这里就体现静态链表在大量插入元素时候效率会很低
 99         for(p = elem + length -1; p >= q ; --p){
100             *(p + 1) = *p;
101         }
102         *q = e;
103         ++length;
104         return true;
105     }
106     /**
107      *根据i获取链表元素值
108      */
109     T& GetElem(const int &i) const{
110 
111         if(i < 1 || i > length){
112             T t = T();
113             return t;
114         }
115 
116         return *(elem+i-1);
117 
118     }
119 
120     void test(){
121         ArrayList list(5);
122         for(int i = 0; i < 10; ++i){
123             list.Insert(1,i);
124         }
125         for(int i = 0; i < 10; ++i){
126             std::cout<<list.GetElem(i)<<" ";
127         }
128         std::cout<<endl;
129         list.Delete(4);
130         for(int i = 0; i < 10; ++i){
131             std::cout<<list.GetElem(i)<<" ";
132         }
133     }
134 };
135 
136 #endif /* ARRAYLIST_H_ */

欢迎继续阅读“启迪思维：数据结构和算法”系列