數(shù)據(jù)結(jié)構(gòu)第1講---線性表

1、一、了解計(jì)算機(jī)的工作方式一、了解計(jì)算機(jī)的工作方式l將編好的程序和原始數(shù)據(jù)，輸入并存儲在計(jì)將編好的程序和原始數(shù)據(jù)，輸入并存儲在計(jì)算機(jī)的內(nèi)存儲器中（即算機(jī)的內(nèi)存儲器中（即“存儲程序存儲程序”）；）；l計(jì)算機(jī)按照程序逐條取出指令加以分析，并計(jì)算機(jī)按照程序逐條取出指令加以分析，并執(zhí)行指令規(guī)定的操作（即執(zhí)行指令規(guī)定的操作（即“程序控制程序控制”）。）。l這一原理稱為這一原理稱為存貯程序存貯程序和和程序控制程序控制,是現(xiàn)代計(jì)是現(xiàn)代計(jì)算機(jī)的基本工作方式。算機(jī)的基本工作方式。程序程序是計(jì)算機(jī)的靈魂是計(jì)算機(jī)的靈魂 什么是數(shù)據(jù)結(jié)構(gòu)（什么是數(shù)據(jù)結(jié)構(gòu)（data structuredata structure） 什么是

2、算法（什么是算法（algorithmalgorithm） 什么是語言？什么是語言？程序=數(shù)據(jù)結(jié)構(gòu)+算法是數(shù)據(jù)在計(jì)算機(jī)中的組織方式及相應(yīng)的是數(shù)據(jù)在計(jì)算機(jī)中的組織方式及相應(yīng)的基本訪問操作。基本訪問操作。是解決問題的方法（數(shù)據(jù)處理）或者步驟是解決問題的方法（數(shù)據(jù)處理）或者步驟語言是實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法的載體，即編寫語言是實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法的載體，即編寫程序的工具，如程序的工具，如Pascal，C語言，語言，Qbasic，JAVA，C+，VB等等數(shù)據(jù)：數(shù)據(jù)：能夠被計(jì)算機(jī)輸入、存儲、處理、輸出的一切信能夠被計(jì)算機(jī)輸入、存儲、處理、輸出的一切信息息 ,隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的范疇包括：整數(shù)、實(shí)數(shù)、字

3、符串、圖像和聲音等 數(shù)據(jù)元素：數(shù)據(jù)元素：是一個(gè)數(shù)據(jù)整體中相對獨(dú)立的單位，是一個(gè)數(shù)據(jù)整體中相對獨(dú)立的單位，也稱也稱元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。一個(gè)元素可以由若干個(gè)數(shù)元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。一個(gè)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也稱為字段、域、屬性）據(jù)項(xiàng)（也稱為字段、域、屬性） 組成。組成。一、幾個(gè)概念：二、數(shù)據(jù)結(jié)構(gòu)的基本知識數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。將數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。 紅色代表各類數(shù)據(jù)，藍(lán)色框（即一行）表示一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素或一個(gè)數(shù)據(jù)項(xiàng)、一個(gè)記錄、一個(gè)結(jié)點(diǎn)、一個(gè)元素，而每一個(gè)數(shù)據(jù)項(xiàng)都包含學(xué)號、姓名、數(shù)學(xué)分析、普通物理、高等代數(shù)、平均成績共6個(gè)字段字段或6

4、個(gè)域域，其中能通過學(xué)號字段唯一地識別一行記錄，那么學(xué)號字段稱為關(guān)鍵字段。 沒有前驅(qū)的結(jié)點(diǎn)稱為開始結(jié)點(diǎn)開始結(jié)點(diǎn)，沒有后繼的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)終端結(jié)點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)（數(shù)據(jù)元素之間的聯(lián)系，（數(shù)據(jù)元素之間的聯(lián)系，如哪個(gè)元素是第一個(gè)元素、哪個(gè)元素是第二個(gè)元素、如哪個(gè)元素是第一個(gè)元素、哪個(gè)元素是第二個(gè)元素、它的前驅(qū)和后繼是什么）它的前驅(qū)和后繼是什么） 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)（數(shù)據(jù)在計(jì)算機(jī)中的存儲（數(shù)據(jù)在計(jì)算機(jī)中的存儲方式，數(shù)據(jù)的存放方式有順序、鏈接、索引、散列方式，數(shù)據(jù)的存放方式有順序、鏈接、索引、散列等等 ） 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算（查找、插入、刪除、合并、（查找、插入、刪除、合并、排序

