🎯引言

歡迎來(lái)到HanLop博客的C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)初階系列。在這個(gè)系列中，我們將深入探討各種基本的數(shù)據(jù)結(jié)構(gòu)和算法，幫助您打下堅(jiān)實(shí)的編程基礎(chǔ)。本次我將為你講解。順序表（也稱(chēng)為數(shù)組）是一種線性表，因其簡(jiǎn)單易用而廣泛應(yīng)用于各類(lèi)編程任務(wù)中。在本篇文章中，我們將介紹順序表的基本概念、順序表的創(chuàng)建和操作方法，以及其優(yōu)缺點(diǎn)。通過(guò)一些實(shí)際的代碼示例，您將更好地掌握順序表在C語(yǔ)言中的應(yīng)用，從而為后續(xù)學(xué)習(xí)其他數(shù)據(jù)結(jié)構(gòu)打下堅(jiān)實(shí)的基礎(chǔ)。

👓順序表

1.線性表

線性表的概念

線性表是數(shù)據(jù)結(jié)構(gòu)中最基本、最常用的一種結(jié)構(gòu)，由n個(gè)數(shù)據(jù)元素組成一個(gè)有限序列。線性表中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系，即每個(gè)元素都有唯一的前驅(qū)和后繼（除了第一個(gè)和最后一個(gè)元素）。常見(jiàn)的線性表有:順序表、鏈表、棧、隊(duì)列…

線性表的基本特點(diǎn):

1. 線性關(guān)系：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼（第一個(gè)元素除外沒(méi)有前驅(qū)，最后一個(gè)元素除外沒(méi)有后繼）。

2. 唯一性：每個(gè)元素在表中的位置是唯一的。

3. 相同類(lèi)型：線性表中的所有元素都是相同的數(shù)據(jù)類(lèi)型。

邏輯結(jié)構(gòu)

線性表的邏輯結(jié)構(gòu)是指線性表中元素之間的關(guān)系。線性表中的元素具有一對(duì)一的線性關(guān)系，即每個(gè)元素都有唯一的前驅(qū)和后繼（第一個(gè)元素除外沒(méi)有前驅(qū)，最后一個(gè)元素除外沒(méi)有后繼）。這種邏輯結(jié)構(gòu)決定了線性表的基本操作和特點(diǎn)。

物理結(jié)構(gòu)

線性表的物理結(jié)構(gòu)是指線性表在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式。主要有兩種存儲(chǔ)方式：

1. 順序存儲(chǔ)結(jié)構(gòu)（順序表，數(shù)組）：
   • 元素依次存儲(chǔ)在一段連續(xù)的內(nèi)存空間中。
   • 優(yōu)點(diǎn)：可以通過(guò)索引快速訪問(wèn)元素，查找效率高。
   • 缺點(diǎn)：插入和刪除操作效率較低，因?yàn)樾枰苿?dòng)大量元素。
2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）：
   • 元素存儲(chǔ)在任意的內(nèi)存位置，元素之間通過(guò)指針連接。
   • 優(yōu)點(diǎn)：插入和刪除操作效率較高，不需要移動(dòng)元素，只需改變指針。
   • 缺點(diǎn)：查找效率較低，因?yàn)樾枰獜念^遍歷到所需位置。

2.順序表

2.1概念

• 定義：順序表是由一組連續(xù)的存儲(chǔ)單元組成的線性表，元素之間的邏輯順序與物理存儲(chǔ)位置相對(duì)應(yīng)。
• 特點(diǎn)：
  • 元素類(lèi)型相同，存儲(chǔ)在一塊連續(xù)的內(nèi)存空間中。
  • 支持通過(guò)索引快速訪問(wèn)元素。
  • 插入和刪除操作需要移動(dòng)大量元素，效率較低。
• 適用場(chǎng)景：適合于元素?cái)?shù)量固定且需要頻繁進(jìn)行查找操作的場(chǎng)景。

2.2結(jié)構(gòu)

順序表的物理結(jié)構(gòu)如下：

存儲(chǔ)結(jié)構(gòu)：使用一段連續(xù)的內(nèi)存空間存儲(chǔ)元素，可以通過(guò)下標(biāo)來(lái)訪問(wèn)各個(gè)元素。(底層本質(zhì)上數(shù)組,對(duì)數(shù)組進(jìn)行封裝后成了順序表)

