數(shù)據(jù)結(jié)構(gòu)與算法（C語(yǔ)言） 教案 第02章 線性表

千等教育

數(shù)據(jù)結(jié)構(gòu)與算法（C語(yǔ)言篇）

教學(xué)設(shè)計(jì)

課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法rc語(yǔ)言篇）

授課年級(jí)：____________________________________

授課學(xué)期：____________________________________

教卵發(fā)名：____________________________________

2020年03月01日

計(jì)劃

課程名稱第2章線性表4學(xué)時(shí)

學(xué)時(shí)

本章主要介紹線性表的概念、線性表的順序存儲(chǔ)、線性表的鏈?zhǔn)酱鎯?chǔ)、

內(nèi)容分析

單向循環(huán)鏈表、雙向循環(huán)鏈表

教學(xué)目標(biāo)要求學(xué)生了解線性表的基本概念、掌握線性表順序存儲(chǔ)結(jié)構(gòu)的代碼編寫(xiě)

與方法、掌握線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的代碼編寫(xiě)方法、掌握單向循環(huán)鏈表的代碼

教學(xué)要求編寫(xiě)方法、掌握雙向循環(huán)鏈表的代碼編寫(xiě)方法

教學(xué)重點(diǎn)線性表的順序存儲(chǔ)、線性表的鏈?zhǔn)酱鎯?chǔ)、單向循環(huán)鏈表、雙向循環(huán)鏈表

教學(xué)難點(diǎn)線性表的順序存儲(chǔ)、線性表的鏈?zhǔn)酱鎯?chǔ)、單向循環(huán)鏈表、雙向循環(huán)鏈表

教學(xué)方式課堂講解及ppt演示

第一課時(shí)

（線性表的概念、線性表的順序存儲(chǔ)、線性表的鏈?zhǔn)酱鎯?chǔ)）

Q內(nèi)容回顧

1.回顧上節(jié)內(nèi)容，引出本課時(shí)主題。

上節(jié)已經(jīng)介紹了數(shù)據(jù)結(jié)構(gòu)與算法概述，本章將主要介紹數(shù)據(jù)結(jié)構(gòu)中的

核心概念——線性表，線性表作為一種最基本的數(shù)據(jù)結(jié)構(gòu)類型，表中的數(shù)據(jù)

元素之間滿足線性結(jié)構(gòu)。線性表可以通過(guò)不同的物理結(jié)構(gòu)實(shí)現(xiàn)，如順序存儲(chǔ)

與鏈?zhǔn)酱鎯?chǔ)。使用順序存儲(chǔ)實(shí)現(xiàn)的線性表稱為順序表，使用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)的

線性表稱為單鏈表。單鏈表作為數(shù)據(jù)結(jié)構(gòu)中常用的數(shù)據(jù)存儲(chǔ)方式，還可以實(shí)

現(xiàn)單向循環(huán)鏈表以及雙向循環(huán)鏈表。本章將主要討論這些數(shù)據(jù)結(jié)構(gòu)的代碼實(shí)

現(xiàn)以及結(jié)構(gòu)中數(shù)據(jù)元素的操作。

教2.明確學(xué)習(xí)目標(biāo)

（1）能夠掌握線性表的定義

學(xué)（2）能夠掌握線性表的運(yùn)算

（3）能夠掌握順序表的定義

過(guò)（4）能夠掌握順序表的創(chuàng)建

（5）能夠掌握插入數(shù)據(jù)結(jié)點(diǎn)

程（6）能夠掌握刪除數(shù)據(jù)結(jié)點(diǎn)

（7）能夠掌握其他操作

（8）能夠掌握順序表總結(jié)

（9）能夠掌握單鏈表的定義

（10）能夠掌握單鏈表的創(chuàng)建

（11）能夠掌握插入數(shù)據(jù)結(jié)點(diǎn)

Q知識(shí)講解

＞線性表的定義

線性表中的數(shù)據(jù)元素之間滿足線性結(jié)構(gòu)（線性結(jié)構(gòu)的概念詳見(jiàn)1.2.1

節(jié)）。線性表是n個(gè)數(shù)據(jù)元素的有限序列,記為（a1,a2,a3,an）,

其含義如下。

（1）n為數(shù)據(jù)元素的個(gè)數(shù)，也可以稱為線性表的長(zhǎng)度，當(dāng)n為0時(shí)，線

性表稱為空表。

（2）ai為線性表中的第i個(gè)數(shù)據(jù)元素（也可以稱為數(shù)據(jù)結(jié)點(diǎn)），i稱

為數(shù)據(jù)元素在線性表中的位序（等同于數(shù)組元素的下標(biāo)）。

從線性表的定義可以看出，線性表中存在唯一的首個(gè)數(shù)據(jù)元素和唯一的

末尾數(shù)據(jù)元素。除了首個(gè)數(shù)據(jù)元素，其他每個(gè)數(shù)據(jù)元素都有一個(gè)直接前驅(qū)（ai

的直接前驅(qū)為ai-1））；除了末尾數(shù)據(jù)元素，其他每個(gè)數(shù)據(jù)元素都有一