5、、統(tǒng)計(jì)、簡單計(jì)算、輸入、輸出等）排序、統(tǒng)計(jì)、簡單計(jì)算、輸入、輸出等） 二、數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，以下研究的數(shù)據(jù)結(jié)構(gòu)，均指邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)，以下研究的數(shù)據(jù)結(jié)構(gòu)，均指邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)1、數(shù)據(jù)的邏輯結(jié)構(gòu)（1）線線性結(jié)構(gòu)性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。（2）非線非線性結(jié)

6、構(gòu)性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。2、通過圖理解線性與非線性線性結(jié)構(gòu)舉例：舉例：10個(gè)學(xué)生按學(xué)號排列示意圖：示意圖： 特點(diǎn)：特點(diǎn)：每個(gè)數(shù)據(jù)只有一個(gè)前驅(qū)、一個(gè)后繼（第每個(gè)數(shù)據(jù)只有一個(gè)前驅(qū)、一個(gè)后繼（第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼）一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼）是是1：1的關(guān)系。的關(guān)系。樹型結(jié)構(gòu)舉例：舉例：一個(gè)領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)的關(guān)系一個(gè)領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)的關(guān)系(14人，單向人，單向)示意圖：示意圖： 特點(diǎn)：特點(diǎn)：除第一個(gè)結(jié)點(diǎn)除第一個(gè)結(jié)點(diǎn)外，都有一個(gè)前驅(qū)，外，都有一個(gè)前驅(qū)，可有多個(gè)后繼可有多個(gè)后繼 ；最下；最下一層只有前驅(qū)

7、無后繼一層只有前驅(qū)無后繼 ，是是1：N的關(guān)系。的關(guān)系。圖型結(jié)構(gòu)舉例：舉例：人與人之間互相認(rèn)識的關(guān)系人與人之間互相認(rèn)識的關(guān)系(雙向的雙向的) 示意圖：示意圖：特點(diǎn)：特點(diǎn)：每個(gè)結(jié)點(diǎn)都可有多個(gè)前驅(qū)和多個(gè)后每個(gè)結(jié)點(diǎn)都可有多個(gè)前驅(qū)和多個(gè)后繼繼 ，M：N的關(guān)系。的關(guān)系。 順序存儲把邏輯上相鄰的結(jié)點(diǎn)存儲在物理上相鄰的存儲單元,通常借助于程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)鏈?zhǔn)酱鎯壿嬌舷噜徳夭灰笃湮锢砦恢孟噜彛亻g的邏輯關(guān)系通過附設(shè)的指針字段來表示,每個(gè)結(jié)點(diǎn)的存儲單元由數(shù)據(jù)域和指針域兩部分組成2、數(shù)據(jù)的存儲結(jié)構(gòu)有時(shí)，為了查找的方便，還采用索引存儲方法和散列存儲方法。索引存儲用結(jié)點(diǎn)的索引號來確定結(jié)點(diǎn)的存儲地址散列

8、存儲根據(jù)結(jié)點(diǎn)的值來確定結(jié)點(diǎn)的存儲地址查找、插入、刪除、合并、排序、統(tǒng)計(jì)、簡單計(jì)算、輸入、輸出等。算法算法實(shí)質(zhì)上是針對所處理問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上所施加的一種運(yùn)算。如何設(shè)計(jì)數(shù)據(jù)的邏輯結(jié)構(gòu)如何選擇數(shù)據(jù)的物理結(jié)構(gòu)如何優(yōu)化設(shè)計(jì)思想和技巧學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的優(yōu)化算法3、數(shù)據(jù)的運(yùn)算3、小結(jié)三種基本數(shù)據(jù)結(jié)構(gòu)、小結(jié)三種基本數(shù)據(jù)結(jié)構(gòu)考慮數(shù)據(jù)之間前驅(qū)與后繼的對應(yīng)關(guān)系考慮數(shù)據(jù)之間前驅(qū)與后繼的對應(yīng)關(guān)系:l線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對一的線性關(guān)系數(shù)據(jù)元素之間存在一對一的線性關(guān)系(1:1)l樹形結(jié)構(gòu)樹形結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對多的層次關(guān)系數(shù)據(jù)元素之間存在一對多的層次關(guān)系(1:N)l圖狀結(jié)