基本操作：

1. 插入操作：

   • 定義：在順序表的指定位置插入一個(gè)新的元素。

   • 步驟：如果插入位置不在表尾，需要將插入位置后的元素依次后移一位，然后將新元素插入到指定位置。

   • 時(shí)間復(fù)雜度：最壞情況下是O(n)，因?yàn)榭赡苄枰苿?dòng)表尾的所有元素。

2. 刪除操作：

   • 定義：刪除順序表中指定位置的元素。

   • 步驟：將刪除位置后的元素依次前移一位，覆蓋被刪除的元素位置。

   • 時(shí)間復(fù)雜度：最壞情況下是O(n)，因?yàn)榭赡苄枰苿?dòng)表尾的所有元素。

3. 修改操作：

   • 定義：修改順序表中指定位置的元素值。

   • 步驟：直接通過(guò)索引定位到指定位置，修改元素的值。

   • 時(shí)間復(fù)雜度：O(1)，因?yàn)樾薷牟僮魇侵苯佣ㄎ坏轿恢眠M(jìn)行修改。

4. 查找操作：

   • 定義：查找順序表中指定元素或元素位置。

   • 步驟：通過(guò)順序表的索引直接訪問(wèn)指定位置的元素，或者遍歷整個(gè)表查找特定元素。

   • 時(shí)間復(fù)雜度：最壞情況下是O(n)，因?yàn)榭赡苄枰闅v整個(gè)表來(lái)查找元素。

2.3分類(lèi)

2.3.1靜態(tài)順序表：

• 定義：靜態(tài)順序表是在程序運(yùn)行前就確定了大小，內(nèi)存空間是靜態(tài)分配的，不可動(dòng)態(tài)改變大小。
• 特點(diǎn)：數(shù)組長(zhǎng)度在創(chuàng)建時(shí)固定，不能動(dòng)態(tài)增加或減少。
• 優(yōu)點(diǎn)：訪問(wèn)速度快，不需要額外的空間管理。
• 缺點(diǎn)：浪費(fèi)內(nèi)存空間，不能適應(yīng)動(dòng)態(tài)變化的數(shù)據(jù)需求。

//靜態(tài)順序表
typedef int SLDateType;
#define N 10
typedef struct SeqList
{SLDateType a[N];int size;
}SeqList;

2.3.2動(dòng)態(tài)順序表：

• 定義：動(dòng)態(tài)順序表是在程序運(yùn)行時(shí)根據(jù)需要?jiǎng)討B(tài)分配內(nèi)存空間的順序表。
• 特點(diǎn)：可以動(dòng)態(tài)地增加或減少數(shù)組的長(zhǎng)度。
• 優(yōu)點(diǎn)：節(jié)約內(nèi)存空間，適應(yīng)動(dòng)態(tài)變化的數(shù)據(jù)需求。
• 缺點(diǎn)：可能導(dǎo)致頻繁的內(nèi)存分配和拷貝，影響性能。

typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;

2.4動(dòng)態(tài)順序表的實(shí)現(xiàn)

2.4.1SeqList.h文件

//SeqList.h文件的代碼
#include <stdio.h>//標(biāo)準(zhǔn)輸入輸出庫(kù)，提供了標(biāo)準(zhǔn)的輸入輸出函數(shù)。
#include <stdlib.h>//標(biāo)準(zhǔn)庫(kù)，提供了動(dòng)態(tài)內(nèi)存分配、隨機(jī)數(shù)生成、程序控制等函數(shù)。
#include <assert.h>//斷言庫(kù)，用于在程序中插入檢查點(diǎn)，確保某個(gè)條件為真，如果條件為假則終止程序執(zhí)行。//動(dòng)態(tài)順序表
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;//順序表初始化
void SeqListInit(SeqList* p);
//順表打印
void SeqListPrint(SeqList* p);
//順序表的銷(xiāo)毀
void SeqListDestory(SeqList* p);//順序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
//順序表增容
void CheckCapacity(SeqList* p);
//順序表頭插
void SeqListPushFront(SeqList* p, SLDateType x);
//順序表尾刪
void SeqListPopBack(SeqList* p);//在pos位置插入數(shù)字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
//刪除pos位置的數(shù)字
void SeqListErase(SeqList* p,int pos);
//找到指定的數(shù)字位置,返回下標(biāo)
int SeqListFind(SeqList* p, SLDateType x);

