一、線性表的定義
線性表是 n (n >= 0) 個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表:順序表、鏈表、棧、隊列…
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
數(shù)組形式
鏈表形式
二、順序表
1. 順序表的定義
順序表是一種線性數(shù)據(jù)結(jié)構(gòu)，通過連續(xù)的內(nèi)存空間存儲元素，可以隨機訪問任何位置的元素。它支持在常量時間內(nèi)進行插入、刪除和訪問操作，但在插入或刪除元素時可能需要移動后續(xù)元素，導(dǎo)致時間復(fù)雜度為O(n)。
2. 順序表的結(jié)構(gòu)
2.1 靜態(tài)順序表
靜態(tài)順序表使用定長數(shù)組，當(dāng)數(shù)組存儲滿后則不能再進行存儲。
2.2 動態(tài)順序表
動態(tài)順序表使用動態(tài)申請的數(shù)組進行存儲，當(dāng)順序表被存滿后，會自動擴大容量。
3. 動態(tài)順序表的接口實現(xiàn)
3.1 順序表的接口
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
int size;
int capacity;
}SeqList;
// 對數(shù)據(jù)的管理:增刪查改
//順序表的初始化
void SeqListInit(SeqList* ps);
//順序表的銷毀
void SeqListDestroy(SeqList* ps);
//順序表的打印
void SeqListPrint(SeqList* ps);
//順序表的尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
//順序表的頭插
void SeqListPushFront(SeqList* ps, SLDateType x);
//順序表的的頭刪
void SeqListPopFront(SeqList* ps);
//順序表的尾刪
void SeqListPopBack(SeqList* ps);
// 順序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 順序表刪除pos位置的值
void SeqListErase(SeqList* ps, int pos);
3.2 接口的實現(xiàn)
void SeqListInit(SeqList* ps)
{
//動態(tài)申請十個 SLDateType 類型大小的空間
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 10);
//判斷是否開辟成功
if (ps->a == NULL)
{
perror("malloc");
return;
}
ps->size = 0; //順序表初始化，順序表內(nèi)無數(shù)據(jù)，則賦值為 0
ps->capacity = 10; //容量為動態(tài)申請的元素個數(shù)
}
void SeqListDestroy(SeqList* ps)
{
//將動態(tài)申請的空間釋放
free(ps->a);
ps->a = NULL;
}
int CheckSeqList(SeqList* ps)
{
//檢查順序表是否被填滿
if (ps->capacity == ps->size)
{
//若填滿則將動態(tài)申請的內(nèi)存擴大為原來的兩倍
SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (ps->capacity * 2));
//定義一個變量接收擴大后返回空間的首地址
//目的：若開辟失敗也不會改變原來的內(nèi)存
if (tmp == NULL)
{
perror("realloc");
return 0;
}
ps->a = tmp;
//將容量變成原來的兩倍
ps->capacity *= 2;
}
return 1;
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
//判斷順序表是否為滿，未滿則進行下面的步驟
//若滿了，則先擴容，再進行下面的步驟
if (CheckSeqList(ps) == 0)
{
return;
}
//將需要尾插的數(shù)據(jù)放在下標(biāo)為size的數(shù)組中
ps->a[ps->size] = x;
//存儲的元素加一
ps->size++;
}
void SeqListPrint(SeqList* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
//判斷順序表是否為滿，未滿則進行下面的步驟
//若滿了，則先擴容，再進行下面的步驟
if (CheckSeqList(ps) == 0)
{
return;
}
//下面省略的代碼是沒有用隨機插入函數(shù)實現(xiàn)的
/*int i = 0;
for (i = ps->size - 1; i >= 0; i--)
{
//將所有的元素向后移動一位
ps->a[i + 1] = ps->a[i];
}
ps->a[0] = x; //將需要插入的元素放在首元素的位置
ps->size++;*/ //存儲元素個數(shù)加一
//下面省略的代碼是沒有用隨機插入函數(shù)實現(xiàn)的，并使用memmove函數(shù)移動數(shù)組
/*memmove(ps->a + 1, ps->a, sizeof(SLDateType) * ps->size);
ps->a[0] = x;
ps->size++;*/
//該代碼是使用隨機插入函數(shù)實現(xiàn)的
SeqListInsert(ps, 0, x);
}
void SeqListPopFront(SeqList* ps)
{
//下面省略的代碼是沒有用隨機刪除函數(shù)實現(xiàn)的
//斷言：順序表為空不能刪除
//assert(ps->size != 0);
/*int i = 0;
//將首元素后面的元素全部向前移動一位
for (i = 0; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;*/ //存儲元素個數(shù)減一
//下面省略的代碼是沒有用隨機刪除函數(shù)實現(xiàn)的，并使用memmove函數(shù)移動數(shù)組
/*memmove(ps->a, ps->a + 1, sizeof(SLDateType) * (ps->size - 1));
ps->size--;*/
//該代碼是使用隨機刪除函數(shù)實現(xiàn)的
SeqListErase(ps, 0);
}
void SeqListPopBack(SeqList* ps)
{
//下面省略的代碼是沒有用隨機刪除函數(shù)實現(xiàn)的
//斷言：順序表為空不能刪除
/*assert(ps->size != 0);
ps->size--;*/ //存儲元素個數(shù)減一
//該代碼是使用隨機刪除函數(shù)實現(xiàn)的
SeqListErase(ps , ps ->size - 1);
}
int SeqListFind(SeqList* ps, SLDateType x)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
int i = 0;
//需要插入的位置不能在size下標(biāo)元素的后面
//原因是size - 1 下標(biāo)中的元素是最后一個元素
assert(ps->size >= pos);
/*for (i = ps->size - 1; i >= pos; i--)
{
ps->a[i + 1] = ps->a[i];
}
ps->a[pos] = x;
ps->size++;*/
memmove(ps->a + pos + 1, ps->a + pos, sizeof(SLDateType)*(ps->size - pos));
ps->a[pos] = x;
ps->size++;
}
void SeqListErase(SeqList* ps, int pos)
{
//順序表不能為空
assert(ps->size != 0);
int i = 0;
//將需要刪除元素的后面的元素全部向前移動一位
for (i = pos; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
三、順序表總結(jié)
1. 動態(tài)順序表的優(yōu)點
（1）可以根據(jù)需要動態(tài)地分配內(nèi)存，靈活性更高。
（2）可以避免靜態(tài)數(shù)組可能出現(xiàn)的內(nèi)存浪費問題。
（3）由于內(nèi)存空間是動態(tài)分配的，因此可以處理數(shù)據(jù)量不確定或者變化的情況。
2. 動態(tài)順序表的缺點
（1）動態(tài)內(nèi)存分配比靜態(tài)內(nèi)存分配要慢一些，會增加程序的運行時間。
（2）需要手動管理內(nèi)存，包括申請和釋放，容易出現(xiàn)內(nèi)存泄漏和內(nèi)存碎片等問題。
（3）難以預(yù)測、控制內(nèi)存的使用情況，容易出現(xiàn)因為內(nèi)存不足而導(dǎo)致程序崩潰的情況文章來源：http://www.zghlxwxcb.cn/news/detail-439921.html
結(jié)尾
如果有什么建議和疑問，或是有什么錯誤，希望大家能夠提一下。
希望大家以后也能和我一起進步?。?br> 如果這篇文章對你有用的話，希望能給我一個小小的贊！文章來源地址http://www.zghlxwxcb.cn/news/detail-439921.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】線性表之順序表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
