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

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

3、符串、圖像和聲音等 數(shù)據(jù)元素：數(shù)據(jù)元素：是一個數(shù)據(jù)整體中相對獨立的單位，是一個數(shù)據(jù)整體中相對獨立的單位，也稱也稱元素、結(jié)點、頂點、記錄。一個元素可以由若干個數(shù)元素、結(jié)點、頂點、記錄。一個元素可以由若干個數(shù)據(jù)項（也稱為字段、域、屬性）據(jù)項（也稱為字段、域、屬性） 組成。組成。一、幾個概念：二、數(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)色框（即一行）表示一個數(shù)據(jù)元素數(shù)據(jù)元素或一個數(shù)據(jù)項、一個記錄、一個結(jié)點、一個元素，而每一個數(shù)據(jù)項都包含學(xué)號、姓名、數(shù)學(xué)分析、普通物理、高等代數(shù)、平均成績共6個字段字段或6

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

5、、統(tǒng)計、簡單計算、輸入、輸出等）排序、統(tǒng)計、簡單計算、輸入、輸出等） 二、數(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)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。（2）非線非線性結(jié)

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

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

8、存儲根據(jù)結(jié)點的值來確定結(jié)點的存儲地址查找、插入、刪除、合并、排序、統(tǒng)計、簡單計算、輸入、輸出等。算法算法實質(zhì)上是針對所處理問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上所施加的一種運算。如何設(shè)計數(shù)據(jù)的邏輯結(jié)構(gòu)如何選擇數(shù)據(jù)的物理結(jié)構(gòu)如何優(yōu)化設(shè)計思想和技巧學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的優(yōu)化算法3、數(shù)據(jù)的運算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ù)元素數(shù)據(jù)元素樹圖用圓圈代表一個數(shù)據(jù)元素用圓圈代表一個數(shù)據(jù)元素在邏輯上相鄰的數(shù)據(jù)在存儲時仍然相鄰嗎？在邏輯上相鄰的數(shù)據(jù)在存儲時仍然相鄰嗎？為什么？為什么？順序存儲（如數(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)的基本運算數(shù)據(jù)結(jié)構(gòu)的基本運算 線性

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)的三個方面：小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個方面： 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu) :查找、插入、刪除等查找、插入、刪除等 線性表的長度：線性表的長度：所含元素的個數(shù)所含元素的個數(shù), ,用用n n表示，表示，n=n=。當(dāng)當(dāng)n=0n=0時時, ,表示線性表是一個空表，即表中不包含任何元表示線性表是一個空表，即表中不包含任何元素。素。線性表線性表是由是由n n（n0n0）個）個具有相同特性具有相同特性數(shù)據(jù)元素數(shù)據(jù)元素( (結(jié)點結(jié)點) ) 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、線性表的特點、線性表的特點對于非空的線性表：對于非空的線性表：有且僅有一個開始結(jié)點有且僅有一個開始結(jié)點a a1 1，沒有直接前趨，有且，沒有直接前趨，有且僅有一個直接后繼僅有一個直接后繼a a2 2；有且僅有一個終結(jié)結(jié)點有且僅有一個終結(jié)結(jié)點a an n，沒有直接后繼，有且，沒有直接后繼，有且僅有一個直接前趨僅有一個直接前趨a an-1n-1；其余的內(nèi)部結(jié)點其余的內(nèi)部結(jié)點a ai i（2in-12in-1）都有且僅有一個）都有且僅有一個直接前趨直接前趨a ai-1i-1和一個和一

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

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

14、中中, 確定第一個數(shù)和最后確定第一個數(shù)和最后 一個數(shù)的位置。假設(shè)圓盤上一個數(shù)的位置。假設(shè)圓盤上5為第一個數(shù)，為第一個數(shù)，12為為最后一個數(shù)。則可將這最后一個數(shù)。則可將這20個數(shù)放在個數(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)初始化，將兩個線性表中分別存儲最初的兩個值初始化，將兩個線性表中分別存儲最初的兩個值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） 向計算機申請內(nèi)存地址向計算機申請內(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;指針變量所指向的類型不同，指針變量所指向的類型不同，計算機所給予的存儲單元的多計算機所給予的存儲單元的多少也不相同。少也不相同。指針類型定義中的基類型只能指針類型定義中的基類型只能是類型標(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)系運算對指針變量可以進(jìn)行關(guā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)系運算的結(jié)果關(guān)系運算的結(jié)果, ,仍是仍是 FALSE , TRUE FALSE ,

19、TRUE 。鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)指針變量的基本操作指針變量的基本操作由于指針變量代表的是存儲單元地址，它不能用輸出語句進(jìn)行打印，故在調(diào)試程序時要多加小心1、下面的自定義函數(shù)完成對一個單鏈表的查詢操作，則方框中應(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個元素個元素(1)(1)設(shè)臨時工作變量設(shè)臨時工作變量p p指針指向鏈表的指針指向鏈表的頭結(jié)點頭結(jié)點( (頭結(jié)點的地址不能丟失和改變，頭結(jié)點的地址不能丟失和改變，否則會丟失整個鏈表否則會丟失整個鏈表);); 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é)點，結(jié)點，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é)點刪除）表中節(jié)點刪除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é)點開始沿線性鏈表方向進(jìn)行探求，一從頭結(jié)點開始沿線性鏈表方向進(jìn)行探求，一般用于指向剛查過的結(jié)點地址，另一個用于指向下般用于指向剛查過的結(jié)

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

