順序表前言

順序表作為數(shù)據(jù)結構的入門知識，整體知識較為簡單，主要對動態(tài)內存開辟 結構體 指針有要求，其余難度較低

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

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

// 對數(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);

定義順序表

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

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

首先對順序表進行定義

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

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

順序表初始化

把順序表的結構體定義完成后就可以創(chuàng)建一個順序表了，創(chuàng)建好初始值后就要對順序表進行一定的初始化內容

代碼實現(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;
}

關于assert函數(shù)

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

順序表的銷毀

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

代碼實現(xiàn)如下

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

關于置空指針

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

打印順序表

將順序表里的信息打印到屏幕上，進行可視化觀察有無錯誤信息

代碼實現(xiàn)如下

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

順序表的尾插

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

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

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

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

因此函數(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("擴容成功 當前容量%d\n", ps->capacity);
	}
}

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

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

函數(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ù)的實現(xiàn)，對于在尾部插入函數(shù)只需要將x換成size即可

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

順序表的頭插

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

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

順序表的頭刪

有了前面的想法，我們也把在x位置的元素進行刪除封裝成一個函數(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--;
}

那么頭刪就是把標號為0的元素刪除

具體函數(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);
}

順序表定向位置查找

最簡單的功能，只需要遍歷順序表即可

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ù)結構入門的部分，難度偏低文章來源地址http://www.zghlxwxcb.cn/news/detail-612796.html

到了這里，關于數(shù)據(jù)結構：手撕順序表---順序表增刪查改尋找功能的實現(xiàn)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！