9、構(gòu)圖狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對多的網(wǎng)狀關(guān)系數(shù)據(jù)元素之間存在多對多的網(wǎng)狀關(guān)系(M:N) 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02線性表圖書館書目表數(shù)據(jù)元素?cái)?shù)據(jù)元素樹圖用圓圈代表一個(gè)數(shù)據(jù)元素用圓圈代表一個(gè)數(shù)據(jù)元素在邏輯上相鄰的數(shù)據(jù)在存儲時(shí)仍然相鄰嗎？在邏輯上相鄰的數(shù)據(jù)在存儲時(shí)仍然相鄰嗎？為什么？為什么？順序存儲（如數(shù)組，相鄰）順序存儲（如數(shù)組，相鄰）鏈?zhǔn)酱鎯Γㄈ缰羔槪幌噜彛╂準(zhǔn)酱鎯Γㄈ缰羔?，不相鄰?數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算 線性

10、結(jié)構(gòu)線性結(jié)構(gòu) 順序存儲順序存儲 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu) :查找、插入、刪除等查找、插入、刪除等 線性表的長度：線性表的長度：所含元素的個(gè)數(shù)所含元素的個(gè)數(shù), ,用用n n表示，表示，n=n=。當(dāng)當(dāng)n=0n=0時(shí)時(shí), ,表示線性表是一個(gè)空表，即表中不包含任何元表示線性表是一個(gè)空表，即表中不包含任何元素。素。線性表線性表是由是由n n（n0n0）個(gè)）個(gè)具有相同特性具有相同特性數(shù)據(jù)元素?cái)?shù)據(jù)元素( (結(jié)點(diǎn)結(jié)點(diǎn)) ) a a1 1，a a2 2，a an n組成的有限序列。組成的有限序列。1、線性表的概念、線

11、性表的概念a1a2aiai+1an線性表的邏輯結(jié)構(gòu)表示：線性表的邏輯結(jié)構(gòu)表示：三、線性結(jié)構(gòu)三、線性結(jié)構(gòu)線性表線性表2、線性表的特點(diǎn)、線性表的特點(diǎn)對于非空的線性表：對于非空的線性表：有且僅有一個(gè)開始結(jié)點(diǎn)有且僅有一個(gè)開始結(jié)點(diǎn)a a1 1，沒有直接前趨，有且，沒有直接前趨，有且僅有一個(gè)直接后繼僅有一個(gè)直接后繼a a2 2；有且僅有一個(gè)終結(jié)結(jié)點(diǎn)有且僅有一個(gè)終結(jié)結(jié)點(diǎn)a an n，沒有直接后繼，有且，沒有直接后繼，有且僅有一個(gè)直接前趨僅有一個(gè)直接前趨a an-1n-1；其余的內(nèi)部結(jié)點(diǎn)其余的內(nèi)部結(jié)點(diǎn)a ai i（2in-12in-1）都有且僅有一個(gè)）都有且僅有一個(gè)直接前趨直接前趨a ai-1i-1和一個(gè)和一

12、個(gè)a ai+1i+1。3、線性表的基本操作、線性表的基本操作u初始化：設(shè)置一個(gè)空的線性表u求長度：求線性表中數(shù)據(jù)元素的個(gè)數(shù)u獲取元素：取出線性表中的某個(gè)數(shù)據(jù)元素u查找：搜索線性表里滿足某一條件的元素u插入：把給定元素插入到線性表中u刪除：刪除線性表中的元素u判斷線性表是否滿: :若滿,返回True，否則返回Falseu判斷線性表是否空: :若空,返回True，否則返回False數(shù)據(jù)結(jié)構(gòu)教材數(shù)據(jù)結(jié)構(gòu)教材P22P22在我們生活中有哪些屬于線性表的例子在我們生活中有哪些屬于線性表的例子,列舉幾個(gè)。列舉幾個(gè)。1 1、英文字母表（、英文字母表（A A，B B，Z Z）是線性表，）是線性表，表中每個(gè)字母是

13、一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）表中每個(gè)字母是一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）2 2、學(xué)生成績表中，每個(gè)學(xué)生及其成績是一、學(xué)生成績表中，每個(gè)學(xué)生及其成績是一個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號、姓名、個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。 順序存儲是線性表的一種最順序存儲是線性表的一種最簡單的存儲結(jié)構(gòu)，存儲方式是：簡單的存儲結(jié)構(gòu)，存儲方式是：在內(nèi)存中為線性表開辟一塊連在內(nèi)存中為線性表開辟一塊連續(xù)的存儲空間續(xù)的存儲空間。用數(shù)組來存放用數(shù)組來存放每一個(gè)節(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)。s+n-1s+i-1s+1sanaia3a2a1內(nèi) 存單 元編 號 (1)設(shè)和存放在設(shè)和存放在S

14、中中, 確定第一個(gè)數(shù)和最后確定第一個(gè)數(shù)和最后 一個(gè)數(shù)的位置。假設(shè)圓盤上一個(gè)數(shù)的位置。假設(shè)圓盤上5為第一個(gè)數(shù)，為第一個(gè)數(shù)，12為為最后一個(gè)數(shù)。則可將這最后一個(gè)數(shù)。則可將這20個(gè)數(shù)放在個(gè)數(shù)放在a數(shù)組中。數(shù)組的下數(shù)組中。數(shù)組的下標(biāo)取標(biāo)取0-19。0imax then begin max:=s;smax:=i;end; if sm*fzk do k:=k+1; if z*fmkm*fzk then begin 插入表中插入表中 end; end;(2)初始化，將兩個(gè)線性表中分別存儲最初的兩個(gè)值初始化，將兩個(gè)線性表中分別存儲最初的兩個(gè)值fz1:=0;fm1:=1;fz2:=1;fm2:=1;total:

15、=2; 下標(biāo)下標(biāo)12分子分子01分母分母11如何將數(shù)據(jù)插入到如何將數(shù)據(jù)插入到k k位置處？位置處？K to total?關(guān)于數(shù)組的復(fù)習(xí) 排序 查找 方陣 高精度5 5、線性表的鏈?zhǔn)酱鎯?、線性表的鏈?zhǔn)酱鎯χ羔樖且源鎯卧牡刂纷鳛槠渲档囊环N數(shù)據(jù)類型，是一種可指針是以存儲單元的地址作為其值的一種數(shù)據(jù)類型，是一種可以根據(jù)需要動態(tài)申請內(nèi)存單元的一種數(shù)據(jù)類型。以根據(jù)需要動態(tài)申請內(nèi)存單元的一種數(shù)據(jù)類型。 100 p1p134F234F234F234F2定義方式：定義方式：Type Type 指針類型標(biāo)識符指針類型標(biāo)識符=類型標(biāo)識符類型標(biāo)識符； var var 指針變量名：指針類型標(biāo)識符；指針變量名：指針類

16、型標(biāo)識符；newnew（p1p1） 向計(jì)算機(jī)申請內(nèi)存地址向計(jì)算機(jī)申請內(nèi)存地址 鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)如何申請、釋放存儲單元如何申請、釋放存儲單元 p1p134F234F234F234F2typetype p=integer; p=integer;var p1:p;var p1:p;p1:=200p1:=200 給給p1p1指向的單元賦值指向的單元賦值dispose(p1) 釋放存儲單元釋放存儲單元20020034F2 地址被釋放，變量P與地址34F2沒有關(guān)系 p1:integer;arrp = array1.10 of real；Type p=integer; arr=array1.4 of cha

17、r; arrp = arr; Var p1:p; p2:arrp;指針變量所指向的類型不同，指針變量所指向的類型不同，計(jì)算機(jī)所給予的存儲單元的多計(jì)算機(jī)所給予的存儲單元的多少也不相同。少也不相同。指針類型定義中的基類型只能指針類型定義中的基類型只能是類型標(biāo)識符，不能是具體的是類型標(biāo)識符，不能是具體的類型定義。類型定義。 p1p1 p2p2i鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)什么是指針什么是指針 beginbegin new(p1);p1:=100; new(p1);p1:=100; new(p2);p2:=200; new(p2);p2:=200; p1:=p2; p1:=p2; end. end.3010301

18、1402040214022402340243011p14024p24024p1(1) (1) 同一基類型的指針變量可以互相賦值。同一基類型的指針變量可以互相賦值。鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)指針變量的基本操作指針變量的基本操作p1:=p2; ?(2)(2)對指針變量可以進(jìn)行關(guān)系運(yùn)算對指針變量可以進(jìn)行關(guān)系運(yùn)算 如如:if P1P2 then :if P1P2 then 語句語句1 else 1 else 語句語句2; 2; while P3 NIL do while P3 NIL do . . . . end; end; 關(guān)系運(yùn)算的結(jié)果關(guān)系運(yùn)算的結(jié)果, ,仍是仍是 FALSE , TRUE FALSE ,

19、TRUE 。鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)指針變量的基本操作指針變量的基本操作由于指針變量代表的是存儲單元地址，它不能用輸出語句進(jìn)行打印，故在調(diào)試程序時(shí)要多加小心1、下面的自定義函數(shù)完成對一個(gè)單鏈表的查詢操作，則方框中應(yīng)填入（ ）。function find(var head:pointer;var x:integer):pointer;var p:pointer;begin p:=head; while ( ) do p:=p.next; find := p;end;A(p.datax) B(pnil)C(p.datax) OR (pnil) D(p.datax) AND (pnil)2、下列關(guān)于線性表的

20、敘述正確的是（）A、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B、線性表采用順序存儲，便于進(jìn)行插入和刪除操作C、線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元D、線性表采用鏈接存儲，便于插入和刪除操作Type p= node ; node= record data : integer ; next:p； end; var p1, p2 : p1 1、查找鏈表的第、查找鏈表的第n n個(gè)元素個(gè)元素(1)(1)設(shè)臨時(shí)工作變量設(shè)臨時(shí)工作變量p p指針指向鏈表的指針指向鏈表的頭結(jié)點(diǎn)頭結(jié)點(diǎn)( (頭結(jié)點(diǎn)的地址不能丟失和改變，頭結(jié)點(diǎn)的地址不能丟失和改變，否則會丟失整個(gè)鏈表否則會丟失整個(gè)鏈表);); p:=

21、head; p:=head;(2)x:=0;(2)x:=0; while xn do while xn do begin begin inc(x);p:=p.next; inc(x);p:=p.next; end; end; 2 2、鏈表元素的刪除（、鏈表元素的刪除（刪除刪除r r結(jié)點(diǎn)，結(jié)點(diǎn)，p p是是r r的前驅(qū)的前驅(qū)）（1 1）表頭刪除）表頭刪除p:=head;r:=p.next;p.next:=r.next; dispose(r);rheadnilpr:=p.next;p.next:=nil; dispose(r);（2 2）表尾刪除）表尾刪除headnilrpnilheadnilrpr

22、:=p.next;p.next:=r.next; dispose(r);（3 3）表中節(jié)點(diǎn)刪除）表中節(jié)點(diǎn)刪除3 3、鏈表元素的插入、鏈表元素的插入 new(s);readln(x);s.data:=x;new(s);readln(x);s.data:=x; s.next:=nil; p.next:=s s.next:=nil; p.next:=s表尾插入headpsxnilnew(s);readln(x);s.data:=x; new(s);readln(x);s.data:=x; s.next:=head; head:=ss.next:=head; head:=s；表頭插入headpsnil

23、xnew(s);readln(x);s.data:=x;new(s);readln(x);s.data:=x;s.next:=p.next; p.next:=ss.next:=p.next; p.next:=spheadsnilx表中插入線性鏈表應(yīng)用的三種模式：線性鏈表應(yīng)用的三種模式： （1）數(shù)據(jù)元素的查找數(shù)據(jù)元素的查找 （2）數(shù)據(jù)元素的插入數(shù)據(jù)元素的插入 （3）數(shù)據(jù)元素的刪除。數(shù)據(jù)元素的刪除。線性鏈表的訪問基本方法是：線性鏈表的訪問基本方法是：（1 1）從頭結(jié)點(diǎn)開始沿線性鏈表方向進(jìn)行探求，一從頭結(jié)點(diǎn)開始沿線性鏈表方向進(jìn)行探求，一般用于指向剛查過的結(jié)點(diǎn)地址，另一個(gè)用于指向下般用于指向剛查過的結(jié)

24、點(diǎn)地址，另一個(gè)用于指向下一個(gè)待查的結(jié)點(diǎn)地址。一個(gè)待查的結(jié)點(diǎn)地址。（2 2）結(jié)束訪問的條件有兩個(gè)：一個(gè)是結(jié)點(diǎn)地址為結(jié)束訪問的條件有兩個(gè)：一個(gè)是結(jié)點(diǎn)地址為Nil,Nil,另一個(gè)是找到了相應(yīng)的結(jié)點(diǎn)。另一個(gè)是找到了相應(yīng)的結(jié)點(diǎn)。 容易出錯(cuò)的是：當(dāng)容易出錯(cuò)的是：當(dāng)p p為為nilnil時(shí)，取時(shí)，取p.datap.data時(shí)出錯(cuò)，時(shí)出錯(cuò)，因?yàn)橐驗(yàn)閜 p是是nilnil，p.datap.data的值無意義。的值無意義。例例5.15.1：輸入一個(gè)正整數(shù)序列：輸入一個(gè)正整數(shù)序列, ,遇遇0 0時(shí)停止，按輸入時(shí)停止，按輸入數(shù)據(jù)的順序建立如下鏈表數(shù)據(jù)的順序建立如下鏈表: :（從表頭插入結(jié)點(diǎn)）（從表頭插入結(jié)點(diǎn)） （1

25、1）初始化）初始化（2 2）申請一個(gè)結(jié)點(diǎn)并賦值，然后將結(jié)點(diǎn)插入表頭）申請一個(gè)結(jié)點(diǎn)并賦值，然后將結(jié)點(diǎn)插入表頭（3 3）重復(fù)（）重復(fù)（2 2），直到輸入的值為等于），直到輸入的值為等于0 0結(jié)束。結(jié)束。分析：分析：實(shí)戰(zhàn)演練實(shí)戰(zhàn)演練 readln(n) ; head:=nil; while n 0 do插入表頭插入表頭,形成鏈表形成鏈表 begin new ( p ) ; p.data:=n; p.next:=head; head:= p ; read ( n ) ; end ; 參考程序：參考程序： head:=nil; read(x); while x0 do begin if head=nil

26、 then begin new(p); p.data:=x;p.next:=nil; q:=p; head:=p end else begin 結(jié)點(diǎn)插入結(jié)點(diǎn)插入 end; read(x); end; headnew(p); p.data:=x;pnext:=nil;q.next:=p; q:=p; 空間空間分配分配靜態(tài)分配。程序執(zhí)行前靜態(tài)分配。程序執(zhí)行前須確定存儲規(guī)模。估計(jì)須確定存儲規(guī)模。估計(jì)過大造成空間浪費(fèi)，估過大造成空間浪費(fèi)，估計(jì)太小使空間溢出機(jī)會計(jì)太小使空間溢出機(jī)會增多。增多。 動態(tài)分配動態(tài)分配, ,只要內(nèi)存空間尚有空只要內(nèi)存空間尚有空閑，就不會產(chǎn)生溢出。當(dāng)線性表閑，就不會產(chǎn)生溢出。當(dāng)線

27、性表的長度變化較大，難以估計(jì)存儲的長度變化較大，難以估計(jì)存儲規(guī)模時(shí)，宜采用動態(tài)鏈表作存儲規(guī)模時(shí)，宜采用動態(tài)鏈表作存儲結(jié)構(gòu)為好結(jié)構(gòu)為好。 時(shí)間時(shí)間存取存取隨機(jī)存取結(jié)構(gòu)，查找方隨機(jī)存取結(jié)構(gòu)，查找方便，但插入和刪除操作便，但插入和刪除操作很費(fèi)時(shí)。很費(fèi)時(shí)。順序存取結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)，順序存取結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)，需從頭指針起順著鏈掃描才能取需從頭指針起順著鏈掃描才能取得。得。 插入插入刪除刪除操作操作在順序表中進(jìn)行插入和在順序表中進(jìn)行插入和刪除，平均要移動表中刪除，平均要移動表中近一半的結(jié)點(diǎn)，尤其是近一半的結(jié)點(diǎn)，尤其是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動結(jié)點(diǎn)的時(shí)間大時(shí)，移動結(jié)點(diǎn)的時(shí)間開銷就

28、相當(dāng)可觀。開銷就相當(dāng)可觀。 在鏈表進(jìn)行插入和刪除，只需要在鏈表進(jìn)行插入和刪除，只需要修改指針。對于頻繁進(jìn)行插入和修改指針。對于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。指針表示的單循環(huán)鏈表為宜。 實(shí)戰(zhàn)演練：例實(shí)戰(zhàn)演練：例5.25.2線性鏈表的歸并運(yùn)算：線性鏈表的歸并運(yùn)算：將下列兩個(gè)有序線性表進(jìn)行歸并。將下列兩個(gè)有序線性表進(jìn)行歸并。線性表（線性表（1 1）是：）是：33，5 5，8 8，1111，1313線性表（線性表（2 2）是：

29、）是：11，4 4，5 5，9 9，1515歸并后的線性表為：歸并后的線性表為：11，3 3，4 4，5 5，8 8，9 9，1111，1313，1515（1 1）線性鏈表中的結(jié)點(diǎn)是按數(shù)據(jù)域由小到大進(jìn)行排）線性鏈表中的結(jié)點(diǎn)是按數(shù)據(jù)域由小到大進(jìn)行排列的，根據(jù)兩個(gè)線性列的，根據(jù)兩個(gè)線性鏈鏈表中結(jié)點(diǎn)數(shù)據(jù)域的大小進(jìn)行表中結(jié)點(diǎn)數(shù)據(jù)域的大小進(jìn)行歸并運(yùn)算；哪個(gè)表中的數(shù)據(jù)小就歸并哪一個(gè)；歸并運(yùn)算；哪個(gè)表中的數(shù)據(jù)小就歸并哪一個(gè)；1 1、建立鏈表、建立鏈表2 2、歸并、歸并問題分析：問題分析：（2 2）當(dāng)兩個(gè)線性）當(dāng)兩個(gè)線性鏈鏈表中有一個(gè)已歸并完畢，則另一個(gè)線表中有一個(gè)已歸并完畢，則另一個(gè)線性性鏈鏈表的剩余部分全

30、部復(fù)制到所建立的新線性表的剩余部分全部復(fù)制到所建立的新線性鏈鏈表中。表中。（3 3）如果出現(xiàn)同值時(shí)，則選一個(gè)值。）如果出現(xiàn)同值時(shí)，則選一個(gè)值。p1:=head1;p2:=head2;p1:=head1;p2:=head2;while (p1nil) and (p2nil) dowhile (p1nil) and (p2nil) do begin begin if p1.data=p2.data if p1.data=p2.data then then 將鏈表將鏈表(1)(1)當(dāng)前結(jié)點(diǎn)加到新鏈表中當(dāng)前結(jié)點(diǎn)加到新鏈表中,p1,p1指針后移指針后移; ; else else 將鏈表將鏈表(2)(2)

31、當(dāng)前結(jié)點(diǎn)加到新鏈表中當(dāng)前結(jié)點(diǎn)加到新鏈表中,p2,p2指針后移指針后移; ; end; end;if p1nil then if p1nil then 將鏈表將鏈表(1)(1)剩余的結(jié)點(diǎn)連接到新表的后面剩余的結(jié)點(diǎn)連接到新表的后面; ;if p2nil then if p2nil then 將鏈表將鏈表(2)(2)剩余結(jié)點(diǎn)連到新表的后面剩余結(jié)點(diǎn)連到新表的后面; ;歸并算法：歸并算法：procedure combine(var head3:point;head1,head2:point);procedure combine(var head3:point;head1,head2:point); va

32、r p1,p2,q,r:point; var p1,p2,q,r:point; begin begin new(head3);r:=head3; new(head3);r:=head3; p1:=head1;p2:=head2; p1:=head1;p2:=head2; while (p1nil) and (p2nil) do while (p1nil) and (p2nil) do if p1.data=p2.data if p1.data=p2.data then begin then begin new(q);r.next:=q;q.data:=p1.data; new(q);r.nex