個(gè)直接后繼（ai的直接后繼為ai+1）,如圖所示。

＞線性表的運(yùn)算

線性表的運(yùn)算指的是對(duì)線性表中的數(shù)據(jù)進(jìn)行操作，其具體的實(shí)現(xiàn)與線性

表的物理結(jié)構(gòu)有關(guān)。線性表常見(jiàn)的幾種運(yùn)算如下。

（1）置空：將線性表變成空表。

（2）求長(zhǎng)度：獲取線性表數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

（3）取結(jié)點(diǎn)：取出線性表中的某個(gè)數(shù)據(jù)結(jié)點(diǎn)。

（4）定位：獲取某一個(gè)指定的數(shù)據(jù)結(jié)點(diǎn)。

（5）插入：將數(shù)據(jù)結(jié)點(diǎn)插入到線性表的指定位置。

（6）刪除：刪除線性表中的指定數(shù)據(jù)結(jié)點(diǎn)。

上述運(yùn)算并非線性表的所有運(yùn)算，也不一定要同時(shí)使用，用戶可根據(jù)不

同的需求合理選擇。

＞順序表的定義

一般情況下，線性表中的所有數(shù)據(jù)結(jié)點(diǎn)的類型是相同的。在C語(yǔ)言中，

通常使用一維數(shù)組和結(jié)構(gòu)體來(lái)表示順序表，代碼實(shí)現(xiàn)如下所示。

tdefineN32/*定義數(shù)組的大小*/

/*重定義int類型為datatype_t,表示順序表中結(jié)點(diǎn)的類型為datatype_t*/

typedefintdatatype/;

typedefstruct{/*定義結(jié)構(gòu)體*/

/*順序表中各結(jié)點(diǎn)存儲(chǔ)在該數(shù)組中,結(jié)點(diǎn)最多為32個(gè)（數(shù)據(jù)類型不固定，本代碼展示為整型）*/

datatype/data[N];

intlast;/*順序表最后?個(gè)結(jié)點(diǎn)的下標(biāo)值*/

}seqlist_t;

＞順序表的創(chuàng)建

在對(duì)順序表中的數(shù)據(jù)結(jié)點(diǎn)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空的順序表。

假設(shè)一個(gè)結(jié)點(diǎn)所占的空間大小為L(zhǎng)，順序表中的結(jié)點(diǎn)有n個(gè)，則線性表所占

的空間為n*L。但實(shí)際的情況是順序表中的結(jié)點(diǎn)數(shù)是不確定的，其占有的空

間也是不確定的，因此需要先分配max*L個(gè)連續(xù)的存儲(chǔ)單元，使其能存儲(chǔ)max

個(gè)結(jié)點(diǎn)。

＞插入數(shù)據(jù)結(jié)點(diǎn)

2.2.2節(jié)完成了創(chuàng)建空順序表的操作，接下來(lái)將通過(guò)代碼展示如何在順

序表中插入數(shù)據(jù)結(jié)點(diǎn)。在插入數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷順序表是否為滿，如

果為滿則不允許插入數(shù)據(jù)結(jié)點(diǎn)，否則會(huì)造成數(shù)據(jù)在內(nèi)存上越界。

1.不指定位置插入數(shù)據(jù)結(jié)點(diǎn)

插入數(shù)據(jù)結(jié)點(diǎn)需要先判斷順序表是否為滿，代碼如下所示。(變量定義

與例2-1一致)

intseqlist_full(seqlist_t*1){/*參數(shù)為指向結(jié)構(gòu)體的指針*/

returnL->last==N-l?1:0;/*判斷數(shù)組的下標(biāo)值*/

}

2.指定位置插入數(shù)據(jù)結(jié)點(diǎn)

指定位置插入數(shù)據(jù)結(jié)點(diǎn)，需要先遍歷整個(gè)順序表，然后找到指定的位置,

并將該位置后的結(jié)點(diǎn)依次向后移動(dòng)，最后插入數(shù)據(jù)，如圖所示。

先移位后插入

移位

插入,_,—

移位

3.顯示數(shù)據(jù)結(jié)點(diǎn)

插入數(shù)據(jù)結(jié)點(diǎn)完成后，可通過(guò)打印順序表中結(jié)點(diǎn)的數(shù)據(jù)判斷是否插入成

功，代碼實(shí)現(xiàn)如下所示。(變量定義與例2T一致)

