靜態(tài)順序表我們已經(jīng)實現(xiàn)完畢了，下來我們實現(xiàn)一下動態(tài)順序表

靜態(tài)鏈接：數(shù)據(jù)結(jié)構(gòu)之順序表——動態(tài)順序表(C語言版)
首先來了解一下兩個順序表的差別
一、內(nèi)存管理的靈活性
動態(tài)分配與釋放：動態(tài)順序表能夠在運行時根據(jù)需要動態(tài)地分配和釋放內(nèi)存空間。這意味著，當(dāng)數(shù)據(jù)量增加時，它可以自動擴容以容納更多的數(shù)據(jù)；而當(dāng)數(shù)據(jù)量減少時，理論上也可以相應(yīng)地釋放不再需要的內(nèi)存空間（盡管這通常需要程序員手動操作或依賴?yán)厥諜C制，具體取決于編程語言）。這種靈活性使得動態(tài)順序表能夠更高效地管理內(nèi)存資源。
避免內(nèi)存浪費：與靜態(tài)順序表相比，動態(tài)順序表能夠更準(zhǔn)確地根據(jù)實際需求分配內(nèi)存空間，從而避免了因預(yù)先分配過多內(nèi)存而導(dǎo)致的內(nèi)存浪費問題。同時，它也能夠在數(shù)據(jù)量減少時釋放部分內(nèi)存空間，進一步提高了內(nèi)存資源的利用率。
二、操作的便捷性
插入與刪除操作的靈活性：在動態(tài)順序表中，插入和刪除操作可以更加靈活地進行。由于內(nèi)存空間是動態(tài)分配的，因此可以在不移動大量元素的情況下完成插入和刪除操作（盡管在某些情況下仍然需要移動部分元素以保持?jǐn)?shù)據(jù)的連續(xù)性）。相比之下，靜態(tài)順序表在進行插入和刪除操作時通常需要移動大量的元素，這降低了操作的效率。
適應(yīng)數(shù)據(jù)變化的能力：動態(tài)順序表能夠更好地適應(yīng)數(shù)據(jù)量的變化。當(dāng)數(shù)據(jù)量增加時，它可以自動擴容以容納更多的數(shù)據(jù)；而當(dāng)數(shù)據(jù)量減少時，它也可以相應(yīng)地調(diào)整內(nèi)存空間的大小。這種能力使得動態(tài)順序表在處理不確定大小的數(shù)據(jù)集時更加高效和便捷
。
總而言之，就是為了使我們的順序表更加靈活，長度不夠去動態(tài)開辟。
下來我們通過代碼來實現(xiàn)一下動態(tài)順序表。
首先還是一樣，我們從頭文件開始寫起

#pragma once
//包含頭文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 定義順序表存儲的數(shù)據(jù)類型 
typedef int SQDataType;
// 定義順序表的結(jié)構(gòu)體  
typedef struct {SQDataType* arr;// 指向動態(tài)分配數(shù)組的指針（數(shù)組的首地址）  int size; // 順序表當(dāng)前存儲的元素個數(shù)（有效長度）int capacity; // 順序表的容量（即數(shù)組的總大小）  
}SL;
void SListInIt(SL* ps);//初始化函數(shù)

為了方便測試，我們完成打印函數(shù)

void PrintSList(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d  ", ps->arr[i]);}printf("\n");
}

下來我們完成初始化函數(shù)：

//包含我們自己寫的頭文件
#include"SList_02.h"
// 初始化順序表  
// 為順序表分配初始內(nèi)存，并設(shè)置size為0，capacity為指定的初始容量  
void SListInIt(SL* ps)
{ps->arr = NULL;//將數(shù)組的首地址賦值為空ps->size = 0;//數(shù)組的有效長度ps->capacity = 0;//容量
}

OK，經(jīng)過調(diào)試我們知道我們的初始化已經(jīng)完成了

下來我們寫尾插函數(shù)

void SListPushback(SL* ps,SQDataType x)
{//首先進行動態(tài)內(nèi)存分配mallocint newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;if (ps->capacity == ps->size){SQDataType* temp = malloc(newcapacity * sizeof(SQDataType));if (temp == NULL){printf("erro\n");exit(-1);}else{ps->arr = temp;ps->capacity = newcapacity;}}ps->arr[ps->size] = x;ps->size++;
}

運行一下

尾插成功
由于我們每次都需要檢查一下剩余的空間是否足夠所以我們這里寫一個檢查函數(shù)，就會方便很多