25、1）初始化）初始化（2 2）申請一個結(jié)點并賦值，然后將結(jié)點插入表頭）申請一個結(jié)點并賦值，然后將結(jié)點插入表頭（3 3）重復(fù)（）重復(fù)（2 2），直到輸入的值為等于），直到輸入的值為等于0 0結(jié)束。結(jié)束。分析：分析：實戰(zhàn)演練實戰(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é)點插入結(jié)點插入 end; read(x); end; headnew(p); p.data:=x;pnext:=nil;q.next:=p; q:=p; 空間空間分配分配靜態(tài)分配。程序執(zhí)行前靜態(tài)分配。程序執(zhí)行前須確定存儲規(guī)模。估計須確定存儲規(guī)模。估計過大造成空間浪費，估過大造成空間浪費，估計太小使空間溢出機會計太小使空間溢出機會增多。增多。 動態(tài)分配動態(tài)分配, ,只要內(nèi)存空間尚有空只要內(nèi)存空間尚有空閑，就不會產(chǎn)生溢出。當(dāng)線性表閑，就不會產(chǎn)生溢出。當(dāng)線

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

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)鏈表為宜。 實戰(zhàn)演練：例實戰(zhàn)演練：例5.25.2線性鏈表的歸并運算：線性鏈表的歸并運算：將下列兩個有序線性表進(jìn)行歸并。將下列兩個有序線性表進(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é)點是按數(shù)據(jù)域由小到大進(jìn)行排）線性鏈表中的結(jié)點是按數(shù)據(jù)域由小到大進(jìn)行排列的，根據(jù)兩個線性列的，根據(jù)兩個線性鏈鏈表中結(jié)點數(shù)據(jù)域的大小進(jìn)行表中結(jié)點數(shù)據(jù)域的大小進(jìn)行歸并運算；哪個表中的數(shù)據(jù)小就歸并哪一個；歸并運算；哪個表中的數(shù)據(jù)小就歸并哪一個；1 1、建立鏈表、建立鏈表2 2、歸并、歸并問題分析：問題分析：（2 2）當(dāng)兩個線性）當(dāng)兩個線性鏈鏈表中有一個已歸并完畢，則另一個線表中有一個已歸并完畢，則另一個線性性鏈鏈表的剩余部分全

30、部復(fù)制到所建立的新線性表的剩余部分全部復(fù)制到所建立的新線性鏈鏈表中。表中。（3 3）如果出現(xiàn)同值時，則選一個值。）如果出現(xiàn)同值時，則選一個值。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é)點加到新鏈表中當(dāng)前結(jié)點加到新鏈表中,p1,p1指針后移指針后移; ; else else 將鏈表將鏈表(2)(2)

31、當(dāng)前結(jié)點加到新鏈表中當(dāng)前結(jié)點加到新鏈表中,p2,p2指針后移指針后移; ; end; end;if p1nil then if p1nil then 將鏈表將鏈表(1)(1)剩余的結(jié)點連接到新表的后面剩余的結(jié)點連接到新表的后面; ;if p2nil then if p2nil then 將鏈表將鏈表(2)(2)剩余結(jié)點連到新表的后面剩余結(jié)點連到新表的后面; ;歸并算法：歸并算法：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時申請了新結(jié)點，能否時申請了新結(jié)點，能否不申請新結(jié)點來實現(xiàn)線性鏈表的歸并？不申請新結(jié)點來實現(xiàn)線性鏈表的歸并？想一想：想一想：不帶附加不帶附加頭結(jié)點的頭結(jié)點的鏈表鏈表heada1 a2 a3 a4a1 a2 a3 a4帶附加頭結(jié)帶附加頭結(jié)點的鏈表點的鏈表線性鏈表的幾種形式：線性鏈表的幾種形式： 其特點如下：其特點如下：單向鏈表單向鏈表雙向鏈表雙向鏈表雙向鏈表雙向鏈表雙鏈表的操作與單鏈表基本一致：雙鏈表的操作與單鏈表基本一致：123412type

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

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