intseqlist_show(seqlist_t*1)(/*子函數(shù)，參數(shù)為結(jié)構(gòu)體指針*/

inti=0;

for(i=0;i<=l->last;i++)(/*通過(guò)for循環(huán)遍歷順序表中所有的結(jié)點(diǎn)*/

printf;/*輸出結(jié)點(diǎn)保存的數(shù)據(jù)(這里的數(shù)據(jù)為整數(shù))*/

}

printf(H\nn);/*輸出換行*/

return0;

4.整體測(cè)試

將以上功能代碼與例2-1結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，代碼參考教材

2.2.3節(jié)。(變量定義與例2T一致)

例中，主函數(shù)main。主要用于測(cè)試子函數(shù)是否正確，先創(chuàng)建空的順序

表，然后依次插入數(shù)據(jù)結(jié)點(diǎn)，最后通過(guò)指定位置的方式再次插入數(shù)據(jù)結(jié)點(diǎn)。

輸出結(jié)果如下所示。

linux@ubuntu:~/1000phone/data/chap2$./a.out

10203040

510152025303540

linux@ubuntu:~/1000phone/data/chap2$

>刪除數(shù)據(jù)結(jié)點(diǎn)

在刪除數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷順序表是否為空，如果為空，不允許刪

除數(shù)據(jù)結(jié)點(diǎn)。

1.不指定位置刪除數(shù)據(jù)結(jié)點(diǎn)

刪除數(shù)據(jù)結(jié)點(diǎn)需要先判斷順序表是否為空，代碼如下所示0(變量定義

與例2-1一致)

intseqlist_empty(seqlist_t*1)(

returnl->last==-1?1:0;

}

2.指定位置刪除數(shù)據(jù)結(jié)點(diǎn)

指定位置刪除數(shù)據(jù)結(jié)點(diǎn)與插入數(shù)據(jù)結(jié)點(diǎn)類似，如圖所示。

(4；

刪除T產(chǎn)|立

移位

3.整體測(cè)試

將以上功能代碼與例2-2結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，代碼參考教材

2.2.4節(jié)。(變量定義與例2T一致)

例中，主函數(shù)main。主要用于測(cè)試子函數(shù)是否正確，先創(chuàng)建空的順序

表，然后將數(shù)據(jù)結(jié)點(diǎn)依次插入到順序表的末尾，最后通過(guò)兩種方式刪除順序

表中的結(jié)點(diǎn)。輸出結(jié)果如下所示。

linux@ubuntu:1000phone/data/chap2$./a.out

1020304050

203040

linux@ubuntu:~/1000phone/data/chap2$

>其他操作

對(duì)順序表中的數(shù)據(jù)結(jié)點(diǎn)除了可以進(jìn)行插入與刪除，還可以進(jìn)行其他類型

的操作，例如，修改結(jié)點(diǎn)數(shù)據(jù)，查找數(shù)據(jù)結(jié)點(diǎn)位置，刪除重復(fù)數(shù)據(jù)結(jié)點(diǎn)，合

并順序表。

1.修改結(jié)點(diǎn)數(shù)據(jù)

修改結(jié)點(diǎn)數(shù)據(jù)指的是對(duì)順序表中某一結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行修改，如圖所示。

2.查找數(shù)據(jù)結(jié)點(diǎn)位置

查找數(shù)據(jù)結(jié)點(diǎn)位置指的是獲取結(jié)點(diǎn)的下標(biāo)值，如圖所示。

Q-數(shù)據(jù)物

對(duì)比

Ac忠談一

滿足條件

輸出卜標(biāo)為4數(shù)據(jù)40

3.刪除重復(fù)數(shù)據(jù)結(jié)點(diǎn)

刪除重復(fù)數(shù)據(jù)結(jié)點(diǎn)指的是刪除順序表中數(shù)據(jù)相同的結(jié)點(diǎn)，如圖所示。

每輪使用?個(gè)結(jié)點(diǎn)對(duì)比其后的所有結(jié)點(diǎn)

/

結(jié)點(diǎn)0依次對(duì)比結(jié)點(diǎn)1、2、3、4、5、6

c'AWAb......?

TTYTTT

結(jié)點(diǎn)I依次對(duì)比結(jié)點(diǎn)2、3、4、5,6

4.合并順序表

合并順序表指的是將兩個(gè)順序表合并為一個(gè)順序表，同時(shí)去除數(shù)據(jù)重復(fù)

的結(jié)點(diǎn)，如圖所示。

5.整體測(cè)試

將以上功能代碼與例2-2、例2-3使用的函數(shù)接口結(jié)合，查看數(shù)據(jù)操作

是否成功，代碼參考教材2.2.5節(jié)。

＞順序表總結(jié)

通過(guò)前面的介紹可知，順序表是將數(shù)據(jù)結(jié)點(diǎn)放到一塊連續(xù)的內(nèi)存空間上

（使用數(shù)組表示順序表，數(shù)組在內(nèi)存上占有連續(xù)的空間），因此順序表結(jié)構(gòu)

較為簡(jiǎn)單，根據(jù)數(shù)據(jù)結(jié)點(diǎn)的下標(biāo)即可完成數(shù)據(jù)的存取。如圖所示。

雖然通過(guò)結(jié)點(diǎn)下標(biāo)的方式訪問(wèn)數(shù)據(jù)十分高效，但是用戶每次存取數(shù)據(jù)

時(shí)，都需要重新遍歷表，批量移動(dòng)數(shù)據(jù)結(jié)點(diǎn)。如圖所示。

如圖所示，移動(dòng)數(shù)據(jù)是將前一個(gè)結(jié)點(diǎn)的數(shù)據(jù)賦值給后一個(gè)結(jié)點(diǎn)。因此，

無(wú)論是刪除還是插入操作，都會(huì)導(dǎo)致批量的賦值操作。(賦值操作的本質(zhì)是

重寫(xiě)內(nèi)存)

綜上所述，順序表并不適合頻繁存取數(shù)據(jù)，而使用線性表的另一種存儲(chǔ)

形式一一鏈?zhǔn)酱鎯?chǔ)(單鏈表)，則可以很好地解決這一問(wèn)題。

