数据结构第二章线性表

线性表的本质和操作

线性表的表现形式

零个或多个数据元素组成的集合
数据元素在位置上是有序排列的
数据元素的个数是有限的
数据元素的类型必须相同

线性表的抽象定义

线性表具有相同类型的n(≥0)个数据元素的有限序列
(_a_{0,a1,a2,.......,an-1})
ai是表项（数据元素），n是表长度

线性表的本质性质

a0为线性表的第一个元素，只有一个后继
an-1为线性表的最后一个元素，只有一个前驱
除a0和an-1外其它语速ai,既有前驱，又有后继
直接支持逐项访问和顺序存取

线性表的一些常用操作

将元素插入线性表
将元素从线性表中删除
获取目标位置处元素的值
设置目标位置处元素的值
获取线性表的长度
清空线性表

编程实验

静态顺序存储

　　代码如下

#include<iostream>

using namespace std;

template<typename T , int N>
class StaticList{
    protected:
        T m_array[N];
        int m_length;
    public:
        
        StaticList(){
            this->m_length = 0;
        }
        bool insert(const T& e){
            bool ret;
            
            ret = this->length() + 1 <= this->capacity();// 当前要插入的元素保证不能越界 
            if(ret){
                this->m_array[this->length()] =e;
                this->m_length ++ ; 
            } 
            return ret; 
        } 
        
             
        bool insert(int pos,const T& e) {
            bool ret;
                        
            ret = this->length() + 1 <= this->capacity(); //不能越界 
            ret = ret && ((pos >=0 ) && pos <= this->length());//pos合法 
            
            if(ret){
                for(int i = this->length() - 1;i >= pos;i ++){
                    this->m_array[i + 1] = this->m_array[i]; // 从最后一个元素开始后移 一直到pos处 
                }
                this->m_array[pos] = e;
                this->m_length ++;
            }
            return ret;
        } 
        bool remove(int pos){
            bool ret;
            
            ret =  ((pos >=0 ) && pos <= this->length());//pos合法 
            if(ret){
                for(int i = pos;i > 0;i++){
                    this->m_array[i] = this->m_array[i - 1];// 往前移动一个位置 
                }
                this->m_length --; 
            }
            return ret;
        } 
        int find(const T& e ) const{
            int pos = -1;
            
            for(int i = 0;i <= 0;i++){
                if(this->m_array[i] == e){
                    pos = i;
                    break;
                }
            }
            return pos;
        }
        bool set(int pos,const T& e) {
            bool ret;
                    
            ret =  ((pos >=0 ) && pos <= this->length());//pos合法 
            if(ret){
                this->m_array[pos] = e;
            }
            return ret ;
        }
        bool get(int pos,T& e) const {
            bool ret;
                    
            ret =  ((pos >=0 ) && pos <= this->length());//pos合法 
            if(ret){
                e = this->m_array[pos] ;
            }
            return ret ;
        }
        int length() const {
            
            return this->m_length;
        }
        void clear(){
            
            return this->m_length = 0 ;
        }
        int capacity() const  {
            
            return N;
        }
        
        T & operator[](int pos){
            
            return this->m_array[pos];
        }
};

int main()
{
    int i = 0;
    StaticList<int ,10> * list = new StaticList<int,10>;
    
    for(i = 0 ; i < 5 ; i ++){
        list->insert(i);
    }
    
    for(i = 0 ; i < 5 ; i ++){
        cout << (*list)[i] << "	";
    }
    
    cout << endl;
    
    (*list)[4] = 100 ;
    for(i = 0 ; i < list->length() ; i ++){
        cout << (*list)[i] << "	";
    }
    
    cout << endl;
    list->set(2,20);
    for(i = 0 ; i < list->length() ; i ++){
            cout << (*list)[i] << "	";
    }
    
    int val;
    
    list->get(2,val);
    cout << endl << val;
    
    for(i = list->length() ; i < list->capacity() ; i ++){
            list->insert(i);
    }
    
    cout << endl;
    for(i = 0 ; i < list->length() ; i ++){
            cout << (*list)[i] << "	";
    }
    return 0;
}

StaticList

使用原生数组作为顺序存储空间
使用模板参数作为数组的空间，一旦开辟了数组的空间就不能修改
插入，删除，修改元素的时候，一定要确保pos是合法的，不合法的时候可以抛出异常，调用处处理

打印结果

0       1       2       3       4
0       1       2       3       100
0       1       20      3       100
20
0       1       20      3       100     5       6       7       8       9

动态顺序存储

