文章目錄

📝引言
💖線性表之-順序表💖
- 1??靜態順序表
- - 靜態 VS 動態
- 2??動態順序表
- - 📃實作介面目錄
  - 💌初始化
  - 💌列印資料
  - 💌空間銷毀
  - 💌尾部插入
  - 💌尾部洗掉
  - 💌頭部插入
  - 💌頭部洗掉
  - 💌任意位置插入
  - 💌任意位置洗掉
  - 💌查找資料
  - 💌查找某資料并插入資料
  - 💌查找某資料并將其洗掉
  - 💌頭部插入（呼叫任意位置插入介面實作）
  - 💌尾部插入（呼叫任意位置插入介面實作）
  - 💌頭部洗掉（呼叫任意位置洗掉介面實作）
  - 💌尾部洗掉（呼叫任意位置洗掉介面實作）
  - 💌自動擴容
🎯順序表的缺陷
🎯順序表的優點

📝引言

邏輯結構：資料元素之間的邏輯關系；想象出來的，

物理結構：資料結構在計算機中的表示（又稱映像）稱為資料的物理結構，又稱存盤結構；實際在記憶體中存盤的狀態，

順序表的實作

💖線性表之-順序表💖

線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列，線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…

線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

順序表

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

順序表一般可以分為：

靜態順序表：使用定長陣列存盤
動態順序表：使用動態開辟的陣列存盤

1??靜態順序表

初始化：

在這里插入圖片描述

那么我們接下來實作其他介面函式的時候，卻發現了靜態順序表太過于局限，如果說我們的資料存放滿了，就會出問題，不能夠自動擴容，

所以我們考慮用動態順序表，

靜態 VS 動態

在這里插入圖片描述

對比靜態和動態的結構可以看出兩者之間的區別，

靜態順序表較為死板，存盤空間被定死，
動態順序表較為靈活，存盤空間被存放滿時可以自動擴容，

2??動態順序表

初始化：

在這里插入圖片描述

📃實作介面目錄

//初始化順序表
void SeqListInit(SL* ps);
//列印順序表
void SeqListPrint(SL* ps);
//銷毀空間
void SeqListDestory(SL* ps);
//檢查容量增容
void SeqListCheckCapacity(SL* ps);

//頭部插入
void SeqListPushFront(SL* ps, SLDataType x);
//尾部插入
void SeqListPushBack(SL* ps, SLDataType x);
//頭部洗掉
void SeqListPopFront(SL* ps);
//尾部洗掉
void SeqListPopBack(SL* ps);

// 找到了回傳x位置下標，沒有找打回傳-1
int SeqListFind(SL* ps, SLDataType x);

// 指定pos下標位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 洗掉pos位置的資料
void SeqListErase(SL* ps, int pos);

💌初始化

void SeqListInit(SL* ps);

初始化需要傳址，如果傳值是改變不了S1的

void SeqListInit(SL* ps)
{
    assert(ps);
    
	ps->element = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

插入必然涉及到以下三個問題：

順序表沒有空間，需要擴容，
順序表有空間，不需要擴容，直接插入資料即可，
順序表空間已滿，需要擴容，

💌列印資料

列印資料可以傳值也可以傳址，這里仍用的傳址，

//列印順序表
void SeqListPrint(SL* ps)
{
    assert(ps);
    
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->element[i]);
	}
	printf("\n");
}

💌空間銷毀

釋放空間的好處

防止記憶體泄漏
幫助檢查越界（如果越界沒有報錯的時候，當我們釋放空間的時候它會幫助我們報錯）

//銷毀順序表
void SeqListDestory(SL* ps)
{
    assert(ps);
    
	free(ps->element);
	ps->element = NULL;

	ps->capacity = ps->size = 0;
}

💌尾部插入

void SeqListPushBack(SL* ps, SLDataType x);

初始化的時候容量被設定為0，所以我們必須要先對容量進行處理，

然后就是擴容，擴容我們用到realloc，realloc是調整大小的，但是呢，如果原大小為0時，他會和malloc一樣開辟空間，一般我們擴容都是擴到原大小的二倍，

其釋義如下：

The realloc function changes the size of an allocated memory block. The memblock argument points to the beginning of the memory block. If memblock is NULL, realloc behaves the same way as malloc and allocates a new block of size bytes. If memblock is not NULL, it should be a pointer returned by a previous call to calloc, malloc, or realloc.

如果擴容失敗就會回傳空指標，如果成功則把維護擴容之后空間的那個指標交給維護原來那片空間的指標維護，并調整好擴容后的容量大小，

