計(jì)算機(jī)軟件基礎(chǔ)(自考本科線性表)

1、1.線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)（1）線性表：是由）線性表：是由n（n 0）個(gè)數(shù)據(jù)節(jié)點(diǎn)個(gè)數(shù)據(jù)節(jié)點(diǎn) a0，a1 ,，an-1組成的組成的有限有限序列。序列。（2）線性表的邏輯結(jié)構(gòu)特征：）線性表的邏輯結(jié)構(gòu)特征：對(duì)于非空線性表：對(duì)于非空線性表：有且僅有一個(gè)開(kāi)始節(jié)點(diǎn)，該節(jié)點(diǎn)有且僅有一個(gè)直有且僅有一個(gè)開(kāi)始節(jié)點(diǎn)，該節(jié)點(diǎn)有且僅有一個(gè)直接的后繼；接的后繼；有且只有一個(gè)終結(jié)節(jié)點(diǎn)，該節(jié)點(diǎn)有且僅有一個(gè)直有且只有一個(gè)終結(jié)節(jié)點(diǎn)，該節(jié)點(diǎn)有且僅有一個(gè)直接的前驅(qū)；接的前驅(qū)；其余內(nèi)部節(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接其余內(nèi)部節(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。后繼。（2）線性表的邏輯結(jié)構(gòu)特征：）線性表的邏輯結(jié)構(gòu)特征：同

2、一個(gè)線性表中的數(shù)據(jù)節(jié)點(diǎn)具有相同的屬性。同一個(gè)線性表中的數(shù)據(jù)節(jié)點(diǎn)具有相同的屬性。線性表長(zhǎng)度：線性表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。線性表長(zhǎng)度：線性表中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。 2. 線性表的存儲(chǔ)結(jié)構(gòu)線性表的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)：順序表結(jié)構(gòu)；）順序存儲(chǔ)結(jié)構(gòu)：順序表結(jié)構(gòu)；（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈表結(jié)構(gòu)；）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈表結(jié)構(gòu)；1.順序表順序表（1）順序表：）順序表： 把線性表中的數(shù)據(jù)節(jié)點(diǎn)按其邏輯順序依次存把線性表中的數(shù)據(jù)節(jié)點(diǎn)按其邏輯順序依次存放到計(jì)算機(jī)內(nèi)存中的放到計(jì)算機(jī)內(nèi)存中的一連續(xù)空間一連續(xù)空間中，將這一連續(xù)中，將這一連續(xù)空間稱為順序表?？臻g稱為順序表。（2）順序表中數(shù)據(jù)節(jié)點(diǎn)地址的計(jì)算）順序表中數(shù)據(jù)節(jié)點(diǎn)地址的計(jì)算

3、Loc(ai)=loc(a0)+i*d (0in-1)1.順序表順序表（3）用一維數(shù)組描述順序表）用一維數(shù)組描述順序表2.順序表的基本運(yùn)算順序表的基本運(yùn)算查找查找例例8-1在長(zhǎng)度為在長(zhǎng)度為n的線性表的線性表L中順序查找內(nèi)容為中順序查找內(nèi)容為X的節(jié)點(diǎn)。的節(jié)點(diǎn)。要求：寫(xiě)出類要求：寫(xiě)出類C語(yǔ)言算法，求成功的平均查找長(zhǎng)度及時(shí)語(yǔ)言算法，求成功的平均查找長(zhǎng)度及時(shí)間復(fù)雜度間復(fù)雜度T(n)。一個(gè)完整的查找程序：一個(gè)完整的查找程序：一個(gè)完整的查找程序（續(xù)）：一個(gè)完整的查找程序（續(xù)）：順序表查找運(yùn)算的順序表查找運(yùn)算的結(jié)論結(jié)論：（1）查找成功的平均查找次數(shù)為）查找成功的平均查找次數(shù)為：(表長(zhǎng)表長(zhǎng)+1)/2。（2）時(shí)

4、間復(fù)雜度：表長(zhǎng)越長(zhǎng)，查找所消耗時(shí)間越多，）時(shí)間復(fù)雜度：表長(zhǎng)越長(zhǎng)，查找所消耗時(shí)間越多，所以，時(shí)間復(fù)雜度與所以，時(shí)間復(fù)雜度與n有關(guān)，即：有關(guān)，即：T(n)=O(n)。3.順序表的基本運(yùn)算順序表的基本運(yùn)算插入插入step1:判斷表是否滿？如果已滿，則輸出判斷表是否滿？如果已滿，則輸出表滿表滿 ；否則進(jìn)行第二步；否則進(jìn)行第二步；step2:判斷要插入的位置是否在表內(nèi)？如果不在，則判斷要插入的位置是否在表內(nèi)？如果不在，則輸出輸出位置不對(duì)位置不對(duì)；否則進(jìn)行第三步；否則進(jìn)行第三步；step3:從第從第n-1個(gè)節(jié)點(diǎn)到第個(gè)節(jié)點(diǎn)到第i個(gè)節(jié)點(diǎn)全部后移個(gè)節(jié)點(diǎn)全部后移1位；位；step5:將順序表的表長(zhǎng)加將順序表的表長(zhǎng)

5、加1；step4:在順序表的第在順序表的第i個(gè)位置插入個(gè)位置插入x；例例8-2在長(zhǎng)度為在長(zhǎng)度為n的線性表的線性表L中第中第i(0in)個(gè)位置上插入個(gè)位置上插入內(nèi)容為內(nèi)容為x的數(shù)據(jù)節(jié)點(diǎn)。要求：寫(xiě)出類的數(shù)據(jù)節(jié)點(diǎn)。要求：寫(xiě)出類c語(yǔ)言算法，求節(jié)語(yǔ)言算法，求節(jié)點(diǎn)平均移動(dòng)次數(shù)及時(shí)間復(fù)雜度點(diǎn)平均移動(dòng)次數(shù)及時(shí)間復(fù)雜度T(n)。一個(gè)完整的插入運(yùn)算程序一個(gè)完整的插入運(yùn)算程序一個(gè)完整的插入運(yùn)算程序（續(xù)）一個(gè)完整的插入運(yùn)算程序（續(xù)）一個(gè)完整的插入運(yùn)算程序（續(xù)）一個(gè)完整的插入運(yùn)算程序（續(xù)）順序表插入運(yùn)算的順序表插入運(yùn)算的結(jié)論結(jié)論：（1）在線性表中插入一個(gè)數(shù)據(jù)節(jié)點(diǎn)需要移動(dòng)順序表）在線性表中插入一個(gè)數(shù)據(jù)節(jié)點(diǎn)需要移動(dòng)順序表的

6、一半節(jié)點(diǎn)，即的一半節(jié)點(diǎn)，即：n/2。（2）時(shí)間復(fù)雜度：插入運(yùn)算的時(shí)間復(fù)雜度與）時(shí)間復(fù)雜度：插入運(yùn)算的時(shí)間復(fù)雜度與n有關(guān)，有關(guān)，即：即：T(n)=O(n)。3.順序表的基本運(yùn)算順序表的基本運(yùn)算刪除刪除step1:判斷表是否為空？如果為空，則輸出判斷表是否為空？如果為空，則輸出無(wú)法刪除無(wú)法刪除 ；否則進(jìn)行第二步；否則進(jìn)行第二步；step2:判斷要?jiǎng)h除的位置是否在表內(nèi)？如果不在，則判斷要?jiǎng)h除的位置是否在表內(nèi)？如果不在，則輸出輸出位置不對(duì)位置不對(duì)；否則進(jìn)行第三步；否則進(jìn)行第三步；step3:從第從第i+1個(gè)節(jié)點(diǎn)到第個(gè)節(jié)點(diǎn)到第n-1個(gè)節(jié)點(diǎn)全部前移個(gè)節(jié)點(diǎn)全部前移1位（位（采采用覆蓋的形式刪除用覆蓋的形式刪

