順序表前言

順序表作為數(shù)據(jù)結(jié)構(gòu)的入門知識(shí)，整體知識(shí)較為簡(jiǎn)單，主要對(duì)動(dòng)態(tài)內(nèi)存開辟 結(jié)構(gòu)體 指針有要求，其余難度較低

順序表要實(shí)現(xiàn)的功能

順序表主要需要實(shí)現(xiàn)的有順序表的增刪查改和定向搜索銷毀等，具體實(shí)現(xiàn)函數(shù)如下

// 對(duì)數(shù)據(jù)的管理:增刪查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);

void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);

// 順序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 順序表刪除pos位置的值
void SeqListErase(SeqList* ps, int pos);

定義順序表

要實(shí)現(xiàn)順序表，就需要對(duì)順序表進(jìn)行定義，在c語言中通常使用結(jié)構(gòu)體進(jìn)行寫入，包括順序表的容量，順序表中存在元素的個(gè)數(shù)，順序表的主體

在對(duì)順序表的定義中存在兩種，如果不使用動(dòng)態(tài)內(nèi)存開辟，可以直接定義一個(gè)數(shù)組實(shí)現(xiàn)順序表，但由于數(shù)組容量是固定的，會(huì)把整個(gè)順序表固定大小，于是在這里采用動(dòng)態(tài)內(nèi)存開辟的方法實(shí)現(xiàn)順序表

首先對(duì)順序表進(jìn)行定義

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SeqList;

接下來我們就對(duì)順序表的各項(xiàng)功能進(jìn)行依次實(shí)現(xiàn)

順序表初始化

把順序表的結(jié)構(gòu)體定義完成后就可以創(chuàng)建一個(gè)順序表了，創(chuàng)建好初始值后就要對(duì)順序表進(jìn)行一定的初始化內(nèi)容

代碼實(shí)現(xiàn)如下

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = 4;
}

關(guān)于assert函數(shù)

assert的作用是斷言，主要是用來進(jìn)行條件判斷，例如這里檢測(cè)ps，意思就是檢測(cè)ps是否為空指針，如果ps是空指針后續(xù)的操作就不必而行了，這樣有利于檢查錯(cuò)誤信息，當(dāng)運(yùn)行到該語句結(jié)論為假時(shí)，會(huì)直接終止代碼，算是暴力檢查的一種方法

順序表的銷毀

創(chuàng)建完順序表后就要對(duì)順序表進(jìn)行銷毀，銷毀的就是把它對(duì)應(yīng)的空間釋放，置空指針，返回初始值

代碼實(shí)現(xiàn)如下

void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

關(guān)于置空指針

一般來說，把相關(guān)空間釋放后為了避免出現(xiàn)野指針的情況要把指針置空，但不進(jìn)行指針的置空在一些情況下也是可以的，一般釋放空間后都會(huì)緊跟置空指針

打印順序表

將順序表里的信息打印到屏幕上，進(jìn)行可視化觀察有無錯(cuò)誤信息

代碼實(shí)現(xiàn)如下

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

順序表的尾插

將一個(gè)數(shù)據(jù)插入到順序表中就涉及到了順序表的尾插

思路也很簡(jiǎn)單，首先看原來順序表的容量是否滿足要求，如果不滿足就進(jìn)行一定的擴(kuò)容，再把要插入的數(shù)據(jù)放到順序表的尾部即可

如何實(shí)現(xiàn)檢查容量？

如果順序表的size和capacity是一致的，說明已經(jīng)滿了，到達(dá)上限了

因此函數(shù)實(shí)現(xiàn)如下

void SLCheckCapacity(SeqList* ps)
{
	assert(ps);
	SLDateType* tmp = NULL;
	if (ps->capacity == ps->size)
	{
		tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
		printf("擴(kuò)容成功 當(dāng)前容量%d\n", ps->capacity);
	}
}

但是由于后續(xù)還有再規(guī)定位置插入元素的情況，我們可以直接先寫在x位置插入元素的情況

因此函數(shù)實(shí)現(xiàn)就變成了實(shí)現(xiàn)在x位置插入元素

函數(shù)實(shí)現(xiàn)如下

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (pos <= end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size ++ ;
}

有了在x位置插入元素函數(shù)的實(shí)現(xiàn)，對(duì)于在尾部插入函數(shù)只需要將x換成size即可

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	assert(ps);
	SeqListInsert(ps,ps->size,x);
}

順序表的頭插

和順序表的尾插相似，當(dāng)我們有了在x位置插入元素的函數(shù)時(shí)，這些需求就很好寫了

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	assert(ps);
	SeqListInsert(ps, 0, x);
}

順序表的頭刪

有了前面的想法，我們也把在x位置的元素進(jìn)行刪除封裝成一個(gè)函數(shù)

函數(shù)實(shí)現(xiàn)如下

void SeqListErase(SeqList* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int end = ps->size-1;
	while (pos <= end)
	{
		ps->a[pos] = ps->a[pos + 1];
		pos++;
	}
	ps->size--;
}

那么頭刪就是把標(biāo)號(hào)為0的元素刪除

具體函數(shù)實(shí)現(xiàn)如下

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	SeqListErase(ps, 0);
}

順序表的尾刪

有了頭刪的想法，尾刪和頭刪基本一致

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	int end = ps->size - 1;
	SeqListErase(ps, end);
}

順序表定向位置查找

最簡(jiǎn)單的功能，只需要遍歷順序表即可

int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	for(int i=0;i<ps->size;i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}

整體來說順序表是數(shù)據(jù)結(jié)構(gòu)入門的部分，難度偏低文章來源地址http://www.zghlxwxcb.cn/news/detail-565632.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)---手撕順序表---順序表增刪查改尋找功能的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！