前言?

成都創(chuàng)新互聯(lián)長(zhǎng)期為千余家客戶(hù)提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為阿巴嘎企業(yè)提供專(zhuān)業(yè)的網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)，阿巴嘎網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

大家好啊，這里是幸麟

一名普通的大學(xué)牲

🧩希望通過(guò)寒假多學(xué)一些知識(shí)，對(duì)自己進(jìn)行一些有益的補(bǔ)充

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

目錄

什么是順序表

接口

初始化SLInit

順序表空間檢查&擴(kuò)容

插入元素

頭插SLPushFront

尾插

萬(wàn)能插SLInsert

刪除數(shù)據(jù)

萬(wàn)能刪SLErase

查詢(xún)SLFind

打印順序表SLPrint

---

---

什么是順序表

順序表是線性表的一種，是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。

但其存儲(chǔ)并不像數(shù)組那樣可以在其區(qū)間內(nèi)任意位置存儲(chǔ)，順序表需要依次存儲(chǔ)，正如其名，只有存儲(chǔ)完上一位置后才能存儲(chǔ)下一位置

順序表：（自己做的可能有點(diǎn)不太好看哈），其中size代表下一個(gè)要存儲(chǔ)在a數(shù)組內(nèi)的元素下標(biāo)，也代表有效數(shù)據(jù)的數(shù)量

其中順序表可以分為采用定長(zhǎng)數(shù)組進(jìn)行存儲(chǔ)的靜態(tài)順序表和使用動(dòng)態(tài)開(kāi)辟數(shù)組的動(dòng)態(tài)順序表

其中靜態(tài)順序表由于是采用定長(zhǎng)數(shù)組進(jìn)行存儲(chǔ)，常常會(huì)有數(shù)組開(kāi)大了空間浪費(fèi)，數(shù)組開(kāi)小了不夠用的窘?jīng)r，所以實(shí)際中還是動(dòng)態(tài)順序表使用居多

接口

其中我們用typedef定義我們創(chuàng)建的結(jié)構(gòu)體seqlist為SL，這樣寫(xiě)起來(lái)時(shí)方便一些

同時(shí)由于我們可能更改順序表中存儲(chǔ)數(shù)據(jù)的類(lèi)型，為了方便日后可能有的調(diào)整我們定義一個(gè)數(shù)據(jù)類(lèi)型SLDataType，這里先使用int，如果以后想將存儲(chǔ)數(shù)據(jù)類(lèi)型為longlong的元素直接更改SLDataType即可

#pragma once
#include#include 
#includeusing namespace std;
typedef int SLDataType ;
typedef struct Seqlist
{
	SLDataType* a;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組
	int size;//有效數(shù)據(jù)的大小，同時(shí)也是下一個(gè)數(shù)據(jù)存儲(chǔ)位置
	int capacity;//順序表空間的大小
}SL;

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

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

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

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

初始化SLInit

在初始化時(shí)，我們要注意ps所指向的地址是不是空指針，如果是空指針程序會(huì)錯(cuò)誤，所以這邊加了一個(gè)斷言判斷，剛開(kāi)始的順序表空間與有效數(shù)據(jù)大小都沒(méi)有，所以直接賦0

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

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

順序表空間檢查&擴(kuò)容

在每一次進(jìn)行插入操作時(shí)我們都應(yīng)該進(jìn)行一次空間的檢查，如果發(fā)現(xiàn)以使用的有效數(shù)據(jù)大小與順序表空間相等時(shí)就需要使用realloc函數(shù)對(duì)其進(jìn)行擴(kuò)容（一般擴(kuò)大的容量為原來(lái)的兩倍），在給newcapacity賦值時(shí)可以加一個(gè)判斷，如果capacity并沒(méi)有容量（即為0時(shí)），則讓newcapacity=4，給予一個(gè)初始的空間

值得注意的是使用realloc函數(shù)申請(qǐng)空間時(shí)，可能會(huì)出現(xiàn)以下三種情況

①數(shù)組a原本的地址后面有充足的空余空間，擴(kuò)容結(jié)束后返回原來(lái)數(shù)組a的地址

②數(shù)組a原本的地址后面并沒(méi)有足夠的空間用來(lái)擴(kuò)容，這時(shí)候就需要重新找一個(gè)地址進(jìn)行擴(kuò)容，所以這時(shí)候會(huì)返回一個(gè)新的地址

③realloc有可能擴(kuò)容失敗，返回一個(gè)空指針NULL

所以我們這里用用一個(gè)指針tmp用來(lái)接收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

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

創(chuàng)建一個(gè)變量end，從size-1,即最后一個(gè)數(shù)據(jù)的下標(biāo)開(kāi)始，把每一個(gè)數(shù)據(jù)往后挪一個(gè)位置，直到移完第一個(gè)數(shù)據(jù)，然后再將所要插入的數(shù)據(jù)插入即可，插入結(jié)束后size++，有效數(shù)據(jù)＋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++;
}

代碼：

尾插

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

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

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

萬(wàn)能插SLInsert

所有的插入，都可以用萬(wàn)能插實(shí)現(xiàn)，頭插和尾插也都是萬(wàn)能插的一種特殊情況

頭插相當(dāng)在pos=0時(shí)的萬(wàn)能插，尾插相當(dāng)于pos=size-1時(shí)的萬(wàn)能插

，我們用pos表示想要插入的位置，同時(shí)pos有效范圍為[0,size-1]，如果超出這個(gè)范圍會(huì)出錯(cuò)，所以這邊加個(gè)斷言，移動(dòng)數(shù)據(jù)的時(shí)候同樣使用從size-1開(kāi)始移動(dòng)，直到把原本下標(biāo)為pos的數(shù)據(jù)移走，然后在pos位置插入新數(shù)據(jù)，結(jié)束后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++;
}

刪除數(shù)據(jù)

我們插入有頭插，尾插，萬(wàn)能插

那同理，我們刪除也有頭刪，尾刪，萬(wàn)能刪

同樣，這邊頭刪，尾刪都可以用萬(wàn)能刪來(lái)替代，所以刪除部分我們主要介紹萬(wàn)能刪

萬(wàn)能刪SLErase

如果想要?jiǎng)h除在pos位置的元素，我們可以讓pos后面的數(shù)據(jù)全部往前挪，用后面的數(shù)據(jù)覆蓋掉pos位置的數(shù)據(jù)即可完成刪除，結(jié)束后size--，有效數(shù)據(jù)-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--;
}

查詢(xún)SLFind

這個(gè)操作主要是用于尋找在順序表中第一個(gè)出現(xiàn)的元素x的位置，如果沒(méi)有找到則返回-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的數(shù)組，也可以這么寫(xiě)，增加一個(gè)形參begin用于表示查詢(xún)開(kāi)始的下標(biāo)位置

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

打印時(shí)下標(biāo)從0開(kāi)始打印，從圖可以看到，size所指向的下標(biāo)是未使用的位置，所以打印size-1結(jié)束即可

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

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

好了我們的順序表的介紹到這里就結(jié)束了，如果有錯(cuò)誤歡迎在評(píng)論區(qū)指出

寫(xiě)文不易，可以給個(gè)贊嗎

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：【初識(shí)數(shù)據(jù)結(jié)構(gòu)】c語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表（已配圖）-創(chuàng)新互聯(lián)
URL標(biāo)題：http://www.rwnh.cn/article24/cecdje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、網(wǎng)站設(shè)計(jì)、服務(wù)器托管、全網(wǎng)營(yíng)銷(xiāo)推廣、響應(yīng)式網(wǎng)站、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)