数组
数组是一种线性表数据结构。它用一组连续内存空间,来存储一组具有相同数据类型数据。
1.线性表:数据存储像一条线一样的结构,每个线性表上的数据最多只有前和后的两个方向,如数组、链表、队列、栈等都是这种结构,所以实现的数组的动态操作,其他结构也可轻易的类似实现。更重要的是,在这之后看源码就可大大降低难度。(博主自己看的是STL源码剖析)
2.非线性表:如二叉树、堆、图等。
3连续内存空间和相同数据类型:当数组作插入、删除操作时,为了保证数据的连续性,往往需要做大量的数据搬移工作,效率很低。
动态数组功能实现
1.数组初始化
考虑到扩容时数据搬移可能会发生的内存泄露,博主这里采用两只手的原则,即设定一个内存标志位 ItemsFlag 。当 ItemsFlag = 0,using preitems;当 ItemsFlag = 1,using items。下文扩容部分有具体实现。默认数组容量10。
enum { MAX = 10 }; explicit GenericArray(int ss = MAX); template<class T> GenericArray<T>::GenericArray(int ss) : capacity(ss),counts(0) { itemsFlag = 0; preitems = new T[capacity]; items = nullptr; }
2.析构函数
释放内存。
template<class T> GenericArray<T>::~GenericArray() { if (preitems != nullptr) delete[]preitems; if (items != nullptr) delete[]items; }
3.检查下标
检查要操作的下标是否在数组容量范围内。
template<class T> bool GenericArray<T>::checkIndex(int index) { if (index < 0 || index >= capacity) { int cap = capacity - 1; cout << "Out of the range! Please ensure the index be in 0 ~ " << cap << 'n'; return false; } return true; }
4.获取元素数目和容量、判断数组空和满
int count()const { return counts; } int getCapacity()const { return capacity; } bool isEmpty()const { return counts == 0; } bool isFull()const { return counts >= capacity; }
5.取索引对应值、按索引修改值、打印输出、是否包含某值
template<class T> T GenericArray<T>::get(int index) { if (!itemsFlag) return preitems[index]; else return items[index]; } void GenericArray<T>::set(int index, T elem) { if(checkIndex(index)) { if (!itemsFlag) preitems[index] = elem; else items[index] = elem; return; } } template<class T> void GenericArray<T>::printArray()const { for (int i = 0; i < counts; i++) if (!itemsFlag) cout << preitems[i] << 't'; else cout << items[i] << 't'; cout << 'n'; return; } template<class T> bool GenericArray<T>::contains(T arr) { for (int i = counts - 1; i >= 0; i--) if (!itemsFlag) { if (arr == preitems[i]) return true; } else { if (arr == items[i]) return true; } return false; }
6.查找某值下标、删除某值
查找某值的下标时,要考虑到该值在数组中是否重复,所以博主用了一个结构体 findArrIndex 来存储该值重复的次数和对应的下标。
struct findArrIndex { int numIndex; int *findIndex; }; template<class T> void GenericArray<T>::find(T arr, findArrIndex *ps) { ps->findIndex = new int[counts]; ps->numIndex = 0; for (int i = 0, j = 0; i < counts; i++, j++) if (!itemsFlag) { if (arr == preitems[i]) { (ps->findIndex)[j] = i; (*ps).numIndex++; cout << i << 't'; } } else if (arr == items[i]) { (ps->findIndex)[j] = i; (*ps).numIndex++; cout << i << 't'; } cout << 'n'; return; } template<class T> void GenericArray<T>::removeElement(findArrIndex *ps) { for (int i = ps->numIndex; i > 0; i--) remove((ps->findIndex)[i - 1]); delete[](ps->findIndex); } template<class T> void GenericArray<T>::set(int index, T elem) { if(checkIndex(index)) { if (!itemsFlag) preitems[index] = elem; else items[index] = elem; return; } }
7.扩容
添加数据操作时需判断数组容量是否足够,若不够需考虑扩容。
template<class T> void GenericArray<T>::renewCapacity() { cout << "The array's capacity is small! Renew capacity.n"; if (capacity < 1000) capacity = capacity << 1; else capacity = capacity >> 1 + capacity; if (!itemsFlag) { itemsFlag = 1; items = new T[capacity]; for (int i = 0; i<counts; i++) *(items + i) = *(preitems + i); //items[i]=proitems[i]; //cout << items << 'n'; //cout << preitems << 'n'; delete[]preitems; preitems = nullptr; } else { itemsFlag = 0; preitems = new T[capacity]; for (int i = 0; i<counts; i++) *(preitems + i) = *(items + i); delete[]items; items = nullptr; } }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/482575.html