List.h
#ifndef LIST_H #define LIST_H #include"Object.h" namespace DTLib { template<typename T> class List :public Object { protected: //这里是为了干什么的（） List(const List&); List& operator= (const List&); public: List(){} virtual bool insert(const T& e)=0; virtual bool insert(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; }; } #endif // LIST_H这里将拷贝构造函数 和赋值函数 写在了protected内；
是为了避免 其带来的错误，具体的可以看数据结构 -210-212
SeqList.h
#ifndef SEQLIST #define SEQLIST #include "Object.h" #include "List.h" #include "Exception.h" namespace DTLib { template<typename T> class SeqList :public List<T> { protected: T* m_array; //数组指针 int m_length; public: virtual bool insert(const T& e){ return insert(m_length,e); } bool insert(int i,const T& e){ bool ret = ((i>=0)&&(i<=m_length)); ret =ret&&(m_length<capacity()); if(ret){ //插入位置往后的所有元素的移动 是否耗时 取决于插入的类型 for(int p=m_length-1;p>=i;p--){ m_array[p+1]=m_array[p]; } m_array[i]=e; } m_length++; return ret; } bool remove(int i){ bool ret = ((i>=0)&&(i<m_length)); if(ret){ //插入位置往后的所有元素的移动 for(int p=i;p<=m_length-1;p++){ m_array[p]=m_array[p+1]; } } m_length--; return ret; } bool set(int i,const T& e){ bool ret = ((i>=0)&&(i<m_length)); if(ret){ m_array[i] = e; } return ret; } bool get(int i,T& e){ bool ret = ((i>=0)&&(i<m_length)); if(ret){ e = m_array[i] ; } return ret; } int length()const { return m_length; } void clear(){ m_length= 0; } T& operator[](int i){ bool ret = ((i>=0)&&(i<m_length)); if(ret){ return m_array[i]; } else{ THROW_EXCEPTION(InvalidOperationException,"Parameter i is invalid...."); } } T operator[](int i) const{ //去除const 属性 return const_cast<SeqList<T>&> (*this)[i]; } virtual int capacity() const=0; }; } #endif // SEQLISTDynamicList.h
#ifndef DYNAMOCLIST_H #define DYNAMOCLIST_H #include"SeqList.h" #include"Exception.h" //动态申请 连续堆空间 作为顺序存储空间 怎么保证异常的安全性（是什么？基本保证是什么） namespace DTLib { template<typename T> class DynamicList : public SeqList<T> { protected: int m_capacity; public: //构造函数 直接初始化 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 enough memory for object..."); } } int capacity()const{ return m_capacity; } //重新设置存储空间的大小 void resize(int capacity) { if(capacity!=m_capacity) { T* array = new T[capacity]; //考虑一下这里为什么不直接用m_array =.. 呢？ if(array != NULL ) { //保持原来的顺序 or 或则保持原来所有的数组 int length =(this->m_length < capacity ? this->m_length : capacity); for(int i =0;i<length;i++) { array[i]= this->m_array[i]; } //这个指针 体现了什么 ，如果我不用这个指针 直接delete 有什么问题？？ // 这里注释这条语句，直接在最后面 delete[] this->m_array 有什么问题 T* temp =this->m_array; //这个其实就是 先保存原理啊的地址，为了 后面删除原来的地址空间内存 this->m_array =array; this->m_length = length; this->m_capacity = capacity; //delete[] this->m_array; //自己想想为什么 delete[] temp;//这里的异常安全 是 当T 是类对象，delete 会触发类对象的析构函数 如果析构函数中 存在异常返回，那么下面的语句就没啥用了 } else { THROW_EXCEPTION(NoEnoughMemoryException," resize __ no enough memory for object..."); } } } //归还空间 ~DynamicList(){ delete [] this->m_array; //这里是调用自己的delete[]来删除数组 } }; } #endif // DYNAMOCLIST_H链表：
#ifndef LINKLIST_H #define LINKLIST_H #include "List.h" #include "Exception.h" namespace DTLib { template<typename T> class LinkList :public List<T> { protected: struct Node:public Object{ //头节点的隐患 T value;//这里创建了T 的对象 如果这个对象（一般是类）中 有异常 会直接导致程序无法继续执行下去； Node* next; }; //mutable Node m_header; //为什么用这个mutable const 中 不可以改变值 加上mutable 就可以； //这里为什么这样去使用 使用匿名的类型 不能调用构造函数 //这里一定要通多继承 来同化m_header, 否则测函数接口的时候 不会成功 mutable struct:public Object{ char reseved[sizeof(T)]; Node* next; }m_header; int m_length; //reinterpret_cast 这里要进行强制类型的转换 Node* position(int i)const{ Node* ret =reinterpret_cast<Node*>(&m_header); for(int t=0;t<i;t++){ ret=ret->next; } return ret; } public: //构造函数 初始化成员 LinkList(){ m_header.next = NULL; m_length = 0; } bool insert(const T& e){ return insert(m_length,e); } bool insert(int i,const T& e){ bool ret = ((i>=0)&&(i<=m_length)); if(ret){ Node* node = new Node(); if(node!=NULL){ Node* current = position(i); /* Node* current = &m_header; for(int t=0;t<i;t++){ current=current->next; }*/ //插入的关键 node->value = e; node->next =current->next; current->next =node; m_length++; }else { THROW_EXCEPTION(NoEnoughMemoryException,"no node enough memory to insert"); } } return ret; } bool remove(int i){ bool ret = ((i>=0)&&(i<m_length)); if(ret){ Node* current = position(i); //删除的关键 Node* toDel = current->next; current->next=toDel->next; delete toDel; m_length--; } return ret; } bool set(int i,const T& e){ bool ret = ((i>=0)&&(i<m_length)); if(ret){ Node* current = position(i); current->next->value = e; } return ret; } //Get 的重载 T get(int i){ T ret; if(get(i,ret)){ return ret; }else{ THROW_EXCEPTION(IndexOutOfBoundsException,"Invalid i in get()"); } } bool get(int i,T& e)const{ bool ret = ((i>=0)&&(i<m_length)); if(ret){ Node* current = position(i); e = current->next->value; } return ret; } int length()const{ return m_length; } //遍历节点 删除所有的 void clear(){ while(m_header.next!=NULL){ Node* toDel =m_header.next; m_header.next=toDel->next; delete toDel; } m_length=0; } ~LinkList(){ clear(); } }; } #endif // LINKLIST_H测试：
#include <iostream> #include"exception.h" #include "Object.h" #include"SmartPointer.h" #include"List.h" #include "SeqList.h" #include "StaticList.h" #include"DynamicList.h" #include "staticarray.h" #include "dynamicarray.h" #include "LinkList.h" using namespace std; using namespace DTLib; class Test{ public: Test() { throw(0); } }; int main() { LinkList<int> list; for(int i=0;i<5;i++){ list.insert(i); } for(int i=0;i<list.length();i++){ cout<<list.get(i)<<endl; } //LinkList<Test> list; //cout<<"xly"<<endl; return 0; }其中Test 测试 告诉我：更改代码后 一定要再重新测试代码的正确性！
