前言

hello，大家好，今天我們來分享關于資料結構的第二篇博文《紅玫瑰與白玫瑰之爭》，還請大家繼續支持，看到這篇博文的標題，你也許會感到懵懵的，其實我在這篇博文里主要要介紹的是關于順序表和鏈表的知識，那么為什么會有這樣一個題目呢？希望你可以耐心讀完本文，并且從中找到答案，

一、聽說你還不知道啥是線性表？

1.線性表的概念

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

2.線性表的特點

1. 有頭有尾，即必存在唯一的一個頭元素，也必存在唯一的一個尾元素，
2. 除最后一個元素外，均有唯一后件，除第一個元素外，均有唯一前件，

3.線性表的分類

看完以上介紹，你也許對線性表有了初步的了解，也有了初步的迷茫，哈哈哈，莫慌，我們繼續往下了解兩個典型的線性表，“紅玫瑰”順序表和“白玫瑰”鏈表，

二、紅玫瑰——順序表

1.概念及結構

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

1. 靜態順序表：使用定長陣列存盤，
2. 動態順序表：使用動態開辟陣列存盤
   注意：順序表的邏輯結構和物理結構是一致的，

2.順序表的靜態存盤

我們先來看一個順序表的靜態存盤的例子

// 順序表的靜態存盤
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
 SLDataType array[N]; // 定長陣列
size_t size; // 有效資料的個數 
}SeqList;

根據這個例子我們可以看出來，靜態順序表只適用于確定知道需要存多少資料的場景，靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用，這顯然存在著弊端，不能適應多種多樣的靈活場景，于是，我們在實際中，多用動態存盤，

3.順序表的動態存盤

1.舉例

我們先來看一下動態存盤的例子

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

我們發現，利用指標，指向動態開辟的陣列，我們便能根據需求，開辟出合適大小的空間，這更能廣泛地運用在我們的實際操作中，
下面，我們來分享一個利用動態表來首先增刪查改的程式的代碼：

2.利用動態表實作增刪查改

首先，上頭檔案

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

// 靜態的順序表
//#define N 100
//struct SeqList
//{
//	int a[N];
//	int size;
//};

//typedef ContactInfo SeqDataType;
typedef int SeqDataType;

typedef struct SeqList
{
	SeqDataType* a;
	int size;      // 有效資料的個數
	int capacity;  // 容量
}SeqList, SEQ;

// 記憶體中個管理資料的結構增刪查改的借口

// 頭插尾插，頭刪尾刪
void SeqListInit(SeqList* pq);
void SeqListDestory(SeqList* pq);

void SeqListPrint(SeqList* pq);

//void SeqListPushBack(SEQ seq, SeqDataType x);
void SeqListPushBack(SeqList* pq, SeqDataType x);
void SeqListPushFront(SeqList* pq, SeqDataType x);
void SeqListPopBack(SeqList* pq);
void SeqListPopFront(SeqList* pq);

接下來，上函式實作的檔案

#include "SeqList.h"

void SeqListInit(SeqList* pq)
{
	//assert(pq != NULL);
	assert(pq);

	pq->a = NULL;
	pq->size = pq->capacity = 0;
}

void SeqListDestory(SeqList* pq)
{
	assert(pq);

	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}

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

void SeqCheckCapacity(SeqList* pq)
{
	// 滿了，需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

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

	SeqCheckCapacity(pq);

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

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++;
}

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

	--pq->size;
}

void SeqListPopFront(SeqList* pq)
{}

最后，上test檔案

#include "SeqList.h"

void TestSeqList1()
{
	SeqList s;
	SeqListInit(&s);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, 0);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);


	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListDestory(&s);
}

int main()
{
	TestSeqList1();

	return 0;
}

4.順序表的問題及思考

我們知道，動態表相對于靜態表可以滿足我們對于靈活運用空間的要求，那么，動態表就真的十分完美而不存在問題了嗎？我們來看看以下思考：

1. 中間/頭部的插入洗掉，時間復雜度為O(N)
2. 增容需要申請新空間，拷貝資料，釋放舊空間，會有不小的消耗，并且一次擴容過少，大量插入資料時，需要頻繁增容，一次擴容過多，則會造成空間浪費，增容是有代價的，
3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個資料，后面沒有資料插入了，那么就浪費了95個資料空間，

那么怎么解決這些問題呢？
我們來看另一種型別的順序表——鏈表，

三、白玫瑰——鏈表

1、鏈表的概念：

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

2、鏈表的分類

鏈表多種多樣，以下是一些分類，并且這些分類還可以組合，

雖然鏈表型別多種多樣，亂花漸欲迷人眼，但是在實際中，我們最常用的是兩種鏈表：

1. 無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，
2. 帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，實作反而簡單了，

3、鏈表的實作

1、無頭+單向+非回圈鏈表增刪查改實作

// 1、無頭+單向+非回圈鏈表增刪查改實作
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next;
}SListNode;
// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表列印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);

2、帶頭+雙向+回圈鏈表增刪查改實作

// 2、帶頭+雙向+回圈鏈表增刪查改實作
typedef int LTDataType;
typedef struct ListNode
{
 LTDataType _data;
 struct ListNode* _next;
 struct ListNode* _prev;
}ListNode;
// 創建回傳鏈表的頭結點.
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(ListNode* plist);
// 雙向鏈表列印
void ListPrint(ListNode* plist);
// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* plist);
// 雙向鏈表頭插
void ListPopFront(ListNode* plist);
// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表洗掉pos位置的節點
void ListErase(ListNode* pos)

四、紅玫瑰白玫瑰之爭

張愛玲說“也許每一個男子全都有過這樣的兩個女人，至少兩個，娶了紅玫瑰，久而久之，紅的變了墻上的一抹蚊子血，白的還是“床前明月光”；娶了白玫瑰，白的便是衣服上的一粒飯粘子，紅的卻是心口上的一顆朱砂痣，”
我說：“也許每個程式員都曾面對過這樣兩種線性表，至少兩個，用了順序表，支持隨機訪問，久而久之，發現它中間或前面部分的插入洗掉時間復雜度O(N) 增容的代價比較大；用了鏈表，任意位置插入洗掉時間復雜度為O(1) 沒有增容問題，插入開辟的空間，卻發現它不支持隨機訪問，

順序表和鏈表的區別和聯系

1、順序表

2、鏈表

一個人可能無法同時擁有紅玫瑰和白玫瑰，但是一個程式員卻可以同時擁有線性表和鏈表，人生中有很多猝不及防的錯過，但程式中，代碼卻可以讓你有擁有一切的可能！！！

五、總結

好了，以上就是今天的分享了，希望對大家有所幫助，如有錯漏，也歡迎大家批評指正，