順序表的理解：

線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。

順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個(gè)元素、使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系，采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組地址連續(xù)的存儲單元中。

靜態(tài)順序表就是像數(shù)組一樣的大小固定的，動態(tài)的可以在容量不夠時(shí)進(jìn)行擴(kuò)容而達(dá)到能夠存儲大量數(shù)據(jù)的效果?。。?/p>

一、先創(chuàng)建一個(gè)結(jié)構(gòu)體來表示順序表

typedef int DATE;//重命名順序表的數(shù)據(jù)類型
typedef struct ArrayList {
	DATE* date;
	size_t size;//順序表長度
	size_t capacity;//順序表容量
}AL;

二、順序表的所有接口展示

void Init(AL* al);
void checkCapacity(AL* al);
void pushBack(AL* al, DATE info);
void pushFront(AL* al, DATE info);
void insertDate(AL* al,size_t pos, DATE info);
void printDate(AL* al);
void Erase(AL* al, size_t pos);
void PopBack(AL* al);
void PopFront(AL* al);
size_t FindDate(AL* al, DATE info);
void ExchangeDate(AL* al, size_t pos, DATE info);
void Deatory(AL* al);

三、每個(gè)接口功能介紹及實(shí)現(xiàn)原理

1、初始化函數(shù)的實(shí)現(xiàn)

void Init(AL* al)
{
	assert(al);
	al->size = 0;
	al->capacity = 4;//初始化容量為4
	DATE* tmp = (DATE*)malloc(sizeof(DATE) * al->capacity);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	al->date = tmp;
}

初始化順序表的長度為0、容量為4！

2、檢查容量函數(shù)的實(shí)現(xiàn)

void checkCapacity(AL* al)
{
	if (al->size == al->capacity)
	{
		DATE* tmp = (DATE*)realloc(al->date, sizeof(DATE) * al->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		al->capacity *= 2;
		al->date = tmp;
		printf("擴(kuò)容成功！\n");
	}
}

如果長度等于容量時(shí)就說明需要擴(kuò)容了，就將容量擴(kuò)到2倍大小

3、尾插函數(shù)的實(shí)現(xiàn)

void pushBack(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	al->date[al->size] = info;
	al->size++;
}

每次插入之前一定要檢查容量
尾插就是在size尾位置寫入需要插入的值，然后要對長度進(jìn)行加一

4、頭插函數(shù)的實(shí)現(xiàn)

void pushFront(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	if (al->size == 0)
	{
		al->date[0] = info;
		al->size++;
	}
	else
	{
		size_t end = al->size;
		while (end)
		{
			al->date[end] = al->date[end-1];
			end--;
		}
		al->date[0] = info;
		al->size++;
	}
}

頭插一個(gè)數(shù)據(jù)，必須將后面的數(shù)據(jù)向后面移動，移動的過程中可能超過容量大小，所以在插入時(shí)都需要進(jìn)行擴(kuò)容判斷

挪動方法如上

5、尾刪函數(shù)

void PopBack(AL* al)
{
    assert(ps);
	assert(al->size > 0);
	al->size--;
}

將長度減一即可刪除最后一個(gè)數(shù)據(jù)

6、頭刪函數(shù)

void PopFront(AL* al)
{
    assert(al->size > 0);
	int begin = 1;
	while (begin<al->size)
	{
		al->date[begin - 1] = al->date[begin];
		begin++;
     }
	al->size--;
}

挪動順序方法如下：

定義一個(gè)變量begin=1,首先是要將數(shù)據(jù)2移動到數(shù)據(jù)1的位置，對應(yīng)的操作是
al->date[begin - 1] = al->date[begin];然后begin++,依次將數(shù)據(jù)3挪到數(shù)據(jù)2的位置，數(shù)據(jù)4挪到數(shù)據(jù)3的位置。循環(huán)最后一次是將數(shù)據(jù)5挪到數(shù)據(jù)4的位置，也就是begin=4,al->size=5.則循環(huán)判斷條件為beginsize,循環(huán)結(jié)束后將
al->size–;

7、任意位置刪除數(shù)據(jù)函數(shù)的實(shí)現(xiàn)

void Erase(AL* al, size_t pos)
{
	assert(al);
	assert(pos >= 0 && pos <= al->size);
	if (al->size == 0)
	{
		printf("暫無數(shù)據(jù)！！\n");
		return;
	}
	size_t end = pos;
	while (end<al->size-1)
	{![在這里插入圖片描述])

		al->date[end] = al->date[end + 1];
		end++;
	}
	al->size--;
}