>單鏈表的定義

單鏈表不同于順序表，其結(jié)點(diǎn)存儲(chǔ)在內(nèi)存地址非連續(xù)的存儲(chǔ)單元上，并

通過(guò)指針建立它們之間的關(guān)系。需要注意的是，單鏈表中的結(jié)點(diǎn)形式不同于

順序表，如圖所示。

斗中

datanext------------datanext...................datanext

由圖可知，單鏈表中的結(jié)點(diǎn)都是由兩部分組成，一部分為數(shù)據(jù)域(data),

另一部分為指針域(next)。簡(jiǎn)單地說(shuō)，數(shù)據(jù)域用來(lái)存放結(jié)點(diǎn)的數(shù)據(jù)，而指

針域存放的是一個(gè)指針，該指針保存的是下一個(gè)結(jié)點(diǎn)的內(nèi)存地址，或者說(shuō)該

指針指向下一個(gè)結(jié)點(diǎn)，如圖所示。

A

—ao|*po-j~?|ai|*pi-)-a2|*p2~??…”|an-i|

>單鏈表的創(chuàng)建

在對(duì)單鏈表中的數(shù)據(jù)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空的單鏈表。通過(guò)

代碼實(shí)現(xiàn)創(chuàng)建一個(gè)空的單鏈表，如例所示。

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefintdatatypet;

5

6/*定義結(jié)點(diǎn)結(jié)構(gòu)體*/