代碼解析:

動(dòng)態(tài)順序表結(jié)構(gòu)體定義

typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;  // 指向動(dòng)態(tài)數(shù)組的指針int size;       // 當(dāng)前動(dòng)態(tài)順序表中元素的個(gè)數(shù)int capacity;   // 當(dāng)前動(dòng)態(tài)順序表的容量
} SeqList;

• SLDateType：定義動(dòng)態(tài)順序表中存儲(chǔ)的元素類(lèi)型為 int。
• struct SeqList：定義了動(dòng)態(tài)順序表的結(jié)構(gòu)體，包含：
  • SLDateType* a：指向動(dòng)態(tài)數(shù)組的指針，用于存儲(chǔ)順序表中的元素。
  • int size：當(dāng)前動(dòng)態(tài)順序表中元素的個(gè)數(shù)。
  • int capacity：當(dāng)前動(dòng)態(tài)順序表的容量，即可以存儲(chǔ)的最大元素個(gè)數(shù)。

函數(shù)聲明

// 順序表初始化
void SeqListInit(SeqList* p);
// 順序表打印
void SeqListPrint(SeqList* p);
// 順序表的銷(xiāo)毀
void SeqListDestory(SeqList* p);// 順序表尾插
void SeqListPushBack(SeqList* p, SLDateType x);
// 順序表增容
void CheckCapacity(SeqList* p);
// 順序表頭插
void SeqListPushFront(SeqList* p, SLDateType x);
// 順序表尾刪
void SeqListPopBack(SeqList* p);// 在pos位置插入數(shù)字
void SeqListInsert(SeqList* p, int pos, SLDateType X);
// 刪除pos位置的數(shù)字
void SeqListErase(SeqList* p, int pos);
// 找到指定的數(shù)字位置,返回下標(biāo)
int SeqListFind(SeqList* p, SLDateType x);

這些函數(shù)聲明定義了動(dòng)態(tài)順序表的基本操作：

• SeqListInit：初始化動(dòng)態(tài)順序表。
• SeqListPrint：打印動(dòng)態(tài)順序表中的元素。
• SeqListDestory：銷(xiāo)毀動(dòng)態(tài)順序表，釋放內(nèi)存。
• SeqListPushBack：尾部插入元素。
• CheckCapacity：檢查并增加動(dòng)態(tài)順序表的容量。
• SeqListPushFront：頭部插入元素。
• SeqListPopBack：尾部刪除元素。
• SeqListInsert：在指定位置插入元素。
• SeqListErase：刪除指定位置的元素。
• SeqListFind：查找指定元素并返回其位置。

這些函數(shù)聲明提供了對(duì)動(dòng)態(tài)順序表進(jìn)行初始化、增刪改查等基本操作的接口，具體的實(shí)現(xiàn)應(yīng)該在對(duì)應(yīng)的 SeqList.c 文件中完成。

2.4.2SeqList.c文件

