千等教育

數據結構與算法（C語言篇）

教學設計

課程名稱：數據結構與算法rc語言篇）

授課年級：____________________________________

授課學期：____________________________________

教卵發名：____________________________________

2020年03月01日

計劃

課程名稱第2章線性表4學時

學時

本章主要介紹線性表的概念、線性表的順序存儲、線性表的鏈式存儲、

內容分析

單向循環鏈表、雙向循環鏈表

教學目標要求學生了解線性表的基本概念、掌握線性表順序存儲結構的代碼編寫

與方法、掌握線性表鏈式存儲結構的代碼編寫方法、掌握單向循環鏈表的代碼

教學要求編寫方法、掌握雙向循環鏈表的代碼編寫方法

教學重點線性表的順序存儲、線性表的鏈式存儲、單向循環鏈表、雙向循環鏈表

教學難點線性表的順序存儲、線性表的鏈式存儲、單向循環鏈表、雙向循環鏈表

教學方式課堂講解及ppt演示

第一課時

（線性表的概念、線性表的順序存儲、線性表的鏈式存儲）

Q內容回顧

1.回顧上節內容，引出本課時主題。

上節已經介紹了數據結構與算法概述，本章將主要介紹數據結構中的

核心概念——線性表，線性表作為一種最基本的數據結構類型，表中的數據

元素之間滿足線性結構。線性表可以通過不同的物理結構實現，如順序存儲

與鏈式存儲。使用順序存儲實現的線性表稱為順序表，使用鏈式存儲實現的

線性表稱為單鏈表。單鏈表作為數據結構中常用的數據存儲方式，還可以實

現單向循環鏈表以及雙向循環鏈表。本章將主要討論這些數據結構的代碼實

現以及結構中數據元素的操作。

教2.明確學習目標

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

學（2）能夠掌握線性表的運算

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

過（4）能夠掌握順序表的創建

（5）能夠掌握插入數據結點

程（6）能夠掌握刪除數據結點

（7）能夠掌握其他操作

（8）能夠掌握順序表總結

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

（10）能夠掌握單鏈表的創建

（11）能夠掌握插入數據結點

Q知識講解

＞線性表的定義

線性表中的數據元素之間滿足線性結構（線性結構的概念詳見1.2.1

節）。線性表是n個數據元素的有限序列,記為（a1,a2,a3,an）,

其含義如下。

（1）n為數據元素的個數，也可以稱為線性表的長度，當n為0時，線

性表稱為空表。

（2）ai為線性表中的第i個數據元素（也可以稱為數據結點），i稱

為數據元素在線性表中的位序（等同于數組元素的下標）。

從線性表的定義可以看出，線性表中存在唯一的首個數據元素和唯一的

末尾數據元素。除了首個數據元素，其他每個數據元素都有一個直接前驅（ai

的直接前驅為ai-1））；除了末尾數據元素，其他每個數據元素都有一

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

＞線性表的運算

線性表的運算指的是對線性表中的數據進行操作，其具體的實現與線性

表的物理結構有關。線性表常見的幾種運算如下。

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

（2）求長度：獲取線性表數據結點的個數。

（3）取結點：取出線性表中的某個數據結點。

（4）定位：獲取某一個指定的數據結點。

（5）插入：將數據結點插入到線性表的指定位置。

（6）刪除：刪除線性表中的指定數據結點。

上述運算并非線性表的所有運算，也不一定要同時使用，用戶可根據不

同的需求合理選擇。

＞順序表的定義

一般情況下，線性表中的所有數據結點的類型是相同的。在C語言中，

通常使用一維數組和結構體來表示順序表，代碼實現如下所示。

tdefineN32/*定義數組的大小*/

/*重定義int類型為datatype_t,表示順序表中結點的類型為datatype_t*/

typedefintdatatype/;

typedefstruct{/*定義結構體*/

/*順序表中各結點存儲在該數組中,結點最多為32個（數據類型不固定，本代碼展示為整型）*/

datatype/data[N];

intlast;/*順序表最后?個結點的下標值*/

}seqlist_t;

＞順序表的創建

在對順序表中的數據結點進行操作之前，需要先創建一個空的順序表。

假設一個結點所占的空間大小為L，順序表中的結點有n個，則線性表所占

的空間為n*L。但實際的情況是順序表中的結點數是不確定的，其占有的空

間也是不確定的，因此需要先分配max*L個連續的存儲單元，使其能存儲max

個結點。

＞插入數據結點

2.2.2節完成了創建空順序表的操作，接下來將通過代碼展示如何在順

序表中插入數據結點。在插入數據結點之前，需要判斷順序表是否為滿，如

果為滿則不允許插入數據結點，否則會造成數據在內存上越界。

1.不指定位置插入數據結點

插入數據結點需要先判斷順序表是否為滿，代碼如下所示。(變量定義

與例2-1一致)

intseqlist_full(seqlist_t*1){/*參數為指向結構體的指針*/

returnL->last==N-l?1:0;/*判斷數組的下標值*/

}

2.指定位置插入數據結點

指定位置插入數據結點，需要先遍歷整個順序表，然后找到指定的位置,

并將該位置后的結點依次向后移動，最后插入數據，如圖所示。

先移位后插入

移位

插入,_,—

移位

3.顯示數據結點

插入數據結點完成后，可通過打印順序表中結點的數據判斷是否插入成

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

intseqlist_show(seqlist_t*1)(/*子函數，參數為結構體指針*/

inti=0;

for(i=0;i<=l->last;i++)(/*通過for循環遍歷順序表中所有的結點*/

printf;/*輸出結點保存的數據(這里的數據為整數)*/

}

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

return0;

4.整體測試

將以上功能代碼與例2-1結合，測試數據操作是否成功，代碼參考教材

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

例中，主函數main。主要用于測試子函數是否正確，先創建空的順序

表，然后依次插入數據結點，最后通過指定位置的方式再次插入數據結點。

輸出結果如下所示。

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

10203040

510152025303540

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

>刪除數據結點

在刪除數據結點之前，需要判斷順序表是否為空，如果為空，不允許刪

除數據結點。

1.不指定位置刪除數據結點

刪除數據結點需要先判斷順序表是否為空，代碼如下所示0(變量定義

與例2-1一致)

intseqlist_empty(seqlist_t*1)(

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

}

2.指定位置刪除數據結點

指定位置刪除數據結點與插入數據結點類似，如圖所示。

(4；

刪除T產|立

移位

3.整體測試

將以上功能代碼與例2-2結合，測試數據操作是否成功，代碼參考教材

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

例中，主函數main。主要用于測試子函數是否正確，先創建空的順序

表，然后將數據結點依次插入到順序表的末尾，最后通過兩種方式刪除順序

表中的結點。輸出結果如下所示。

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

1020304050

203040

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

>其他操作

對順序表中的數據結點除了可以進行插入與刪除，還可以進行其他類型

的操作，例如，修改結點數據，查找數據結點位置，刪除重復數據結點，合

并順序表。

1.修改結點數據

修改結點數據指的是對順序表中某一結點的數據進行修改，如圖所示。

2.查找數據結點位置

查找數據結點位置指的是獲取結點的下標值，如圖所示。

Q-數據物

對比

Ac忠談一

滿足條件

輸出卜標為4數據40

3.刪除重復數據結點

刪除重復數據結點指的是刪除順序表中數據相同的結點，如圖所示。

每輪使用?個結點對比其后的所有結點

/

結點0依次對比結點1、2、3、4、5、6

c'AWAb......?

TTYTTT

結點I依次對比結點2、3、4、5,6

4.合并順序表

合并順序表指的是將兩個順序表合并為一個順序表，同時去除數據重復

的結點，如圖所示。

5.整體測試

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

是否成功，代碼參考教材2.2.5節。

＞順序表總結

通過前面的介紹可知，順序表是將數據結點放到一塊連續的內存空間上

（使用數組表示順序表，數組在內存上占有連續的空間），因此順序表結構

較為簡單，根據數據結點的下標即可完成數據的存取。如圖所示。

雖然通過結點下標的方式訪問數據十分高效，但是用戶每次存取數據

時，都需要重新遍歷表，批量移動數據結點。如圖所示。

如圖所示，移動數據是將前一個結點的數據賦值給后一個結點。因此，

無論是刪除還是插入操作，都會導致批量的賦值操作。(賦值操作的本質是

重寫內存)

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

形式一一鏈式存儲(單鏈表)，則可以很好地解決這一問題。

>單鏈表的定義

單鏈表不同于順序表，其結點存儲在內存地址非連續的存儲單元上，并

通過指針建立它們之間的關系。需要注意的是，單鏈表中的結點形式不同于

順序表，如圖所示。

斗中

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

由圖可知，單鏈表中的結點都是由兩部分組成，一部分為數據域(data),

另一部分為指針域(next)。簡單地說，數據域用來存放結點的數據，而指

針域存放的是一個指針，該指針保存的是下一個結點的內存地址，或者說該

指針指向下一個結點，如圖所示。

A

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

>單鏈表的創建

在對單鏈表中的數據進行操作之前，需要先創建一個空的單鏈表。通過

代碼實現創建一個空的單鏈表，如例所示。

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefintdatatypet;

5

6/*定義結點結構體*/

7typedefstructnode{

8datatypetdata;/*數據域*/

9structnode*next;/*指針域，指針指向下一個結點*/

10Jlinklistt;

11

12/*子函數，創建一個空的單鏈表，其本質為創建一個鏈表頭*/

13linklistt*linklistcreate(){

14/*使用malloc函數在內存上申請空間，空間大小為一個結構體的大小*/

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

16

17/*初始化，指針指向為NULL,此時不指向任何其他結點*/

18h->next=NULL;

19returnh;

20)

21intmain(intargc,constchar*argv[])

22(

23linklistt*h;

24h?linklistcreate();/*調用子函數*/

25return0;

26}

＞插入數據結點

2.3.2節完成了創建空單鏈表的操作，接下來將通過代碼展示如何在單

鏈表中插入數據結點。向單鏈表插入數據結點的方法有很多，包括頭插法、

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

1.頭插法

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

數據結點無須判斷單鏈表是否為滿。使用頭插法插入數據結點有兩種不同的

情況，即插入第一個數據結點與插入除第一個結點以外的其他數據結點，如

圖所示。

頭插法插入第一個數據結點的原理

假設該結點為頭結

插入第一步：斷開原來的連接關系，實際不存在，點連”第.個結

next初始指向為NULL點，實際不存在

頭結點

使用新結點的指針指向頭

插入第：步：將頭結點指需要插入的新結點站點連接的第一個結點，

針重新折向新插入的結點實際為NULL

頭插法插入數據結點的厚理

針重新指向新插入的結點結點連接的第一個結點

由圖可以看出，插入數據結點的本質為修改數據結點的指針域，使指針

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

/*參數1為指向頭結點的指針，參數2為新結點的數據*/

intlinklist_head_insert(linklist_t*h,datatype_tvalue){

linklist_t*temp;

/*為新插入的數據結點申請空間*/

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

temp->data=value;/*為新插入結點的數據域賦值數據*/

temp->next=h->next;/*將頭結點指針指向的下一個結點的地址賦值給新結點的指針*/

h->next=temp;/*將頭結點指針指向新的結點*/

return0;

2.尾插法

尾插法即從單鏈表的末尾插入數據結點，如圖所示。

在未插入數據結點之前，該指針指向為NULL

NULL

插入

data?next

新結點

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

/*末尾插入數據結點，參數1為頭結點指針，參數2為插入的數據*/

intlinklist_tail_insert(linklist_t*hzdatatype]value){

linklist_t*temp;

/*為需要插入的數據結點申請內存空間*/

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

/*為需要插入的數據結點賦值數據*/

temp->data=value;

/*遍歷整個單鏈表，找到最后一個結點*/

while(h->next!=NULL){

h=h->next;

}

h->next=temp;/*插入結點*/

temp->next=NULL;/*將插入結點的指針指向NULL*/

return0;

3.順序插入法

順序插入法是頭插法的改良版，在插入數據結點前需要進行判斷，保證

單鏈表中的數據有序排列，如圖所示。

插入數據比結點數據大，則

移動到下一個結點繼續對比

新結點

插入采用頭插法的思想

4.指定位置插入法

指定位置插入法類似于頭插法，不同的是該方法在插入數據結點前進行

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

插入數據時，計算結點的下

標，移動指針到規定的位置

新結點

插入采用頭插法的思想

5.顯示數據結點

插入數據結點完成后，即可通過打印結點數據判斷結點是否插入成功。

遍歷整個單鏈表的方法很簡單，只需要使用指針依次訪問結點中的數據即

可，如圖所示。

判斷h->ncxt為

執行h=h?>ncxt執行h=h?>ncxiNULL

指針發生移動指針發生移動不執行h=h->next

IIll-7\~

X*ncxt-

頭結點

頭結點起始地址為h

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

6.整體測試

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

2.3.3節。

第二課時

（線性表的鏈式存儲、單向循環鏈表、雙向循環鏈表）

Q內容回顧

1.回顧上節內容，引出本課時主題。

上節已經介紹了線性表的定義、線性表的運算、順序表的定義、順序表

的創建、插入數據結點、刪除數據結點、其他操作、順序表總結、單鏈表的

定義、單鏈表的創建和插入數據結點，下面將介紹刪除數據結點、其他操作、

單向循環鏈表的定義、單向循環鏈表的創建、插入數據與顯示數據、雙向循

環鏈表的定義、雙向循環鏈表的創建和插入與刪除數據結點。

2.明確學習目標

(1)能夠掌握刪除數據結點

(2)能夠掌握其他操作

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

(4)能夠掌握單向循環鏈表的創建

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

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

(7)能夠掌握雙向循環鏈表的創建

(8)能夠掌握插入與刪除數據結點

我知識講解

>刪除數據結點

在刪除數據結點之前，需要判斷單鏈表是否為空(如果為空，則不允許

刪除數據結點)。接下來將通過代碼展示如何在單鏈表中刪除數據結點。從

單鏈表刪除數據結點的方法包括頭刪法、指定數據刪除法。

1.頭刪法

刪除數據結點需要先判斷單鏈表是否為空，代碼實現如下所示。(變量

定義與例2-5一致)

/*判斷鏈表是否為空，參數為頭結點的地址*/

intlinklist_empty(linklist_t*h){

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

)

2.指定數據刪除法

指定數據刪除法是根據指定的具體數據，刪除單鏈表中與數據對應的結

點，如圖所示。

3.整體測試

將以上功能代碼與例2-6結合測試，查看數據操作是否成功，代碼參考

教材234節。

例中，主函數主要用于測試子函數是否正確。測試分為3個部分：先創

建一個空單鏈表，使用順序插入法將數據80、60、40插入鏈表，通過顯示

結點數據，判斷結點是否插入成功并自動排序；使用頭刪法將數據從鏈表中

刪除，通過顯示結點數據，判斷第一個結點是否刪除；使用指定數據刪除法

將數據從鏈表中刪除，通過顯示結點數據，判斷數據為80的結點是否刪除。

運行結果如下所示。

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

406080

6080

60

linux@ubuntu:~/1000phone/data$

>其他操作

單鏈表中的數據結點除了可以完成插入與刪除的需求，還可以進行其他

類型的操作，例如，修改結點數據，查找數據結點位置，鏈表數據翻轉，合

并單鏈表。

1.修改結點數據

修改結點數據指的是通過指定的數據在鏈表中尋找匹配的結點，并將該

結點的數據修改。代碼如下所示。

/*子函數，修改結點中的數據*/

/*參數1為指向頭結點的指針，參數2為指定的數據，參數3為新修改的數據*/

intlinklistchange(linklistt*h,datatypetoldvalue,datatypet

newvalue){

/*循環遍歷整個鏈表，查找是否有匹配的結點*/

while(h->next!=NULL){

if(h->next->data==oldvalue)(/*如果有數據匹配的結點*/

h->next->data=newvalue;/*修改結點中的數據*/

return0;

}

else(

h=h->next;/*如果未找到則繼續對比下一個結點*/

}

}

printf(Hnovalue\nM);/*未發現匹配的結點，輸出提示信息*/

return-1;/*返回異常，表示未發現匹配結點*/

)

2.查找數據結點位置

查找數據結點位置指的是通過指定的數據在鏈表中尋找匹配的結點，并

獲取該結點在單鏈表中的下標。

/*子函數，根據指定數據查找匹配的數據結點，輸出結點下標*/

/*參數1為指向頭結點的指針，參數2為指定的數據*/

intlinklist_search(linklist_t*h,datatype/value){

intpos=0;

〃遍歷整個鏈表，查找是否有匹配的結點

while(h->next!=NULL){

if(h->next->data==value){/*如果有數據匹配的結點,/

returnpos;/*返回下標值*/

}

else(

h=h->next;"如果未找到則繼續對比下一個結點*/

pos++;/*下標值加1*/

}

)

printf("nofound\nn);/*未發現匹配的結點，輸出提示信息*/

return-1;/*返回異常，表示未發現匹配結點*/

)

3.鏈表數據翻轉

鏈表數據翻轉指的是將單鏈表中的數據倒序排列。例如，單鏈表中結點

數據的順序為1、2、3、4、5,經過翻轉后結點數據的順序為5、4、3、2、

k如圖所示。

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

4.合并單鏈表

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

頭結點

5.整體測試

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

2.3.5節。

例中，主函數主要用于測試子函數是否正確。測試分為4個部分：先創

建一個空單鏈表1.使用尾插法將數據70、50、20、10插入鏈表，通過顯示

結點數據，判斷結點是否插入成功；將單鏈表1中的結點數據修改為30,通

過顯示結點數據，判斷數據是否修改成功；將單鏈表1中的數據結點翻轉，

通過顯示結點數據，判斷鏈表是否翻轉成功；創建空單鏈表2,使用尾插法

將數據20、40、60插入鏈表，將單鏈表1和單鏈表2進行合并，通過顯示

結點數據，判斷單鏈表合并是否成功。運行結果如下所示。

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

70502010/*鏈表1插入數據成功*/

70503010/*鏈表1修改數據成功*/

10305070/*鏈表1翻轉成功（數據倒置）*/

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

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

＞單向循環鏈表的定義

在單鏈表中，頭結點指針是相當重要的，因為單鏈表的操作都需要頭結

點指針。如果頭指針丟失或者損壞，那么整個鏈表都會遺失，并且浪費鏈表

內存空間。為了避免這種情況的產生，可以將單鏈表設計成循環鏈表。循環

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

單向循環鏈表指的是在單鏈表的基礎上，將尾結點的指針指向鏈表中的

頭結點，而非NULL,如圖所示。

由圖所示，單向循環鏈表中的結點通過指針指向形成一個閉合的連接，

結點的結構與單鏈表相同，代碼如下所示。

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

/*結點結構*/

typedefstructnode{

datatype_tdata;/*結點數據*/

structnode*next;/*指向下一個結點的指針*/

}looplist_t;

A單向循環鏈表的創建

在對單向循環鏈表中的數據進行操作之前，需要先創建一個空表。通過

代碼實現創建空的單向循環鏈表，如例所示。

1#include<stdio.h>

2#include<stdlib.h>

3

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

5

6typedefstructnode{

7datatypetdata;/*結點數據*/

8structnode*next;/*指向下一個結點的指針*/

9)looplistt;

10/*子函數，創建單向循環鏈農*/

11looplistt*looplistcreate(){

12looplistt*h;

13/*使用malloc函數為頭結點申請內存空間，大小為sizeof(looplistt)*/

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

15

16h->next=h;/*將頭結點指針指向自身，開始時只有一個頭結點*/

17

18returnh;/*返回頭結點地址*/

19)

20intmain(intargc,constchar*argv[])

21(

22looplistt*h;

23

24h=looplistcreate();

25return0;

26)

A插入數據與顯示數據

1.頭插法

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

/*頭插法插入數據，參數1為頭結點指針，參數2為插入的結點數據★/

intlooplist_head_insert(looplist_t*h,datatype/value){

looplist_t*temp;

/*使用malloc函數為新插入的結點申請內存空間*/

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

/*為結點賦值，保存數據*/

temp->data=value;

/*頭插法*/

temp->next=h->next;

h->next=temp;

return0;

)

2.顯示數據

顯示數據即獲取單向循環鏈表中結點的數據，代碼如下所示。

/*顯示數據*/

intlooplist_show(looplist_t*h)(

looplist_t*p=h;

/*遍歷數據到最后-一個結點為止*/

while{h->next!=p){

h=h->next;/*移動指針，進行遍歷*/

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

)

printf("\n");

return0;

)

3.整體測試

將以上功能代碼與例2-9結合，測試數據操作是否成功，代碼參考教材

2.4.3節。

>雙向循環鏈表的定義

在單鏈表中，如果需要查找某一個結點的后繼時，直接通過指針移動到

下一個結點即可。但是要查找某一結點的前驅時，則需要從鏈表頭開始。為

了提高數據操作的效率，引入雙向循環鏈表。

雙向循環鏈表中結點的結構與單鏈表不同，每一個結點都有一個指向前

一個結點的指針和一個指向后一個結點的指針，如圖所示。

指向上一個結點指向下一個結點

?priordata*next

結點結構的代碼實現如下所示。

typedefintdatatype_t;

typedefstructnode(

datatype/data;/*結點數據*/

structnode*prior;/*指向上一個結點*/

structnode*next;/*指向下一個結點*/

}dlinklist_t;

＞雙向循環鏈表的創建

在對雙向循環鏈表中的數據進行操作之前，需要先創建一個空表。通過

代碼實現創建空的雙向循環鏈表，如例所示。

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefintdatatypet;

5typedefstructnode{

6datatypetdata;/*結點數據*/

7structnode*prior;/*指向