柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】順序表
柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】順序表
Hi~！這里是奮斗的小羊，很榮幸您能閱讀我的文章，誠請(qǐng)?jiān)u論指點(diǎn)，歡迎歡迎 ~~ ??個(gè)人主頁：奮斗的小羊 ??所屬專欄：C語言
?本系列文章為個(gè)人學(xué)習(xí)筆記，在這里撰寫成文一為鞏固知識(shí)，二為展示我的學(xué)習(xí)過程及理解。文筆、排版拙劣，望見諒。
目錄
前言1、數(shù)據(jù)結(jié)構(gòu)2、線性表3、順序表3.1 為什么要有順序表？3.2 創(chuàng)建和初始化3.3 頭插3.4 尾插3.5 在指定位置前插入3.6 頭刪3.7 尾刪3.8 刪除指定位置的數(shù)據(jù)3.9 順序表的查找3.10 順序表銷毀3.11 測試
總結(jié)
前言
本篇文章將詳細(xì)介紹順序表的基本搭建過程。 我們都知道順序表的底層其實(shí)就是數(shù)組，但是既然有了數(shù)組為什么還要有順序表呢？ 其實(shí)相比如數(shù)組，順序表還是有很多優(yōu)勢的。比如動(dòng)態(tài)擴(kuò)容、增刪查改效率高、支持動(dòng)態(tài)元素類型、停供更多的操作方法等。順序表相對(duì)于數(shù)組具有更高的靈活性和功能性，可以更方便地對(duì)數(shù)據(jù)進(jìn)行操作和管理。
1、數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是由“數(shù)據(jù)”和“結(jié)構(gòu)”兩詞組成。 什么是數(shù)據(jù)？數(shù)據(jù)是記錄事實(shí)、觀察結(jié)果或描述信息的集合，通常以數(shù)字、文字、圖像或聲音的形式存在。 什么是結(jié)構(gòu)？簡單來說結(jié)構(gòu)就是組織數(shù)據(jù)的方式。
數(shù)據(jù)結(jié)構(gòu)是指計(jì)算機(jī)存儲(chǔ)、組織和管理數(shù)據(jù)的方式。
2、線性表
線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表有：順序表、鏈表、棧、隊(duì)列、字符串…… 線性表在邏輯上是線性結(jié)構(gòu)，也就是連續(xù)的一條直線，但物理上并不一定連續(xù)，線性表在物理上存儲(chǔ)時(shí)， 通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
3、順序表
3.1 為什么要有順序表？
順序表的底層其實(shí)就是數(shù)組。
順序表是線性表的一種，并且順序表在邏輯上和物理上都是線性的。
數(shù)組就可以管理數(shù)據(jù)，為什么還要有順序表呢？數(shù)組也可以實(shí)現(xiàn)一些增刪查改的操作，但是實(shí)現(xiàn)起來比較麻煩，于是順序表就把這些比較麻煩的操作封裝好，使我們使用起來更加方便。 順序表也分靜態(tài)順序表和動(dòng)態(tài)順序表。 靜態(tài)順序表底層是定長數(shù)組，空間給大了浪費(fèi)，給小了不夠，有缺陷。 動(dòng)態(tài)順序表的空間大小是可變的，是由動(dòng)態(tài)內(nèi)存函數(shù)realloc對(duì)開辟的動(dòng)態(tài)內(nèi)存空間進(jìn)行調(diào)整。 我們通常使用動(dòng)態(tài)順序表。
3.2 創(chuàng)建和初始化
首先我們需要一個(gè)指針來接收由動(dòng)態(tài)內(nèi)存函數(shù)開辟的空間，還需要一個(gè)變量記錄當(dāng)前順序表內(nèi)數(shù)據(jù)個(gè)數(shù)，因?yàn)槲覀儎?chuàng)建的是動(dòng)態(tài)順序表，大小經(jīng)常變化，所以我們還需要一個(gè)變量來記錄當(dāng)前空間的大小。最后我們?cè)侔堰@些值封裝到一個(gè)結(jié)構(gòu)體中，這個(gè)結(jié)構(gòu)體就是我們要?jiǎng)?chuàng)建的動(dòng)態(tài)順序表。
//順序表管理數(shù)據(jù)的類型
typedef int sl_data_type;
typedef struct seqlist
{
sl_data_type* arr;
int size;//數(shù)據(jù)個(gè)數(shù)
int capacity;//空間大小
}SL;
我們希望創(chuàng)建的順序表能管理多種類型的數(shù)據(jù)，所以使用類型重定義標(biāo)識(shí)符typedef。 創(chuàng)建好順序表后，為了以后使用方便我們將它的初始化步驟也分裝成一個(gè)函數(shù)：
void sl_init(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
注意指針要賦NULL。
3.3 頭插
創(chuàng)建和初始化順序表后，我們來實(shí)現(xiàn)在順序表頭部插入數(shù)據(jù)。 插入數(shù)據(jù)是直接插嗎？不是的，我們還需要判斷當(dāng)前順序表中是否有足夠的空間讓我們插入數(shù)據(jù)，因?yàn)椴还苁悄姆N插入的方式都要進(jìn)行判斷，所以我們干脆把這一步驟分裝成一個(gè)函數(shù)，方便后續(xù)使用。 如何判斷當(dāng)前順序表是否有足夠的空間呢？是ps->capacity>0嗎？ 不是的，因?yàn)橛幸环N特殊情況是當(dāng)前順序表的空間剛好被使用完，合理的判斷條件是當(dāng)ps->size == ps->capacity時(shí)，我們申請(qǐng)空間。 但是申請(qǐng)空間又有一個(gè)問題擺在我們面前：申請(qǐng)多大？仿佛又回到了定長數(shù)組的問題。 不過不要慌，由數(shù)學(xué)推理得出，一次申請(qǐng)空間大小是原空間大小2倍最合理。
//檢查是否有空間允許插入數(shù)據(jù)
void check_capacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//為了處理capacity為0的問題
sl_data_type* tmp = (sl_data_type*)realloc(ps->arr, newcapacity * sizeof(sl_data_type));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
tmp = NULL;
ps->capacity = newcapacity;//及時(shí)更新空間大小
}
}
空間大小需要乘以相應(yīng)類型的大小。 在使用realloc函數(shù)時(shí)不要忘了其返回值也有為NULL的可能，所以需要一個(gè)臨時(shí)指針過渡，這個(gè)臨時(shí)指針使用完也不要忘了賦NULL，以防止其成為野指針。 順序表的空間大小最后也不要忘了及時(shí)更新。 判斷是否有足夠的空間后，接下來就是在順序表的頭部插入數(shù)據(jù)。 我們先要將原先的數(shù)據(jù)向后挪動(dòng)一位，將順序表的第一位空出來，插入我們想插入的數(shù)據(jù)。
void sl_push_front(SL* ps, sl_data_type x)
{
assert(ps != NULL);
check_capacity(ps);
int i = 0;
for (i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
開始插入操作之前，為了防止意外我們先判斷一下傳過來的順序表的指針是否為空。 最后不要忘了給順序表內(nèi)記錄數(shù)據(jù)個(gè)數(shù)的變量++。
3.4 尾插
相比于頭插，尾插沒有挪動(dòng)原有數(shù)據(jù)的操作，在判斷完空間大小和數(shù)據(jù)個(gè)數(shù)后直接在數(shù)據(jù)末尾插入就行，同樣也不要忘了讓記錄數(shù)據(jù)個(gè)數(shù)的變量++
void sl_push_back(SL* ps, sl_data_type x)
{
assert(ps != NULL);
check_capacity(ps);
ps->arr[ps->size++] = x;
}
3.5 在指定位置前插入
順序表中不止在頭部和尾部插入數(shù)據(jù)，也可在指定的任意有效位置插入數(shù)據(jù)，所以我們的函數(shù)就要多一個(gè)指定位置的參數(shù)。 指定的位置還必須要有效，因?yàn)轫樞虮碇械臄?shù)據(jù)一定是連續(xù)的。 插入之前，我們需要將指定位置后面的數(shù)據(jù)往后挪動(dòng)一位，給要插入的數(shù)據(jù)留出空間。
void sl_insert(SL* ps, int pos, sl_data_type x)
{
assert(ps != NULL);
assert(pos >= 0 && pos <= ps->size);//確保指定的位置是有效的
check_capacity(ps);
int i = 0;
for (i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
插入數(shù)據(jù)后，記錄數(shù)據(jù)個(gè)數(shù)的變量不要忘了++。
3.6 頭刪
在刪除完順序表的第一個(gè)數(shù)據(jù)后，也需要將剩余的數(shù)據(jù)向前挪動(dòng)一位，以確保數(shù)據(jù)是在下標(biāo)為0處開始。 在刪除數(shù)據(jù)之前，我們還要考慮到一種特殊情況，就是當(dāng)前順序表中沒有數(shù)據(jù)，那沒有數(shù)據(jù)肯定是不能進(jìn)行刪除操作的。
void sl_pop_front(SL* ps)
{
assert(ps != NULL);
assert(ps->size != 0);//順序表為空不能刪除
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
刪除操作完成后，數(shù)據(jù)個(gè)數(shù)–；
3.7 尾刪
尾刪則比較簡單，因?yàn)槲覀冎恍枰層涗洈?shù)據(jù)個(gè)數(shù)的變量-1，在訪問順序表的時(shí)候訪問不到這個(gè)數(shù)據(jù)，就相當(dāng)于刪除了這個(gè)數(shù)據(jù) 同樣的，尾刪也需要考慮當(dāng)前數(shù)據(jù)個(gè)數(shù)是否為0的情況。
void sl_pop_back(SL* ps)
{
assert(ps != NULL);
assert(ps->size != 0);//順序表為空不能刪除
ps->size--;
}
3.8 刪除指定位置的數(shù)據(jù)
這個(gè)指定的位置也必須是有效的。 同時(shí)也要保證當(dāng)前順序表中的數(shù)據(jù)個(gè)數(shù)不為0。
void sl_erase(SL* ps, int pos)
{
assert(ps != NULL);
assert(ps->size != 0);//實(shí)際下面的斷言側(cè)面完成了這句代碼
assert(pos >= 0 && pos < ps->size);//確保指定的位置是有效的
int i = 0;
for (i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
3.9 順序表的查找
想要在順序表中查找一個(gè)數(shù)據(jù)，只需要像遍歷數(shù)組一樣遍歷順序表就行。 找到則返回?cái)?shù)據(jù)對(duì)應(yīng)的下標(biāo)，找不到則返回-1。
int sl_find(SL* ps, sl_data_type x)
{
assert(ps != NULL);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
3.10 順序表銷毀
我們向內(nèi)存申請(qǐng)了一塊空間使用完成后，還要?dú)w還給操作系統(tǒng) 在上面調(diào)整順序表大小的操作中，我們使用的是動(dòng)態(tài)內(nèi)存函數(shù)realloc，因此還要使用函數(shù)free釋放掉動(dòng)態(tài)開辟的空間，也不要忘了給指針賦NULL
void sl_destroy(SL* ps)
{
assert(ps != NULL);
if (ps->arr != NULL)//動(dòng)態(tài)內(nèi)存函數(shù)開辟了空間
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
3.11 測試
為了對(duì)我們創(chuàng)建的順序表進(jìn)行測試，方便起見再寫一個(gè)打印函數(shù)。
void sl_print(const SL sl)
{
int i = 0;
for (i = 0; i < sl.size; i++)
{
printf("%d ", sl.arr[i]);
}
printf("\n");
}
測試代碼如下：
void test()
{
SL sl;
sl_init(&sl);
sl_push_front(&sl, 1);
sl_push_front(&sl, 2);
sl_push_front(&sl, 3);
sl_print(sl);
sl_push_back(&sl, 4);
sl_push_back(&sl, 5);
sl_push_back(&sl, 6);
sl_print(sl);
sl_pop_front(&sl);
sl_print(sl);
sl_pop_back(&sl);
sl_print(sl);
sl_pop_front(&sl);
sl_print(sl);
sl_pop_back(&sl);
sl_print(sl);
sl_pop_front(&sl);
sl_print(sl);
sl_pop_back(&sl);
sl_print(sl);
sl_destroy(&sl);
}
運(yùn)行結(jié)果：
結(jié)果和我們預(yù)期的效果一致。 整個(gè)程序的原碼如下： seqlist.h:
#pragma once
#include
#include
#include
//順序表管理數(shù)據(jù)的類型
typedef int sl_data_type;
typedef struct seqlist
{
sl_data_type* arr;
int size;//數(shù)據(jù)個(gè)數(shù)
int capacity;//空間大小
}SL;
//順序表初始化
void sl_init(SL* ps);
//頭插
void sl_push_front(SL* ps, sl_data_type x);
//尾插
void sl_push_back(SL* ps, sl_data_type x);
//在指定位置之前插入數(shù)據(jù)
void sl_insert(SL* ps, int pos, sl_data_type x);
//頭刪
void sl_pop_front(SL* ps);
//尾刪
void sl_pop_back(SL* ps);
//刪除指定位置的數(shù)據(jù)
void sl_erase(SL* ps, int pos);
//順序表的查找
int sl_find(SL* ps, sl_data_type x);
//順序表打印
void sl_print(const SL sl);
//順序表銷毀
void sl_destroy(SL* ps);
seqlist.c:
#define _CRT_SECURE_NO_WARNINGS
#include "seqlist.h"
void sl_init(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//檢查是否有空間允許插入數(shù)據(jù)
void check_capacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//為了處理capacity為0的問題
sl_data_type* tmp = (sl_data_type*)realloc(ps->arr, newcapacity * sizeof(sl_data_type));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
tmp = NULL;
ps->capacity = newcapacity;//及時(shí)更新空間大小
}
}
void sl_push_front(SL* ps, sl_data_type x)
{
assert(ps != NULL);
check_capacity(ps);
int i = 0;
for (i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
void sl_push_back(SL* ps, sl_data_type x)
{
assert(ps != NULL);
check_capacity(ps);
ps->arr[ps->size++] = x;
}
void sl_insert(SL* ps, int pos, sl_data_type x)
{
assert(ps != NULL);
assert(pos >= 0 && pos <= ps->size);//確保指定的位置是有效的
check_capacity(ps);
int i = 0;
for (i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
void sl_pop_front(SL* ps)
{
assert(ps != NULL);
assert(ps->size != 0);//順序表為空不能刪除
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
void sl_pop_back(SL* ps)
{
assert(ps != NULL);
assert(ps->size != 0);//順序表為空不能刪除
ps->size--;
}
void sl_erase(SL* ps, int pos)
{
assert(ps != NULL);
assert(ps->size != 0);
assert(pos >= 0 && pos < ps->size);//確保指定的位置是有效的
int i = 0;
for (i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
int sl_find(SL* ps, sl_data_type x)
{
assert(ps != NULL);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
void sl_print(const SL sl)
{
int i = 0;
for (i = 0; i < sl.size; i++)
{
printf("%d ", sl.arr[i]);
}
printf("\n");
}
void sl_destroy(SL* ps)
{
assert(ps != NULL);
if (ps->arr != NULL)//動(dòng)態(tài)內(nèi)存函數(shù)開辟了空間
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
test.c:
#define _CRT_SECURE_NO_WARNINGS
#include "seqlist.h"
void test()
{
SL sl;
sl_init(&sl);
sl_push_front(&sl, 1);
sl_push_front(&sl, 2);
sl_push_front(&sl, 3);
sl_print(sl);
sl_push_back(&sl, 4);
sl_push_back(&sl, 5);
sl_push_back(&sl, 6);
sl_print(sl);
sl_pop_front(&sl);
sl_print(sl);
sl_pop_back(&sl);
sl_print(sl);
sl_pop_front(&sl);
sl_print(sl);
sl_pop_back(&sl);
sl_print(sl);
sl_pop_front(&sl);
sl_print(sl);
sl_pop_back(&sl);
sl_print(sl);
sl_insert(&sl, 0, 4);
sl_print(sl);
sl_erase(&sl, 1);
sl_print(sl);
int ret = sl_find(&sl, 3);
if (ret >= 0)
{
printf("%d\n", sl.arr[ret]);
}
else
{
printf("沒找到");
}
sl_destroy(&sl);
}
int main()
{
test();
return 0;
}
總結(jié)
我們常用的是動(dòng)態(tài)順序表，通過realloc函數(shù)來對(duì)空間大小適當(dāng)?shù)臄U(kuò)容順序表中的元素在內(nèi)存中是連續(xù)存儲(chǔ)的，可以通過下標(biāo)直接訪問元素，提高了查找效率適合： 頻繁訪問、很少插入和刪除的數(shù)據(jù)集合。由于順序表支持通過下標(biāo)直接訪問元素，適合頻繁讀取和遍歷元素的場景不適合： 頻繁插入和刪除的場景。由于插入和刪除操作需要移動(dòng)數(shù)據(jù)，頻繁插入和刪除會(huì)影響性能，不適合該類場景
柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】順序表
精彩內(nèi)容
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Starday星光出海站
