服务器之家

服务器之家 > 正文

C++实现动态数组功能

时间:2021-07-10 16:10     来源/作者:fall_foliage

数组

数组是一种线性表数据结构。它用一组连续内存空间,来存储一组具有相同数据类型数据。

1.线性表:数据存储像一条线一样的结构,每个线性表上的数据最多只有前和后的两个方向,如数组、链表、队列、栈等都是这种结构,所以实现的数组的动态操作,其他结构也可轻易的类似实现。更重要的是,在这之后看源码就可大大降低难度。(博主自己看的是STL源码剖析)
2.非线性表:如二叉树、堆、图等。
3连续内存空间和相同数据类型:当数组作插入、删除操作时,为了保证数据的连续性,往往需要做大量的数据搬移工作,效率很低。

动态数组功能实现

1.数组初始化

考虑到扩容时数据搬移可能会发生的内存泄露,博主这里采用两只手的原则,即设定一个内存标志位 ItemsFlag 。当 ItemsFlag = 0,using preitems;当 ItemsFlag = 1,using items。下文扩容部分有具体实现。默认数组容量10。

?
1
2
3
4
5
6
7
8
9
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.析构函数

释放内存。

?
1
2
3
4
5
6
7
8
template<class T>
GenericArray<T>::~GenericArray()
{
 if (preitems != nullptr)
 delete[]preitems;
 if (items != nullptr)
 delete[]items;
}

3.检查下标

检查要操作的下标是否在数组容量范围内。

?
1
2
3
4
5
6
7
8
9
10
11
12
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.获取元素数目和容量、判断数组空和满

?
1
2
3
4
int count()const { return counts; }
int getCapacity()const { return capacity; }
bool isEmpty()const { return counts == 0; }
bool isFull()const { return counts >= capacity; }

5.取索引对应值、按索引修改值、打印输出、是否包含某值

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 来存储该值重复的次数和对应的下标。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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.扩容

添加数据操作时需判断数组容量是否足够,若不够需考虑扩容。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
 }
}

8.添加数据:数组添加数据包括按索引下标插值、数组头插值、数组尾插值。实质上后两种都可以通过调用按索引下标插值函数实现。前文也提到过,数组添加操作中复杂的是大量的数据搬移工作:将某个元素按索引下标插入到数组第k个位置,需要将k ~ n部分的元素向后搬移一位,然后插入元素,更新元素数目。若插入到数组尾,时间复杂度O(1);插入到数组头,时间复杂度O(n);插入的平均时间复杂度为(1+2+…+n)/n = O(n)。
另外,还有一个优化问题:若数组是无序数组,则插入时不需要搬移数据:若将某个元素插入到数组第k个位置,首先将该位置的元素移动到数组末尾,然后将待插入元素插入到第k个位置,时间复杂度O(1)。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template<class T>
void GenericArray<T>::add(int index, T elem)
{
 if (isFull())
 {
 cout << "Array is full!" << '\n';
 renewCapacity();
 }
 if (checkIndex(index))
 if(!itemsFlag)
 {
  for (int i = counts; i > index; i--)
  preitems[i] = preitems[i - 1];
  preitems[index] = elem;
 }
 else
 {
  for (int i = counts; i > index; i--)
  items[i] = items[i - 1];
  items[index] = elem;
 }
 counts++;
 return;
}
 
template<class T>
void GenericArray<T>::addFirst(T elem)
{
 add(0, elem);
}
 
template<class T>
void GenericArray<T>::addLast(T elem)
{
 add(counts, elem);
}

9.删除数据:数组删除数据包括按索引下标删除、数组头删除、数组尾删除。实质上后两种都可以通过调用按索引下标删除函数实现。与前文类似,数组删除操作中复杂的也是大量的数据搬移工作:按索引下标将某个元素删除,需要将k+1 ~ n部分的元素向前搬移一位,更新元素数目。若删除数组尾,直接元素数目减一即可,时间复杂度O(1);删除数组头,时间复杂度O(n);删除的平均时间复杂度(1+2+…+n)/n = O(n)。
另外,有一个优化问题:如果想多次删除数组中的值,可以先对要删除的值做好标记,做完标记后一次删除,这样就大大减少了搬移的次数。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template<class T>
T GenericArray<T>::remove(int index)
{
 if (!isEmpty())
 {
 if (checkIndex(index))
 {
  if (!itemsFlag)
  {
  T temp = preitems[index];
  for (int i = index+1; i < counts; i++)
   preitems[i - 1] = preitems[i];
  counts--;
  return temp;
  }
  else
  {
  T temp = items[index];
  for (int i = index + 1; i < counts; i++)
   items[i - 1] = items[i];
  counts--;
  return temp;
  }
 }
 }
 else
 {
 cout << "Array is empty!" << '\n';
 return -1;
 }
}
template<class T>
T GenericArray<T>::removeFirst()
{
 return remove(0);
}
template<class T>
T GenericArray<T>::removeLast()
{
 return remove(counts - 1);
}

好啦,基本上就这么多了。

最后总结一下,多看源码还是很重要的。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/weixin_43428242/article/details/83989513

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部