前言
本篇講述了順序表的相關(guān)知識(shí)，以及動(dòng)態(tài)順序表的代碼實(shí)現(xiàn)。
1.線性表
順序表和鏈表一般情況下都會(huì)叫他們線性表。
線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使 用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列、字符串…
線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的， 線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
2.順序表
順序表簡(jiǎn)單說(shuō)就是一個(gè)數(shù)組。
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存
儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
順序表一般可以分為：
- 靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素。
- 動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)。
2.1 靜態(tài)順序表
2.2 動(dòng)態(tài)順序表
3動(dòng)態(tài)順序表代碼詳解
3.1 順序表功能(頭文件)
這里的順序表和我們之前的通訊錄有些相像，我們可以結(jié)合之前的通訊錄來(lái)學(xué)習(xí)。
鏈接: 八功能通訊錄
順序表的頭文件（功能）如下：seqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
// sequence list
typedef struct SeqList
{
SLDataType* a;
int size; // 有效數(shù)據(jù)
int capacity; // 空間容量
}SL;
void SLInit(SL* psl);//初始化順序表
void SLDestroy(SL* psl);//摧毀順序表
void SLPrint(SL* psl);//打印順序表
void SLCheckCapacity(SL* psl);//檢測(cè)順序表的容量
// 頭尾插入刪除
void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//頭插
void SLPopBack(SL* psl);//尾刪
void SLPopFront(SL* psl);//頭刪
// 任意下標(biāo)位置的插入刪除
void SLInsert(SL* psl, int pos, SLDataType x);//任意下標(biāo)插
void SLErase(SL* psl, int pos);//任意下標(biāo)刪
// 找到返回下標(biāo)
// 沒(méi)有找到返回-1
int SLFind(SL* psl, SLDataType x);
3.2 各功能函數(shù)
3.2.1 初始化順序表
void SLInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
3.2.2 摧毀順序表
void SLDestroy(SL* psl)
{
assert(psl);
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
}
3.2.3 打印順序表
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
3.2.4 檢測(cè)順序表的容量
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapacity;
}
}
3.2.5 在順序表尾部插入元素
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
3.2.6 在順序表頭部插入元素
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
// 挪動(dòng)數(shù)據(jù)
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
3.2.7 在順序表尾部刪除元素
void SLPopBack(SL* psl)
{
assert(psl);
assert(psl->size > 0);
psl->size--;
}
3.2.8 在順序表頭部刪除元素
void SLPopFront(SL* psl)
{
assert(psl);
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
3.2.9 在順序表任意處插入元素
void SLInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SLCheckCapacity(psl);
// 挪動(dòng)數(shù)據(jù)
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}
3.2.10 在順序表任意處刪除元素
void SLErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
// 挪動(dòng)覆蓋
int begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
3.2.11 查找元素
int SLFind(SL* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
3.2.12 主函數(shù)
主函數(shù)包括目錄及各個(gè)功能的測(cè)試。完整代碼見(jiàn)3.2.13 gitee
3.2.13 完整代碼
鏈接: 動(dòng)態(tài)順序表完整代碼:gitee文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-730339.html
4.順序表的缺陷
1.尾部插入效率尚可，頭部或者中間插入刪除，需要挪動(dòng)數(shù)據(jù)，效率低下。
2.容量滿了之后只能擴(kuò)容。擴(kuò)容是有一定的消耗，且存在一定的空間浪費(fèi)。（假設(shè)空間為100，擴(kuò)容到200，但只需要120個(gè)數(shù)據(jù)，會(huì)有大量空間浪費(fèi)）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-730339.html
到了這里，關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)-----順序表(多功能動(dòng)態(tài)順序表的代碼實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
