本期帶大家一起來用C語言代碼實現(xiàn)順序表??????

一、順序表的概念?

順序表是一段物理地址連續(xù)的存儲單元，依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。分為靜態(tài)順序表與動態(tài)順序表。 ?? ?? ??

二、順序表的結(jié)構(gòu)?

靜態(tài)順序表：使用定長數(shù)組用來存儲數(shù)據(jù)
優(yōu)點：操作簡單，代碼實現(xiàn)容易
缺點：定長數(shù)組很受限制，數(shù)組開小了不夠用，開大了又浪費

動態(tài)順序表：使用動態(tài)開辟的數(shù)組進行存儲數(shù)據(jù)
優(yōu)點：數(shù)組可以根據(jù)自己的需求進行調(diào)解
缺點：代碼過于復(fù)雜

三、順序表的實現(xiàn)（動態(tài)順序表）?

這里先建立三個文件：
1?? ：SeqList.h文件，用于函數(shù)聲明
2?? ：SeqList.c文件，用于函數(shù)的定義
3?? ：Test.c文件，用于測試函數(shù)
建立三個文件的目的： 將順序表作為一個項目來進行書寫，方便我們的學(xué)習(xí)與觀察。

一、??定義順序表結(jié)構(gòu)體??

順序表結(jié)構(gòu)體里面的成員基本的有
指向動態(tài)開辟的空間的指針a??
當(dāng)前順序表當(dāng)中存儲的數(shù)據(jù)個數(shù)size??
以及順序表當(dāng)前的容量capacity??

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType* a;
	int size;
	int capacity;

}SL;

這里我們使用typedef對我們所存儲的數(shù)據(jù)，以及順序表結(jié)構(gòu)體重命名，方便我們后續(xù)修改 ?? ?? ??

二、??接口的實現(xiàn)??

1.接口：初始化結(jié)構(gòu)體（SLInit）????

這里我們對結(jié)構(gòu)體里面的內(nèi)容進行初始化

初始化為容量為4，所存儲的數(shù)據(jù)個數(shù)為0，并且利用malloc函數(shù)進行動態(tài)開辟

void SLInit(SL* psl)
{
	assert(psl);

	psl->a = (SLTDataType*)malloc(sizeof(SLTDataType) * 4);
	if (psl->a == NULL)
	{
		perror("psl::null");
		return;
	}
	psl->capacity = 4;
	psl->size = 0;

}

2.接口：擴容順序表????

我們往順序表當(dāng)中添加數(shù)據(jù)的時候，需要判斷順序表當(dāng)中數(shù)據(jù)的個數(shù)是否達到了最大容量
如果達到了最大容量，則進行擴容?? ??

void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)
	{
		SLTDataType* tmp = (SLTDataType*)realloc(psl->a,sizeof(SLTDataType) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc:null");
			return;
		}
		psl-> a= tmp;
		psl->capacity *= 2;
	}
}

3.接口：頭插數(shù)據(jù)????

當(dāng)我們需要在順序表的開頭第一個位置插入數(shù)據(jù)的時候，我們需要進行如下操作?? ?? ??

錯誤想法：

這里是引用但是當(dāng)我們從前面往后面進行覆蓋的話，那么原來的數(shù)據(jù)都會被覆蓋掉，所以這是一個錯誤的想法?? ?? ??

正確想法：

void STLpushfront(SL* psl, SLTDataType s)
{
	SLCheckCapacity(psl);

	for (int i = 0; i < psl->size; i++)
	{
		psl->a[psl->size - i] = psl->a[psl->size - i - 1];

	}
	psl->a[0] = s;

	psl->size++;
}

4.接口：尾插數(shù)據(jù)????

尾插數(shù)據(jù)相對于頭插數(shù)據(jù)來說是比較簡單的?? ?? ??
首先我們需要先檢查順序表當(dāng)中的有效數(shù)據(jù)是否已經(jīng)達到了當(dāng)前的容量然后
只需要將我們需要插入的數(shù)據(jù)插在順序表當(dāng)中有效數(shù)據(jù)的后面一個就行
同時讓我們順序表當(dāng)中的有效數(shù)據(jù)加一即可 ?? ?? ??

void STLpushback(SL* psl,SLTDataType s)
{
	SLCheckCapacity(psl);
	psl->a[psl->size] = s;
	psl->size++;

}

5.接口：頭刪數(shù)據(jù)????

我們刪除數(shù)據(jù)的時候，需要將頭部的數(shù)據(jù)進行刪除
這時候我們需要采取覆蓋的原理來實現(xiàn)