7、除）；）；step4:將順序表的表長(zhǎng)減去將順序表的表長(zhǎng)減去1；例例8-3在表長(zhǎng)為在表長(zhǎng)為n的線性表的線性表L中刪除第中刪除第i(0in一一1)個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。 要求：寫(xiě)出類要求：寫(xiě)出類c語(yǔ)言算法，求節(jié)點(diǎn)平均移動(dòng)次數(shù)及時(shí)間復(fù)語(yǔ)言算法，求節(jié)點(diǎn)平均移動(dòng)次數(shù)及時(shí)間復(fù)雜度雜度T(n)。一個(gè)完整的刪除運(yùn)算程序一個(gè)完整的刪除運(yùn)算程序一個(gè)完整的刪除運(yùn)算程序（續(xù)）一個(gè)完整的刪除運(yùn)算程序（續(xù)）一個(gè)完整的刪除運(yùn)算程序（續(xù)）一個(gè)完整的刪除運(yùn)算程序（續(xù)）順序表刪除運(yùn)算的順序表刪除運(yùn)算的結(jié)論結(jié)論：（1）在線性表中刪除一個(gè)數(shù)據(jù)節(jié)點(diǎn)需要移動(dòng)順序表）在線性表中刪除一個(gè)數(shù)據(jù)節(jié)點(diǎn)需要移動(dòng)順序表的一半節(jié)點(diǎn)，即的一半節(jié)點(diǎn)，即：n/2。

