文章目錄

• 前言
• 一、什么是線性表？
• 二、順序表：
• 三、鏈表：
• 四、順序表和鏈表對(duì)比：
• 總結(jié)

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比陸港網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式陸港網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋陸港地區(qū)。費(fèi)用合理售后完善，10余年實(shí)體公司更值得信賴。

---

前言

線性表是實(shí)際中廣泛應(yīng)用的重要數(shù)據(jù)結(jié)構(gòu)，本文用通俗易懂的方法講解它。

---

一、什么是線性表？

首先，我們了解下“線性表”的基本概念：

• 全名為“線性存儲(chǔ)結(jié)構(gòu)”，使用線性表存儲(chǔ)數(shù)據(jù)的方式可以這樣理解，即“把所有數(shù)據(jù)用一根線兒串起來(lái)，再存儲(chǔ)到物理空間中”。
• 是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表有：順序表、鏈表、隊(duì)列…

二、順序表：

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

順序表一般可以分為：

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

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

擴(kuò)容方法：動(dòng)態(tài)開辟一塊新的空間（一般為原空間的兩倍），將原空間的數(shù)據(jù)拷貝到新的空間，然后讓array指針指向新的空間并且釋放舊空間。

對(duì)比以上兩者：

區(qū)別：

• 靜態(tài)順序表和動(dòng)態(tài)順序表唯一不同的是，靜態(tài)順序表在創(chuàng)建順序表的時(shí)候容量已經(jīng)確定，不可以更改，而動(dòng)態(tài)順序表的容量是由malloc函數(shù)動(dòng)態(tài)開辟，當(dāng)容量不夠用時(shí)可以增加容量capacity。

優(yōu)缺點(diǎn)：

• 靜態(tài)順序表創(chuàng)建空間時(shí)為靜態(tài)開辟，不用malloc函數(shù)，代碼相對(duì)簡(jiǎn)單（一點(diǎn)點(diǎn)），不存在內(nèi)存泄露問(wèn)題。
• 動(dòng)態(tài)順序表，動(dòng)態(tài)開辟空間，使用相對(duì)靈活，相比于靜態(tài)開辟空間也可以少空間浪費(fèi)。

動(dòng)態(tài)順序表代碼演示：初始化、插入數(shù)據(jù)和檢查容量

//初始化順序表
void SeqList_Init(SeqList* ps)
{SLDataType* tmp = (SLDataType*)malloc(5 * sizeof(SLDataType));
	if (tmp == NULL)
	{perror(malloc);
		exit(-1);
	}
	ps->arr = tmp;
	ps->size = 0;
	ps->capacity = 5;
}
//檢查容量
void Check_Capacity(SeqList* ps)
{assert(ps);
	if (ps->size == ps->capacity)
	{SLDataType* tmp = (SLDataType*)realloc(ps->arr, 2*ps->capacity* sizeof(SLDataType));
		if (tmp == NULL)
		{	perror(realloc);
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = 2 * ps->capacity;
		printf("擴(kuò)容成功\n");
	}
}
//插入數(shù)據(jù)
void SeqList_Insert(SeqList* ps, SLDataType pos)
{assert(ps);
	Check_Capacity(ps);//檢查容量
	SLDataType num = 0;
	printf("請(qǐng)輸入需要寫入的值:>");
	scanf("%d", &num);
	if (ps->size == 0 || pos == ps->size)
	{ps->arr[pos] = num;
	}	
	SLDataType end = ps->size - 1;
	while (end >= pos)
	{ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = num;
	ps->size++;
}
//頭部插入數(shù)據(jù)
void SeqList_PushFront(SeqList* ps)
{SeqList_Insert(ps, 0);
}
//尾部插入數(shù)據(jù)
void SeqList_PushBack(SeqList* ps)
{SeqList_Insert(ps, ps->size);
}

三、鏈表：

概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。

下圖為單鏈表的邏輯結(jié)構(gòu)類型：

注意：

1. 鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但在物理上不一定連續(xù)
2. 現(xiàn)實(shí)中結(jié)點(diǎn)一般都是在堆上申請(qǐng)出來(lái)的
3. 從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可連續(xù)，也可能不連續(xù)

鏈表的分類

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

1. 單向或者雙向：

2. 帶頭和不帶頭：
   

3. 循環(huán)和不循環(huán)：
   
   經(jīng)過(guò)以上三種可以有2^3=8種類型。

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：

• 無(wú)頭單向鏈表和帶頭雙向循環(huán)鏈表：
  

這邊通過(guò)單鏈表頭部和尾部插入數(shù)據(jù)代碼幫大家理解過(guò)程：

//創(chuàng)建結(jié)點(diǎn)
SListNode* BuySListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//頭插數(shù)據(jù)
void SListPushFront(SListNode** pphead, SLTDataType x)
{SListNode* newnode = BuySListNode(x);//讀取新建的結(jié)點(diǎn)
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾插數(shù)據(jù)
void SListPushBack(SListNode** pphead, SLTDataType x)
{SListNode* newnode = BuySListNode(x);//讀取新建的結(jié)點(diǎn)
	if (*pphead == NULL)
	{*pphead = newnode;
		return;
	}
	SListNode* tail = *pphead;
	while (tail->next != NULL)
	{tail = tail->next;
	}
	tail->next = newnode;
}

四、順序表和鏈表對(duì)比：

不同點(diǎn)	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上連續(xù)，但物理上不一定連續(xù)
隨機(jī)訪問(wèn)	支持	不支持
任意位置插入或刪除元素	可能搬移元素，效率低	只需修改指針指向
插入	動(dòng)態(tài)順序表，空間不夠需要擴(kuò)容	沒(méi)有容量概念
應(yīng)用場(chǎng)景	元素高效存儲(chǔ)+頻繁訪問(wèn)	任意位置插入和刪除
緩存利用率	高	低

---

總結(jié)

以上就是今天要講的順序表和鏈表的內(nèi)容啦，如果本篇博客對(duì)你有所幫助的話，請(qǐng)給博主一個(gè)三連哦！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：C語(yǔ)言鏈表詳解（通俗易懂）-創(chuàng)新互聯(lián)
文章鏈接：http://weahome.cn/article/pcjdd.html