??前言：
順序表是數(shù)據(jù)結(jié)構(gòu)里面很基礎(chǔ)的一類，它是線性表的一種，其它線性表還有鏈表、棧和隊(duì)列等，今天來和博主一起學(xué)習(xí)關(guān)于順序表的知識吧。
??順序表和數(shù)組的區(qū)別
順序表，它分為兩類：
動(dòng)態(tài)順序表和靜態(tài)順序表，這兩個(gè)表的區(qū)別就是前者的空間不固定，是支持?jǐn)U容的，后者的空間是固定的，但是兩者的共同點(diǎn)是空間都是連續(xù)的，動(dòng)態(tài)順序表的底層是動(dòng)態(tài)數(shù)組，而靜態(tài)順序表的底層是數(shù)組。
- 很明顯我們經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)就是動(dòng)態(tài)的順序表，因?yàn)殪o態(tài)的順序表空間固定，沒什么實(shí)際的價(jià)值。
- 還有一個(gè)區(qū)別就是，動(dòng)態(tài)順序表是基于動(dòng)態(tài)數(shù)組的，但是它作為一個(gè)數(shù)據(jù)結(jié)構(gòu)，提供了很多動(dòng)態(tài)數(shù)組沒有直接提供的功能，像
增、刪、查、改、創(chuàng)建和銷毀、以及計(jì)算數(shù)組的大小這些基本的功能。
??動(dòng)態(tài)順序表的模擬實(shí)現(xiàn)
??動(dòng)態(tài)順序表的基本結(jié)構(gòu)設(shè)計(jì)
#define DataTypeVector int
typedef struct my_vector
{
int* a;//儲存數(shù)據(jù)
size_t size;//順序表的數(shù)據(jù)大小
size_t capacity;//順序表的空間大小
}mv;
各種接口：
//初始化
mv* Init();
//頭插
void push_front(mv* mv1, DataTypeVector x);
//頭刪
void pop_front(mv* mv1);
//尾插
void push_back(mv* mv1, DataTypeVector x);
//尾刪
void pop_back(mv* mv1);
//插入--在某個(gè)位置之前
void insert(mv* mv1,size_t positon, DataTypeVector x);
//刪除某個(gè)位置的元素
void erase(mv* mv1,size_t position);
//查找某個(gè)值，并返回它出現(xiàn)的位置,沒有找到，返回-1；
int find(mv* mv1, DataTypeVector x);
//計(jì)算動(dòng)態(tài)順序表的大小
size_t Size(mv* mv1);
//銷毀動(dòng)態(tài)順序表
void Destroy(mv** mv1);
//修改某個(gè)位置的值
void Modify(mv* mv1, size_t position, DataTypeVector x);
??動(dòng)態(tài)順序表的各種功能模擬實(shí)現(xiàn)
?? 初始化（init）
返回值版本：
//初始化動(dòng)態(tài)順序表
//返回值版本
mv* Init()
{
mv* mv1 = (mv*)malloc(sizeof(mv));
if (mv1 == NULL)
{
printf("malloc Falied\n");
exit(-1);
}
mv1->a = NULL;
mv1->capacity = 0;
mv1->size = 0;
return mv1;
}
二級指針版本：
//二級指針版本，不帶返回值
void Init(mv** mv1)
{
assert(mv1);
(*mv1) = (mv*)malloc(sizeof(mv));
if ((*mv1) == NULL)
{
printf("malloc failed\n");
exit(-1);
}
(*mv1)->a = NULL;
(*mv1)->capacity = NULL;
(*mv1)->size = NULL;
}
?? 頭插、頭刪
?? 頭插
//頭插
void push_front(mv* mv1, DataTypeVector x)
{
assert(mv1 != NULL);
if ((mv1)->capacity == (mv1)->size)//判斷是否需要擴(kuò)容
{
(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
DataTypeVector* tmp = NULL;
tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
mv1->a = tmp;
}
//將所有值后移
for (size_t i = mv1->size; i > 0; --i)
{
mv1->a[i] = mv1->a[i-1];
}
mv1->a[0] = x;
++mv1->size;
}
?? 頭刪
//頭刪
void pop_front(mv* mv1)
{
assert(mv1 != NULL);
assert(mv1->size > 0);
//將后面的值依次覆蓋前面的值
for (size_t i = 0; i < mv1->size-1; ++i)
{
mv1->a[i] = mv1->a[i + 1];
}
--mv1->size;//別忘了數(shù)組的大小要減減
}
?? 尾插、尾刪
?? 尾插
//尾插
void push_back(mv* mv1, DataTypeVector x)
{
assert(mv1 != NULL);
if ((mv1)->capacity == (mv1)->size)//判斷是否需要擴(kuò)容
{
(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
DataTypeVector* tmp = NULL;
tmp = (DataTypeVector*)realloc(mv1->a,sizeof(DataTypeVector) * mv1->capacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
mv1->a = tmp;
}
mv1->a[mv1->size] = x;
++mv1->size;
}
?? 尾刪
//尾刪
void pop_back(mv* mv1)
{
assert(mv1);
assert(mv1->size > 0);
--mv1->size;
}
?? 計(jì)算動(dòng)態(tài)順序表的大小（size接口）
//計(jì)算動(dòng)態(tài)線性表的大小
size_t Size(mv* mv1)
{
assert(mv1);
return mv1->size;
}
?? 動(dòng)態(tài)順序表在特定位置插入（insert）
這里我們仿照C++STL庫，只實(shí)現(xiàn)了在pos位置之前插入。
//插入--在某個(gè)位置之前
//插入--在某個(gè)位置之前
void insert(mv* mv1, size_t position,DataTypeVector x)
{
assert(mv1 != NULL);
assert(position < mv1->size);
if ((mv1)->capacity == (mv1)->size)//判斷是否需要擴(kuò)容
{
(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
DataTypeVector* tmp = NULL;
tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
if (tmp == NULL)
{
printf("calloc failed\n");
exit(-1);
}
mv1->a = tmp;
}
//從下標(biāo)size開始，把數(shù)據(jù)都往后挪動(dòng).
for (size_t i = mv1->size; i > position; --i)
{
mv1->a[i] = mv1->a[i-1];
}
//最后把下標(biāo)position位置賦值為x
mv1->a[position] = x;
//別忘了size
++mv1->size;
}
?? 動(dòng)態(tài)順序表在特定位置刪除（erase）
//刪除某個(gè)位置的元素
void erase(mv* mv1, size_t position)
{
assert(mv1 != NULL);
assert(position < mv1->size);
for (size_t i = position; i < mv1->size-1; ++i)
{
mv1->a[i] = mv1->a[i + 1];
}
--mv1->size;
}
?? 動(dòng)態(tài)順序表的查找
//查找某個(gè)值，并返回它出現(xiàn)的位置,沒有找到，返回-1；
int find(mv* mv1,DataTypeVector x)
{
assert(mv1 != NULL);
for (size_t i = 0; i < mv1->size; ++i)
{
if (x == mv1->a[i])//找到直接返回下標(biāo)i
return i;
}
return -1;//沒有找到返回-1
}
這里順序表不一定是有序的，所以不能使用二分查找。
?? 修改某個(gè)位置的值
void Modify(mv* mv1,size_t position,DataTypeVector x)
{
assert(mv1);
assert(position < mv1->size);
mv1->a[position] = x;
}
?? 動(dòng)態(tài)順序表的銷毀
動(dòng)態(tài)順序表的底層就是動(dòng)態(tài)數(shù)組，它是堆上開辟的，通常遵循一下原則：
1. 由誰申請就由誰釋放。 這是一個(gè)約定俗成的說法，指的是誰（程序員）申請的內(nèi)存，需要自己負(fù)責(zé)去釋放，避免出現(xiàn)內(nèi)存泄漏。
2.只能一次釋放整個(gè)動(dòng)態(tài)數(shù)組，而不能只釋放一部分
只要我們遵循這兩個(gè)原則，然后再對順序表類型的成員進(jìn)行置空和置零，就實(shí)現(xiàn)了動(dòng)態(tài)線順序表的銷毀。
//銷毀動(dòng)態(tài)順序表
void Destroy(mv** mv1)
{
assert(mv1 != NULL);
(*mv1)->capacity = (*mv1)->size = 0;
free((*mv1)->a);//先銷毀順序表里面的成員
(*mv1)->a = NULL;
free(*mv1);//銷毀整個(gè)順序表
*mv1 = NULL;
}
?? 總結(jié)
關(guān)于《數(shù)據(jù)結(jié)構(gòu)初階之順序表（C語言實(shí)現(xiàn)）》這篇文章就講解到這兒，感謝大家的支持，歡迎大家留言交流以及批評指正。接下來將為大家?guī)硪黄恫灰粯拥腃語言之easyx庫的使用》，敬請期待吧。下面是本篇博客的思維導(dǎo)圖希望對您有所幫助。文章來源：http://www.zghlxwxcb.cn/news/detail-770299.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-770299.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)初階之順序表（C語言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
