前言?

成都創新互聯長期為千余家客戶提供的網站建設服務，團隊從業經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態環境。為阿巴嘎企業提供專業的網站制作、成都網站設計，阿巴嘎網站改版等技術服務。擁有10多年豐富建站經驗和眾多成功案例,為您定制開發。

大家好啊，這里是幸麟

一名普通的大學牲

🧩希望通過寒假多學一些知識，對自己進行一些有益的補充

也愿意與各位一起奮斗，為了更好的明天努力

目錄

什么是順序表

接口

初始化SLInit

順序表空間檢查&擴容

插入元素

頭插SLPushFront

尾插

萬能插SLInsert

刪除數據

萬能刪SLErase

查詢SLFind

打印順序表SLPrint

---

---

什么是順序表

順序表是線性表的一種，是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

但其存儲并不像數組那樣可以在其區間內任意位置存儲，順序表需要依次存儲，正如其名，只有存儲完上一位置后才能存儲下一位置

順序表：（自己做的可能有點不太好看哈），其中size代表下一個要存儲在a數組內的元素下標，也代表有效數據的數量

其中順序表可以分為采用定長數組進行存儲的靜態順序表和使用動態開辟數組的動態順序表

其中靜態順序表由于是采用定長數組進行存儲，常常會有數組開大了空間浪費，數組開小了不夠用的窘況，所以實際中還是動態順序表使用居多

接口

其中我們用typedef定義我們創建的結構體seqlist為SL，這樣寫起來時方便一些

同時由于我們可能更改順序表中存儲數據的類型，為了方便日后可能有的調整我們定義一個數據類型SLDataType，這里先使用int，如果以后想將存儲數據類型為longlong的元素直接更改SLDataType即可

#pragma once
#include#include 
#includeusing namespace std;
typedef int SLDataType ;
typedef struct Seqlist
{
	SLDataType* a;//指向動態開辟的數組
	int size;//有效數據的大小，同時也是下一個數據存儲位置
	int capacity;//順序表空間的大小
}SL;

void SLPrint(SL* ps);//打印
void SLInit(SL* ps);//初始化
void SLDestory(SL* ps);//順序表銷毀
void SLCheckCapacity(SL* ps);//順序表擴容

//尾插尾刪
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);

//頭插頭刪
void SLPushFront(SL* ps,SLDataType x);
void SLPopFront(SL* ps);

//萬能插，萬能刪
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

初始化SLInit

在初始化時，我們要注意ps所指向的地址是不是空指針，如果是空指針程序會錯誤，所以這邊加了一個斷言判斷，剛開始的順序表空間與有效數據大小都沒有，所以直接賦0

void SLInit(SL* ps)
{
	assert(ps);//斷言ps是否為空指針，防止程序錯誤

	ps->a = NULL;
	ps->size = 0;//順序表空間與有效數據大小都為0
	ps->capacity = 0;
}

順序表空間檢查&擴容

在每一次進行插入操作時我們都應該進行一次空間的檢查，如果發現以使用的有效數據大小與順序表空間相等時就需要使用realloc函數對其進行擴容（一般擴大的容量為原來的兩倍），在給newcapacity賦值時可以加一個判斷，如果capacity并沒有容量（即為0時），則讓newcapacity=4，給予一個初始的空間

值得注意的是使用realloc函數申請空間時，可能會出現以下三種情況

①數組a原本的地址后面有充足的空余空間，擴容結束后返回原來數組a的地址

②數組a原本的地址后面并沒有足夠的空間用來擴容，這時候就需要重新找一個地址進行擴容，所以這時候會返回一個新的地址

③realloc有可能擴容失敗，返回一個空指針NULL

所以我們這里用用一個指針tmp用來接收realloc的返回值，如果返回值不為NULL則將a的地址變更為tmp接收的地址

void SLCheckCapacity(SL* ps)
{
	if (ps->size >= ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

插入元素 頭插SLPushFront

由于是插入操作，所以在開始前一定要檢查一下容量是否充足

創建一個變量end，從size-1,即最后一個數據的下標開始，把每一個數據往后挪一個位置，直到移完第一個數據，然后再將所要插入的數據插入即可，插入結束后size++，有效數據＋1

void SLPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

代碼：

尾插

由于是插入操作同樣需要檢查一個容量是否足夠

然后直接插入末尾即可，同樣最后size++，有效數據＋1

void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

萬能插SLInsert

所有的插入，都可以用萬能插實現，頭插和尾插也都是萬能插的一種特殊情況

頭插相當在pos=0時的萬能插，尾插相當于pos=size-1時的萬能插

，我們用pos表示想要插入的位置，同時pos有效范圍為[0,size-1]，如果超出這個范圍會出錯，所以這邊加個斷言，移動數據的時候同樣使用從size-1開始移動，直到把原本下標為pos的數據移走，然后在pos位置插入新數據，結束后size++

void SLInsert(SL* ps, int pos,SLDataType x )
{
	assert(ps);
	assert(pos >= 0);
	assert(pos<= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

刪除數據

我們插入有頭插，尾插，萬能插

那同理，我們刪除也有頭刪，尾刪，萬能刪

同樣，這邊頭刪，尾刪都可以用萬能刪來替代，所以刪除部分我們主要介紹萬能刪

萬能刪SLErase

如果想要刪除在pos位置的元素，我們可以讓pos后面的數據全部往前挪，用后面的數據覆蓋掉pos位置的數據即可完成刪除，結束后size--，有效數據-1

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(ps->size >pos);
	int begin = pos + 1;
	while (beginsize)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

查詢SLFind

這個操作主要是用于尋找在順序表中第一個出現的元素x的位置，如果沒有找到則返回-1

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i< ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

如果我們想要找到所有值為x的數組，也可以這么寫，增加一個形參begin用于表示查詢開始的下標位置

int SLFind1(SL* ps, SLDataType x, int begin)
{
	assert(ps);

	for (int i = begin; i< ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

SL s1;
	int pos = 0;
	while (SLFind1(&s1, 1, pos) != -1)
	{
		pos = SLFind1(&s1, 1, pos);
	}

這樣每次SLFind1返回值就是想要查找的元素的位置

打印順序表SLPrint

打印時下標從0開始打印，從圖可以看到，size所指向的下標是未使用的位置，所以打印size-1結束即可

void SLPrint(SL* ps)
{
	assert(ps);

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

好了我們的順序表的介紹到這里就結束了，如果有錯誤歡迎在評論區指出

寫文不易，可以給個贊嗎

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享題目：【初識數據結構】c語言實現動態順序表（已配圖）-創新互聯
URL標題：http://vcdvsql.cn/article24/cecdje.html

成都網站建設公司_創新互聯，為您提供網站收錄、網站設計、服務器托管、全網營銷推廣、響應式網站、App設計

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