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

1、一、了解計(jì)算機(jī)的工作方式一、了解計(jì)算機(jī)的工作方式l將編好的程序和原始數(shù)據(jù)，輸入并存儲(chǔ)在計(jì)將編好的程序和原始數(shù)據(jù)，輸入并存儲(chǔ)在計(jì)算機(jī)的內(nèi)存儲(chǔ)器中（即算機(jī)的內(nèi)存儲(chǔ)器中（即“存儲(chǔ)程序存儲(chǔ)程序”）；）；l計(jì)算機(jī)按照程序逐條取出指令加以分析，并計(jì)算機(jī)按照程序逐條取出指令加以分析，并執(zhí)行指令規(guī)定的操作（即執(zhí)行指令規(guī)定的操作（即“程序控制程序控制”）。）。l這一原理稱(chēng)為這一原理稱(chēng)為存貯程序存貯程序和和程序控制程序控制,是現(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） 什么是語(yǔ)言？什么是語(yǔ)言？程序=數(shù)據(jù)結(jié)構(gòu)+算法是數(shù)據(jù)在計(jì)算機(jī)中的組織方式及相應(yīng)的是數(shù)據(jù)在計(jì)算機(jī)中的組織方式及相應(yīng)的基本訪問(wèn)操作。基本訪問(wèn)操作。是解決問(wèn)題的方法（數(shù)據(jù)處理）或者步驟是解決問(wèn)題的方法（數(shù)據(jù)處理）或者步驟語(yǔ)言是實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法的載體，即編寫(xiě)語(yǔ)言是實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法的載體，即編寫(xiě)程序的工具，如程序的工具，如Pascal，C語(yǔ)言，語(yǔ)言，Qbasic，JAVA，C+，VB等等數(shù)據(jù)：數(shù)據(jù)：能夠被計(jì)算機(jī)輸入、存儲(chǔ)、處理、輸出的一切信能夠被計(jì)算機(jī)輸入、存儲(chǔ)、處理、輸出的一切信息息 ,隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的范疇包括：整數(shù)、實(shí)數(shù)、字

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

4、個(gè)域域，其中能通過(guò)學(xué)號(hào)字段唯一地識(shí)別一行記錄，那么學(xué)號(hào)字段稱(chēng)為關(guān)鍵字段。 沒(méi)有前驅(qū)的結(jié)點(diǎn)稱(chēng)為開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)，沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為終端結(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ī)中的存儲(chǔ)（數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，數(shù)據(jù)的存放方式有順序、鏈接、索引、散列方式，數(shù)據(jù)的存放方式有順序、鏈接、索引、散列等等 ） 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算（查找、插入、刪除、合并、（查找、插入、刪除、合并、排序

5、、統(tǒng)計(jì)、簡(jiǎn)單計(jì)算、輸入、輸出等）排序、統(tǒng)計(jì)、簡(jiǎn)單計(jì)算、輸入、輸出等） 二、數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱(chēng)為在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱(chēng)為數(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)有兩大類(lèi)：線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類(lèi)：線性結(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è)開(kāi)始結(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ù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。2、通過(guò)圖理解線性與非線性線性結(jié)構(gòu)舉例：舉例：10個(gè)學(xué)生按學(xué)號(hào)排列示意圖：示意圖： 特點(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)系。樹(shù)型結(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、無(wú)后繼一層只有前驅(qū)無(wú)后繼 ，是是1：N的關(guān)系。的關(guān)系。圖型結(jié)構(gòu)舉例：舉例：人與人之間互相認(rèn)識(shí)的關(guān)系人與人之間互相認(rèn)識(shí)的關(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)系。 順序存儲(chǔ)把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元,通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)邏輯上相鄰元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示,每個(gè)結(jié)點(diǎn)的存儲(chǔ)單元由數(shù)據(jù)域和指針域兩部分組成2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有時(shí)，為了查找的方便，還采用索引存儲(chǔ)方法和散列存儲(chǔ)方法。索引存儲(chǔ)用結(jié)點(diǎn)的索引號(hào)來(lái)確定結(jié)點(diǎn)的存儲(chǔ)地址散列

8、存儲(chǔ)根據(jù)結(jié)點(diǎn)的值來(lái)確定結(jié)點(diǎn)的存儲(chǔ)地址查找、插入、刪除、合并、排序、統(tǒng)計(jì)、簡(jiǎn)單計(jì)算、輸入、輸出等。算法算法實(shí)質(zhì)上是針對(duì)所處理問(wèn)題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(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ū)與后繼的對(duì)應(yīng)關(guān)系考慮數(shù)據(jù)之間前驅(qū)與后繼的對(duì)應(yīng)關(guān)系:l線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系(1:1)l樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系(1:N)l圖狀結(jié)

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

10、結(jié)構(gòu)線性結(jié)構(gòu) 順序存儲(chǔ)順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 樹(shù)形結(jié)構(gòu)樹(shù)形結(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) :查找、插入、刪除等查找、插入、刪除等 線性表的長(zhǎng)度：線性表的長(zhǎng)度：所含元素的個(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)對(duì)于非空的線性表：對(duì)于非空的線性表：有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a a1 1，沒(méi)有直接前趨，有且，沒(méi)有直接前趨，有且僅有一個(gè)直接后繼僅有一個(gè)直接后繼a a2 2；有且僅有一個(gè)終結(jié)結(jié)點(diǎn)有且僅有一個(gè)終結(jié)結(jié)點(diǎn)a an n，沒(méi)有直接后繼，有且，沒(méi)有直接后繼，有且僅有一個(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求長(zhǎng)度：求線性表中數(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é)生成績(jī)表中，每個(gè)學(xué)生及其成績(jī)是一、學(xué)生成績(jī)表中，每個(gè)學(xué)生及其成績(jī)是一個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號(hào)、姓名、個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號(hào)、姓名、各科成績(jī)及平均成績(jī)等數(shù)據(jù)項(xiàng)組成。各科成績(jī)及平均成績(jī)等數(shù)據(jù)項(xiàng)組成。 順序存儲(chǔ)是線性表的一種最順序存儲(chǔ)是線性表的一種最簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)方式是：簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)方式是：在內(nèi)存中為線性表開(kāi)辟一塊連在內(nèi)存中為線性表開(kāi)辟一塊連續(xù)的存儲(chǔ)空間續(xù)的存儲(chǔ)空間。用數(shù)組來(lái)存放用數(shù)組來(lái)存放每一個(gè)節(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)。s+n-1s+i-1s+1sanaia3a2a1內(nèi) 存單 元編 號(hào) (1)設(shè)和存放在設(shè)和存放在S

