前言
數(shù)據(jù)結(jié)構(gòu)入門 — 順序表詳解
博客主頁鏈接：https://blog.csdn.net/m0_74014525
關注博主，后期持續(xù)更新系列文章
文章末尾有源碼*****感謝觀看，希望對你有所幫助*****
一、順序表
1. 順序表是什么
順序表是連續(xù)存儲的
順序表是一種線性表的數(shù)據(jù)結(jié)構(gòu)，它的數(shù)據(jù)元素按照一定次序依次存儲在計算機存儲器中，使用連續(xù)的存儲空間來存儲。順序表中每個數(shù)據(jù)元素的位置都有一個序號，這個序號也稱為元素在順序表中的下標。順序表的特點是：元素的邏輯順序與物理順序相同，支持隨機訪問，插入和刪除元素的時間復雜度為O(n)，查找元素的時間復雜度為O(1)。
2. 優(yōu)缺點
優(yōu)點
優(yōu)點是訪問速度快，因為它的元素在內(nèi)存中是連續(xù)存儲的，可以直接通過下標訪問，而且不需要額外的空間來存儲指向下一個節(jié)點的指針。缺點
缺點是插入和刪除元素的時間復雜度為O(n)，因為需要移動其他元素的位置，而且不利于動態(tài)擴展容量。
二、概念及結(jié)構(gòu)
元素的類型、元素的個數(shù)、數(shù)組的大小和數(shù)組的指針
順序表的實現(xiàn)需要預留一段連續(xù)的存儲空間來存儲所有的元素，目前常見的實現(xiàn)方式是使用數(shù)組來實現(xiàn)順序表。數(shù)組的地址是連續(xù)的，因此可以通過數(shù)組下標進行快速訪問元素。為了實現(xiàn)順序表，需要定義一個數(shù)據(jù)結(jié)構(gòu)，包含元素的類型、元素的個數(shù)、數(shù)組的大小和數(shù)組的指針等信息。
1. 靜態(tài)順序表
靜態(tài)順序表是一種使用連續(xù)存儲空間實現(xiàn)的線性表結(jié)構(gòu)，其特點是在創(chuàng)建表時就需要預先分配好固定長度的存儲空間，表長也就固定了下來，不能動態(tài)擴展或縮小。
在靜態(tài)順序表中，數(shù)據(jù)元素按照順序依次存放，每個元素都占用相同的存儲空間，而且元素在內(nèi)存中的地址也是連續(xù)的。
2. 動態(tài)順序表
動態(tài)順序表是一種線性表的實現(xiàn)方式，它在靜態(tài)順序表的基礎上，將存儲空間由固定長度改為動態(tài)分配。
當動態(tài)順序表中存放的元素個數(shù)達到當前存儲空間的上限時，可以重新申請更大的空間來存放更多的元素，因此動態(tài)順序表的長度是可變的。動態(tài)順序表的實現(xiàn)通常采用數(shù)組形式，通過realloc函數(shù)來動態(tài)分配空間。
三、順序表接口實現(xiàn)（代碼演示）
1. 動態(tài)存儲結(jié)構(gòu)
即定義順序表的結(jié)構(gòu)。由動態(tài)開辟的數(shù)組、有效數(shù)據(jù)個數(shù)和容量空間的大小組成
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a; // 指向動態(tài)開辟的數(shù)組
int size; // 有效數(shù)據(jù)個數(shù)
int capacity; // 容量空間的大小
}SL;
2. 順序表打印
使用循環(huán)，將順序表遍歷一遍，進行打印
//打印順序表
void SLPrint(SL* pc)
{
assert(pc);
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("%d ", pc->a[i]);
}
printf("\n");
}
3. 順序表初始化
在順便表初始化時，先用malloc開辟4個空間，如果開啟失敗報錯并返回
//初始化順序表
void SLInit(SL *pc)
{
assert(pc);
//開啟內(nèi)存
pc->a=(SLDataType*)malloc(sizeof(SLDataType) * 4);
//檢查是否開辟成功
if (pc->a==NULL)
{
perror("SLInit");
//return;
exit(-1);
}
pc->capacity = 4;
pc->size = 0;
}
4. 檢查空間大小
檢查空間，當順序表內(nèi)的數(shù)據(jù)等于初始化開辟的空間時，再開辟4個空間（用realloc開辟乘2的空間）
//檢查內(nèi)存容量
void SLCheckCapacity(SL* pc)
{
assert(pc);
if (pc->size == pc->capacity)
{
SLDataType*tem = (SLDataType*)realloc(pc->a, sizeof(SLDataType)*2*pc->capacity); //要乘以2
if (tem == NULL)
{
perror("SLCheckCapacity");
exit(-1);
}
pc->a = tem;
pc->capacity *= 2;
}
}
5. 增刪查改接口
以增刪查改順序依次編排
頭插：
頭插，即在順序表頭部進行插入數(shù)值，在SLCheckCapacity檢查空間是否充足后，進行插入數(shù)值
//頭插
void SLPushFront(SL* pc,SLDataType x)
{
assert(pc);
SLCheckCapacity(pc);
int end = pc->size - 1;
while (end >=0)
{
pc->a[end + 1] = pc->a[end];
--end;
}
pc->a[0] = x;
pc->size++;
}
尾插：
尾插，即找到順序表的尾，下標為pc->size的位置插入數(shù)值
//尾插
void SLPushBack(SL* pc, SLDataType x)
{
assert(pc);
SLCheckCapacity(pc);
pc->a[pc->size] = x;
pc->size++;
}
頭刪：
頭刪，將后面的數(shù)值依次向前覆蓋。覆蓋時要注意順序，將在前的先覆蓋，防止數(shù)組丟失，然后將順序表的size(數(shù)據(jù)個數(shù)減一）
//頭刪
void SLPopFront(SL* pc)
{
assert(pc);
int start = 1;
while (start < pc->size)
{
pc->a[start] = pc->a[start + 1];
++start;
}
pc->size--;
}
尾刪：
尾刪，即將有效數(shù)據(jù)減一，直接將pc所指向的size減一
//尾刪
void SLPopBack(SL* pc)
{
assert(pc->size > 0);
pc->size--;
}
查找：
查找方法有很多種，這里使用暴力查找，將順序表遍歷一遍，找到要找的元素并返回下標
//查找數(shù)字位置
int SLFind(SL* pc, SLDataType x)
{
int i = 0;
for (i = 0; i < pc->size; i++)
{
if (pc->a[i] == x)
{
return i;
}
}
return -1;
}
指定位置插入
這里配合查找函數(shù)使用，找到要找的數(shù)值的下標，進入下列函數(shù)，將pos之后的值依次下向后移動，在pos位置插入數(shù)值
// 在pos位置插入x
void SLInsert(SL* pc, int pos, SLDataType x)
{
assert(pc);
assert(pos >= 0 && pos <= pc->size);
SLCheckCapacity(pc);
int end = pc->size - 1;
while (end >= pos)
{
pc->a[end + 1] = pc->a[end];
--end;
}
pc->a[pos] = x;
pc->size++;
}
指定位置刪除
這里配合查找函數(shù)使用，找到要找的數(shù)值的下標，進入下列函數(shù)，將pos位置后的數(shù)值依次向前覆蓋
// 刪除pos位置的值
void SLErase(SL* pc, int pos)
{
assert(pc);
assert(pos >= 0 && pos < pc->size);
int start = pos+ 1;
while (start < pc->size)
{
pc->a[start - 1] = pc->a[start];
++start;
}
pc->size--;
}
更改指定位置
這里配合查找函數(shù)使用，找到要找的數(shù)值的下標，進入下列函數(shù)，將pos位置的值進行修改
//更改制定位置的數(shù)字
void SLModify(SL* pc, int pos, SLDataType x)
{
assert(pc);
assert(pos >= 0 && pos < pc->size);
pc->a[pos] = x;
}
6. 順序表銷毀
順序表進行銷毀，將開辟的數(shù)值空間進行釋放，并置為空（NULL）將空間和數(shù)據(jù)個數(shù)置為0 ，這樣順序表就銷毀完成
//銷毀釋放內(nèi)存
void SLDestroy(SL* pc)
{
assert(pc);
free(pc->a);
pc->a=NULL;
pc->capacity = 0;
pc->size=0;
}
四、所有文件代碼
1. Gitee鏈接
***查看所有代碼***
點擊右邊藍色文字 DuckBro Gitee 代碼倉庫
總結(jié)
順序表是一種線性表，它的重點是：
-
物理結(jié)構(gòu)：順序表的數(shù)據(jù)元素在內(nèi)存中是連續(xù)存放的，即使用一段連續(xù)的存儲空間來存儲線性表的元素。
-
邏輯結(jié)構(gòu)：順序表是一種線性表，它的元素在邏輯上是依次排列的。
-
數(shù)據(jù)操作：順序表支持基本的數(shù)據(jù)操作，包括插入、刪除、查找等操作。其中，插入和刪除操作需要移動大量元素，時間復雜度較高，而查找操作可以通過使用二分查找等算法來提高效率。
-
容量管理：順序表的容量是由數(shù)組的長度來決定的。如果數(shù)組長度不夠，順序表需要進行擴容操作，如果數(shù)組長度過長，會浪費內(nèi)存空間。
-
性能特點：由于順序表的數(shù)據(jù)元素在內(nèi)存中是連續(xù)存放的，所以順序表具有快速的隨機訪問能力，但插入、刪除操作較為耗時。因此，適合于需要隨機訪問元素，但不頻繁進行插入、刪除操作的場景。順序表文章來源：http://www.zghlxwxcb.cn/news/detail-668085.html
如這篇博客對大家有幫助的話，希望 三連 支持一下 ?。?！ 如果有錯誤感謝大佬的斧正 如有 其他見解發(fā)到評論區(qū)，一起學習 一起進步。文章來源地址http://www.zghlxwxcb.cn/news/detail-668085.html
到了這里，關于數(shù)據(jù)結(jié)構(gòu)入門 — 順序表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
