計算機軟件基礎(自考本科線性表)

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

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

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

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

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

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

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

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

9、相鄰的。結(jié)構(gòu)上是不相鄰的。空間使用空間使用在使用前，事先分配存在使用前，事先分配存儲空間。儲空間。只在使用時才申請存儲空只在使用時才申請存儲空間，使用過后其存儲空間間，使用過后其存儲空間可以刪除?？梢詣h除。3.單鏈表運算符號的說明單鏈表運算符號的說明4. 單鏈表上的簡單運算單鏈表上的簡單運算例例8-4 求單鏈表的表長求單鏈表的表長（不包括表頭節(jié)點）（不包括表頭節(jié)點）。例例8-5 在單鏈表中查找內(nèi)容為在單鏈表中查找內(nèi)容為x的節(jié)點（的節(jié)點（find）7.插入運算（插入運算（insert）-插入已知插入已知地址地址的節(jié)點的節(jié)點如：在如：在p指針所指節(jié)點后面插入已知指針所指節(jié)點后面插入已知地址為地址為

10、s的節(jié)點的節(jié)點7.插入運算（插入運算（insert）-插入已知插入已知內(nèi)容內(nèi)容的節(jié)點的節(jié)點如：在如：在p指針所指節(jié)點后面插入已知指針所指節(jié)點后面插入已知內(nèi)容為內(nèi)容為x的節(jié)點的節(jié)點8.刪除運算（刪除運算（delete）如：刪除如：刪除p指針所指節(jié)點的下一個節(jié)點指針所指節(jié)點的下一個節(jié)點1.單循環(huán)鏈表的形態(tài)單循環(huán)鏈表的形態(tài)非空表：非空表：空表：空表：注意：注意：單鏈表只能沿著鏈表從前向后訪問單鏈表只能沿著鏈表從前向后訪問表中的各節(jié)點，表中的各節(jié)點，無法找到某節(jié)點前無法找到某節(jié)點前面的其他節(jié)點面的其他節(jié)點；單循環(huán)鏈表可以通過任一節(jié)點訪問單循環(huán)鏈表可以通過任一節(jié)點訪問表中的其他節(jié)點。表中的其他節(jié)點。2.

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

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

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

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