14、中中, 確定第一個(gè)數(shù)和最后確定第一個(gè)數(shù)和最后 一個(gè)數(shù)的位置。假設(shè)圓盤(pán)上一個(gè)數(shù)的位置。假設(shè)圓盤(pán)上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è)線性表中分別存儲(chǔ)最初的兩個(gè)值初始化，將兩個(gè)線性表中分別存儲(chǔ)最初的兩個(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)酱鎯?chǔ)、線性表的鏈?zhǔn)酱鎯?chǔ)指針是以存儲(chǔ)單元的地址作為其值的一種數(shù)據(jù)類(lèi)型，是一種可指針是以存儲(chǔ)單元的地址作為其值的一種數(shù)據(jù)類(lèi)型，是一種可以根據(jù)需要?jiǎng)討B(tài)申請(qǐng)內(nèi)存單元的一種數(shù)據(jù)類(lèi)型。以根據(jù)需要?jiǎng)討B(tài)申請(qǐng)內(nèi)存單元的一種數(shù)據(jù)類(lèi)型。 100 p1p134F234F234F234F2定義方式：定義方式：Type Type 指針類(lèi)型標(biāo)識(shí)符指針類(lèi)型標(biāo)識(shí)符=類(lèi)型標(biāo)識(shí)符類(lèi)型標(biāo)識(shí)符； var var 指針變量名：指針類(lèi)型標(biāo)識(shí)符；指針變量名：指針類(lèi)

16、型標(biāo)識(shí)符；newnew（p1p1） 向計(jì)算機(jī)申請(qǐng)內(nèi)存地址向計(jì)算機(jī)申請(qǐng)內(nèi)存地址 鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)如何申請(qǐng)、釋放存儲(chǔ)單元如何申請(qǐng)、釋放存儲(chǔ)單元 p1p134F234F234F234F2typetype p=integer; p=integer;var p1:p;var p1:p;p1:=200p1:=200 給給p1p1指向的單元賦值指向的單元賦值dispose(p1) 釋放存儲(chǔ)單元釋放存儲(chǔ)單元20020034F2 地址被釋放，變量P與地址34F2沒(méi)有關(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;指針變量所指向的類(lèi)型不同，指針變量所指向的類(lèi)型不同，計(jì)算機(jī)所給予的存儲(chǔ)單元的多計(jì)算機(jī)所給予的存儲(chǔ)單元的多少也不相同。少也不相同。指針類(lèi)型定義中的基類(lèi)型只能指針類(lèi)型定義中的基類(lèi)型只能是類(lèi)型標(biāo)識(shí)符，不能是具體的是類(lèi)型標(biāo)識(shí)符，不能是具體的類(lèi)型定義。類(lèi)型定義。 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) 同一基類(lèi)型的指針變量可以互相賦值。同一基類(lèi)型的指針變量可以互相賦值。鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)指針變量的基本操作指針變量的基本操作p1:=p2; ?(2)(2)對(duì)指針變量可以進(jìn)行關(guān)系運(yùn)算對(duì)指針變量可以進(jìn)行關(guān)系運(yùn)算 如如:if P1P2 then :if P1P2 then 語(yǔ)句語(yǔ)句1 else 1 else 語(yǔ)句語(yǔ)句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)指針變量的基本操作指針變量的基本操作由于指針變量代表的是存儲(chǔ)單元地址，它不能用輸出語(yǔ)句進(jìn)行打印，故在調(diào)試程序時(shí)要多加小心1、下面的自定義函數(shù)完成對(duì)一個(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、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B、線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C、線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D、線性表采用鏈接存儲(chǔ)，便于插入和刪除操作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)的地址不能丟失和改變，否則會(huì)丟失整個(gè)鏈表否則會(huì)丟失整個(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ù)元素的刪除。線性鏈表的訪問(wèn)基本方法是：線性鏈表的訪問(wèn)基本方法是：（1 1）從頭結(jié)點(diǎn)開(kāi)始沿線性鏈表方向進(jìn)行探求，一從頭結(jié)點(diǎn)開(kāi)始沿線性鏈表方向進(jìn)行探求，一般用于指向剛查過(guò)的結(jié)點(diǎn)地址，另一個(gè)用于指向下般用于指向剛查過(guò)的結(jié)