8、（2）時(shí)間復(fù)雜度：刪除運(yùn)算的時(shí)間復(fù)雜度與）時(shí)間復(fù)雜度：刪除運(yùn)算的時(shí)間復(fù)雜度與n有關(guān)，有關(guān)，即：即：T(n)=O(n)。1.單鏈表的形態(tài)單鏈表的形態(tài)非空表：非空表：空表：空表：2.線性表順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的異同點(diǎn)線性表順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的異同點(diǎn)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)空間存儲(chǔ)空間連續(xù)的存儲(chǔ)空間連續(xù)的存儲(chǔ)空間可以連續(xù)，可以不連續(xù)（可以連續(xù)，可以不連續(xù)（分散）的存儲(chǔ)空間分散）的存儲(chǔ)空間節(jié)點(diǎn)間的相節(jié)點(diǎn)間的相鄰關(guān)系鄰關(guān)系邏輯上的相鄰關(guān)系與存邏輯上的相鄰關(guān)系與存儲(chǔ)結(jié)構(gòu)上的相鄰關(guān)系一儲(chǔ)結(jié)構(gòu)上的相鄰關(guān)系一致。致。邏輯上是相鄰的，在存儲(chǔ)邏輯上是相鄰的，在存儲(chǔ)結(jié)構(gòu)上是不

9、相鄰的。結(jié)構(gòu)上是不相鄰的?？臻g使用空間使用在使用前，事先分配存在使用前，事先分配存儲(chǔ)空間。儲(chǔ)空間。只在使用時(shí)才申請(qǐng)存儲(chǔ)空只在使用時(shí)才申請(qǐng)存儲(chǔ)空間，使用過(guò)后其存儲(chǔ)空間間，使用過(guò)后其存儲(chǔ)空間可以刪除。可以刪除。3.單鏈表運(yùn)算符號(hào)的說(shuō)明單鏈表運(yùn)算符號(hào)的說(shuō)明4. 單鏈表上的簡(jiǎn)單運(yùn)算單鏈表上的簡(jiǎn)單運(yùn)算例例8-4 求單鏈表的表長(zhǎng)求單鏈表的表長(zhǎng)（不包括表頭節(jié)點(diǎn)）（不包括表頭節(jié)點(diǎn)）。例例8-5 在單鏈表中查找內(nèi)容為在單鏈表中查找內(nèi)容為x的節(jié)點(diǎn)（的節(jié)點(diǎn)（find）7.插入運(yùn)算（插入運(yùn)算（insert）-插入已知插入已知地址地址的節(jié)點(diǎn)的節(jié)點(diǎn)如：在如：在p指針?biāo)腹?jié)點(diǎn)后面插入已知指針?biāo)腹?jié)點(diǎn)后面插入已知地址為地址為