void SLPopFront(SL* psl)
{
	if (psl->size == 0)
	{
		printf("順序表當(dāng)中數(shù)據(jù)為空\n");
		return;
	}
	
	for (int i = 0; i < psl->size; i++)
	{
		psl->a[i] = psl->a[i + 1];

	}
	psl->size--;

}

6.接口：尾刪數(shù)據(jù)????

尾刪數(shù)據(jù)的話同尾插數(shù)據(jù)的原理是一樣的
只需要將順序表當(dāng)中的有效數(shù)據(jù)的個數(shù)進行變化就行?? ?? ?? ??

void SLPopBack(SL* psl)
{
	if (psl->size == 0)
	{
		printf("順序表當(dāng)中數(shù)據(jù)為空\n");
		return;
	}
	psl->size--;
}

7.接口：在指定位置插入數(shù)據(jù)（SLInsert）????

當(dāng)然，添加數(shù)據(jù)的話不僅僅局限于我們的頭插和尾插數(shù)據(jù)
還可以是在指定下標(biāo)pos進行插入數(shù)據(jù)
函數(shù)的原型：void SLInsert(SL* ps, int pos, SLDateType x)
注意：要實現(xiàn)這一功能，我們依然需要一個end下標(biāo)，數(shù)據(jù)從后往前依次后挪，直到pos下標(biāo)移動完畢?? ??
另外，別忘了檢查容量。

我們首先需要找到當(dāng)前順序表最后一個位置的數(shù)據(jù)
然后將前面的數(shù)據(jù)賦給后一個位置?? ?
直到找到我們的pos位置，將我們需要添加的數(shù)據(jù)添加到順序表當(dāng)中
同樣在開始的時候需要檢查是否擴容

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

	psl->a[pos] = x;
	psl->size++;

}

函數(shù)拓展：該功能其實也可以實現(xiàn)頭插和尾插，所以我們可以在頭插和尾插中復(fù)用該功能

// 頭插
void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListInsert(ps, 0, x);
}
 
// 尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListInsert(ps, ps->sz, x);
}

8.接口：在指定位置刪除數(shù)據(jù)????

同我們的在指定位置添加數(shù)據(jù)一樣
當(dāng)我們需要在指定位置刪除數(shù)據(jù)的時候?? ?
我們需要傳入一個下標(biāo)pos進行刪除的操作

然后我們需要將從下標(biāo)開始的數(shù)據(jù)改為下標(biāo)+1的數(shù)據(jù)

例如 a=a+1

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	for (int i = pos; i < psl->size - 1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}

	psl->size--;

}

函數(shù)拓展：該功能其實也可以實現(xiàn)頭刪和尾插=刪，所以我們可以在頭刪和尾插】刪中復(fù)用該功能

// 頭刪
void SeqListPopFront(SL* ps)
{
	SeqListErase(ps, 0);
}
 
// 尾刪
void SeqListPopBack(SL* ps)
{
	SeqListErase(ps, ps->sz - 1);
}

9.接口：查找某一個數(shù)據(jù)的位置（SLFind）????

查找順序表當(dāng)中是否存在某個數(shù)據(jù)

如果存在的話就返回所對應(yīng)的下標(biāo)
不存在的話則返回-1

int SLFind(SL* psl, SLTDataType x)
{

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

10.接口：修改指定下標(biāo)的數(shù)據(jù)????

首先判斷傳入的下標(biāo)是否合法???
合法的話則將對應(yīng)下標(biāo)的數(shù)據(jù)修改

void SLModify(SL* psl, int pos, SLTDataType x)
{
	assert(psl);

	assert(0 < pos && pos < psl->size);

	psl->a[pos] = x;
}

接口11：打印函數(shù)（SLprint）????

主要利用順序表當(dāng)中有效數(shù)據(jù)的個數(shù)進行數(shù)據(jù)的打印?? ??

void SLprint(SL* psl)
{

	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		/*printf("%d ", *(psl->a + i));*/

		printf("%d ", psl->a[i]);
	}
	printf("\n");

}

接口12：銷毀（SLDestory）????

由于我們的順序表是動態(tài)開辟出來的的
所以我們需要在結(jié)束程序的時候需要將開辟出來的空間進行銷毀
避免內(nèi)存泄漏?? ??

void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);

	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;

}

四、順序表的應(yīng)用小項目?

順序表實現(xiàn)通訊錄

五、感謝與交流?

??????如果大家通過本篇博客收獲了,對順序表有了新的了解的話
那么希望支持一下哦如果還有不明白的，疑惑的話，或者什么比較好的建議的話，可以發(fā)到評論區(qū)，
我們一起解決，共同進步 ??????
最后謝謝大家????????????

文章來源地址http://www.zghlxwxcb.cn/news/detail-423391.html

到了這里，關(guān)于順序表—C語言實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！