7typedefstructnode{

8datatypetdata;/*數(shù)據(jù)域*/

9structnode*next;/*指針域，指針指向下一個(gè)結(jié)點(diǎn)*/

10Jlinklistt;

11

12/*子函數(shù)，創(chuàng)建一個(gè)空的單鏈表，其本質(zhì)為創(chuàng)建一個(gè)鏈表頭*/

13linklistt*linklistcreate(){

14/*使用malloc函數(shù)在內(nèi)存上申請(qǐng)空間，空間大小為一個(gè)結(jié)構(gòu)體的大小*/

15linklistt*h=(linklistt*)malloc(sizeof(linklistt)：

16

17/*初始化，指針指向?yàn)镹ULL,此時(shí)不指向任何其他結(jié)點(diǎn)*/

18h->next=NULL;

19returnh;

20)

21intmain(intargc,constchar*argv[])

22(

23linklistt*h;

24h?linklistcreate();/*調(diào)用子函數(shù)*/

25return0;

26}

＞插入數(shù)據(jù)結(jié)點(diǎn)

2.3.2節(jié)完成了創(chuàng)建空單鏈表的操作，接下來(lái)將通過(guò)代碼展示如何在單

鏈表中插入數(shù)據(jù)結(jié)點(diǎn)。向單鏈表插入數(shù)據(jù)結(jié)點(diǎn)的方法有很多，包括頭插法、

尾插法、順序插入法、指定位置插入法。

1.頭插法

單鏈表不同于順序表，單鏈表使用的存儲(chǔ)空間是不固定的。因此，插入

數(shù)據(jù)結(jié)點(diǎn)無(wú)須判斷單鏈表是否為滿。使用頭插法插入數(shù)據(jù)結(jié)點(diǎn)有兩種不同的

情況，即插入第一個(gè)數(shù)據(jù)結(jié)點(diǎn)與插入除第一個(gè)結(jié)點(diǎn)以外的其他數(shù)據(jù)結(jié)點(diǎn)，如

圖所示。

頭插法插入第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的原理

假設(shè)該結(jié)點(diǎn)為頭結(jié)

插入第一步：斷開(kāi)原來(lái)的連接關(guān)系，實(shí)際不存在，點(diǎn)連”第.個(gè)結(jié)

next初始指向?yàn)镹ULL點(diǎn)，實(shí)際不存在

頭結(jié)點(diǎn)

使用新結(jié)點(diǎn)的指針指向頭

插入第：步：將頭結(jié)點(diǎn)指需要插入的新結(jié)點(diǎn)站點(diǎn)連接的第一個(gè)結(jié)點(diǎn)，

針重新折向新插入的結(jié)點(diǎn)實(shí)際為NULL

頭插法插入數(shù)據(jù)結(jié)點(diǎn)的厚理

針重新指向新插入的結(jié)點(diǎn)結(jié)點(diǎn)連接的第一個(gè)結(jié)點(diǎn)

由圖可以看出，插入數(shù)據(jù)結(jié)點(diǎn)的本質(zhì)為修改數(shù)據(jù)結(jié)點(diǎn)的指針域，使指針

指向的地址改變，代碼如下所示。（變量定義與例2-5一致）

/*參數(shù)1為指向頭結(jié)點(diǎn)的指針，參數(shù)2為新結(jié)點(diǎn)的數(shù)據(jù)*/

intlinklist_head_insert(linklist_t*h,datatype_tvalue){

linklist_t*temp;

/*為新插入的數(shù)據(jù)結(jié)點(diǎn)申請(qǐng)空間*/

temp=(linklist_t*)malloc(sizeof(linklist_t));

temp->data=value;/*為新插入結(jié)點(diǎn)的數(shù)據(jù)域賦值數(shù)據(jù)*/

temp->next=h->next;/*將頭結(jié)點(diǎn)指針指向的下一個(gè)結(jié)點(diǎn)的地址賦值給新結(jié)點(diǎn)的指針*/

h->next=temp;/*將頭結(jié)點(diǎn)指針指向新的結(jié)點(diǎn)*/

return0;

2.尾插法

尾插法即從單鏈表的末尾插入數(shù)據(jù)結(jié)點(diǎn)，如圖所示。

在未插入數(shù)據(jù)結(jié)點(diǎn)之前，該指針指向?yàn)镹ULL

NULL

插入

data?next

新結(jié)點(diǎn)

代碼如下所示。(變量定義與例2-5一致)

/*末尾插入數(shù)據(jù)結(jié)點(diǎn)，參數(shù)1為頭結(jié)點(diǎn)指針，參數(shù)2為插入的數(shù)據(jù)*/

intlinklist_tail_insert(linklist_t*hzdatatype]value){

linklist_t*temp;

/*為需要插入的數(shù)據(jù)結(jié)點(diǎn)申請(qǐng)內(nèi)存空間*/

temp=(linklist_t*)malloc(sizeof(linklist_t));

/*為需要插入的數(shù)據(jù)結(jié)點(diǎn)賦值數(shù)據(jù)*/

temp->data=value;

/*遍歷整個(gè)單鏈表，找到最后一個(gè)結(jié)點(diǎn)*/

while(h->next!=NULL){

h=h->next;

}

h->next=temp;/*插入結(jié)點(diǎn)*/

temp->next=NULL;/*將插入結(jié)點(diǎn)的指針指向NULL*/

return0;

3.順序插入法

順序插入法是頭插法的改良版，在插入數(shù)據(jù)結(jié)點(diǎn)前需要進(jìn)行判斷，保證

單鏈表中的數(shù)據(jù)有序排列，如圖所示。

插入數(shù)據(jù)比結(jié)點(diǎn)數(shù)據(jù)大，則

移動(dòng)到下一個(gè)結(jié)點(diǎn)繼續(xù)對(duì)比

新結(jié)點(diǎn)

插入采用頭插法的思想

4.指定位置插入法

指定位置插入法類似于頭插法，不同的是該方法在插入數(shù)據(jù)結(jié)點(diǎn)前進(jìn)行

了判斷，選擇位置后再進(jìn)行插入操作，如圖所示。

插入數(shù)據(jù)時(shí)，計(jì)算結(jié)點(diǎn)的下

標(biāo)，移動(dòng)指針到規(guī)定的位置

新結(jié)點(diǎn)

插入采用頭插法的思想

5.顯示數(shù)據(jù)結(jié)點(diǎn)

插入數(shù)據(jù)結(jié)點(diǎn)完成后，即可通過(guò)打印結(jié)點(diǎn)數(shù)據(jù)判斷結(jié)點(diǎn)是否插入成功。

遍歷整個(gè)單鏈表的方法很簡(jiǎn)單，只需要使用指針依次訪問(wèn)結(jié)點(diǎn)中的數(shù)據(jù)即

可，如圖所示。

判斷h->ncxt為

執(zhí)行h=h?>ncxt執(zhí)行h=h?>ncxiNULL

指針發(fā)生移動(dòng)指針發(fā)生移動(dòng)不執(zhí)行h=h->next

IIll-7\~

X*ncxt-

頭結(jié)點(diǎn)

頭結(jié)點(diǎn)起始地址為h

輸出h->data輸出h->data

6.整體測(cè)試

將以上功能代碼與例2-5結(jié)合，查看數(shù)據(jù)操作是否成功，代碼參考教材

2.3.3節(jié)。

第二課時(shí)

（線性表的鏈?zhǔn)酱鎯?chǔ)、單向循環(huán)鏈表、雙向循環(huán)鏈表）

Q內(nèi)容回顧

1.回顧上節(jié)內(nèi)容，引出本課時(shí)主題。

上節(jié)已經(jīng)介紹了線性表的定義、線性表的運(yùn)算、順序表的定義、順序表

的創(chuàng)建、插入數(shù)據(jù)結(jié)點(diǎn)、刪除數(shù)據(jù)結(jié)點(diǎn)、其他操作、順序表總結(jié)、單鏈表的

定義、單鏈表的創(chuàng)建和插入數(shù)據(jù)結(jié)點(diǎn)，下面將介紹刪除數(shù)據(jù)結(jié)點(diǎn)、其他操作、

單向循環(huán)鏈表的定義、單向循環(huán)鏈表的創(chuàng)建、插入數(shù)據(jù)與顯示數(shù)據(jù)、雙向循