void SqListCheck(SL* ps)
{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//創(chuàng)建一個變量newcapacity,如果原來的容量為0則修改為4，如果不為0，則為原來的二倍if (ps->capacity == ps->size)//說明容量滿了，需要擴容了{SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//擴容二倍//如果擴容失敗if (tmp == NULL){printf("error\n");exit(-1);//非正常退出程序}//正常執(zhí)行else{ps->arr = tmp;//擴容的新地址給原來的變量ps->capacity = newcapacity;//新容量賦值給原來的容量}}
}

頭插函數(shù)

void SListPushFront(SL* ps, SQDataType x)
{//程序開始先檢查一下需不需要擴容SqListCheck(ps);//ps已經(jīng)是指針變量了指向SL類型//頭插就是把所有的數(shù)據(jù)往后挪動一位，空出來索引為0的位置，將新數(shù)據(jù)插入進去int end = ps->size - 1;//由于我們每次插入數(shù)據(jù)之后，size都會++所以這里end表示的是索引值while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}

測試一下沒有問題

頭刪函數(shù)：

void SqListDeleteFront(SL* ps)
{//和靜態(tài)一樣，只需要覆蓋就好了int start = 0;while (start < ps->size){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;
}

調(diào)用了兩次，成功刪除
尾刪函數(shù)：

void SqListDeleteback(SL* ps)
{//直接把有效長度減一就可以了，很簡單ps->size--;
}

刪除成功
隨機插入函數(shù)：

void SqListInter(SL* ps, int pos, SQDataType x)
{	assert(pos < ps->size);//斷言一下看是否插入合法SqListCheck(ps);//檢查一下，長度不夠的話就擴容int end = ps->size - 1;//跟頭插差不多，循環(huán)條件改到pos 就可以了while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;//賦值要插入的值給索引pos的位置ps->size++;}

成功插入
隨機刪除函數(shù)：

void SqListDelete(SL* ps, int pos)
{assert(pos < ps->size);//斷言一下看是否刪除合法int start = pos;while (start < ps->size){ps->arr[start - 1] = ps->arr[start];start++;}ps->size--;}

刪除成功，這里不是按照索引刪除的，是按照數(shù)字的真實位置刪除，如果需要按照索引刪除，只需要改一下代碼：

void SqListDelete(SL* ps, int pos)
{assert(pos < ps->size);//斷言一下看是否刪除合法int start = pos+1;while (start < ps->size){ps->arr[start - 1] = ps->arr[start];start++;}ps->size--;}

現(xiàn)在就是根據(jù)索引刪除啦

改函數(shù)：

void SqListModity(SL* ps, int pos, SQDataType x)
{assert(pos < ps->size);//斷言一下看是否改變合法//改直接改就行了，看是根據(jù)索引改，還是根據(jù)真實序號改//這里我們以索引為例ps->arr[pos] = x;}

成功修改了
查函數(shù)：是按照索引來顯示的，如果要按照真實位置則需要在打印的時候換成 i + 1

void SqListFound(SL* ps, SQDataType x)
{int count = 0;for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("此元素是第%d個元素\n", i);count++;break;}}if (count == 0){printf("順序表中沒有這個元素\n");}}

而且我們也可以用排序的方式來查，這里提供接口函數(shù)

//快速排序
void SqListSort(SL* ps)
{qsort(ps->arr, ps->size, sizeof(SQDataType), cmp);
}
//排序方法
int cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
//二分查找
int Binary_Search(struct Sq* ps, int x)
{int min = 0;int max = ps->size - 1;int mid = 0;while (min <= max){mid = (min + max) / 2;if (ps->arr[mid] < x){min = mid + 1;}else if (ps->arr[mid] > x){max = mid - 1;}else{return mid;}}return -1;
}

大家可以試一下
關(guān)于qsort函數(shù)，大家可以看qsort快速排序以及冒泡模擬實現(xiàn)
最后我們還得釋放多余的空間，釋放函數(shù)：

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

以下是完整代碼：

頭文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
typedef struct {SQDataType* arr;int size;int capacity;
}SL;
void SListInit(SL* ps);//初始化函數(shù)
void SListPushback(SL* ps,SQDataType x);//尾插函數(shù)
void SListPushFront(SL* ps, SQDataType x);//頭插函數(shù)
void PrintSList(SL* ps);//打印函數(shù)
void SqListDeleteFront(SL* ps);//頭刪
void SqListDeleteback(SL* ps);//尾刪
void SqListInter(SL* ps, int pos, SQDataType x);//隨即插入
void SqListDelete(SL* ps, int pos);//隨機刪除
void SqListModity(SL* ps, int pos, SQDataType x);//改函數(shù)
void SqListFound(SL* ps, SQDataType x);//查函數(shù)
void SqListCheck(SL* ps);//檢查函數(shù)
void SqListDestory(SL* ps);//釋放函數(shù)

函數(shù)

#include"SList_02.h"
void SListInit(SL* ps)
{ps->arr = NULL;//將數(shù)組的首地址賦值為空ps->size = 0;//數(shù)組的有效長度ps->capacity = 0;//容量
}
void PrintSList(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d  ", ps->arr[i]);}printf("\n");
}
void SqListCheck(SL* ps)
{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//創(chuàng)建一個變量newcapacity,如果原來的容量為0則修改為4，如果不為0，則為原來的二倍if (ps->capacity == ps->size)//說明容量滿了，需要擴容了{SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//擴容二倍//如果擴容失敗if (tmp == NULL){printf("error\n");exit(-1);//非正常退出程序}//正常執(zhí)行else{ps->arr = tmp;//擴容的新地址給原來的變量ps->capacity = newcapacity;//新容量賦值給原來的容量}}
}
//void SqListCheck(SL* ps)
//{
//	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//	//如果滿了就要擴容
//	if (ps->size == ps->capacity)
//	{
//		/*ps->capacity=realloc(ps->arr,ps->capacity=ps->capacity*2)*/
//		SQDataType* temp = realloc(ps->arr, newcapacity * sizeof(SQDataType));
//		if (temp == NULL)
//		{
//			printf("fail\n");
//			exit(-1);
//		}
//		else
//		{
//			ps->arr = temp;
//			ps->capacity = newcapacity;
//		}
//	}
//}
void SListPushback(SL* ps,SQDataType x)
{//首先進行動態(tài)內(nèi)存分配mallocint newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;if (ps->capacity == ps->size){SQDataType* temp = malloc(newcapacity * sizeof(SQDataType));if (temp == NULL){printf("erro\n");exit(-1);}else{ps->arr = temp;ps->capacity = newcapacity;}}ps->arr[ps->size] = x;ps->size++;
}void SListPushFront(SL* ps, SQDataType x)
{//程序開始先檢查一下需不需要擴容SqListCheck(ps);//ps已經(jīng)是指針變量了指向SL類型//頭插就是把所有的數(shù)據(jù)往后挪動一位，空出來索引為0的位置，將新數(shù)據(jù)插入進去int end = ps->size - 1;//由于我們每次插入數(shù)據(jù)之后，size都會++所以這里end表示的是索引值while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}
void SqListDeleteFront(SL* ps)
{//和靜態(tài)一樣，只需要覆蓋就好了int start = 0;while (start < ps->size){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;
}
void SqListDeleteback(SL* ps)
{//直接把有效長度減一就可以了，很簡單ps->size--;
}
void SqListInter(SL* ps, int pos, SQDataType x)
{	assert(pos < ps->size);//斷言一下看是否插入合法SqListCheck(ps);//檢查一下，長度不夠的話就擴容int end = ps->size - 1;//跟頭插差不多，循環(huán)條件改到pos 就可以了while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;//賦值要插入的值給索引pos的位置ps->size++;}
void SqListDelete(SL* ps, int pos)
{assert(pos < ps->size);//斷言一下看是否刪除合法int start = pos+1;while (start <=ps->size){ps->arr[start-1] = ps->arr[start];start++;}ps->size--;}
void SqListModity(SL* ps, int pos, SQDataType x)
{assert(pos < ps->size);//斷言一下看是否改變合法//改直接改就行了，看是根據(jù)索引改，還是根據(jù)真實序號改//這里我們以索引為例ps->arr[pos] = x;}
void SqListFound(SL* ps, SQDataType x)
{int count = 0;for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("此元素是第%d個元素\n", i);count++;break;}}if (count == 0){printf("順序表中沒有這個元素\n");}}
void SqListDestory(SL* ps)
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}

測試函數(shù)

#include"SList_02.h"
void test()
{SL s;SListInit(&s);SListPushback(&s, 5);SListPushback(&s, 7);PrintSList(&s);SListPushFront(&s, 3);SListPushFront(&s, 9);SListPushFront(&s, 6);PrintSList(&s);SListPushFront(&s, 8);SListPushFront(&s, 11);SListPushFront(&s, 16);SListPushFront(&s, 15);SListPushFront(&s, 1);PrintSList(&s);SqListDeleteFront(&s);SqListDeleteFront(&s);PrintSList(&s);SqListDeleteback(&s);SqListDeleteback(&s);PrintSList(&s);SqListInter(&s, 2, 50);PrintSList(&s);SqListInter(&s, 5, 60);PrintSList(&s);SqListDelete(&s, 2);PrintSList(&s);SqListDelete(&s, 5);PrintSList(&s);SqListModity(&s, 3, 25);PrintSList(&s);SqListModity(&s, 3, 29);PrintSList(&s);SqListFound(&s, 29);SqListFound(&s, 1);SqListDestory(&s);}
int main()
{test();return 0;
}