//SeqList.c文件
//這里引入了頭文件 SeqList.h，其中定義了動(dòng)態(tài)順序表的結(jié)構(gòu)體 SeqList 和函數(shù)聲明。
#include "SeqList.h"
//順序表的初始化
void SeqListInit(SeqList* p)
{assert(p);p->a = NULL;p->size = p->capacity = 0;
}//順序表的銷(xiāo)毀
void SeqListDestory(SeqList* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}//順序表打印
void SeqListPrint(SeqList* p)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){printf("%d ", p->a[i]);}printf("\n");
}//檢查并增加動(dòng)態(tài)順序表的容量。
void CheckCapacity(SeqList* p)
{assert(p);int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;if (p->capacity == p->size){p->capacity = newcapacity;SLDateType* tmp = (SLDateType*)realloc(p->a, p->capacity * sizeof(SLDateType));if (tmp != NULL){p->a = tmp;}else{exit(1);}}
}//順序表尾插
void SeqListPushBack(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);p->a[p->size] = x;p->size++;
}//順序表頭插
void SeqListPushFront(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);int i = 0;for (i = p->size; i > 0; i--){p->a[i] = p->a[i-1];}p->a[0] = x;p->size++;
}//順序表尾刪
void SeqListPopBack(SeqList* p)
{assert(p);assert(p->size);p->size--;}//順序表頭刪
void SeqListPopFront(SeqList* p)
{assert(p);assert(p->size);int i = 0;for (i = 0; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}//在pos位置插入數(shù)字
void SeqListInsert(SeqList* p, int pos, SLDateType x)
{assert(p != NULL);assert(pos >= 0 && pos <= p->size);//檢查是否需要增容CheckCapacity(p);for (int i = p->size-1; i > pos-1 ; --i){p->a[i + 1] = p->a[i];//p->a[pos+1]=p->a[pos]}p->a[pos] = x;p->size++;
}//刪除pos位置的數(shù)字
void SeqListErase(SeqList* p, int pos)
{assert(p != NULL);assert(pos >= 0 && pos < p->size);for (int i = pos; i < p->size-1; i++){p->a[i] = p->a[i + 1];//p->a[size-2]=p->a[size-1]}p->size--;
}//找到指定的數(shù)字位置,返回下標(biāo)
int SeqListFind(SeqList* p, SLDateType x)
{assert(p != NULL);for (size_t i = 0; i < p->size; i++){if (p->a[i] == x){return i;}}return -1;
}

代碼解析:

初始化函數(shù) SeqListInit

void SeqListInit(SeqList* p)
{assert(p);p->a = NULL;p->size = p->capacity = 0;
}

• 功能：初始化動(dòng)態(tài)順序表。
• 說(shuō)明：將動(dòng)態(tài)順序表指針 p 所指向的順序表 a 設(shè)置為 NULL，并將 size（元素個(gè)數(shù)）和 capacity（容量）都設(shè)置為 0。使用斷言 assert(p) 確保傳入的指針 p 不為空。

銷(xiāo)毀函數(shù) SeqListDestory

void SeqListDestory(SeqList* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}

• 功能：銷(xiāo)毀動(dòng)態(tài)順序表。
• 說(shuō)明：釋放動(dòng)態(tài)順序表 a 所指向的內(nèi)存空間，將 a 置為 NULL，并將 size 和 capacity 置為 0。同樣使用斷言 assert(p) 確保傳入的指針 p 不為空。

打印函數(shù) SeqListPrint

void SeqListPrint(SeqList* p)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){printf("%d ", p->a[i]);}printf("\n");
}

• 功能：打印動(dòng)態(tài)順序表中的元素。
• 說(shuō)明：遍歷順序表 a 中的每個(gè)元素，依次打印出來(lái)。使用斷言 assert(p) 確保傳入的指針 p 不為空。

增容函數(shù) CheckCapacity

void CheckCapacity(SeqList* p)
{assert(p);int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;if (p->capacity == p->size){p->capacity = newcapacity;SLDateType* tmp = (SLDateType*)realloc(p->a, p->capacity * sizeof(SLDateType));if (tmp != NULL){p->a = tmp;}else{exit(1);}}
}

• 功能：檢查并增加動(dòng)態(tài)順序表的容量。
• 說(shuō)明：
  • 如果當(dāng)前順序表 a 的容量 capacity 等于當(dāng)前元素個(gè)數(shù) size，則表示需要增加容量。
  • 計(jì)算新的容量 newcapacity，如果當(dāng)前容量為 0，則設(shè)置為 4，否則擴(kuò)大為原來(lái)的兩倍。
  • 使用 realloc 函數(shù)重新分配 a 的內(nèi)存空間，將新的容量分配給 a。如果分配失敗，程序退出。
  • 使用斷言 assert(p) 確保傳入的指針 p 不為空。

尾部插入函數(shù) SeqListPushBack

void SeqListPushBack(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);p->a[p->size] = x;p->size++;
}

• 功能：在動(dòng)態(tài)順序表尾部插入元素 x。
• 說(shuō)明：首先調(diào)用 CheckCapacity 函數(shù)檢查并增加容量。然后將元素 x 插入到順序表 a 的末尾，并更新 size。

頭部插入函數(shù) SeqListPushFront

