順序表

1.數據結構相關概念

1、什么是數據結構

數據結構是由“數據”和“結構”兩詞組合?來。
**什么是數據？**常?的數值1、2、3、4…、教務系統?保存的??信息（姓名、性別、年齡、學歷等等）、????眼可以看到的信息（?字、圖?、視頻等等），這些都是數據
什么是結構？
當我們想要使??量使?同?類型的數據時，通過?動定義?量的獨?的變量對于程序來說，可讀性?常差，我們可以借助數組這樣的數據結構將?量的數據組織在?起，結構也可以理解為組織數據的?式。
想要找到草原上名叫“咩咩”的?很難，但是從?圈?找到1號?就很簡單，?圈這樣的結構有效將?群組織起來。
概念：數據結構是計算機存儲、組織數據的?式。數據結構是指相互之間存在?種或多種特定關系
的數據元素的集合。數據結構反映數據的內部構成，即數據由那部分構成，以什么?式構成，以及數據元素之間呈現的結構。

總結：
1）能夠存儲數據（如順序表、鏈表等結構）

2）存儲的數據能夠?便查找

2、為什么需要數據結構？

如圖中所?，不借助排隊的?式來管理客?，會導致客?就餐感受差、等餐時間?、餐廳營業混亂等情況。同理，程序中如果不對數據進?管理，可能會導致數據丟失、操作數據困難、野指針等情況。通過數據結構，能夠有效將數據組織和管理在?起。按照我們的?式任意對數據進?增刪改查等操
作。
最基礎的數據結構：數組。

【思考】有了數組，為什么還要學習其他的數據結構？
假定數組有10個空間，已經使?了5個，向數組中插?數據步驟：
求數組的?度，求數組的有效數據個數，向下標為數據有效個數的位置插?數據（注意：這?是否要判斷數組是否滿了，滿了還能繼續插?嗎）…
假設數據量?常龐?，頻繁的獲取數組有效數據個數會影響程序執?效率。
結論：最基礎的數據結構能夠提供的操作已經不能完全滿?復雜算法實現。

2.順序表

1、順序表的概念及結構

順序表是線性表的一種

線性表有物理結構和邏輯結構

線性表的物理結構不一定連續

但邏輯結構一定連續

那什么是線性表呢？

線性表（linearlist）是n個具有相同特性的數據元素的有限序列。線性表是?種在實際中?泛使?的數據結構，常?的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構，也就說是連續的?條直線。但是在物理結構上并不?定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。
案例：蔬菜分為綠葉類、?類、菌菇類。

線性表指的是具有部分相同特性的?類數據結構的集合

順序表的物理結構跟邏輯結構都是連續的

2、順序表分類

? 順序表和數組的區別
? 順序表的底層結構是數組，對數組的封裝，實現了常?的增刪改查等接?

? 順序表分類
? 靜態順序表

? 動態順序表

3、動態順序表的實現

先創建1個頭文件用來聲明函數，兩個.c文件，SeqList.c順序表的實現，test.c用來測試

1.定義一個動態順序表

typedef struct SeqList//sequence順序的 
{SLDataType* arr;int size;//有效數據個數int capacity;//空間大小
}SL;//SeqList太長 我們把他換成SL 

因為我們不知道以后使用時要用什么類型的數據，所以我們最好給數據類型起一個別名

typedef int SLDataType;

2.順序表的初始化

void SLInit(SL *s)
{s->arr = NULL;s->size = s->capacity = 0;
}

注意:這里函數傳參一定要用地址傳參

3.順序表的銷毀

void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

4.順序表達的尾插

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//表達式為真，繼續執行 表達式為假 程序報錯//插入之前先看空間夠不夠if (ps->size == ps->capacity)
{//申請空間//只有realloc可以增容//增容通常來說是成倍數的增加 一般是2倍或3倍 不能頻繁增容 會造成性能降低int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//用臨時變量來接收，防止內存開辟失敗數據丟失if (tmp == NULL){perror("realloc fail");exit(1);//直接退出程序，不再執行}//空間申請成功ps->arr = tmp;ps->capacity = newcapacity;
}ps->arr[ps->size++] = x;	
}

5.順序表的頭插

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//先讓順序表中數據整體后移一位for (int i = ps->size; i>0; i--){ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]}ps->arr[0] = x;ps->size++;//加了一個數據
}

6.空間大小檢查函數

我們注意到在頭插跟尾插中都 檢查了空間的大小

所以我們可以把他封裝成函數

oid SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){//申請空間//只有realloc可以增容//增容通常來說是成倍數的增加 一般是2倍或3倍 不能頻繁增容 會造成性能降低int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(1);//直接退出程序，不再執行}//空間申請成功ps->arr = tmp;ps->capacity = newcapacity;}
}

7.順序表的尾刪

void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//判斷順序表是否為空//ps->arr[ps->size - 1] = -1;ps->size--;	
}

8.順序表的頭刪

void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];//逐個向前替換 最后一個是arr[size-2]=arr[size-1]}ps->size--;//這個不能忘
}

9.測試看效果

#include"SeqList.h"
void SLTest01()
{SL sl;SLInit(&sl);//這里要傳地址  傳值（值拷貝） 這都沒有初始化 沒有值SLPushBack(&sl, 1);//尾插SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrintf(sl);//打印函數 放下文//頭插SLPushFront(&sl, 5);SLPushFront(&sl, 6);SLPrintf(sl);
//尾刪SLPopBack(&sl);SLPrintf(sl);//頭刪SLPopFront(&sl);SLPopFront(&sl);SLPopFront(&sl);SLPrintf(sl);SLDestroy(&sl);//銷毀
}
int main()
{SLTest01();return 0;
}

void SLPrintf(SL s)//上文中的打印函數 這里不是對底層的修改 所以傳值即可
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}