數(shù)據(jù)結(jié)構(gòu)之——動態(tài)數(shù)組（順序表）
1.動態(tài)數(shù)組和靜態(tài)數(shù)組
靜態(tài)數(shù)組：靜態(tài)數(shù)組在內(nèi)存中位于棧區(qū)，是在編譯時就已經(jīng)在棧上分配了固定大小，程序結(jié)束由系統(tǒng)釋放。在運行時不能改變數(shù)組大小。
//靜態(tài)數(shù)組
int N = 10;
int a[N]; /*定義一個數(shù)組大小為10的數(shù)組，因為靜態(tài)數(shù)組在編譯階段就會確定數(shù)組大小，所以這里的N必須是一個確定的值
如果在這里沒有給出N值的大小，會導(dǎo)致編譯失敗*/
動態(tài)數(shù)組：動態(tài)數(shù)組是malloc（在c語言中使用malloc函數(shù)）或者new(在c++中使用new操作符)出來的，位于內(nèi)存的堆區(qū)，它的大小是在程序運行時給定的，可以動態(tài)的改變數(shù)組的大小，以及動態(tài)的增，刪，查，改數(shù)組中的元素。
//動態(tài)數(shù)組
struct Array
{
int* a; //這里只需要定義一個指針，在程序運行起來之后如果在堆區(qū)開辟了一塊數(shù)組空間，就讓這個指針指向數(shù)組的首地址即可
int size; //size用于記錄當(dāng)前數(shù)組儲存了多少個元素
int acpcaity; //acpcaity用于記錄當(dāng)前數(shù)組的容量大?。ㄔ摂?shù)組最多能存儲多少個元素）
}
2.如何維護(hù)一個動態(tài)數(shù)組
根據(jù)上圖將維護(hù)一個數(shù)組分為以下三點：
1.當(dāng)數(shù)組未創(chuàng)建時只需要讓arr指針指向NULL，size,acpcaity都初始化為零，當(dāng)成功在堆區(qū)創(chuàng)建了一個數(shù)組之后我們只需要把arr指針指向該數(shù)組的首地址即可。
2.每次對數(shù)組進(jìn)行添加元素或者刪除元素時，都要對應(yīng)的對size進(jìn)行相應(yīng)的加減操作，size必須準(zhǔn)確的記錄數(shù)組中的元素個數(shù)
3.每次對數(shù)組擴(kuò)容時都要實時更新當(dāng)前數(shù)組大小給acpcaity，以便于更準(zhǔn)確的控制數(shù)組大小如果acpcaity大于數(shù)組真實容量，可能導(dǎo)致程序崩潰。
列： 如果當(dāng)前acpcaity=5;而當(dāng)前數(shù)組實際容量為4，這時通過arr[4]插入第5個元素時，就會因為非法訪問內(nèi)存而導(dǎo)致程序崩潰
如果acpcaity小于數(shù)組真實容量，會導(dǎo)致數(shù)組頻繁擴(kuò)容，造成資源浪費。
以下是一個動態(tài)數(shù)組的小案列，用C語言實現(xiàn)c++中的vector容器（沒有學(xué)過的c++的家人們完全可以忽略這句話，因為這就是一個簡單動態(tài)數(shù)組的實現(xiàn)，vector容器的底層也是用動態(tài)數(shù)組實現(xiàn)的）
//頭文件（vector.h）
#pragma once
#include<stdio.h>
//如果想儲存其他數(shù)據(jù)類型只需將這里的int換成你想要儲存的數(shù)據(jù)類型即可
typedef int anytype; //儲存int類型的數(shù)據(jù)
//typedef double anytype; //儲存double類型的數(shù)據(jù)
typedef struct STL_Vector
{
anytype* arr; //定義一個指針，用于指向后面創(chuàng)建的數(shù)組的首地址
int size; //記錄數(shù)組當(dāng)前元素個數(shù)
int capacity; //記錄數(shù)組當(dāng)前容量大小
}vector;
//接口函數(shù)
void VectorInit(vector * v); //初始化結(jié)構(gòu)體
void Add_Capacity(vector* v); //當(dāng)數(shù)組容量不夠時擴(kuò)容
void push_back(vector* v, anytype x); //尾部插入元素
void push_front(vector* v, anytype x); //頭部插入元素
void My_print(vector v); //遍歷數(shù)組
void pop_back(vector* v); //刪除最后一個元素
int find(vector v, anytype x); //查找指定元素的位置，返回元素位置
void pop_front(vector* v); //刪除第一個元素下標(biāo)
int pos_insert(vector* v,int pos, anytype x);//指定下標(biāo)位置插入元素
int pos_delect(vector* v, int pos); //指定下標(biāo)位置刪除元素
以下是接口函數(shù)的實現(xiàn)
//.c文件（vector.c）
#include"vector.h"
//初始化結(jié)構(gòu)體
void VectorInit(vector* v){
v->arr = NULL;
v->capacity = v->size = 0;
}
//創(chuàng)建數(shù)組或?qū)σ呀?jīng)滿的數(shù)組進(jìn)行擴(kuò)容
void Add_Capacity(vector* v){
if (v->size == v->capacity){ //當(dāng)size=capacity時，說明數(shù)組可能還未創(chuàng)建，或數(shù)組已經(jīng)滿了
int newspace = v->capacity == 0 ? 4 : v->capacity * 2; /*如果數(shù)組容量為零就先給4個整形的大小，否則就在原來的
基礎(chǔ)上乘以2，每次擴(kuò)容2倍*/
anytype* tem = (anytype*)realloc(v->arr, newspace * sizeof(anytype));
/*1.擴(kuò)容成功，返回新空間的地址
2.擴(kuò)容失敗，返回NULL*/
if (tem == NULL){
printf("擴(kuò)容失?。?);
exit(-1); //擴(kuò)容失敗直接退出程序
}
v->arr = tem;
v->capacity = newspace;
}
}
//尾插數(shù)據(jù)
void push_back(vector* v, anytype x){
Add_Capacity(v); //首先要確定數(shù)組是否創(chuàng)建，容量是否大于零，如果數(shù)據(jù)未創(chuàng)建，先創(chuàng)建數(shù)組，如果已創(chuàng)建但是容量已滿，就擴(kuò)容
if (v->arr != NULL){
v->arr[v->size] = x;
v->size++;
}
}
//頭插數(shù)據(jù)
void push_front(vector* v, anytype x){
Add_Capacity(v);
int ret = v->size;
for (ret; ret>=0; ret--){
v->arr[ret] = v->arr[ret-1];
}
if (v->arr != NULL){
v->arr[0] = x;
v->size++;
}
}
//尾刪數(shù)據(jù)
void pop_back(vector* v){
if (v->size > 0){ //首先判斷數(shù)組中是否有數(shù)據(jù)，有數(shù)據(jù)才刪除，以下同理
v->size--;
}
}
//頭刪數(shù)據(jù)
void pop_front(vector* v){
if (v->size > 0){
int ret = v->size;
for (int i= 0; i<ret; i++){
v->arr[i] = v->arr[i+1];
}
v->size--;
}
}
//查找數(shù)據(jù)，成功返回數(shù)據(jù)下標(biāo)，失敗返回-1
int find(vector v, anytype x){
if (v.size > 0){
for (int i = 0; i < v.size; i++){
if (v.arr[i] == x){
return i;
}
}
}
return -1;
}
//指定下標(biāo)添加數(shù)據(jù)
int pos_insert(vector* v, int pos, anytype x){
Add_Capacity(v);
if (pos >= 0 && pos <= v->size){
int i = v->size;
for (i - 1; pos <= i; i--){
v->arr[i] = v->arr[i-1];
}
v->arr[pos] = x;
v->size++;
return 0;
}
return -1;
}
//指定下標(biāo)刪除數(shù)據(jù)
int pos_delect(vector* v, int pos){
Add_Capacity(v);
if (pos >= 0 && pos < v->size){
int i = v->size;
for (pos; pos < i; pos++){
v->arr[pos] = v->arr[pos+1];
}
v->size--;
return 0;
}
return -1;
}
//遍歷數(shù)組
void My_print(vector v){
if (v.arr == NULL){
printf("數(shù)組未創(chuàng)建！\n");
return;
}
else if (v.size == 0){
printf("數(shù)組為空！\n");
return;
}
for (int i=0; i < v.size; i++){
printf("%d ",v.arr[i]);
}
printf("\n");
}
3.動態(tài)數(shù)組和靜態(tài)數(shù)組的優(yōu)缺點
靜態(tài)數(shù)組：
優(yōu)點：
(1).容量大小固定，下標(biāo)固定，查找數(shù)據(jù)快，效率高
缺點:
(1).如果數(shù)組滿了，就不能繼續(xù)插入數(shù)據(jù)了
(2). 很難確定數(shù)組的容量大小，給大了浪費，給大小不夠放
(3).同一個數(shù)組只能儲存一種數(shù)據(jù)類型
動態(tài)數(shù)組：
優(yōu)點：
(1).可以根據(jù)數(shù)據(jù)量的大小動態(tài)擴(kuò)容和縮小容量
(2).可以通過下標(biāo)快速查找數(shù)據(jù)
缺點：
(1).頭插數(shù)據(jù)，中間插入數(shù)據(jù)時，需要挪動數(shù)據(jù)，速度慢效率低
(2).同一個數(shù)組只能儲存一種數(shù)據(jù)類型
面試常見考點
1.請你說說delete和free的區(qū)別
(1). delete是操作符，free是庫函數(shù)
(2). delete用于在c++中釋放new創(chuàng)建的空間，free用于釋放c語言中malloc創(chuàng)建的空間
(3). 調(diào)用free之前需要檢查要釋放的指針是否為空，而delete則不需要
2.請你說說malloc和new的區(qū)別
(1).new/delete是C++操作符，需要編譯器支持，而malloc/free是庫函數(shù)，需要引入頭文件。
(2).使用new操作符申請內(nèi)存分配時無須指定內(nèi)存塊的大小，編譯器會根據(jù)類型信息自行計算。而malloc則需要指定要開辟空間的大小。
(3). new操作符內(nèi)存分配成功時，返回的是對象類型的指針，類型嚴(yán)格與對象匹配，無須進(jìn)行類型轉(zhuǎn)換，故new是符合類型安全性的操作符。而malloc內(nèi)存分配成功則是返回void * ，需要通過強制類型轉(zhuǎn)換將void*指針轉(zhuǎn)換成我們需要的類型。
(4).new內(nèi)存分配失敗時，會拋出bac_alloc異常。malloc分配內(nèi)存失敗時返回NULL。
(5). new會先調(diào)用operator new函數(shù)，申請足夠的內(nèi)存（通常底層使用malloc實現(xiàn)）。然后調(diào)用類型的構(gòu)造函數(shù)，初始化成員變量，最后返回自定義類型指針。delete先調(diào)用析構(gòu)函數(shù)，然后調(diào)用operator delete函數(shù)釋放內(nèi)存（通常底層使用free實現(xiàn)）。
(6). C++允許重載new/delete操作符，特別的，布局new的就不需要為對象分配內(nèi)存，而是指定了一個地址作為內(nèi)存起始區(qū)域，new在這段內(nèi)存上為對象調(diào)用構(gòu)造函數(shù)完成初始化工作，并返回此地址。而malloc不允許重載。
(7).new操作符從自由存儲區(qū)（free store）上為對象動態(tài)分配內(nèi)存空間，而malloc函數(shù)從堆上動態(tài)分配內(nèi)存。自由存儲區(qū)是C++基于new操作符的一個抽象概念，凡是通過new操作符進(jìn)行內(nèi)存申請，該內(nèi)存即為自由存儲區(qū)。而堆是操作系統(tǒng)中的術(shù)語，是操作系統(tǒng)所維護(hù)的一塊特殊內(nèi)存，用于程序的內(nèi)存動態(tài)分配，C語言使用malloc從堆上分配內(nèi)存，使用free釋放已分配的對應(yīng)內(nèi)存。自由存儲區(qū)不等于堆，如上所述，布局new就可以不位于堆中。
轉(zhuǎn)載自文章來源：http://www.zghlxwxcb.cn/news/detail-590650.html
總結(jié)
順序表應(yīng)該是數(shù)據(jù)結(jié)構(gòu)中最簡單的一個了，接下來的時間我也會更加努力的學(xué)習(xí)，提升自己的同時給家人們帶來更優(yōu)質(zhì)的文章，最后希望該篇文章能幫助到大家，作者本人水平有限，如果文章中錯誤或者不足的地方歡迎大家指出。文章來源地址http://www.zghlxwxcb.cn/news/detail-590650.html
到了這里，關(guān)于C/C++數(shù)據(jù)結(jié)構(gòu)之動態(tài)數(shù)組篇的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![數(shù)據(jù)結(jié)構(gòu)03：棧、隊列和數(shù)組 隊習(xí)題01[C++]](https://imgs.yssmx.com/Uploads/2024/04/849898-1.png)