10、s的節(jié)點(diǎn)的節(jié)點(diǎn)7.插入運(yùn)算（插入運(yùn)算（insert）-插入已知插入已知內(nèi)容內(nèi)容的節(jié)點(diǎn)的節(jié)點(diǎn)如：在如：在p指針?biāo)腹?jié)點(diǎn)后面插入已知指針?biāo)腹?jié)點(diǎn)后面插入已知內(nèi)容為內(nèi)容為x的節(jié)點(diǎn)的節(jié)點(diǎn)8.刪除運(yùn)算（刪除運(yùn)算（delete）如：刪除如：刪除p指針?biāo)腹?jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指針?biāo)腹?jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)1.單循環(huán)鏈表的形態(tài)單循環(huán)鏈表的形態(tài)非空表：非空表：空表：空表：注意：注意：?jiǎn)捂湵碇荒苎刂湵韽那跋蚝笤L問(wèn)單鏈表只能沿著鏈表從前向后訪問(wèn)表中的各節(jié)點(diǎn)，表中的各節(jié)點(diǎn)，無(wú)法找到某節(jié)點(diǎn)前無(wú)法找到某節(jié)點(diǎn)前面的其他節(jié)點(diǎn)面的其他節(jié)點(diǎn)；單循環(huán)鏈表可以通過(guò)任一節(jié)點(diǎn)訪問(wèn)單循環(huán)鏈表可以通過(guò)任一節(jié)點(diǎn)訪問(wèn)表中的其他節(jié)點(diǎn)。表中的其他節(jié)點(diǎn)。2.

11、單循環(huán)鏈表的刪除運(yùn)算單循環(huán)鏈表的刪除運(yùn)算例如：一個(gè)單循環(huán)鏈表，沒(méi)有頭指針只有尾指針例如：一個(gè)單循環(huán)鏈表，沒(méi)有頭指針只有尾指針r，試，試寫(xiě)出刪除尾指針寫(xiě)出刪除尾指針r的前一個(gè)節(jié)點(diǎn)。的前一個(gè)節(jié)點(diǎn)。2.單循環(huán)鏈表的刪除運(yùn)算單循環(huán)鏈表的刪除運(yùn)算Step1：找出：找出r節(jié)點(diǎn)前前的那個(gè)節(jié)點(diǎn)節(jié)點(diǎn)前前的那個(gè)節(jié)點(diǎn)p；Step2：讓：讓p指向指向 q的下一個(gè)節(jié)點(diǎn)；的下一個(gè)節(jié)點(diǎn)；Step3：從鏈表中刪除：從鏈表中刪除q所指向的節(jié)點(diǎn)；所指向的節(jié)點(diǎn)；Step3：回收：回收q。2.單循環(huán)鏈表的刪除運(yùn)算單循環(huán)鏈表的刪除運(yùn)算1.雙循環(huán)鏈表的形態(tài)雙循環(huán)鏈表的形態(tài)非空表：非空表：空表：空表：2.雙循環(huán)鏈表的類型定義雙循環(huán)鏈表的類

12、型定義每個(gè)節(jié)點(diǎn)有每個(gè)節(jié)點(diǎn)有3個(gè)成員：個(gè)成員：prior：左鏈域，存放直接前驅(qū)節(jié)點(diǎn)的地址；：左鏈域，存放直接前驅(qū)節(jié)點(diǎn)的地址；next ：右鏈域，存放直接后繼節(jié)點(diǎn)的地址；：右鏈域，存放直接后繼節(jié)點(diǎn)的地址；data ： 數(shù)據(jù)域，存放本節(jié)點(diǎn)的信息內(nèi)容。數(shù)據(jù)域，存放本節(jié)點(diǎn)的信息內(nèi)容。2.雙循環(huán)鏈表的類型定義雙循環(huán)鏈表的類型定義3.雙循環(huán)鏈表的特點(diǎn)雙循環(huán)鏈表的特點(diǎn):p-prior-next=p-next-prior=p4.雙循環(huán)鏈表的基本運(yùn)算雙循環(huán)鏈表的基本運(yùn)算-插入插入例如：在例如：在p所指節(jié)點(diǎn)的前面插入地址為所指節(jié)點(diǎn)的前面插入地址為s的節(jié)點(diǎn)。的節(jié)點(diǎn)。4.雙循環(huán)鏈表的基本運(yùn)算雙循環(huán)鏈表的基本運(yùn)算-插入插