24、點(diǎn)地址，另一個(gè)用于指向下一個(gè)待查的結(jié)點(diǎn)地址。一個(gè)待查的結(jié)點(diǎn)地址。（2 2）結(jié)束訪問(wèn)的條件有兩個(gè)：一個(gè)是結(jié)點(diǎn)地址為結(jié)束訪問(wèn)的條件有兩個(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的值無(wú)意義。的值無(wú)意義。例例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）申請(qǐng)一個(gè)結(jié)點(diǎn)并賦值，然后將結(jié)點(diǎn)插入表頭）申請(qǐng)一個(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í)行前須確定存儲(chǔ)規(guī)模。估計(jì)須確定存儲(chǔ)規(guī)模。估計(jì)過(guò)大造成空間浪費(fèi)，估過(guò)大造成空間浪費(fèi)，估計(jì)太小使空間溢出機(jī)會(huì)計(jì)太小使空間溢出機(jī)會(huì)增多。增多。 動(dòng)態(tài)分配動(dòng)態(tài)分配, ,只要內(nèi)存空間尚有空只要內(nèi)存空間尚有空閑，就不會(huì)產(chǎn)生溢出。當(dāng)線性表閑，就不會(huì)產(chǎn)生溢出。當(dāng)線

27、性表的長(zhǎng)度變化較大，難以估計(jì)存儲(chǔ)的長(zhǎng)度變化較大，難以估計(jì)存儲(chǔ)規(guī)模時(shí)，宜采用動(dòng)態(tài)鏈表作存儲(chǔ)規(guī)模時(shí)，宜采用動(dòng)態(tài)鏈表作存儲(chǔ)結(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)行插入和刪除，平均要移動(dòng)表中刪除，平均要移動(dòng)表中近一半的結(jié)點(diǎn)，尤其是近一半的結(jié)點(diǎn)，尤其是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動(dòng)結(jié)點(diǎn)的時(shí)間大時(shí)，移動(dòng)結(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)就

28、相當(dāng)可觀。開(kāi)銷(xiāo)就相當(dāng)可觀。 在鏈表進(jìn)行插入和刪除，只需要在鏈表進(jìn)行插入和刪除，只需要修改指針。對(duì)于頻繁進(jìn)行插入和修改指針。對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若表的插入和刪除主要儲(chǔ)結(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、歸并、歸并問(wèn)題分析：?jiǎn)栴}分析：（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í)申請(qǐng)了新結(jié)點(diǎn)，能否時(shí)申請(qǐng)了新結(jié)點(diǎn)，能否不申請(qǐng)新結(jié)點(diǎn)來(lái)實(shí)現(xiàn)線性鏈表的歸并？不申請(qǐng)新結(jié)點(diǎn)來(lái)實(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)如下：?jiǎn)蜗蜴湵韱蜗蜴湵黼p向鏈表雙向鏈表雙向鏈表雙向鏈表雙鏈表的操作與單鏈表基本一致：雙鏈表的操作與單鏈表基本一致：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ā)可以訪問(wèn)其他結(jié)點(diǎn)。問(wèn)其他結(jié)點(diǎn)。便于訪問(wèn)、插入和刪除。便于訪問(wè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)。如下圖： 問(wèn)題描述：設(shè)有問(wèn)題描述：設(shè)有n n個(gè)人圍成一圈，并按順個(gè)人圍成一圈，并按順時(shí)針?lè)较驈臅r(shí)針?lè)较驈? 1到到n n編號(hào)；從第編號(hào)；從第s s個(gè)人開(kāi)始進(jìn)個(gè)人開(kāi)始進(jìn)行行1 1到到m m報(bào)數(shù)，數(shù)到報(bào)數(shù)，數(shù)到m m的人出圈；接著再?gòu)牡娜顺鋈?；接著再?gòu)乃竺嬉粋€(gè)人重新開(kāi)始他后面一個(gè)人重新開(kāi)始1 1到到m m報(bào)數(shù)，直到報(bào)數(shù)，直到所有人出圈為止。輸出出圈人的次序。所有人出圈為止。輸出出圈人的次序。