//尾部插入
void SeqListPushBack(SL* ps, SLDataType x)
{
    assert(ps);
	//當容量不足或者沒有容量的時候就擴容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
		SLDataType* temp = (SLDataType*)realloc(ps->element, newcapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}

		ps->element = temp;
		ps->capacity = newcapacity;
		
	}
	//尾部插入
	ps->element[ps->size] = x;
	ps->size++;
}

💌尾部洗掉

void SeqListPopBack(SL* ps);

我們先要知道，如果這個陣列本來就沒有內容或者被刪完了就不能繼續刪了，所以要控制這一點，有效值要控制大于0，然后洗掉的話，直接自減有效值也就是丟棄右邊的資料讓有效值的范圍左走就行了，

//尾部洗掉
void SeqListPopBack(SL* ps)
{
    assert(ps);
	/*
	//溫柔洗掉
	if (ps->size > 0)
	{
		ps->size--;
	}
	*/

	//暴力洗掉
	assert(ps->size > 0);
	ps->size--;
}

💌頭部插入

void SeqListPushBack(SL* ps, SQDataType x);

在這里插入圖片描述

從4開始依次往后挪一個位置，size為當前的有效位，size起始值是從1開始的，end作為索引位置的下標，所以end是作為下標的存在，下標是從0開始的，所以要減1，

當end指向0的時候，存上資料就終止頭插的步驟，

//頭部插入
void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps);
	//檢查容量是否足夠并增容
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;
	
	while (end >= 0)
	{
		ps->element[end + 1] = ps->element[end];
		--end;
	}
	//插入
	ps->element[0] = x;
	ps->size++;
}

至此，我們實作了尾部插入和頭部插入，相信已經可以發現只要是插入都存在空間不足或者沒有空間時需要擴容的情況，這里需要反復復用我們寫的擴容的代碼，故此，可以將其包裝成一個函式void SeqListCheckCapacity(SL* ps);

💌頭部洗掉

void SeqListPopFront(SL* ps);

頭刪就是往左邊覆寫，注意這里的起始位置是從第二個資料開始，

//頭部洗掉
void SeqListPopFront(SL* ps)
{
    assert(ps);
	assert(ps->size > 0);

	int begin = 1;
	while (begin <= ps->size - 1)
	{
		ps->element[begin - 1] = ps->element[begin];
		++ begin;
	}
	ps->size--;
}

💌任意位置插入

void SeqListInsert(SL* ps, int pos, SQDataType x);

在任意位置插入資料，那么這個位置pos必須要是在有效資料內插入，不可能說到右邊空的空間去插入吧，（保證插入位置的有效性）

插入資料的時候也可能空間已經滿了，所以提前還得檢查空間增容，

然后開始插入資料，我們得把pos位置上以及其右邊的資料依次右移一個位置騰出pos的空間去插入資料，插入資料后有效位數需要加1，

在這里插入圖片描述

注：如果有N個資料，那么第N個資料的下標為N-1，

//指定pos下標位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//保證插入范圍的有效性
	assert(pos >= 0 && pos <= ps->size);
	//檢查容量
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;

	while (end >= pos)
	{
		ps->element[end + 1] = ps->element[end];
		--end;
	}

	ps->element[pos] = x;
	ps->size++;

}

斷言中的pos <= ps->size等于可以保證實作尾插的操作，

💌任意位置洗掉

void SeqListErase(SL* ps, int pos);

同樣洗掉范圍也必須是在有效范圍內，（保證插入位置的有效性）

那么洗掉資料還是一如既往的覆寫，也就是從pos位置右邊的一個資料開始，將其一個一個依次向左移動一個位置也就是覆寫，

洗掉完資料后，有效位數需要減1，

//洗掉pos位置的資料
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//保證洗掉位置的有效性
	assert(pos >= 0 && pos < ps->size);

	int begin = pos + 1;
	
	while (begin <= ps->size - 1)
	{
		ps->element[begin - 1] = ps->element[begin];
		++begin;
	}

	ps->size--;
}

💌查找資料

遍歷一遍資料就好了

//查找某個資料，找到了回傳查找資料位置下標，沒有找打回傳-1
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);

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

💌查找某資料并插入資料

結合呼叫前面實作的查找資料和任意位置插入介面即可

//示例
int main()
{	SL s1;

	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
 
    int pos = SeqListFind(&s1, 3);
 	if(pos != -1)
    {
        SeqListInsert(&s1, pos, 10);
    }
 	else
        printf("find fail!\n");
 
 	SeqListPrint(&s1);
 
 	return 0;
}

💌查找某資料并將其洗掉

