日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無(wú)先后，達(dá)者為師

網(wǎng)站首頁(yè) 編程語(yǔ)言 正文

C語(yǔ)言深入淺出講解順序表的實(shí)現(xiàn)_C 語(yǔ)言

作者：scut-ALong ? 更新時(shí)間： 2022-06-14 編程語(yǔ)言

今天起開(kāi)始編寫(xiě)數(shù)據(jù)結(jié)構(gòu)中的各種數(shù)據(jù)結(jié)構(gòu)及算法的實(shí)現(xiàn)，說(shuō)到順序表，我們首先得了解下線(xiàn)性表。

1.線(xiàn)性表

線(xiàn)性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線(xiàn)性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線(xiàn)性表：順序表、鏈表、棧、隊(duì)列、字符串…

線(xiàn)性表在邏輯上是線(xiàn)性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線(xiàn)。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線(xiàn)性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

線(xiàn)性表的存儲(chǔ)

2.順序表

2.1 概念及結(jié)構(gòu)

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

1.靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)。

2.動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)。

//順序表的靜態(tài)存儲(chǔ) 
#define N 100
struct SeqList
{
	int a[N];//定長(zhǎng)存儲(chǔ)
	int size;//有效數(shù)據(jù)的個(gè)數(shù)
};

//順序表的動(dòng)態(tài)存儲(chǔ)
typedef struct SeqList
{
	SeqDataType* a;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組
	int size;	  //有效數(shù)據(jù)個(gè)數(shù)
	int capacity; //容量
}SeqList;

順序表本質(zhì)上是數(shù)組，在數(shù)組上增加了兩個(gè)要求：

1.插入數(shù)據(jù)的過(guò)程中，可以動(dòng)態(tài)增長(zhǎng)

2.并且要求里面存儲(chǔ)的數(shù)據(jù)必須是從左往右，是連續(xù)的

順序表的缺陷

1.動(dòng)態(tài)增容有性能消耗

2.頭部插入數(shù)據(jù)時(shí)，需要挪動(dòng)數(shù)據(jù)

2.2 提供接口

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了，空間開(kāi)多了浪費(fèi)，開(kāi)少了不夠用。所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表，根據(jù)需要?jiǎng)討B(tài)的分配空間大小，所以下面我們來(lái)實(shí)現(xiàn)動(dòng)態(tài)順序表。

首先在頭文件<SeqList.h>中提供接口：

typedef int SeqDataType; //需要插入什么類(lèi)型的數(shù)據(jù)，就改成對(duì)應(yīng)類(lèi)型

typedef struct SeqList
{
	SeqDataType* a;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組
	int size;	  //有效數(shù)據(jù)個(gè)數(shù)
	int capacity; //容量
}SeqList;

//內(nèi)存中管理數(shù)據(jù)結(jié)構(gòu) 提供增刪查改的接口
//順序表初始化
void SeqListInit(SeqList* pq);
//順序表銷(xiāo)毀
void SeqListDestory(SeqList* pq);
//順序表打印
void SeqListPrint(SeqList* pq);//打印數(shù)組
//檢查空間，如果滿(mǎn)了，進(jìn)行增容
void SeqCheckCapacity(SeqList* pq)
//順序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//順序表頭插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//順序表尾刪
void SeqListPopBack(SeqList* pq);
//順序表頭刪
void SeqListPopFront(SeqList* pq);
//順序表查找x
int SeqListFind(SeqList* pq, SeqDataType x);//查找 查到返回下標(biāo)，沒(méi)查到返回-1
//順序表在指定位置插入數(shù)據(jù)
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下標(biāo)pos位置處插入數(shù)據(jù)
//順序表在指定位置刪除數(shù)據(jù)
void SeqListErase(SeqList* pq, int pos);//把下標(biāo)為pos位置處的數(shù)據(jù)刪除
//順序表在指定位置替換數(shù)據(jù)
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小標(biāo)為pos位置的值改為x

2.3 接口實(shí)現(xiàn)

在源文件SeqList.c中實(shí)現(xiàn)接口功能

（1）順序表初始化

void SeqListInit(SeqList* pq)
{
	assert(pq != NULL);//或者 assert(pq); 斷言 防止傳入空指針
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

（2）順序表銷(xiāo)毀

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

（3）順序表打印

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

（4）檢查空間，如果滿(mǎn)了，進(jìn)行增容

//檢查是否需要擴(kuò)容
void SeqCheckCapacity(SeqList* pq)
{
	//滿(mǎn)了，需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);

		//realloc接收的地址如果為空，將像malloc一樣，開(kāi)辟一塊新空間
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 開(kāi)辟的新空間的地址
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//失敗了就退出
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

（5）順序表尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
{
	assert(pq);

	SeqCheckCapacity(pq);

	pq->a[pq->size] = x;
	pq->size++;
}

（6）順序表頭插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);

	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= 0)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[0] = x;
	pq->size++;
}

（7）順序表尾刪

void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	pq->size--;
}

（8）順序表頭刪

void SeqListPopFront(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);

	int begin = 0;
	while (begin < pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

（9）順序表查找x

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return x;
		}
	}
	return -1;//沒(méi)找到
}

（10）順序表在指定位置插入數(shù)據(jù)

void SeqListInsert(SeqList* pq, int pos, SeqDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->assert(pq);assert(pos >= 0 && pos < pq->size);SeqCheckCapacity(pq);//檢查是否需要擴(kuò)容int end = pq->size - 1;while (end >= pos){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->pq->a[end + 1] = pq->a[end];end--;}pq->a[pos] = x;pq->size++;}void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	SeqCheckCapacity(pq);//檢查是否需要擴(kuò)容

	int end = pq->size - 1;
	while (end >= pos)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[pos] = x;
	pq->size++;
}

（11）順序表在指定位置刪除數(shù)據(jù)

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

（12）順序表在指定位置替換數(shù)據(jù)

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	pq->a[pos] = x;
}

主函數(shù)的設(shè)計(jì)大家可以自由發(fā)揮，做個(gè)簡(jiǎn)單的測(cè)試功能調(diào)用函數(shù)或是創(chuàng)建菜單欄實(shí)現(xiàn)交互都可以。我水平有限，請(qǐng)朋友們諒解！寫(xiě)的不好的地方還請(qǐng)大佬們指出。

下期預(yù)告——單鏈表

原文鏈接：https://blog.csdn.net/qq_43460230/article/details/124160112

欄目分類(lèi)
最近更新