13、入例如：在例如：在p所指節(jié)點(diǎn)的前面插入地址為所指節(jié)點(diǎn)的前面插入地址為s的節(jié)點(diǎn)。的節(jié)點(diǎn)。4.雙循環(huán)鏈表的基本運(yùn)算雙循環(huán)鏈表的基本運(yùn)算-刪除刪除例如：刪除例如：刪除p指針?biāo)傅墓?jié)點(diǎn)指針?biāo)傅墓?jié)點(diǎn)1.尾插法尾插法依次輸入依次輸入abc時(shí)，以尾插法建立的單鏈表為：時(shí)，以尾插法建立的單鏈表為：2.頭插法頭插法依次輸入依次輸入abc時(shí)，以頭插法建立的單鏈表為：時(shí)，以頭插法建立的單鏈表為：例例8-10依次輸入一串字符依次輸入一串字符abc，以，以*作為結(jié)束標(biāo)志，建立并作為結(jié)束標(biāo)志，建立并輸出如下單鏈表：輸出如下單鏈表：例例8-11 依次輸人一串字符依次輸人一串字符abc，以，以*為結(jié)束標(biāo)記，為結(jié)束標(biāo)記，建立

14、并輸出如下單鏈表：建立并輸出如下單鏈表：一、時(shí)間性能一、時(shí)間性能1)若經(jīng)常進(jìn)行的運(yùn)算為查找運(yùn)算，以順序存儲(chǔ)為宜。若經(jīng)常進(jìn)行的運(yùn)算為查找運(yùn)算，以順序存儲(chǔ)為宜。2若經(jīng)常進(jìn)行的運(yùn)算為插入，刪除運(yùn)算，以鏈?zhǔn)酱鎯?chǔ)為宜。若經(jīng)常進(jìn)行的運(yùn)算為插入，刪除運(yùn)算，以鏈?zhǔn)酱鎯?chǔ)為宜。實(shí)例：用鏈表制作通信錄實(shí)例：用鏈表制作通信錄 1定義通信錄結(jié)構(gòu)定義通信錄結(jié)構(gòu) 2編寫(xiě)顯示聯(lián)系人信息模塊編寫(xiě)顯示聯(lián)系人信息模塊 3編寫(xiě)添加聯(lián)系人模塊編寫(xiě)添加聯(lián)系人模塊 4編寫(xiě)查找聯(lián)系人模塊編寫(xiě)查找聯(lián)系人模塊 5編寫(xiě)刪除聯(lián)系人模塊編寫(xiě)刪除聯(lián)系人模塊 6編寫(xiě)主模塊編寫(xiě)主模塊1.（2010.4單選）對(duì)順序存儲(chǔ)的線性表，其長(zhǎng)度為單選）對(duì)順序存儲(chǔ)的線性表，其長(zhǎng)度為n，在等概率情況下，插入一個(gè)數(shù)據(jù)節(jié)點(diǎn)需要移動(dòng)數(shù)據(jù)節(jié)在等概率情況下，插入一個(gè)數(shù)據(jù)節(jié)點(diǎn)需要移動(dòng)數(shù)據(jù)節(jié)點(diǎn)的平均次數(shù)是（點(diǎn)的平均次數(shù)是（ ）。）。A n/2 B n-1 C (n+1)/2 D (n-1)/22.（2010.4單選）線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其存儲(chǔ)空間單選）線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其存儲(chǔ)空間是（是（ ）。）。A 必須是連續(xù)的必須是連續(xù)的 B 一定是不連續(xù)的一定是不連續(xù)的 C 可連續(xù)，也可不連續(xù)可連續(xù)，也可不連續(xù) D 多個(gè)節(jié)點(diǎn)地址必須連續(xù)多個(gè)節(jié)點(diǎn)地址必須連續(xù)3.（2010.4填空）已知