腳本之家服務器常用軟件

快捷導航

C語言?超詳細順序表的模擬實現(xiàn)實例建議收藏

更新時間：2022年03月25日 14:36:15 作者：鹿九丸

程序中經常需要將一組數(shù)據(jù)元素作為整體管理和使用，需要創(chuàng)建這種元素組，用變量記錄它們，傳進傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個數(shù)可能發(fā)生變化，順序表則是將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關系由它們的存儲順序自然表示

1 順序表的動態(tài)存儲
2 順序表初始化
3 順序表的銷毀
4 順序表的尾插
5 順序表的尾刪
6 順序表的頭插
7 順序表的頭刪
8 順序表容量的檢查與擴容
9 順序表任意位置的插入
10 順序表任意位置的刪除
11 順序表的打印
12 順序表元素的查找
13 順序表元素的修改

概念及結構

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

順序表一般可以分為：

靜態(tài)順序表：使用定長數(shù)組存儲元素，元素的數(shù)目無法進行修改。

//順序表的靜態(tài)存儲
#define N 7
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType array[N];//定長數(shù)組
	size_t size;//有效數(shù)據(jù)的個數(shù)
}SeqList;

動態(tài)順序表

//順序表的動態(tài)存儲
typedef struct SeqList
{
	SLDataType* array;//指向動態(tài)開辟的數(shù)組，空間不夠可以增容
	size_t size;//有效數(shù)據(jù)的個數(shù)
	size_t capacity;//容量空間的大小
};

接口實現(xiàn)

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導致N定大了，空間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實現(xiàn)動態(tài)順序表。

1 順序表的動態(tài)存儲

typedef int SLDataType;//順序表中存儲的數(shù)據(jù)，此處假設是int型
typedef struct SeqList
{
	int* a;//指向動態(tài)開辟的數(shù)組空間，空間可以隨時增容
	int size;//存儲數(shù)據(jù)個數(shù)
	int capacity;//存儲空間大小
}SL,SeqList;

2 順序表初始化

void SeqListInit(SeqList* psl);//聲明
void SeqListInit(SeqList* psl)
{
	assert(psl);//進行斷言是因為當psl為NULL時，下面的操作將無法進行，因為空指針是無法進行解引用的。
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}//函數(shù)實現(xiàn)

注意：進行斷言是因為當psl為NULL時，下面的操作將無法進行，因為空指針是無法進行解引用的，后面也是如此。

3 順序表的銷毀

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

注意：free后面括號中的指針必須是malloc開辟出來的那塊空間，且不能有任何的偏差（即指針不能發(fā)生移動）。

下面進行舉例：

像上面這樣使用是完全沒有問題的，但是像下面這樣進行使用就出現(xiàn)了問題：

tmp進行自增操作后，就指向了下圖所示位置：

free的位置是tmp++后的位置，這不符合C語言的規(guī)定，且即使正常的釋放掉了，前面的那一塊int空間也將引起內存泄漏問題，即動態(tài)開辟的內存忘記釋放。

4 順序表的尾插

void SeqListPushBack(SeqList* psl,SLDataType x);//聲明
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	//如果滿了，就進行擴容
	SeqListCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

5 順序表的尾刪

void SeqListPopBack(SeqList* psl);
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	if(psl->size > 0)
	{
		psl->size -= 1;
	}
}

6 順序表的頭插

void SeqListPushFront(SeqList* psl, SLDataType x);
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end+1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;
}

順序表的頭插會涉及到后續(xù)元素的移動，頭插時要將順序表中的元素從后面開始進行移動，因為從前面開始移動的話會出現(xiàn)覆蓋現(xiàn)象。下面是圖示：

7 順序表的頭刪

同理，如果想要元素不被覆蓋，就只能從前向后進行移動。

void SeqListPopFront(SeqList* psl);
void SeqListPopFront(SeqList* psl)
{
	//挪出數(shù)據(jù)，騰出頭部空間
	//方法一：從1開始移動
	/*assert(psl);
	if (psl->size > 0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
		psl->size--;
	}*/
	//方法二：從0開始移動
	assert(psl);
	if (psl->size > 0)
	{
		int begin = 0;
		while (begin < psl->size - 1)
		{
			psl->a[begin] = psl->a[begin + 1];
			begin++;
		}
		psl->size--;
	}
}

下圖是兩種移動方式的區(qū)別：

問：為什么不可以直接將指針進行加1操作？

free釋放空間時的指針和malloc開辟空間的指針必須相同
mallo開辟的空間存在浪費，即0的那塊空間被浪費，無法進行使用，因為那塊空間是被合法申請的。

8 順序表容量的檢查與擴容

void SeqListCheckCapacity(SeqList* psl);
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->capacity == psl->size)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity *= 2;
		}
	}
}

注意點1：此處考慮使用的是如果容量不夠，就將容量擴容為原容量的兩倍，但是最開始的容量是0，所以要考慮到最開始為0的情況。

注意點2：要對擴容是否成功進行檢測，即判斷剛申請的空間是否為空。

9 順序表任意位置的插入

void SeqListInsert(SeqList* psl,size_t pos,SLDataType x);
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	//較為溫和的檢查方式
	/*if (pos > psl->size)
	{
		exit(-1);
	}*/
	assert(pos <= psl->size);//較為暴力的檢查方式
	SeqListCheckCapacity(psl);
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end-1];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}

注意：

問：為什么end從psl->size開始？

答：此處需要注意的是pos和end的類型，為什么呢？因為兩者都是無符號類型，所以尤其注意當end到了-1的時候，就會變成一個很大的數(shù)字，此時如果以此作為下標進行訪問，一定會出現(xiàn)越界訪問內存的情況，考慮一種極端情況，當pos為0的時候，end最小的時候就是為0，所以此時不會出現(xiàn)越界的情況，但是如果end是從psl->size - 1開始的話，那么while循環(huán)體內的語句就變成下面這樣：

while(end > pos)
{
	psl->a[end+1] = psl->a[end];
	--end;
}

最后end的最小值會變成-1，但是因為end是size_t類型，所以會變成一個很大的數(shù)字，在whle()循環(huán)條件判定時條件始終是滿足的，同時在進入循環(huán)體內之后，會出現(xiàn)越界訪問內存的操作。所以兩種情況的圖如下所示：

10 順序表任意位置的刪除

void SeqListErase(SeqList* psl, size_t pos);
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos <= psl->size);
	size_t begin = pos+1;
	while (begin < psl->size)
	{
		psl->a[begin-1] = psl->a[begin];
		++begin;
	}
	psl->size--;
}

11 順序表的打印

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

12 順序表元素的查找

int SeqListFind(SeqList* psl,SLDataType x);
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
			return i;//找到了對應元素，返回相應的下標
	}
	return -1;//說明沒有找到對應的元素
}

13 順序表元素的修改

void SeqListModify(SeqList* psl, size_t pos, SLDataType x);
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;
}

到此這篇關于C語言超詳細順序表的模擬實現(xiàn)實例建議收藏的文章就介紹到這了,更多相關C語言順序表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: