赞
踩
什么是线性表?
线性表是具有相同类型的n个数据元素的优先序列。
线性表(List)的表现形式:
1、零和多个数据元素的集合;
2、数据元素在位置上是有序排列的;
3、数据元素的个数是有限的;
4、数据元素的类型必须相同。
线性表的性质:
a0为线性表的第一个元素,只有一个后继;a(n-1)为最后一个元素,只有前驱;除了这两个外,其他元素,既有前驱,也有后继。直接支持逐项访问和顺序存取。
如何在程序中描述和使用一个线性表?
先对线性表的操作进行抽象:插入元素、删除元素、获取元素、设置元素、获取长度、清空。
设计一个类模板来实现线性表的上述操作,并且将其设计为一个抽象类,针对不同类型的线性表功能设计,进行不同类型的子类设计。
上述操作的函数映射(面向对象的方法)为:
- template <typename T>
- class List : public Object
- {
- protected:
- List(){}
- List& operator= (const List&);
- public:
- virtual bool insect(int i, const T& e) = 0;
- virtual bool remove(int i) = 0;
- virtual bool set(int i, const T& e) = 0;
- virtual bool get(int i, T& e) const = 0;
- virtual int length() const = 0;
- virtual void clear() = 0;
-
- };
抽象类无法定义对象,但是可以作为指针或者引用类型使用。在主函数中定义一个List类型的整型指针变量,编译成功。
- int main()
- {
- List<int> *l = NULL;
-
- return 0;
- }
顺序存储的定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元,依次存储线性表中的数据元素。
设计思路:可以使用一维数组来实现顺序存储结构。
- T* m_array; //存储空间
- int m_length; //当前长度,使用capacity()函数来访问
顺序存储结构的元素获取:
1、判断目标位置是否合法; 2、将目标位置作为数组下标获取元素。
- bool get(int i,T& e) const
- {
- bool ret = ( (0 <= i) && (i< m_length));
-
- if(ret)
- {
- e = m_array[i];
- }
-
- return ret;
- }
元素插入:
1、判断是否合法; 2、插入后所有元素后移一个位置; 3、插入新元素; 4、线性表长度加1。
注意:原生数组有最大存储量。
- bool insert(int i, const T& e)
- {
- bool ret = ( (0 <= i) && ( i <= m_length) );
-
- ret = ret && (m_length < capacity());
-
- if (ret)
- {
- for( int p = m_length-1; p>=i; p--) //i之前的元素后移一位
- {
- m_array[p + 1] = m_array[p];
- }
-
- m_array[i] = e;
-
- m_length++;
- }
-
- return ret;
- }
元素删除:
1、判断是否合法; 2、目标位置后的元素前移一位; 3、线性表长度减一。
- bool remove(int i)
- {
- bool ret = ( (0 <= i) && (i< m_length));
-
- if(ret)
- {
- for(int p = i;p<m_length-1;p++) //i之后的元素前移一位
- {
- m_array[p] = m_array[ p+ 1 ];
- }
-
- m_length--;
- }
-
- return ret;
- }
SeqList设计要点:
1、关键操作仍旧为抽象类,存储空间的位置和大小在子类中完成;(将capacity()函数声明为纯虚函数,在子类中实现,表示顺序存储空间的最大容量)
2、实现顺序存储结构线性表的关键操作(增、删、查、等);
3、实现数组操作符,方便快速获取元素(重载两个操作符,const和非const版本)。
元素的设置和获取:
- bool set(int i,const T& e)
- {
- bool ret = ( (0 <= i) && (i< m_length));
-
- if(ret)
- {
- m_array[ i ] = e;
-
- }
-
- return ret;
- }
-
- bool get(int i,T& e) const
- {
- bool ret = ( (0 <= i) && (i< m_length));
-
- if(ret)
- {
- e = m_array[i];
- }
-
- return ret;
- }
重载数组操作符:
- T& operator[] (int i)
- {
- if( (0 <= i) && (i < m_length))
- {
- return m_array[i];
- }
- else
- {
- THROW_EXCEPTION(IndexOutOfBoundsException,"Parameter i is invalid..."); //自定义异常类抛出信息
- }
- }
-
- T operator[] (int i) const
- {
- return (const_cast<SeqList<T>&>(*this))[i]; //转换掉表达式的const性质
- }
此处的实现,并没有确定具体的存储空间在哪。
可以通过静态申请存储空间大小和动态申请存储空间,通过继承,实现静态线性表和动态线性表,它们的区别是什么?
- template < typename T, int N> //使用模板参数决定数组大小
- class StaticList : public SeqList<T>
- {
- protected:
- T m_space[N]; //使用原生数组作为顺序存储空间
- public:
- StaticList()
- {
- this->m_array = m_space;
- this->m_length = 0;
- }
-
- int capacity() const
- {
- return N;
- }
- };
在主函数中对StaticList进行调用:
- StaticList<int, 5> sl;
-
- for(int i=sl.capacity(); i >= 0; i--)
- {
- sl.insert(0, i);
- }
-
- for(int i=0; i<sl.length(); i++)
- {
- cout << sl[i] << endl;
- }
-
- sl[3] *= sl[3];
-
- for(int i=0; i<sl.length(); i++)
- {
- cout << sl[i] << endl;
- }
DynamicList:
申请连续堆空间作为顺序存储空间;动态设置顺序存储空间;保证重置顺序存储空间时的异常安全性。
什么是异常安全?
不泄露任何资源,不允许破坏数据。
函数异常安全的基本保证:
如果异常被抛出,对象内的任何成员仍能保持有效状态;没有数据的破坏以及资源泄露。
构造函数用来动态申请空间,定义整型的capacity,用来表示申请的空间大小。
申请空间后必须进行非空检查。
- DynamicList( int capacity)
- {
- this->m_array = new T[capacity]; //申请连续堆空间作为顺序存储空间
-
- if(this->m_array != NULL)
- {
- this->m_length = 0;
- this->m_capacity = capacity;
- }
- else
- {
- THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object...");
- }
- }
定义一个resize()函数用来实现动态设置顺序存储空间的大小。(必须考虑重置前后的大小是否一致,不一致再进行操作)
- void resize(int capacity) //动态设置 顺序存储空间的大小
- {
- if(capacity != m_capacity)
- {
- T* array = new T[capacity]; //保证数据元素没丢掉,即重置之后,剩余的元素不能丢失,用m_array来保存旧的,array来保存新的
-
- if( array != NULL )
- {
- int length =(this->m_length < capacity ? this->m_length : capacity);
-
- for(int i = 0; i < length; i++) //复制数据元素
- {
- array[i] = this->m_array[i];
- }
-
- /***************************************/
- 保证重置顺序存储空间时的异常安全性
- /***************************************/
-
- T* temp = this->m_array; // delete[] this->m_array 只要发生异常,线性表对象不可用
-
- this->m_array =array;
- this->m_length = length;
- this->m_capacity = capacity; //temp的作用在于保重置前的数据存储空间
-
- delete[] temp; //即便异常返回,线性表对象依然可用
- }
- else
- {
- THROW_EXCEPTION(NoEnoughMemoryException,"");
- }
- }
-
- }
针对resize()函数的实现,必须注意一下几点:
保证复制前,数据元素不至于丢失。
delete会调用析构函数,如果抛出异常(泛指类型为类类型的话),线性表对象将不可用。
保存在temp后,即使发生异常,线性表对象依旧可用。
在析构函数中,对构造函数中申请的堆空间进行释放。
- ~DynamicList()
- {
- delete[] this->m_array;
- }
两种线性表的效率分析:大O表示法
时间复杂度:
- bool insert(int i, const T& e); //O(n)
-
- bool remove(int i);//O(n)
-
两个相同的SeqLis,插入和删除操作的平均耗时是否相同?
答案是不同的。必须注意赋值、删除时的操作对象。比如int直接赋值即可,但是对于类类型或者自定义类类型,就可能需要进行拷贝构造等操作,时间复杂度一样,但是耗时肯定是不同的。
下面的代码正确吗?为什么?
在上面的代码中,s2指向了s1new出来的空间的地址,所以当对s1进行delete操作时,已经将new出来的空间还了回去,再进行delete s2,将会出现同一个堆空间被释放两次,行为是未定义的。
如何解决?——深拷贝(deep copy)
C++ Primer Plus第436页:如果类中包含了使用new初始化的指针成员,应对定义一个复制构造函数,以复制指向的数据,而不是指针,这被称为深度拷贝。复制的另一种形式(成员复制或浅复制)只是复制指针值。浅复制仅浅浅地复制指针信息,而不会深入“挖掘”以复制指针引用的结构。
下面的代码正确吗?为什么?
当对d2进行拷贝构造的时候,是将d2直接指向了d1的存储空间,用d1来初始化d2,所以实际上他们指向的是同一块存储空间。(C++ Primer Plus第434页:隐式复制构造函数是按值进行复制的,即上述代码复制的并不是int型数据,而是一个指向int型数据的指针,也就是说将d2=d1后,得到的是两个指向同一组数据的指针,再进行对象析构的时候,会将d1(d2)指向的内存释放两次,会导致不确定、可能有害的结果)。
对于容器类型的类,可以考虑禁止拷贝构造和赋值操作。
代码实现:将拷贝构造函数声明为保护,不需实现,赋值操作符也声明为保护。注:需手动实现构造函数。
- protected:
- List(const List&);
- List& operator= (const List&);
添加代码后将无法实现赋值和拷贝:
- int main()
- {
- DynamicList<int> sl(5);
- DynamicList<int> sn(5);
- //DynamicList<int> sn = sl; 报错
-
- //sn = sl; 报错
- return 0;
- }
在线性表尾部直接添加参数,重载insert():
- bool insert(const T &e) //直接在线性表的尾部添加参数
- {
- return insert(m_length, e);
- }
下面的代码正确吗?为什么?
- StaticList<int , 5> list;
-
- for(int i=0; list.capacity(); i++)
- {
- list[i] = i*i;
- }
答案:不正确;
在实现数组访问操作符的重载时,对数组内容先进行了检查:
- T& operator[] (int i)
- {
- if( (0 <= i) && (i < m_length))
- {
- return m_array[i];
- }
- else
- {
- THROW_EXCEPTION(IndexOutOfBoundsException,"Parameter i is invalid...");
- }
- }
当数组内没有元素的时候(未进行insert()操作)时,将不能访问数组元素。
线性表不是数组,线性表必须先插入元素,再能使用操作符[]访问元素。
顺序存储结构线性表提供了数组操作符重载,通过重载能够方便快捷的获取目标位置处的数据层元素(实现顺序存储结构线性表的意义),在具体的使用形式上类似数组,但是本质不同,不能代替数组使用。
在上一节的最后可以发现,线性表很容易被当做数组使用(功能上的缺陷),但是由于本质不同,两者是不同的,且效率有隐患。——实现一个可以代替原生数组的数组类。
需求分析:创建数组类必须能够替代原生数组的使用
数组类包含长度信息;
数组类能够主动发现越界访问(数组是一片连续的存储空间)。
父类Array实现要点:
1、抽象类模板,存储空间的位置和大小由子类完成;
2、重载数组操作符,判断访问下标是否合法;
3、提供数组长度的抽象访问函数;
4、提供数组对象间的复制操作。
- template < typename T >
- class Array : public Object
- {
- protected:
- T* m_array;
- public:
- virtual bool set(int i ,const T& e) //O(1)
- {
- }
-
- virtual bool get(int i ,T& e) const //O(1)
-
- {
- }
-
- virtual int length() const = 0;
T& operator[] (int i)
//O(1) { } T& operator[] (int i) const
//O(1) { }};
StaticArray设计要点:类模板
1、封装原生数组
2、使用模板参数决定数组大小
3、实现函数返回数组长度
4、拷贝构造和赋值操作
- template < typename T ,int N>
- class StaticArray : public Array<T>
- {
- protected:
- T m_space[N];
- public:
- StaticArray()
- {
- this->m_array = m_space; //将父类的m_array挂接在m_space
- }
-
- StaticArray( const StaticArray<T, N>& obj)
- {
- this->m_array = m_space; //原生数组
-
- for(int i=0; i<N; i++) //具体的复制
- {
- m_space[i] = obj.m_space[i];
- }
- }
-
- StaticArray<T,N>& operator = (const StaticArray<T,N>& obj)
- {
- if(this != &obj)
- {
- for(int i=0; i<N; i++)
- {
- m_space[i] = obj.m_space[i];
- }
- }
- return *this;
- }
-
- int length() const
- {
- return N;
- }
- };
使用StaticArray可以进行拷贝构造和赋值操作,具体实现如下:
- int main()
- {
- StaticArray<int, 5> sa;
-
- for(int i=0; i<sa.length(); i++)
- {
- sa[i] = i;
- }
-
- for(int i=0; i<sa.length(); i++)
- {
- cout << sa[i] << endl;
- }
-
- StaticArray<int, 5> sa1;
- sa1 = sa;
-
- for(int i=0; i<sa1.length(); i++)
- {
- cout << sa1[i] << endl;
- }
-
- for(int i=0; i<sa.length(); i++)
- {
- sa[i] = i*i;
- }
-
- for(int i=0; i<sa.length(); i++)
- {
- cout << sa[i] << endl;
- }
-
- //sa[6] = 100; 越界异常可以被抛出异常(重载数组访问操作符中会对数组下标进行检查)
-
- return 0;
- }
利用原生数组实现了静态数组类的实现,那么如何实现动态数组的实现?两者又有何异同呢?
DynamicArray设计要点:类模板
1、动态确定内部数组空间的大小
2、实现函数返回数组长度
3、拷贝构造和赋值操作
下面代码实现了代码优化。
- template < typename T>
- class DynamicArray : public Array<T>
- {
- protected:
- int m_length;
-
- T* copy( T* array, int len , int newlen) //在堆空间中申请新的内存空间,并执行拷贝操作
- {//复制前进行长度判断、异常安全检查
- }
-
- void update(T* array, int length) //将指定的堆空间作为内部存储数组使用,更新数据
- {//注意异常安全,对数据先进性保存,使用局部指针指向m_array指向的堆空间,操作成功后删除临时申请的堆空间
- }
-
- void init(T* array, int length) //对象构造时的初始化操作
- {
- }
-
- public:
- DynamicArray( int length = 0)
- {
- init(new T[length],length);
- }
-
- DynamicArray(const DynamicArray<T>& obj)
- {
- T* array = copy(obj.m_array,obj.m_length,obj.m_length);
-
- init(array,obj.m_length);
- }
-
- DynamicArray<T>& operator= (const DynamicArray<T>& obj)
- {
- if(this != &obj) //出过BUG
- {
- update(copy(obj.m_array, obj.m_length, obj.m_length), obj.m_length);
- }
- }
-
- int length() const
- {
- return m_length;
- }
-
- void resize(int length)
- {
- update(copy(this->m_array, m_length, length),length);
- }
-
- ~DynamicArray()
- {
- delete[] this->m_array;
- }
-
- };
在主函数中运行如下:
- int main()
- {
- DynamicArray<int> s1(5);
-
- for(int i=0; i<s1.length(); i++)
- {
- s1[i] = i*i;
- }
-
- for(int i=0; i<s1.length(); i++)
- {
- cout << s1[i] << endl;
- }
-
- DynamicArray<int> s2(10);
-
- s2 = s1;
-
- for(int i=0; i<s2.length(); i++)
- {
- cout << s2[i] << endl;
- }
-
- s2.resize(3);
-
- for(int i=0; i<s2.length(); i++)
- {
- cout << s2[i] << endl;
- }
-
- //s2[5] = 100; //越界
-
- return 0;
- }
数组对象能够代替原生的数组,并且使用上功能更多,更安全。
代码优化是项目开发过程中不可或缺的环节,对于重复代码,使用函数模板进行封装。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。