結合呼叫前面實作的查找資料和任意位置洗掉介面即可

//示例
int main()
{	SL s1;

	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
 
    int pos = SeqListFind(&s1, 3);
 	if(pos != -1)
    {
        SeqListErase(&s1, pos);
    }
 	else
        printf("find fail!\n");
 
 	SeqListPrint(&s1);
 
 	return 0;
}

💌頭部插入（呼叫任意位置插入介面實作）

void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    //檢查容量是否足夠并增容
	SeqListCheckCapacity(ps);
    //插入
    SeqListInsert(ps, 0, x);
}

💌尾部插入（呼叫任意位置插入介面實作）

void SeqListPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    //檢查容量是否足夠并增容
	SeqListCheckCapacity(ps);
    //插入
    SeqListInsert(ps, ps->size, x);
}

💌頭部洗掉（呼叫任意位置洗掉介面實作）

void SeqListPopFront(SL* ps)
{
	assert(ps);
    //保證size的有效性（至少有資料才可以刪）
	assert(ps->size > 0);
    
	//洗掉
	SeqListErase(ps, 0);
}

💌尾部洗掉（呼叫任意位置洗掉介面實作）

void SeqListPopBack(SL* ps)
{
    assert(ps);
    //保證size的有效性（至少有資料才可以刪）
    assert(ps->size > 0);
    
    //洗掉
    SeqListErase(ps, ps->size - 1);
}

💌自動擴容

void SeqListCheckCapacity(SL* ps);

擴容我們用到realloc，realloc是調整大小的，但是呢，如果原大小為0時，他會和malloc一樣開辟空間，一般我們擴容都是擴到原大小的二倍，

其釋義如下：

The realloc function changes the size of an allocated memory block. The memblock argument points to the beginning of the memory block. If memblock is NULL, realloc behaves the same way as malloc and allocates a new block of size bytes. If memblock is not NULL, it should be a pointer returned by a previous call to calloc, malloc, or realloc.

如果擴容失敗就會回傳空指標，如果成功則把維護擴容之后空間的那個指標交給維護原來那片空間的指標維護，并調整好擴容后的容量大小，

我們單獨把擴容的步驟封裝成一個函式，

//擴容
void SeqListCheckCapacity(SL* ps)
{
	//當容量不足或者沒有容量的時候就擴容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* temp = (SLDataType*)realloc(ps->element, newcapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}

		ps->element = temp;
		ps->capacity = newcapacity;
	}
}

總結：

洗掉資料需要考慮為空的情況，必須保證size大于0
插入資料需要考慮空間不足的情況，需要擴容

🎯順序表的缺陷

空間不夠需要增容，增容我們用的realloc
這個函式擴容分兩種情況
1. 原地擴；
2. 異地擴；（如果是異地擴容代價會更大）
為了避免頻繁擴容，我們每次擴容的空間視情況而定，但是基本都會大于1，故此如果擴容之后只使用一個空間必定會導致空間的浪費，
資料必須是從開始位置連續存盤，那么我們從頭部或者中間位置插入洗掉資料的時候必定會需要挪動資料，效率不高，

而鏈表就是針對順序表的缺陷設計出來的！

🎯順序表的優點

支持隨機訪問，需要隨機訪問的結構支持的演算法可以很好的適用，

（全劇終）感謝食用！
|
|🔥🔥🔥
|
往期回顧：
【詳解浮點型在記憶體中的存盤】
【位元組序之Little-Endian&Big-Endian】
【自己寫了一個萬能排序】
【圖解指標八大筆試題】

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/341881.html

標籤：其他

上一篇：資料結構之堆疊詳解

下一篇：滲透學習總結-Windows基礎

【資料結構之順序表】附原始碼【收藏】

文章目錄

📝引言

💖線性表之-順序表💖

1??靜態順序表

靜態 VS 動態

2??動態順序表

📃實作介面目錄

💌初始化

💌列印資料

💌空間銷毀

💌尾部插入

💌尾部洗掉

💌頭部插入

💌頭部洗掉

💌任意位置插入

💌任意位置洗掉

💌查找資料

💌查找某資料并插入資料

💌查找某資料并將其洗掉

💌頭部插入（呼叫任意位置插入介面實作）

💌尾部插入 （呼叫任意位置插入介面實作）

💌頭部洗掉（呼叫任意位置洗掉介面實作）

💌尾部洗掉（呼叫任意位置洗掉介面實作）

💌自動擴容

🎯順序表的缺陷

🎯順序表的優點

💌尾部插入（呼叫任意位置插入介面實作）