C語言 數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組模擬實(shí)現(xiàn)順序表流程詳解
更新時(shí)間：2021年11月20日 09:01:00 作者：Ersansui
順序表，全名順序存儲結(jié)構(gòu)，是線性表的一種，線性表用于存儲邏輯關(guān)系為“一對一”的數(shù)據(jù)，順序表自然也不例外，不僅如此，順序表對數(shù)據(jù)的物理存儲結(jié)構(gòu)也有要求，跟隨下文來具體了解吧
代碼已經(jīng)放在Gitee上，需要可以小伙伴可以去看看
用C語言數(shù)組模擬實(shí)現(xiàn)順序表
線性表和順序表
線性表
線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，這是我們廣泛使用的數(shù)據(jù)結(jié)構(gòu)。
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串…
順序表
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
一般可以分為：
- 靜態(tài)順序表：使用定長數(shù)組來存儲元素
- 動態(tài)順序表：使用動態(tài)開辟的數(shù)組來儲存元素
靜態(tài)順序表
//定義靜態(tài)數(shù)組的大小，方便后續(xù)修改
#define MAX_SIZE 50
//重命名數(shù)組的數(shù)據(jù)類型，方便后續(xù)修改
typedef int SLDataType;
//定義結(jié)構(gòu)體
//成員變量為數(shù)組和記錄當(dāng)前數(shù)據(jù)個(gè)數(shù)的變量
//重命名結(jié)構(gòu)體數(shù)據(jù)類型，方便書寫
typedef struct SeqList {
SLDataType arr[MAX_SIZE];
int size;
}SL;
//-----------------------------------------------------------------------------
//以下是一些常見的接口的聲明
//順序表初始化
//利用結(jié)構(gòu)體類型創(chuàng)建一個(gè)靜態(tài)順序表變量后，可以對其進(jìn)行初始化
void SLInit(SL* psl);
//打印順序表
//把順序表的值按照先后順序打印出來
void SLPrint(SL* psl);
//檢查順序表是否已滿
//每次進(jìn)行加入數(shù)據(jù)的操作的時(shí)候需要先檢查是否已經(jīng)滿了，如果滿了就不能夠插入了
void SLCheck(SL* psl);
//順序表的尾插
//在順序表的尾部在插入一個(gè)元素
//由于是數(shù)組加入數(shù)據(jù)很方便，直接使用數(shù)組下標(biāo)就可以訪問到
void SLPushBack(SL* psl, SLDataType data);
//順序表的尾刪
//刪除順序表尾部的數(shù)據(jù)
void SLPopBack(SL* psl);
//順序表的頭插
//在順序表的開頭加入一個(gè)數(shù)據(jù)
void SLPushFront(SL* psl, SLDataType data);
//順序表的頭刪
//把順序表第一位數(shù)據(jù)刪除
void SLPopFront(SL* psl);
//順序表查找某個(gè)數(shù)據(jù)
//查找順序表中是否存在某個(gè)數(shù)據(jù)，如果有就返回對應(yīng)的下標(biāo)
//如果找不到就返回-1
int SLFind(SL* psl, SLDataType x);
//順序表在pos位置插入x
//在指定下標(biāo)位置插入數(shù)據(jù)x，原來x位置的數(shù)據(jù)以及后面的數(shù)據(jù)往后移動
void SLInsert(SL* psl, size_t pos, SLDataType x);
//順序表刪除在pos位置的數(shù)據(jù)
void SLErase(SL* psl, size_t pos);
//順序表某一位置數(shù)據(jù)的修改
void SLModify(SL* psl, size_t pos, SLDataType x);
以下是這些接口的具體實(shí)現(xiàn)
//順序表初始化
void SLInit(SL* psl) {
psl->arr[0] = 0;//此處只能初始化一個(gè)元素
psl->size = 0;
}
//打印順序表
void SLPrint(SL* psl) {
int i = 0;
if (psl->size) {
for (i = 0; i < psl->size; i++) {
//輸出格式，記得根據(jù)SLDataTyped的類型來修改
printf("%d ", psl->arr[i]);
}
printf("\n");
}
else {
printf("Null\n");
}
}
/*
//檢查順序表是否已滿
void SLCheck(SL* psl) {
if (psl->size == MAX_SIZE) {
printf("順序表已滿，無法進(jìn)行后續(xù)操作");
}
}
*/
//順序表的尾插
void SLPushBack(SL* psl, SLDataType data) {
//插入數(shù)據(jù)要先檢查空間是否已滿
//實(shí)現(xiàn)方法一不夠好
/*
if (psl->size == MAX_SIZE) {
printf("空間已滿\n");
return;
}
else {
psl->arr[psl->size] = data;
psl->size++;
}*/
//實(shí)現(xiàn)方法二，簡單明了
assert(psl->size != MAX_SIZE);
psl->arr[psl->size] = data;
psl->size++;
}
//順序表的尾刪
void SLPopBack(SL* psl) {
//判斷是否還有元素可以刪除
assert(psl->size);
psl->size--;
}
//順序表的頭插
void SLPushFront(SL* psl, SLDataType data) {
assert(psl->size != MAX_SIZE);
//src用來后移數(shù)據(jù)
int src = psl->size;
while (src >= 1) {
psl->arr[src] = psl->arr[src - 1];
src--;
}
psl->arr[src] = data;
psl->size++;
}
//順序表的頭刪
void SLPopFront(SL* psl) {
//判斷是否還有數(shù)據(jù)可以刪除
assert(psl->size);
int src = 0;
while (src < psl->size - 1) {
psl->arr[src] = psl->arr[src + 1];
src++;
}
psl->size--;
}
//順序表查找某個(gè)數(shù)據(jù)
int SLFind(SL* psl, SLDataType x) {
int i = 0;
for (i = 0; i < psl->size; i++) {
if (psl->arr[i] == x) {
//找到了就返回該數(shù)據(jù)在順序表中的位置
return i;
}
}
//找不到就返回-1
return -1;
}
//順序表在pos位置插入x
void SLInsert(SL* psl, size_t pos, SLDataType x) {
assert(psl->size < MAX_SIZE);
assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的時(shí)候，相當(dāng)于頭插，尾插
int end = psl->size;
while (end > pos) {
psl->arr[end] = psl->arr[end - 1];
end--;
}
psl->arr[pos] = x;
psl->size++;
}
//順序表刪除在pos位置的數(shù)據(jù)
void SLErase(SL* psl, size_t pos) {
assert(psl->size);
assert(pos >= 0 && pos < psl->size);
int start = pos + 1;
while (start < psl->size) {
psl->arr[start - 1] = psl->arr[start];
start++;
}
psl->size--;
}
//順序表某一位置數(shù)據(jù)的修改
void SLModify(SL* psl, size_t pos, SLDataType x) {
assert(psl->size);
assert(pos >= 0 && pos < psl->size);
psl->arr[pos] = x;
}
上面代碼的測試，我放在了Gitee上，需要的小伙伴可以參考一下
動態(tài)順序表
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費(fèi)，開少了不夠用。所以現(xiàn)實(shí)中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實(shí)現(xiàn)動態(tài)順序表。
//重命名SL的數(shù)據(jù)類型，方便后續(xù)修改
typedef int SLDataType;
//定義結(jié)構(gòu)體
//成員變量為指向動態(tài)順序表的指針，數(shù)據(jù)的個(gè)數(shù)，順序表的容量
//capacity用來管理數(shù)組的總大小，如果size與capacity相等了，就表示數(shù)組已經(jīng)滿了需要擴(kuò)容
//重定義結(jié)構(gòu)體類型名稱，方便操作
typedef struct SeqList {
SLDataType* p;
int size;
int capacity;
}SL;
//----------------------------------------------------------------------
//一下是一些常用的接口，與靜態(tài)順序表差不多
//SL初始化
void SLInit(SL* ps);
//SL空間檢查
//如若size與capacity相等表示數(shù)組已經(jīng)滿了，需要擴(kuò)容
void SLCheckCapacity(SL* ps);
//SL打印
void SLPrint(SL* ps);
//SL銷毀
//因?yàn)閿?shù)組是動態(tài)開辟的，所以在最后不使用的數(shù)組的時(shí)候要釋放空間
void SLDestory(SL* ps);
//SL尾插
void SLPushBack(SL* ps,SLDataType x);
//SL尾刪
void SLPopBack(SL* ps);
//SL頭插
void SLPushFront(SL* ps, SLDataType x);
//SL頭刪
void SLPopFront(SL* ps);
//SL查找某個(gè)數(shù)據(jù)
//如果能找到，返回該數(shù)據(jù)在順序表中下標(biāo)
int SLFind(SL* ps, SLDataType x);
//SL在pos位置插入x
void SLInsert(SL* ps, size_t pos, SLDataType x);
//SL刪除pos位置的值
void SLErase(SL* ps, size_t pos);
//SL修改某一位置的數(shù)據(jù)
void SLModity(SL* ps, size_t pos, SLDataType x);
以下是具體的實(shí)現(xiàn)
//動態(tài)順序表的實(shí)現(xiàn)
#include"DynamicSeqList.h"
//SL初始化
void SLInit(SL* ps) {
ps->p = NULL;
ps->capacity = 0;
ps->size = 0;
}
//SL空間檢查
void SLCheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType));
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
ps->p = tmp;
}
}
//SL打印
void SLPrint(SL* ps) {
if (ps->size == 0) {
printf("順序表為空\n");
}
else {
int i = 0;
for (i = 0; i < ps->size; i++) {
//打印格式記得根據(jù)SLDataType的類型來修改
printf("%d ", ps->p[i]);
}
printf("\n");
}
}
//SL銷毀
//這里并沒有完全銷毀結(jié)構(gòu)體s，只是把成員變量都賦值為0
void SLDestory(SL* ps) {
free(ps->p);
ps->p = NULL;
ps->size = ps->capacity = 0;
}
//SL尾插
void SLPushBack(SL* ps, SLDataType x) {
SLCheckCapacity(ps);
ps->p[ps->size] = x;
ps->size++;
}
//SL尾刪
void SLPopBack(SL* ps) {
//刪除數(shù)據(jù)需要判斷一下順序表是否為空
assert(ps->size > 0);
ps->size--;
}
//SL頭插
void SLPushFront(SL* ps, SLDataType x) {
SLCheckCapacity(ps);
int end = ps->size;
while (end > 0) {
ps->p[end] = ps->p[end - 1];
end--;
}
ps->p[end] = x;
ps->size++;
}
//SL頭刪
void SLPopFront(SL* ps) {
//刪除數(shù)據(jù)需要判斷一下順序表是否為空
assert(ps->size > 0);
int start = 0;
while (start < ps->size - 1) {
ps->p[start] = ps->p[start + 1];
start++;
}
ps->size--;
}
//SL查找某個(gè)數(shù)據(jù)
int SLFind(SL* ps, SLDataType x) {
//需要判斷順序表是否為空，可以用assert，也可以用if判斷
assert(ps->size);
int i = 0;
for (i = 0; i < ps->size; i++) {
if (x == ps->p[i]) {
return i;
}
}
return -1;
}
//SL在pos位置插入x
//當(dāng)pos為0或者pos為size時(shí)，相當(dāng)于頭插、尾插
void SLInsert(SL* ps, size_t pos, SLDataType x) {
SLCheckCapacity(ps);
assert(pos >= 0 && pos <= ps->size);
int end = ps->size;
while (end > pos) {
ps->p[end] = ps->p[end - 1];
end--;
}
ps->p[end] = x;
ps->size++;
}
//SL刪除pos位置的值
void SLErase(SL* ps, size_t pos) {
//判斷要刪除的位置是否在size之內(nèi)
assert(pos >= 0 && pos < ps->size);
int start = pos + 1;
while (start < ps->size) {
ps->p[start - 1] = ps->p[start];
start++;
}
ps->size--;
}
//SL修改某一位置的數(shù)據(jù)
void SLModity(SL* ps, size_t pos, SLDataType x) {
//判斷要修改的位置是否在size之內(nèi)
assert(pos >= 0 && pos < ps->size);
ps->p[pos] = x;
}
同樣的，我自己寫的一些小測試也在Gitee上，需要的小伙伴可以去看看
到此這篇關(guān)于C語言 數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組模擬實(shí)現(xiàn)順序表流程詳解的文章就介紹到這了,更多相關(guān)數(shù)組模擬實(shí)現(xiàn)順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
ENVI使用的是通用柵格數(shù)據(jù)格式,包含一個(gè)簡單的二進(jìn)制文件（ a simple flat binary ）和一個(gè)相關(guān)的ASCII（文本）的頭文件,下面我們就來看看如何使用C++讀取ENVI柵格文件格式吧2024-10-10
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)掃雷項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要為大家詳細(xì)介紹了C++單例模式的幾種實(shí)現(xiàn)方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
C++類和對象深入探索之分文件編寫點(diǎn)和圓的關(guān)系詳解
先前把C++類和對象的封裝講完了，并且留下了一個(gè)判斷兩個(gè)立方體是否相等的案例，但是那么多知識點(diǎn)，僅僅一個(gè)案例是不夠的，所以再來一個(gè)分文件編寫點(diǎn)圓關(guān)系的案例；創(chuàng)建圓類和點(diǎn)類，圓類包含點(diǎn)類，算是一個(gè)嵌套吧，順便復(fù)習(xí)一下分文件編寫的方法，開整2022-05-05
C++實(shí)現(xiàn)LeetCode(110.平衡二叉樹)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(110.平衡二叉樹),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
本篇我將帶領(lǐng)大家攻克掃雷游戲各處難點(diǎn)，讓你寫掃雷不在困難，我們的掃雷游戲可以實(shí)現(xiàn)標(biāo)記雷的功能和展開一片的功能。我們將分三個(gè)文件為大家介紹，分別為test.c,game.h和game.c2022-05-05
這篇文章主要介紹了C/C++中虛函數(shù)詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
本文給大家?guī)砹薈++實(shí)現(xiàn)順序表的方法，代碼簡單易懂，附有注釋，感興趣的朋友一起看下吧2016-08-08
這篇文章主要為大家詳細(xì)介紹了C語言中常見的文件操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要介紹了VScode如何調(diào)用KEIL-MDK問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02