環(huán)鏈表的定義、雙向循環(huán)鏈表的創(chuàng)建和插入與刪除數(shù)據(jù)結(jié)點(diǎn)。

2.明確學(xué)習(xí)目標(biāo)

(1)能夠掌握刪除數(shù)據(jù)結(jié)點(diǎn)

(2)能夠掌握其他操作

(3)能夠掌握單向循環(huán)鏈表的定義

(4)能夠掌握單向循環(huán)鏈表的創(chuàng)建

(5)能夠掌握插入數(shù)據(jù)與顯示數(shù)據(jù)

(6)能夠掌握雙向循環(huán)鏈表的定義

(7)能夠掌握雙向循環(huán)鏈表的創(chuàng)建

(8)能夠掌握插入與刪除數(shù)據(jù)結(jié)點(diǎn)

我知識(shí)講解

>刪除數(shù)據(jù)結(jié)點(diǎn)

在刪除數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷單鏈表是否為空(如果為空，則不允許

刪除數(shù)據(jù)結(jié)點(diǎn))。接下來(lái)將通過(guò)代碼展示如何在單鏈表中刪除數(shù)據(jù)結(jié)點(diǎn)。從

單鏈表刪除數(shù)據(jù)結(jié)點(diǎn)的方法包括頭刪法、指定數(shù)據(jù)刪除法。

1.頭刪法

刪除數(shù)據(jù)結(jié)點(diǎn)需要先判斷單鏈表是否為空，代碼實(shí)現(xiàn)如下所示。(變量

定義與例2-5一致)

/*判斷鏈表是否為空，參數(shù)為頭結(jié)點(diǎn)的地址*/

intlinklist_empty(linklist_t*h){

returnh->next==NULL?1:0;

)

2.指定數(shù)據(jù)刪除法

指定數(shù)據(jù)刪除法是根據(jù)指定的具體數(shù)據(jù)，刪除單鏈表中與數(shù)據(jù)對(duì)應(yīng)的結(jié)

點(diǎn)，如圖所示。

3.整體測(cè)試

將以上功能代碼與例2-6結(jié)合測(cè)試，查看數(shù)據(jù)操作是否成功，代碼參考

教材234節(jié)。

例中，主函數(shù)主要用于測(cè)試子函數(shù)是否正確。測(cè)試分為3個(gè)部分：先創(chuàng)

建一個(gè)空單鏈表，使用順序插入法將數(shù)據(jù)80、60、40插入鏈表，通過(guò)顯示

結(jié)點(diǎn)數(shù)據(jù)，判斷結(jié)點(diǎn)是否插入成功并自動(dòng)排序；使用頭刪法將數(shù)據(jù)從鏈表中

刪除，通過(guò)顯示結(jié)點(diǎn)數(shù)據(jù)，判斷第一個(gè)結(jié)點(diǎn)是否刪除；使用指定數(shù)據(jù)刪除法

將數(shù)據(jù)從鏈表中刪除，通過(guò)顯示結(jié)點(diǎn)數(shù)據(jù)，判斷數(shù)據(jù)為80的結(jié)點(diǎn)是否刪除。

運(yùn)行結(jié)果如下所示。

linux@ubuntu:1000phone/data$./a.out

406080

6080

60

linux@ubuntu:~/1000phone/data$

>其他操作

單鏈表中的數(shù)據(jù)結(jié)點(diǎn)除了可以完成插入與刪除的需求，還可以進(jìn)行其他

類型的操作，例如，修改結(jié)點(diǎn)數(shù)據(jù)，查找數(shù)據(jù)結(jié)點(diǎn)位置，鏈表數(shù)據(jù)翻轉(zhuǎn)，合

并單鏈表。

1.修改結(jié)點(diǎn)數(shù)據(jù)

修改結(jié)點(diǎn)數(shù)據(jù)指的是通過(guò)指定的數(shù)據(jù)在鏈表中尋找匹配的結(jié)點(diǎn)，并將該

結(jié)點(diǎn)的數(shù)據(jù)修改。代碼如下所示。

/*子函數(shù)，修改結(jié)點(diǎn)中的數(shù)據(jù)*/

/*參數(shù)1為指向頭結(jié)點(diǎn)的指針，參數(shù)2為指定的數(shù)據(jù)，參數(shù)3為新修改的數(shù)據(jù)*/

intlinklistchange(linklistt*h,datatypetoldvalue,datatypet

newvalue){

/*循環(huán)遍歷整個(gè)鏈表，查找是否有匹配的結(jié)點(diǎn)*/

while(h->next!=NULL){

if(h->next->data==oldvalue)(/*如果有數(shù)據(jù)匹配的結(jié)點(diǎn)*/

h->next->data=newvalue;/*修改結(jié)點(diǎn)中的數(shù)據(jù)*/

return0;

}

else(

h=h->next;/*如果未找到則繼續(xù)對(duì)比下一個(gè)結(jié)點(diǎn)*/

}

}

printf(Hnovalue\nM);/*未發(fā)現(xiàn)匹配的結(jié)點(diǎn)，輸出提示信息*/

return-1;/*返回異常，表示未發(fā)現(xiàn)匹配結(jié)點(diǎn)*/

)

