緒論
????????從本章開始就是開始數(shù)據(jù)結(jié)構(gòu)的開端，本章將會寫出數(shù)據(jù)結(jié)構(gòu)中的順序表的代碼實現(xiàn)，多會以注釋的方法來描述一些細節(jié)（注釋是我們程序員必須常用的工具）。
? ? ?
?文章來源地址http://www.zghlxwxcb.cn/news/detail-495682.html
話不多說安全帶系好，發(fā)車啦（建議電腦觀看）。
附：紅色，部分為重點部分；藍顏色為需要記憶的部分（不是死記硬背哈，多敲）；黑色加粗或者其余顏色為次重點；黑色為描述需要
目錄
1.線性表
2.順序表
2.1順序表的結(jié)構(gòu)：
2.1.1 順序表的初始化：
2.1.2 順序表的摧毀
2.1.3 順序表的放入數(shù)據(jù)
2.1.4 順序表的刪除數(shù)據(jù)
2.1.5 打印順序表的數(shù)據(jù)? ? ? ?
2.2順序表的源代碼：
1.線性表
知識點：
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串..
細節(jié)（注意點）：
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組（地址連續(xù)）和鏈式結(jié)構(gòu)（地址不連續(xù)）的形式存儲。
2.順序表
知識點：
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲（本質(zhì)就是一個數(shù)組只不過用結(jié)構(gòu)體包裝了一下）。
順序表分為：靜態(tài)順序表（實現(xiàn)開辟好數(shù)組的空間大?。┮约皠討B(tài)順序表（用動態(tài)內(nèi)存管理的方式來進行內(nèi)存管理）
細節(jié)：
我們要實現(xiàn)一個順序表的話首先我們要知道順序表的框架：
- 順序表的結(jié)構(gòu)體
- 數(shù)組（a）
- 順序表中的元素個數(shù)（size）
- 容量（用于動態(tài)順序表，是動態(tài)申請的大小，用于和元素個數(shù)比較判斷申請空間是否足夠）
- 有了這個結(jié)構(gòu)后，我們就需要實現(xiàn)一個順序表的基本功能
- 將數(shù)據(jù)放進順序表中
- 將順序表中的數(shù)據(jù)刪除
- 初始化順序表（主要針對于動態(tài)開辟空間提前申請空間）
- 歸還（摧毀）所借的空間
- 將順序表中的數(shù)據(jù)打印出來
下面這要講的是動態(tài)的順序表、如果需要靜態(tài)的將結(jié)構(gòu)體中的容量去掉，再把數(shù)組改一下即可（若有問題的話可以評論我都會看），我們就把順序表想成一個數(shù)組就能很好的理解了
2.1順序表的結(jié)構(gòu)：
順序表所要的結(jié)構(gòu)是由數(shù)組、元素個數(shù)、容量組成的
代碼實現(xiàn)如下：
typedef struct SeqList//將結(jié)構(gòu)體名稱重命名為
{
SLDataType* a;//開辟SLDataType（用typedef重定義類型名，這樣方便與改變結(jié)構(gòu)體內(nèi)的數(shù)據(jù)類型）類型的空間
//數(shù)組的本質(zhì)是指針所以為了更方便理解就直接寫成指針的形式SLDataType* a
int size;//元素個數(shù)
int capacity;//容量
}SeqList;//重命名為SeqList 這樣方便后面使用
//宏定義如下：
//#define SLDataType int
//使用結(jié)構(gòu)體類型
//SeqList s;即可
//不用寫成 struct SeqList s;2.1.1 順序表的初始化：
將容量capacity和個數(shù)size進行簡單的初始化，主要是申請一片空間來給a來存數(shù)據(jù)
代碼如下：
void InitSeqList(SeqList* obj)//將結(jié)構(gòu)體用指針接收
{
assert(obj);
obj->capacity = INIT_CAPACITY;//通過指針來訪問結(jié)構(gòu)體中的成員，將capacity先初始化為INIT_CAPACITY（用宏來確定capacity的起始大小，這樣方便后改變）
obj->size = 0;//0個成員
obj->a = (SLDataType*)malloc(sizeof(SLDataType) * obj->capacity);//malloc動態(tài)申請結(jié)構(gòu)體大小的capacity個空間
if (obj->a == NULL)//判斷一下是否申請成功
{
perror("malloc");//如果失敗就報錯
return;
}
}
//宏
//#define INIT_CAPACITY 4 （這是應(yīng)該定義在頭文件中的）
//調(diào)用的方法
//SeqList s;（應(yīng)該定義在測試test.c文件中）
//InitSeqList(&s);
//而一般的結(jié)構(gòu)的實現(xiàn)又是放在SeqList.c的文件中，這樣來進行分源管理2.1.2 順序表的摧毀
順序表的摧毀主要是為了將向操作系統(tǒng)借的空間歸還，以及再將容量和元素個數(shù)歸為0
void DestorySeqList(SeqList* obj)//指針接收結(jié)構(gòu)
{
assert(obj);//判斷結(jié)構(gòu)是否為空,防止訪問到NULL指針（這是一個好習慣）
free(obj->a);//直接釋放所借用的空間
obj->a = NULL;//再將其置為NULL
obj->capacity = obj->size = 0;//將容量和個都置為0,摧毀了自然就沒了
}
//調(diào)用方法
//SeqList s;
//DestorySeqList(&s);2.1.3 順序表的放入數(shù)據(jù)
1.從尾部插入數(shù)據(jù)
尾部插入就比較的簡單了，因為順序表其實是一個數(shù)組所以直接在最后位置插入數(shù)據(jù)就行（此時最后位置的下標就是元素個數(shù)）。
?文章來源：http://www.zghlxwxcb.cn/news/detail-495682.html
void SeqListBackPush(SeqList* obj, SLDataType x)//將結(jié)構(gòu)體用指針接收通過指針來找到成員，x是所要尾插的數(shù)據(jù) { assert(obj);//判斷結(jié)構(gòu)體是否為NULL If_Add_Capacity(obj);//判斷數(shù)據(jù)是否已經(jīng)把所借的容量填滿了 obj->a[(obj->size)++] = x;//在a的最后位置插入數(shù)據(jù)，可以發(fā)現(xiàn)其實size個數(shù)就是最后位置的下標 }但要注意判斷容量是否滿足，如果容量已經(jīng)是滿的了（size == capacity）就需要擴容，If_Add_Capacity?(判斷是否要增容)
void If_Add_Capacity(SeqList* obj) { if (obj->size == obj->capacity)//判斷已有成員個數(shù)是否等于容量,若等則進去 { SLDataType* ptr = (SLDataType*)realloc(obj->a, sizeof(SLDataType) * obj->capacity * 2);//進來后就說明空間不夠了，需要開空間 //一般多直接開辟比容量大兩倍的空間 即 對a開辟結(jié)構(gòu)體大小為原capacity兩倍的空間 if (ptr == NULL)//判斷是否申請成功 { perror("realloc");//不成功則報錯 return; } obj->a = ptr;//因為可能是異地擴容所以還要將ptr賦值給數(shù)組a obj->capacity *= 2;//容量 乘于 2 ptr = NULL;//無用的指針置為NULL（好習慣） } }2.從頭部插入
在一個數(shù)組中若想從頭部插入?你就需要把數(shù)據(jù)先全部往后挪動一位，再將這個數(shù)據(jù)存放到第一個位置處。
void SeqListFrontPush(SeqList* obj, SLDataType x) { assert(obj);//判空 If_Add_Capacity(obj);//判是否滿了 for (int i = obj->size; i > 0; i--)//將所有數(shù)據(jù)往后移一位 { obj->a[i] = obj->a[i - 1];//此處只要是未滿的就能直接就行移位并不會有事 } obj->a[0] = x;//在a[0]位置處添加數(shù)據(jù) obj->size++;//元素個數(shù)++,這可別忘了！ }3.指定位置插入
在滿足pos位置是一個正常的位置的前提下,并且同樣需要判斷是否要擴容，?要在某個位置處插入，其本質(zhì)其實和頭插有些類似，需要把插的位置后的數(shù)據(jù)全部往后挪一位后，最后再在那個位置插入數(shù)據(jù)即可。
void SeqListInsert(SeqList* obj, int pos, SLDataType x)//在pos位置處添加數(shù)據(jù) { assert(obj);//判空 pos -= 1;//換成下標 assert(pos >= 0 && pos <= obj->size);//判斷這個位置是否有問題 If_Add_Capacity(obj);//判斷是否滿了 int i = obj->size;//和頭插的方法幾乎一樣 for (i; i > pos; i--)//將從位置處開始的數(shù)據(jù)全部往后挪一位 { obj->a[i] = obj->a[i - 1];//從尾部開始防止覆蓋 } obj->a[i] = x;//在位置處插入數(shù)據(jù) obj->size++;//size++ 別忘了！ }
2.1.4 順序表的刪除數(shù)據(jù)
1. 從尾部刪除
在刪除之前我們需要判斷一下是否還有數(shù)據(jù)在順序表中（assert(obj->size > 0)）,對于一個數(shù)組來說我們刪除時直接對元素個數(shù)進行 - - 即可并不會去真正的刪除，當下一次插入數(shù)據(jù)時就直接覆蓋了，也不會有什么影響。
void SeqListBackPop(SeqList* obj) { assert(obj);//判空 assert(obj->size > 0);//為真就過、為假就會報錯,若沒有數(shù)據(jù)那就是有問題的 obj->size--;//此處的尾刪并不直接將空間歸還，而僅僅只是把元素個數(shù)-1這樣 //就不會訪問到，即使后面需要再次添加數(shù)據(jù)也就直接覆蓋了,因為要歸還空間的成本太高了 }2.從頭部刪除
同樣我們需要先判斷一下順序表中是否還有數(shù)據(jù)、對于頭部刪除來說直接將第一個數(shù)據(jù)覆蓋了就好 。
void SeqListFrontPop(SeqList* obj) { assert(obj);//判空 assert(obj->size > 0);//判斷是否有數(shù)據(jù) for (int i = 0; i < obj->size - 1; i++)//直接從第2個位置開始往前覆蓋掉即可 { obj->a[i] = obj->a[i + 1]; } obj->size--;//注意要 - - }3.指定位置刪除
判斷pos是否在順序表中、最后將從pos+1位置開始數(shù)據(jù)覆蓋即可。
void SeqListErase(SeqList* obj, int pos) { assert(obj);//判空 assert(obj->size > 0);//是否有數(shù)據(jù) pos -= 1;//換成下標 assert(pos >= 0 && pos <= obj->size);//是否符合要求 for (int i = pos; i < obj->size - 1; i++)//和頭刪對應(yīng)此處就應(yīng)該是從pos+1位置處開始往前覆蓋 { obj->a[i] = obj->a[i + 1];//將pos位置處先覆蓋 , 然后以此往后 } obj->size--;//注意 - - }
2.1.5 打印順序表的數(shù)據(jù)? ? ? ?
就和數(shù)組的打印一樣，直接遍歷打印即可
void SeqListPirnt(SeqList* obj)//指針接收結(jié)構(gòu)體
{
assert(obj);//判空
for (int i = 0; i < obj->size; i++)//從下標為0的位置處開始往后遍歷
{
printf("%d ", obj->a[i]);//結(jié)構(gòu)體訪問成員：*obj表示結(jié)構(gòu)體 在 .訪問 就還能寫成 （*obj）.a[i] 這兩個是等價的一般喜歡用前面方法
}
printf("\n");//換行
}
如果有任何問題，歡迎討論！
2.2順序表的源代碼：
我將全部放在一個里面對于分源內(nèi)容請自行分開，或者直接合并也行（合并方法將聲明以及包含自身的頭文件去掉即可直接使用）
//SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_CAPACITY 4
//sequence
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;
}SeqList;
void InitSeqList(SeqList * obj);
void DestorySeqList(SeqList* obj);
void SeqListBackPush(SeqList* obj,SLDataType x );
void SeqListBackPop(SeqList* obj);
void SeqListPirnt(SeqList* obj);
void SeqListFrontPush(SeqList* obj, SLDataType x);
void SeqListFrontPop(SeqList* obj);
void SeqListInsert(SeqList* obj, int pos, SLDataType x);
void SeqListErase(SeqList* obj, int pos);
//SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqLIst.h"
//sequence 順序
void If_Add_Capacity(SeqList* obj)
{
if (obj->size == obj->capacity)
{
SLDataType* ptr = (SLDataType*)realloc(obj->a, sizeof(SLDataType) * obj->capacity * 2);
if (ptr == NULL)
{
perror("realloc");
return;
}
obj->a = ptr;
obj->capacity *= 2;
ptr = NULL;
}
return;
}
void InitSeqList(SeqList* obj)
{
assert(obj);
obj->capacity = INIT_CAPACITY;
obj->size = 0;
obj->a = (SLDataType*)malloc(sizeof(SLDataType) * obj->capacity);
if (obj->a == NULL)
{
perror("malloc");
return;
}
}
void DestorySeqList(SeqList* obj)
{
assert(obj);
free(obj->a);
obj->a = NULL;
obj->capacity = obj->size = 0;
}
void SeqListBackPush(SeqList* obj, SLDataType x)
{
assert(obj);
If_Add_Capacity(obj);
obj->a[(obj->size)++] = x;
}
void SeqListBackPop(SeqList* obj)
{
assert(obj);
assert(obj->size > 0);//為真就過、為假就會報錯
obj->size--;
}
void SeqListPirnt(SeqList* obj)
{
assert(obj);
for (int i = 0; i < obj->size; i++)
{
printf("%d ", obj->a[i]);
}
printf("\n");
}
void SeqListFrontPush(SeqList* obj, SLDataType x)
{
assert(obj);
If_Add_Capacity(obj);
for (int i = obj->size; i > 0; i--)
{
obj->a[i] = obj->a[i - 1];
}
obj->a[0] = x;
obj->size++;
}
void SeqListFrontPop(SeqList* obj)
{
assert(obj);
assert(obj->size > 0);
for (int i = 0; i < obj->size - 1; i++)
{
obj->a[i] = obj->a[i + 1];
}
obj->size--;
}
void SeqListInsert(SeqList* obj, int pos, SLDataType x)
{
assert(obj);
pos -= 1;//換成下標
assert(pos >= 0 && pos <= obj->size);
If_Add_Capacity(obj);
int i = obj->size;
for (i; i > pos; i--)//從最后開始將填充數(shù)據(jù)
{
obj->a[i] = obj->a[i - 1];
}
obj->a[i] = x;
obj->size++;
}
void SeqListErase(SeqList* obj, int pos)
{
assert(obj);
assert(obj->size > 0);
pos -= 1;//換成下標
assert(pos >= 0 && pos <= obj->size);
for (int i = pos; i < obj->size - 1; i++)
{
obj->a[i] = obj->a[i + 1];
}
obj->size--;
}
//test.c
//測試是否能用
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqLIst.h"
int main()
{
SeqList s;
InitSeqList(&s);
SeqListPush(&s, 1);
SeqListPush(&s, 2);
SeqListPush(&s, 3);
SeqListPush(&s, 4);
SeqListPush(&s, 5);
SeqListPop(&s);
SeqListPop(&s);
SeqListPop(&s);
SeqListFrontPush(&s, 0);
SeqListFrontPush(&s, -1);
SeqListInsert(&s, 1, 3);
SeqListErase(&s, 2);
SeqListPirnt(&s);
DestorySeqList(&s);
return 0;
}分源管理時的頭文件?：
?
?
持續(xù)更新大量數(shù)據(jù)結(jié)構(gòu)細致內(nèi)容,三連關(guān)注哈
?
?
?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)順序表（C語言實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