33、t:=q;q.data:=p1.data; r:=q; p1:=p1.next; r:=q; p1:=p1.next; if if p1.data=p2.data then p2:=p2.next; end end else begin else begin new(q);r.next:=q;q.data:=p2.data;r:=q; new(q);r.next:=q;q.data:=p2.data;r:=q; p2:=p2.next; p2:=p2.next; end; end; if p1nil then r.next:=p1; if p1nil then r.next:=p1; if p

34、2nil then r.next:=p2; if p2nil then r.next:=p2; end; end;本算法在構(gòu)建鏈表本算法在構(gòu)建鏈表3 3時(shí)申請了新結(jié)點(diǎn)，能否時(shí)申請了新結(jié)點(diǎn)，能否不申請新結(jié)點(diǎn)來實(shí)現(xiàn)線性鏈表的歸并？不申請新結(jié)點(diǎn)來實(shí)現(xiàn)線性鏈表的歸并？想一想：想一想：不帶附加不帶附加頭結(jié)點(diǎn)的頭結(jié)點(diǎn)的鏈表鏈表heada1 a2 a3 a4a1 a2 a3 a4帶附加頭結(jié)帶附加頭結(jié)點(diǎn)的鏈表點(diǎn)的鏈表線性鏈表的幾種形式：線性鏈表的幾種形式： 其特點(diǎn)如下：其特點(diǎn)如下：單向鏈表單向鏈表雙向鏈表雙向鏈表雙向鏈表雙向鏈表雙鏈表的操作與單鏈表基本一致：雙鏈表的操作與單鏈表基本一致：123412type

35、type point=node; point=node; node=record node=record data:datatype; data:datatype; pre,next:point; pre,next:point; end; end;(1)每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向其前驅(qū)結(jié)點(diǎn)，一一個(gè)指向其前驅(qū)結(jié)點(diǎn)，一個(gè)指向其后繼結(jié)點(diǎn)。個(gè)指向其后繼結(jié)點(diǎn)。(2)從任一結(jié)點(diǎn)出發(fā)可以訪從任一結(jié)點(diǎn)出發(fā)可以訪問其他結(jié)點(diǎn)。問其他結(jié)點(diǎn)。便于訪問、插入和刪除。便于訪問、插入和刪除。單循環(huán)鏈表單循環(huán)鏈表雙循環(huán)鏈表雙循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表（1 1）尾結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)）尾結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)

36、（2 2）從表中任一個(gè)結(jié)點(diǎn)出發(fā)可以找到鏈表中的其他結(jié)點(diǎn)。）從表中任一個(gè)結(jié)點(diǎn)出發(fā)可以找到鏈表中的其他結(jié)點(diǎn)。（3 3）遍歷操作的結(jié)束條件是：）遍歷操作的結(jié)束條件是：（4 4）其他操作與單鏈表一樣。）其他操作與單鏈表一樣。循環(huán)鏈表循環(huán)鏈表注意：注意：帶附加頭結(jié)點(diǎn)帶附加頭結(jié)點(diǎn) p=head.nextp=head.next不帶附加頭結(jié)點(diǎn)不帶附加頭結(jié)點(diǎn)p=headp=head雙向循環(huán)鏈表：最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，雙向循環(huán)鏈表：最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的前趨指向最后一個(gè)結(jié)點(diǎn)。如下圖：且頭結(jié)點(diǎn)的前趨指向最后一個(gè)結(jié)點(diǎn)。如下圖： 問題描述：設(shè)有問題描述：設(shè)有n n個(gè)人圍成一圈，并按順個(gè)人圍成一圈，并按順時(shí)針方向從時(shí)針方向從1 1到到n n編號；從第編號；從第s s個(gè)人開始進(jìn)個(gè)人開始進(jìn)行行1 1到到m m報(bào)數(shù)，數(shù)到報(bào)數(shù)，數(shù)到m m的人出圈；接著再從的人出圈；接著再從他后面一個(gè)人重新開始他后面一個(gè)人重新開始1 1到到m m報(bào)數(shù)，直到報(bào)數(shù)，直到所有人出圈為止。輸出出圈人的次序。所有人出圈為止。輸出出圈人的次序。