　　区别可以追加数组的容量。用堆开辟空间

  1 #include<iostream>
  2 #include<cstdlib> 
  3 using namespace std;
  4 
  5 
  6 class  Object{
  7     
  8     public:
  9         void* operator new(unsigned int size) throw()
 10         {
 11             cout <<"new size"<<size<<endl ;
 12             return malloc(size);
 13         }
 14         void operator delete(void *p)
 15         {
 16             cout <<"delete"<<p<<endl ;
 17             free(p);
 18         }
 19         void* operator new[] (unsigned int size)throw()
 20         {
 21             cout <<"new size []"<<size<<endl ;
 22             return malloc(size);
 23         }
 24         void operator delete[](void *p)
 25         {
 26             cout <<"delete size []"<<p<<endl ;
 27             free(p);
 28         }
 29         bool operator ==(const Object& obj)
 30         {
 31             return (this==&obj);
 32         }
 33         bool operator !=(const Object& obj)
 34         {
 35             return (this!=&obj);
 36         }
 37         
 38 };
 39 template<typename T>
 40 class DaycList : public Object{ 
 41 
 42     protected:
 43         int size;
 44         T   *m_array;
 45         int  m_length;
 46     
 47     public:
 48             
 49         DaycList(){
 50             
 51         }
 52             
 53         DaycList(int size){
 54             this->size = size;
 55             this->m_array = new T[size];
 56         }
 57         bool insert(const T& e){
 58             
 59             bool ret = 1;
 60             
 61             if(this->length() == this->capacity() / 2)
 62              {
 63                  T *temp = this->m_array;
 64                  this->m_array = new T[ 2 * size]; 
 65                  if(this->m_array == NULL){
 66                      ret = 0;
 67                  }
 68                  for(int i = 0 ; i < this->length() ; i ++){
 69                      this->m_array[i] =temp[i];
 70                  }
 71                  this->size *= 2; 
 72                  delete temp;
 73              }
 74                          
 75             this->m_array[this->length()] =e;
 76             this->m_length ++ ; 
 77             return ret; 
 78         } 
 79         
 80         bool insert(int pos,const T& e) {
 81             bool ret;
 82                         
 83             ret =  ((pos >=0 ) && this->length() == this->capacity() / 2);//pos合法 
 84             
 85              if(ret)
 86              {
 87                  T *temp = this->m_array;
 88                  this->m_array = new T[ 2 * size];
 89                  for(int i = 0 ; i < this->length() ; i ++){
 90                      this->m_array =temp[i];
 91                   }
 92                  this->size *= 2; 
 93                  delete temp;
 94              
 95              }
 96             for(int i = this->length() - 1;i >= pos;i ++){
 97                 this->m_array[i + 1] = this->m_array[i]; // 从最后一个元素开始后移 一直到pos处 
 98             this->m_array[pos] = e;
 99             this->m_length ++;
100             }
101             return ret;
102         } 
103         bool remove(int pos){
104             bool ret;
105             
106             ret =  ((pos >=0 ) && pos <= this->length());//pos合法 
107             if(ret){
108                 for(int i = pos;i > 0;i++){
109                     this->m_array[i] = this->m_array[i - 1];// 往前移动一个位置 
110                 }
111                 this->m_length --; 
112             }
113             return ret;
114         } 
115         int find(const T& e ) const{
116             int pos = -1;
117             
118             for(int i = 0;i <= 0;i++){
119                 if(this->m_array[i] == e){
120                     pos = i;
121                     break;
122                 }
123             }
124             return pos;
125         }
126         bool set(int pos,const T& e) {
127             bool ret;
128                     
129             ret =  ((pos >=0 ) && pos <= this->length());//pos合法 
130             if(ret){
131                 this->m_array[pos] = e;
132             }
133             return ret ;
134         }
135         bool get(int pos,T& e) const {
136             bool ret;
137                     
138             ret =  ((pos >=0 ) && pos <= this->length());//pos合法 
139             if(ret){
140                 e = this->m_array[pos] ;
141             }
142             return ret ;
143         }
144         int length() const {
145             
146             return this->m_length;
147         }
148         void clear(){
149             
150             return this->m_length = 0 ;
151         }
152         int capacity() const  {
153             
154             return this->size;
155         }
156         
157         T & operator[](int pos){
158             
159             return this->m_array[pos];
160         }
161         
162         ~DaycList()
163         {
164             delete this->m_array;
165         }
166     
167 };
168 
169 int main()
170 {
171     int i = 0;
172     DaycList<int> * list = new DaycList<int>(10);// 此处申请失败 容易抛出异常 ,所以我们重写new 让其用malloc申请 
173     
174     for(i = 0 ; i < 5 ; i ++){
175         list->insert(i);
176      
177     }
178     
179     for(i = 0 ; i < 5 ; i ++){
180         cout << (*list)[i] << "	";
181     }
182     
183     cout << endl;
184     
185     (*list)[4] = 100 ;
186     for(i = 0 ; i < list->length() ; i ++){
187         cout << (*list)[i] << "	";
188     }
189     
190     cout << endl;
191     list->set(2,20);
192     for(i = 0 ; i < list->length() ; i ++){
193             cout << (*list)[i] << "	";
194     }
195     
196     int val;
197     
198     list->get(2,val);
199     cout << endl << val;
200     
201     for(i = list->length() ; i <= 15 ; i ++){
202             list->insert(i);
203     }
204     
205     cout << endl;
206     for(i = 0 ; i < list->length() ; i ++){
207         cout << (*list)[i] << "	";
208     }
209     
210     cout <<endl; 
211     delete list; 
212     return 0;
213 }

DaycList

打印结果

1 new size12
2 0       1       2       3       4
3 0       1       2       3       100
4 0       1       20      3       100
5 20
6 0       1       20      3       100     5       6       7       8       9       10      11      12      13      14      15
7 delete0xf70ca8

可以在main函数中处理异常，在new T[]的时候空间可能会申请失败，可以抛出异常让调用处处理；65- 67 可以抛出异常这里面没有抛，

长度为容量的一半的时候就会进行扩容，这个根据需求来就行。

数据结构本来就是学的思维！

时间不会留下一切，只有记忆记录了过去！

数据结构第二章 线性表

线性表的本质和操作

线性表的表现形式

线性表的抽象定义

线性表的本质性质

线性表的一些常用操作

编程实验

打印结果

数据结构第二章线性表