線性表是由零個或多個數據元素組成的有序序列。

特點：

• 數據元素間是有順序的；

• 數據元素的個數是有限的；

• 一般來說，數據元素的類型是相同的（強類型語言）。c/c++是強類型語言，必須指定數據類型。js、php、python等語言是弱類型就不需要指定數據類型。

線性表的順序存儲結構指的是用一段連續的存儲空間來存儲線性表中的數據元素，數組就是一個典型的順序存儲結構。

下面實現一個動態數組。

頭文件

#pragma once
class DynamicArray
{
private://成員變量int* data;//data指向存放數據元素的內存空間，堆區空間，數據元素類型默認是整數int size;//動態數組的大小，多少個數據元素，也就是線性表的長度int capacity;//動態數組容量
public://特殊成員函數DynamicArray();//無參構造DynamicArray(int capacity);//有參構造~DynamicArray();//析構//普通成員函數//尾部添加元素void pushBack(int value);//打印動態數組void printDynamicArray();//在指定位置前插入元素void insertByIndex(int index,int value);//查詢相關操作int getCapacity();//返回動態數組容量int getSize();//返回動態數組的大小int getValueByIndex(int index);//返回指定位置的元素int front();//返回動態數組第一個元素int back();//返回動態數組最后一個元素//刪除元素void popBack();//刪除最后一個元素void delByIndex(int index);//刪除元素
};

源文件

#include<iostream>
#include"dynamicArray.h"
using namespace std;
#include<time.h>
DynamicArray::DynamicArray()//無參構造,初始化成員變量
{capacity = 5;//動態數組默認長度為5data = new int[capacity];//data指向五個大小的內存空間size = 0;
}
DynamicArray::DynamicArray(int capacity)//有參構造，傳入容量
{this->capacity = capacity;data = new int[capacity];size = 0;
}
DynamicArray::~DynamicArray()//析構,釋放內存空間
{if(data!=nullptr){delete[]data;data = nullptr;}
}
void DynamicArray::pushBack(int value)
{//考慮容量夠不夠if (capacity == size)//容量已滿，需要擴容，擴充一倍{int* temp_data = new int[capacity * 2];//復制原始空間數據到新空間for (int i = 0; i < size; i++){temp_data[i] = data[i];}delete[]data;//釋放原始空間data = temp_data;capacity = capacity * 2;}data[size] = value;size++;
}
void DynamicArray::insertByIndex(int index, int value)
{if (index<0 || index>size - 1){return;}if (capacity == size){int* temp_data = new int[capacity * 2];for (int i = 0; i < size; i++){temp_data[i] = data[i];}delete[]data;//釋放原始空間data = temp_data;//更新成員變量capacity = capacity * 2;//更新容量//新元素插在index前，index開始的元素都往后移for (int i = size - 1; i >= index; i--){data[i + 1] = data[i];}data[index] = value;size++;}
}
void DynamicArray::printDynamicArray()
{for (int i = 0; i < size; i++){cout << data[i]<<" ";}cout << endl;
}
int DynamicArray::getCapacity()
{return capacity;
}
int DynamicArray::getSize()
{return size;
}
int DynamicArray::getValueByIndex(int index)
{if (index<0 || index>size - 1){return NULL;}return data[index];
}
int DynamicArray::front()
{if (size>0){return data[0];}return NULL;
}
int DynamicArray::back()
{if (size > 0){return data[size - 1];}return NULL;
}
void DynamicArray::popBack()
{if (size > 0){size--;}
}
void DynamicArray::delByIndex(int index)
{if (index<0 || index>size - 1){return;}for (int i = index; i < size - 1; i++){data[i] = data[i + 1];}size--;
}
void test_dynamicarray()
{//DynamicArray dy;DynamicArray* dy = new DynamicArray();//堆對象dy->pushBack(11);dy->pushBack(12);dy->pushBack(13);dy->pushBack(14);dy->pushBack(15);dy->printDynamicArray();dy->insertByIndex(2, 88);dy->printDynamicArray();cout<<"動態數組容量為"<<dy->getCapacity()<<endl;/*for (int i = 0; i < 5; i++){dy->pushBack(i + 20);}dy->printDynamicArray();cout << "動態數組容量為" << dy->getCapacity() << endl;*/cout << "動態數組的大小" << dy->getSize()<<endl;cout << "下標為三的元素" << dy->getValueByIndex(3) << endl;cout << "動態數組第一個元素是" << dy->front()<<endl;cout << "動態數組最后一個元素是" << dy->back() << endl;;dy->popBack();dy->printDynamicArray();dy->delByIndex(2);dy->printDynamicArray();delete dy;
}
void test_homework()
{srand((unsigned int)time(0));//srand(time(0));DynamicArray d;//DynamicArray* dy = new DynamicArray(8);for (int i = 0; i < 8; i++){d.pushBack(rand() % 41+60);//生成0-19之間的整數}//d.pushBack(5);//d.pushBack(7);//d.pushBack(8);//d.pushBack(6);//d.pushBack(2);//d.pushBack(1);//d.pushBack(9);d.printDynamicArray();for (int i = 0; i < d.getSize();){if (d.getValueByIndex(i)%2!=0){d.delByIndex(i);}else{i++;}}d.printDynamicArray();}
int main()
{//test_dynamicarray();test_homework();return 0;
}