●🧑個人主頁:你帥你先說.
●📃歡迎點贊👍關注💡收藏💖
●📖既選擇了遠方，便只顧風雨兼程，
●🤟歡迎大家有問題隨時私信我！
●🧐著作權：本文由[你帥你先說.]原創，CSDN首發，侵權必究，

🐩1.線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

🐒2.順序表

🐎2.1概念及結構

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

順序表一般可以分為：

1. 靜態順序表：使用定長陣列存盤元素，
2. 動態順序表：使用動態開辟的陣列存盤，

🐈2.2介面實作

靜態順序表只適用于確定知道需要存多少資料的場景，靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用，所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實作動態順序表，

typedef int SLDataType;
// 順序表的動態存盤
typedef struct SeqList
{
 SLDataType* array; // 指向動態開辟的陣列
 size_t size ; // 有效資料個數
 size_t capicity ; // 容量空間的大小
}SeqList

🐢2.2.1初始化順序表

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

🐳2.2.2列印順序表

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

🐝2.2.3檢查空間余量

void SeqListCheckCapacity(SL* ps)
{
	// 如果沒有空間或者空間不足，那么我們就擴容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

🐬2.2.4順序表尾插

void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);

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

🐙2.2.5順序表尾刪

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}

🦉2.2.6順序表頭插

void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);

	// 挪動資料
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

🦜2.2.7順序表頭刪

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);

	// 挪動資料
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++ begin;
	}

	ps->size--;
}

🐘2.2.8查找下標

int SeqListFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

🐿?2.2.9指定位置插入

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SeqListCheckCapacity(ps);
	// 挪動資料
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}

	ps->a[pos] = x;
	ps->size++;
}

🐇2.2.10指定位置插入

void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);

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

	ps->size--;
}

🐉2.2.11順序表銷毀

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

🐅3.單鏈表

🦌3.1概念

概念：鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的 ，

這是單鏈表的邏輯結構，是我們假想出來的，方便我們理解，而鏈表的物理結構也就是真實的樣子其實是這樣的，

🐆3.2介面實作

typedef int SLTDateType;
typedef struct SListNode
{
 	SLTDateType data;
 	struct SListNode* next; 
}SLTNode;

從上面那張圖我們知道單鏈表是通過存下一個結點的地址來進行訪問的，
所以單鏈表要訪問下一個結點的操作是這樣的

SLTNode* Node;
Node = Node->next;

搞清楚了這個，接下來的介面實作你才能理解

🐂3.2.1創建結點

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

🐖3.2.2單鏈表尾插

void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}	
}

🐓3.2.3單鏈表尾刪

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead != NULL);
	// 1、一個節點
	// 2、兩個及以上節點
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

🐤3.2.4單鏈表頭插

void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

🐦3.2.5單鏈表頭刪

void SListPopFront(SLTNode** pphead)
{
	//if (*pphead == NULL)
	//	return;
	assert(*pphead != NULL);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

🐧3.2.6單鏈表列印

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

🦢3.2.7尋找結點

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}

	return NULL;
}

🦚3.2.8指定位置插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		// 找到pos的前一個位置
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}

		posPrev->next = newnode;
		newnode->next = pos;
	}
}

🦩3.2.9指定位置后插入

void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);

	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

🐙3.2.10指定位置洗掉

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

🐞3.2.11指定位置后洗掉

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

🦘3.2.12單鏈表銷毀

void SListDestory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕🐕
這樣的文章你還不快 點贊👍關注💡收藏💖
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