刪除一個(gè)數(shù)據(jù)，就要將這個(gè)位置之后的元素全部向前挪動一個(gè)位置
由于下標(biāo)易班都有size_t表示，所以一個(gè)要把握好頭刪時(shí)出現(xiàn)無符號-1和0循環(huán)條件比較大小的情況

如果我們要刪除數(shù)3，然后數(shù)據(jù)3后面的數(shù)據(jù)向前挪動，第一步就是將數(shù)據(jù)4移動到數(shù)據(jù)3的位置，定義一個(gè)變量end=pos=2;對應(yīng)的操作為al->date[end] = al->date[end+1];，然后end++;將數(shù)據(jù)5移動到最開始數(shù)據(jù)4的地方。最后一次循環(huán)是將數(shù)據(jù)5移動到數(shù)據(jù)4的地方，也就是end最后等于3，al->size=5，則循環(huán)判斷條件是end< al->size-1,循環(huán)結(jié)束將al->size–;

8、任意位置插入數(shù)據(jù)函數(shù)的實(shí)現(xiàn)

void insertDate(AL* al, size_t pos, DATE info)
{
	assert(al);
	assert(pos >= 0 && pos <= al->size);
	checkCapacity(al);
	int end = al->size;
	while (end > pos)
	{
		al->date[end] = al->date[end - 1];
		end--;
	}
	al->date[pos] = info;
	al->size++;
}

由于下標(biāo)易班都有size_t表示，所以一個(gè)要把握好頭插時(shí)出現(xiàn)無符號-1和0循環(huán)條件比較大小的情況

任意位置插入需要將插入位置及其以后的數(shù)據(jù)一次向后挪動一個(gè)位置！

9、頭插頭刪和頭刪尾刪函數(shù)的改進(jìn)

我們寫完任意插和任意刪后，就可以對頭插頭刪和頭刪尾刪函數(shù)的改進(jìn)，直接在他們的函數(shù)體里面調(diào)用任意插入和任意刪除函數(shù)

void pushFront(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	if (al->size == 0)
	{
		al->date[0] = info;
		al->size++;
	}
	else
	{
		insertDate(al, 0, info);
	}
}

void pushBack(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	insertDate(al, al->size, info);
}

void PopBack(AL* al)
{
	assert(al);
	if (al->size == 0)
	{
		printf("暫無數(shù)據(jù)??！\n");
		return;
	}
	Erase(al, al->size);

}

void PopFront(AL* al)
{
	assert(al);
	if (al->size == 0)
	{
		printf("暫無數(shù)據(jù)??！\n");
		return;
	}
	Erase(al, 0);
}

頭插就是調(diào)用insert函數(shù)在0位置插入
尾插就是調(diào)用insert函數(shù)在size位置插入
頭刪就是調(diào)用Erase函數(shù)刪除0位置
尾刪就是調(diào)用Erase函數(shù)刪除size位置

10、查找數(shù)據(jù)函數(shù)實(shí)現(xiàn)

size_t FindDate(AL* al, DATE info)
{
	assert(al);
	for (size_t i = 0; i < al->size; i++)
	{
		if (al->date[i] == info)
			return i;
	}
	return -1;
}

依次便利順序表，如果找到需要查找的數(shù)據(jù)，咋返回其下標(biāo)，否則返回-1

11、修改數(shù)據(jù)

void ExchangeDate(AL* al, size_t pos, DATE info)
{
	assert(al);
	assert(pos >= 0 && pos <= al->size);
	al->date[pos] = info;
}

先查找要修改的數(shù)據(jù)是否存在，然后進(jìn)行修改
他一般會和查找函數(shù)配合使用

12、銷毀順序表

由于順序表開辟了堆區(qū)內(nèi)存，所以我們在使用完順序表后一定要對開辟的內(nèi)存進(jìn)行釋放！

void Deatory(AL* al)
{
	assert(al);
	free(al->date);
	al->date=NULL;
	al->capacity = al->size = 0;
}

銷毀一個(gè)順序表，將順序表的容量置為0，順序表的有效數(shù)據(jù)個(gè)數(shù)置為0，將date指針?biāo)赶虻膭討B(tài)開辟的內(nèi)存空間釋放了，由于釋放了動態(tài)開辟的內(nèi)存空間，所有p指向的空間未初始化，date成為野指針，為了防止野指針，將date置為空指針。

數(shù)據(jù)結(jié)構(gòu)篇之——順序表的分享到這里就結(jié)束了，感謝大家的瀏覽訪問?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-716386.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】——順序表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！