实现了一个简易的动态分配内存的线性表结构，实现了插入、删除、重载赋值运算符、拷贝构造函数（有bug，编译不过去）
1 2 #ifndef NULL 3 #define NULL 0 4 #endif 5 6 template7 class CSQList 8 { 9 public: 10 CSQList(); //构造函数 11 CSQList(const CSQList& sqList); //拷贝构造函数 12 CSQList& operator=(const CSQList& sqList); //重载赋值运算符 13 T* InitSQList(); //初始化线性表 14 T* IncreaseSQList(); //再次为线性表分配内存 15 virtual ~CSQList(); //析构函数 16 inline unsigned int Capacity() const; //获得最大容量 17 inline unsigned int Size() const; //当前元素个数 18 bool Insert(unsigned int pos, T& element); //在第pos个位置插入元素 19 T Delete(unsigned int pos); //删除指定位置的元素，返回删除的元素 20 unsigned int Clear(); //清楚所有元素(并非释放内存) 21 22 protected: 23 T* m_pSQList; 24 const unsigned int m_ncInitLength; //初始可以放的元素个数 25 const unsigned int m_ncIncreaseLength; //增长大小 26 unsigned int m_nCapacity; //当前线性表总可以放的元素个数 27 unsigned int m_nSize; //当前线性表中实际元素个数 28 }; 29 30 template 31 T CSQList ::Delete( unsigned int pos ) 32 { 33 if (pos > m_nSize - 1) 34 { 35 return T(0); //这里是一个潜在问题, potential problem 36 } 37 38 T temp = m_pSQList[pos]; 39 40 //当删除的元素为最后一个元素时，循环条件不成立，直接更改m_nSize的值即可; 41 for (unsigned int index = pos; index < m_nSize - 1; ++ index) 42 { 43 m_pSQList[index] = m_pSQList[index + 1]; 44 } 45 46 -- m_nSize; 47 48 return temp; 49 } 50 51 52 template 53 CSQList ::CSQList() : m_pSQList(NULL), m_ncInitLength(20), m_ncIncreaseLength(10), m_nCapacity(0), m_nSize(0){} 54 55 56 template 57 T* CSQList ::InitSQList() 58 { 59 if (NULL != m_pSQList) 60 { 61 return m_pSQList; 62 } 63 64 m_pSQList = (T*)(malloc(m_ncInitLength * sizeof(T))); 65 if (NULL == m_pSQList) 66 { 67 m_nCapacity = 0; 68 } 69 else 70 { 71 m_nCapacity = m_ncInitLength; 72 } 73 74 return m_pSQList; 75 } 76 77 template 78 T* CSQList ::IncreaseSQList() 79 { 80 if (NULL == m_pSQList) 81 { 82 return NULL; 83 } 84 85 m_pSQList = (T*)realloc(m_pSQList, (m_ncIncreaseLength + m_nCapacity) * sizeof(T)); 86 87 m_nCapacity += (NULL == m_pSQList? 0 : m_ncIncreaseLength); 88 89 return m_pSQList; 90 } 91 92 template 93 CSQList ::~CSQList() 94 { 95 if (NULL != m_pSQList) 96 { 97 free(m_pSQList); 98 m_pSQList = NULL; 99 m_nCapacity = 0;100 m_nSize = 0;101 } 102 }103 104 template 105 unsigned int CSQList ::Capacity() const106 {107 return m_nCapacity;108 }109 110 template 111 unsigned int CSQList ::Size() const 112 {113 return m_nSize;114 }115 116 template 117 bool CSQList ::Insert(unsigned int pos, T& element)118 {119 if (pos < 0 || pos > m_nSize)120 {121 return false;122 }123 124 //当 当前个数 + 1 大于 最大容量的时候，必须分配空间125 //如果分配失败，则不能插入元素126 if (m_nSize + 1 > m_nCapacity)127 {128 if (NULL == IncreaseSQList())129 {130 return false;131 }132 }133 //如果插入一个元素 不会超过最大容量，则即使再分配不成功也没有太大问题134 else if (m_nSize + 1 >= (m_nCapacity * 0.8F))135 {136 IncreaseSQList();137 }138 139 for (unsigned int iBegin = m_nSize; iBegin > pos; -- iBegin)140 {141 m_pSQList[iBegin] = m_pSQList[iBegin - 1]; 142 }143 m_pSQList[pos] = element;144 145 ++ m_nSize;146 147 return true;148 }149 150 template 151 unsigned int CSQList ::Clear()152 {153 unsigned int size = m_nSize;154 m_nSize = 0;155 156 return size;157 }158 159 template 160 CSQList ::CSQList(const CSQList& sqList)161 { 162 T* pt = (T*)malloc(sqList.m_nCapacity * sizeof(T));163 if (NULL != pt)164 {165 if (0 == memcpy_s(pt, sizeof(T) * sqList.Size(), sqList.m_pSQList, sizeof(T) * sqList.Size()))166 {167 this->m_pSQList = pt;168 this->m_nSize = sqList.Size();169 this->m_nCapacity = sqList.Capacity();170 } 171 } 172 }173 174 template 175 CSQList & CSQList ::operator =(const CSQList& sqList)176 { 177 T* pt = (T*)malloc(sqList.m_nCapacity * sizeof(T));178 if (NULL != pt)179 {180 if (0 == memcpy_s(pt, sizeof(T) * sqList.Size(), sqList.m_pSQList, sizeof(T) * sqList.Size()))181 {182 if (this->m_pSQList != NULL)183 {184 free(m_pSQList);185 }186 187 this->m_pSQList = pt; 188 this->m_nSize = sqList.Size();189 this->m_nCapacity = sqList.Capacity(); 190 } 191 }192 193 return *this; 194 }
在main函数中使用该线性表
1 #include "stdafx.h" 2 #include3 using namespace std; 4 #include "SQList.h" 5 6 7 int _tmain(int argc, _TCHAR* argv[]) 8 { 9 CSQList sqList;10 sqList.InitSQList();11 int num1 = 0x0a;12 int num2 = 0x01020304;13 14 sqList.Insert(0, num1);15 sqList.Insert(1, num2);16 17 for (int i = 0; i < 20; ++ i)18 {19 sqList.Insert(0, num1);20 }21 22 int value = sqList.Delete(sqList.Size() - 1);23 24 CSQList sqList2; // = sqList; //直接用sqList初始化sqList2时编译错误25 sqList2 = sqList;26 27 sqList2 = sqList;28 29 return 0;30 }
上面第24行如果写为 CSQList<int> sqList2 = sqList; 则编译错误如下：
1>正在编译...
1>SQList.cpp1>e:\files\datastruct\sqlist\sqlist\sqlist.h(161) : error C2758: “CSQList<T>::m_ncInitLength”: 必须在构造函数基/成员初始值设定项列表中初始化1> with1> [1> T=int1> ]1> e:\files\datastruct\sqlist\sqlist\sqlist.h(24) : 参见“CSQList<T>::m_ncInitLength”的声明1> with1> [1> T=int1> ]1> e:\files\datastruct\sqlist\sqlist\sqlist.h(161): 编译类 模板 成员函数“CSQList<T>::CSQList(const CSQList<T> &)”时1> with1> [1> T=int1> ]1> e:\files\datastruct\sqlist\sqlist\sqlist.cpp(12): 参见对正在编译的类 模板 实例化“CSQList<T>”的引用1> with1> [1> T=int1> ]1>e:\files\datastruct\sqlist\sqlist\sqlist.h(161) : error C2758: “CSQList<T>::m_ncIncreaseLength”: 必须在构造函数基/成员初始值设定项列表中初始化1> with1> [1> T=int1> ]1> e:\files\datastruct\sqlist\sqlist\sqlist.h(25) : 参见“CSQList<T>::m_ncIncreaseLength”的声明1> with1> [1> T=int1> ]1>生成日志保存在“file://e:\Files\DataStruct\SQList\SQList\Debug\BuildLog.htm”1>SQList - 2 个错误，0 个警告========== 生成: 0 已成功, 1 已失败, 0 最新, 0 已跳过 ==========
暂时无解