2.查找數(shù)據(jù)結(jié)點(diǎn)位置

查找數(shù)據(jù)結(jié)點(diǎn)位置指的是通過(guò)指定的數(shù)據(jù)在鏈表中尋找匹配的結(jié)點(diǎn)，并

獲取該結(jié)點(diǎn)在單鏈表中的下標(biāo)。

/*子函數(shù)，根據(jù)指定數(shù)據(jù)查找匹配的數(shù)據(jù)結(jié)點(diǎn)，輸出結(jié)點(diǎn)下標(biāo)*/

/*參數(shù)1為指向頭結(jié)點(diǎn)的指針，參數(shù)2為指定的數(shù)據(jù)*/

intlinklist_search(linklist_t*h,datatype/value){

intpos=0;

〃遍歷整個(gè)鏈表，查找是否有匹配的結(jié)點(diǎn)

while(h->next!=NULL){

if(h->next->data==value){/*如果有數(shù)據(jù)匹配的結(jié)點(diǎn),/

returnpos;/*返回下標(biāo)值*/

}

else(

h=h->next;"如果未找到則繼續(xù)對(duì)比下一個(gè)結(jié)點(diǎn)*/

pos++;/*下標(biāo)值加1*/

}

)

printf("nofound\nn);/*未發(fā)現(xiàn)匹配的結(jié)點(diǎn)，輸出提示信息*/

return-1;/*返回異常，表示未發(fā)現(xiàn)匹配結(jié)點(diǎn)*/

)

3.鏈表數(shù)據(jù)翻轉(zhuǎn)

鏈表數(shù)據(jù)翻轉(zhuǎn)指的是將單鏈表中的數(shù)據(jù)倒序排列。例如，單鏈表中結(jié)點(diǎn)

數(shù)據(jù)的順序?yàn)?、2、3、4、5,經(jīng)過(guò)翻轉(zhuǎn)后結(jié)點(diǎn)數(shù)據(jù)的順序?yàn)?、4、3、2、

k如圖所示。

倒序的原理是將原有的連接斷開(kāi)，并重新使用頭插法插入鏈表

4.合并單鏈表

合并單鏈表指的是將兩個(gè)單鏈表合并為一個(gè)單鏈表，如圖所示。

頭結(jié)點(diǎn)

5.整體測(cè)試

將以上功能代碼與例2-7結(jié)合，查看數(shù)據(jù)操作是否成功，代碼參考教材

2.3.5節(jié)。

例中，主函數(shù)主要用于測(cè)試子函數(shù)是否正確。測(cè)試分為4個(gè)部分：先創(chuàng)

建一個(gè)空單鏈表1.使用尾插法將數(shù)據(jù)70、50、20、10插入鏈表，通過(guò)顯示

結(jié)點(diǎn)數(shù)據(jù)，判斷結(jié)點(diǎn)是否插入成功；將單鏈表1中的結(jié)點(diǎn)數(shù)據(jù)修改為30,通

過(guò)顯示結(jié)點(diǎn)數(shù)據(jù)，判斷數(shù)據(jù)是否修改成功；將單鏈表1中的數(shù)據(jù)結(jié)點(diǎn)翻轉(zhuǎn)，

通過(guò)顯示結(jié)點(diǎn)數(shù)據(jù)，判斷鏈表是否翻轉(zhuǎn)成功；創(chuàng)建空單鏈表2,使用尾插法

將數(shù)據(jù)20、40、60插入鏈表，將單鏈表1和單鏈表2進(jìn)行合并，通過(guò)顯示

結(jié)點(diǎn)數(shù)據(jù)，判斷單鏈表合并是否成功。運(yùn)行結(jié)果如下所示。

linux@ubuntu:~/1000phone/data/chap2$./a.out

70502010/*鏈表1插入數(shù)據(jù)成功*/

70503010/*鏈表1修改數(shù)據(jù)成功*/

10305070/*鏈表1翻轉(zhuǎn)成功（數(shù)據(jù)倒置）*/

10203040!506070/*鏈表1與鏈表2合并成功*/

linux@ubuntu:~/1000phone/data/chap2$

＞單向循環(huán)鏈表的定義

在單鏈表中，頭結(jié)點(diǎn)指針是相當(dāng)重要的，因?yàn)閱捂湵淼牟僮鞫夹枰^結(jié)

點(diǎn)指針。如果頭指針丟失或者損壞，那么整個(gè)鏈表都會(huì)遺失，并且浪費(fèi)鏈表

內(nèi)存空間。為了避免這種情況的產(chǎn)生，可以將單鏈表設(shè)計(jì)成循環(huán)鏈表。循環(huán)

鏈表可以是單向循環(huán)也可以是雙向循環(huán)，下面將介紹單向循環(huán)鏈表的操作。

單向循環(huán)鏈表指的是在單鏈表的基礎(chǔ)上，將尾結(jié)點(diǎn)的指針指向鏈表中的

頭結(jié)點(diǎn)，而非NULL,如圖所示。