void SeqListPushFront(SeqList* p, SLDateType x)
{assert(p);CheckCapacity(p);int i = 0;//元素從后往前依次往后移動(dòng)一位 注:不能從前往后 因?yàn)榍懊娴脑赝笠苿?dòng)會(huì)覆蓋掉后面的元素for (i = p->size; i > 0; i--){p->a[i] = p->a[i-1];}p->a[0] = x;p->size++;
}

• 功能：在動(dòng)態(tài)順序表頭部插入元素 x。
• 說(shuō)明：首先調(diào)用 CheckCapacity 函數(shù)檢查并增加容量。然后將順序表 a 中的所有元素后移一位，為新元素騰出空間，最后將 x 插入到順序表 a 的第一個(gè)位置，并更新 size。

尾部刪除函數(shù) SeqListPopBack

void SeqListPopBack(SeqList* p)
{assert(p);assert(p->size > 0);p->size--;
}

• 功能：從動(dòng)態(tài)順序表尾部刪除元素。
• 說(shuō)明：首先使用斷言 assert(p) 確保順序表不為空，然后將 size 減一，表示刪除尾部的元素。

頭部刪除函數(shù) SeqListPopFront

void SeqListPopFront(SeqList* p)
{assert(p);assert(p->size > 0);int i = 0;//元素從前往后依次向前移動(dòng)一位 for (i = 0; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}

• 功能：從動(dòng)態(tài)順序表頭部刪除元素。
• 說(shuō)明：首先使用斷言 assert(p) 確保順序表不為空，然后將順序表 a 中的所有元素前移一位，覆蓋掉第一個(gè)元素，最后將 size 減一，表示刪除頭部的元素。

插入函數(shù) SeqListInsert

void SeqListInsert(SeqList* p, int pos, SLDateType x)
{assert(p != NULL);assert(pos >= 0 && pos <= p->size);CheckCapacity(p);//元素從后往前依次向后移動(dòng)一位 for (int i = p->size-1; i >= pos; --i){p->a[i + 1] = p->a[i];}p->a[pos] = x;p->size++;
}

• 功能：在指定位置 pos 插入元素 x。
• 說(shuō)明：
  • 首先使用斷言確保順序表和位置參數(shù)有效。
  • 調(diào)用 CheckCapacity 函數(shù)檢查并增加容量。
  • 將插入位置 pos 后的所有元素依次后移一位，為新元素 x 騰出空間。
  • 將元素 x 插入到指定位置 pos，并更新 size。

刪除函數(shù) SeqListErase

void SeqListErase(SeqList* p, int pos)
{assert(p != NULL);assert(pos >= 0 && pos < p->size);//元素從前往后依次向前移動(dòng)一位 for (int i = pos; i < p->size-1; i++){p->a[i] = p->a[i + 1];}p->size--;
}

• 功能：刪除指定位置 pos 的元素。
• 說(shuō)明：
  • 首先使用斷言確保順序表和位置參數(shù)有效。
  • 將指定位置 pos 后的所有元素依次前移一位，覆蓋掉要?jiǎng)h除的元素。
  • 最后將 size 減一，表示刪除了一個(gè)元素。

查找函數(shù) SeqListFind

int SeqListFind(SeqList* p, SLDateType x)
{assert(p != NULL);for (size_t i = 0; i < p->size; i++){if (p->a[i] == x){return i;}}return -1;
}

• 功能：查找順序表中值為 x 的元素，返回其位置索引。
• 說(shuō)明：
  • 使用斷言確保順序表有效。
  • 遍歷順序表 a 中的所有元素，找到第一個(gè)值等于 x 的元素，返回其位置索引。
  • 如果未找到，返回 -1 表示未找到。

🥇結(jié)語(yǔ)

通過(guò)本篇文章，我們?cè)敿?xì)介紹了順序表這一重要的數(shù)據(jù)結(jié)構(gòu)及其在C語(yǔ)言中的實(shí)現(xiàn)與應(yīng)用。我們探討了順序表的基本概念、操作方法以及優(yōu)缺點(diǎn)，并通過(guò)實(shí)例代碼展示了如何在實(shí)際編程中使用順序表。掌握順序表不僅有助于理解其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，還能提高代碼編寫(xiě)和優(yōu)化能力。希望本文能為您的編程之旅提供有益的指導(dǎo)。請(qǐng)繼續(xù)關(guān)注HanLop博客，下一篇文章我們將探討另一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)——鏈表，敬請(qǐng)期待！