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

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

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

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

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

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

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

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

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

void SListPushback(SL* ps,SQDataType x)
{//首先進(jìn)行動(dòng)態(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++;
}

運(yùn)行一下

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

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

頭插函數(shù)

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

測(cè)試一下沒有問題

頭刪函數(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)
{//直接把有效長(zhǎng)度減一就可以了，很簡(jiǎn)單ps->size--;
}

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

void SqListInter(SL* ps, int pos, SQDataType x)
{	assert(pos < ps->size);//斷言一下看是否插入合法SqListCheck(ps);//檢查一下，長(zhǎng)度不夠的話就擴(kuò)容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++;}

成功插入
隨機(jī)刪除函數(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ù)字的真實(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ù)真實(shí)序號(hào)改//這里我們以索引為例ps->arr[pos] = x;}

成功修改了
查函數(shù)：是按照索引來(lái)顯示的，如果要按照真實(shí)位置則需要在打印的時(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個(gè)元素\n", i);count++;break;}}if (count == 0){printf("順序表中沒有這個(gè)元素\n");}}

而且我們也可以用排序的方式來(lái)查，這里提供接口函數(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快速排序以及冒泡模擬實(shí)現(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);//隨機(jī)刪除
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ù)組的有效長(zhǎng)度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)建一個(gè)變量newcapacity,如果原來(lái)的容量為0則修改為4，如果不為0，則為原來(lái)的二倍if (ps->capacity == ps->size)//說明容量滿了，需要擴(kuò)容了{SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//擴(kuò)容二倍//如果擴(kuò)容失敗if (tmp == NULL){printf("error\n");exit(-1);//非正常退出程序}//正常執(zhí)行else{ps->arr = tmp;//擴(kuò)容的新地址給原來(lái)的變量ps->capacity = newcapacity;//新容量賦值給原來(lái)的容量}}
}
//void SqListCheck(SL* ps)
//{
//	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//	//如果滿了就要擴(kuò)容
//	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)
{//首先進(jìn)行動(dòng)態(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)
{//程序開始先檢查一下需不需要擴(kuò)容SqListCheck(ps);//ps已經(jīng)是指針變量了指向SL類型//頭插就是把所有的數(shù)據(jù)往后挪動(dòng)一位，空出來(lái)索引為0的位置，將新數(shù)據(jù)插入進(jìn)去int end = ps->size - 1;//由于我們每次插入數(shù)據(jù)之后，size都會(huì)++所以這里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)
{//直接把有效長(zhǎng)度減一就可以了，很簡(jiǎn)單ps->size--;
}
void SqListInter(SL* ps, int pos, SQDataType x)
{	assert(pos < ps->size);//斷言一下看是否插入合法SqListCheck(ps);//檢查一下，長(zhǎng)度不夠的話就擴(kuò)容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ù)真實(shí)序號(hào)改//這里我們以索引為例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個(gè)元素\n", i);count++;break;}}if (count == 0){printf("順序表中沒有這個(gè)元素\n");}}
void SqListDestory(SL* ps)
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}

測(cè)試函數(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;
}