由圖所示，單向循環(huán)鏈表中的結(jié)點(diǎn)通過(guò)指針指向形成一個(gè)閉合的連接，

結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表相同，代碼如下所示。

typedefintdatatype_t;/*重定義int整型為datatype]*/

/*結(jié)點(diǎn)結(jié)構(gòu)*/

typedefstructnode{

datatype_tdata;/*結(jié)點(diǎn)數(shù)據(jù)*/

structnode*next;/*指向下一個(gè)結(jié)點(diǎn)的指針*/

}looplist_t;

A單向循環(huán)鏈表的創(chuàng)建

在對(duì)單向循環(huán)鏈表中的數(shù)據(jù)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空表。通過(guò)

代碼實(shí)現(xiàn)創(chuàng)建空的單向循環(huán)鏈表，如例所示。

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefintdatatypet;/*重定義int整型為datatypet*/

5

6typedefstructnode{

7datatypetdata;/*結(jié)點(diǎn)數(shù)據(jù)*/

8structnode*next;/*指向下一個(gè)結(jié)點(diǎn)的指針*/

9)looplistt;

10/*子函數(shù)，創(chuàng)建單向循環(huán)鏈農(nóng)*/

11looplistt*looplistcreate(){

12looplistt*h;

13/*使用malloc函數(shù)為頭結(jié)點(diǎn)申請(qǐng)內(nèi)存空間，大小為sizeof(looplistt)*/

14h=(looplistt*)malloc(sizeof(looplistt));

15

16h->next=h;/*將頭結(jié)點(diǎn)指針指向自身，開(kāi)始時(shí)只有一個(gè)頭結(jié)點(diǎn)*/

17

18returnh;/*返回頭結(jié)點(diǎn)地址*/

19)

20intmain(intargc,constchar*argv[])

21(

22looplistt*h;

23

24h=looplistcreate();

25return0;

26)

A插入數(shù)據(jù)與顯示數(shù)據(jù)

1.頭插法

插入數(shù)據(jù)可選用頭插法，其原理與單鏈表一致，代碼如下所示。

/*頭插法插入數(shù)據(jù)，參數(shù)1為頭結(jié)點(diǎn)指針，參數(shù)2為插入的結(jié)點(diǎn)數(shù)據(jù)★/

intlooplist_head_insert(looplist_t*h,datatype/value){

looplist_t*temp;

/*使用malloc函數(shù)為新插入的結(jié)點(diǎn)申請(qǐng)內(nèi)存空間*/

temp=(looplist_t*)malloc(sizeof(looplist_t));

/*為結(jié)點(diǎn)賦值，保存數(shù)據(jù)*/

temp->data=value;

/*頭插法*/

temp->next=h->next;

h->next=temp;

return0;

)

2.顯示數(shù)據(jù)

顯示數(shù)據(jù)即獲取單向循環(huán)鏈表中結(jié)點(diǎn)的數(shù)據(jù)，代碼如下所示。

/*顯示數(shù)據(jù)*/

intlooplist_show(looplist_t*h)(

looplist_t*p=h;

/*遍歷數(shù)據(jù)到最后-一個(gè)結(jié)點(diǎn)為止*/

while{h->next!=p){

h=h->next;/*移動(dòng)指針，進(jìn)行遍歷*/

printf(n%d",h->data);

)

printf("\n");

return0;

)

3.整體測(cè)試

將以上功能代碼與例2-9結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，代碼參考教材

2.4.3節(jié)。

>雙向循環(huán)鏈表的定義

在單鏈表中，如果需要查找某一個(gè)結(jié)點(diǎn)的后繼時(shí)，直接通過(guò)指針移動(dòng)到

下一個(gè)結(jié)點(diǎn)即可。但是要查找某一結(jié)點(diǎn)的前驅(qū)時(shí)，則需要從鏈表頭開(kāi)始。為

了提高數(shù)據(jù)操作的效率，引入雙向循環(huán)鏈表。

雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表不同，每一個(gè)結(jié)點(diǎn)都有一個(gè)指向前

一個(gè)結(jié)點(diǎn)的指針和一個(gè)指向后一個(gè)結(jié)點(diǎn)的指針，如圖所示。

指向上一個(gè)結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)

?priordata*next

結(jié)點(diǎn)結(jié)構(gòu)的代碼實(shí)現(xiàn)如下所示。

typedefintdatatype_t;

typedefstructnode(

datatype/data;/*結(jié)點(diǎn)數(shù)據(jù)*/

structnode*prior;/*指向上一個(gè)結(jié)點(diǎn)*/

structnode*next;/*指向下一個(gè)結(jié)點(diǎn)*/

}dlinklist_t;

＞雙向循環(huán)鏈表的創(chuàng)建

在對(duì)雙向循環(huán)鏈表中的數(shù)據(jù)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空表。通過(guò)

代碼實(shí)現(xiàn)創(chuàng)建空的雙向循環(huán)鏈表，如例所示。

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefintdatatypet;

5typedefstructnode{

6datatypetdata;/*結(jié)點(diǎn)數(shù)據(jù)*/

7structnode*prior;/*指向