1.3 線性表及順序存儲(chǔ)結(jié)構(gòu)
考點(diǎn)6 線性表的定義
線性表是n(n≥0)個(gè)元素構(gòu)成的有限序列(a1，a2，…，an)。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為
(a1，a2，…，an)
其中ai(i=1，2，…，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。
其中，每個(gè)元素可以簡(jiǎn)單到是一個(gè)字母或是一個(gè)數(shù)據(jù)，也可能是比較復(fù)雜的由多個(gè)數(shù)據(jù)項(xiàng)組成的。在復(fù)雜的線性表中，由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record)，而由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。非空線性表有如下一些結(jié)構(gòu)特征：
(1)有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；
(2)有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；
(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。
考點(diǎn)7 線性表的順序存儲(chǔ)結(jié)構(gòu)
線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：
(l)線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；
(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。
假設(shè)線性表的每個(gè)元素需要占用k個(gè)存儲(chǔ)單元，并以所占的存儲(chǔ)位置ADR(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置ADR(ai)之間滿足下列關(guān)系：
ADR(ai+1)=ADR(ai)+k
線性表第i個(gè)元素ai的存儲(chǔ)位置為
ADR(ai)=ADR(a1)+(i-1)×k
式中ADR(ai)是線性表的第一個(gè)數(shù)據(jù)元素a，的存儲(chǔ)位置，通常稱做線性表的起始位置或基址。
線性表的這種表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像，這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。表中每一個(gè)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比例的常數(shù)。如圖1-4所示。由此只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。
考點(diǎn)6 線性表的定義
線性表是n(n≥0)個(gè)元素構(gòu)成的有限序列(a1，a2，…，an)。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為
(a1，a2，…，an)
其中ai(i=1，2，…，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。
其中，每個(gè)元素可以簡(jiǎn)單到是一個(gè)字母或是一個(gè)數(shù)據(jù)，也可能是比較復(fù)雜的由多個(gè)數(shù)據(jù)項(xiàng)組成的。在復(fù)雜的線性表中，由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record)，而由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。非空線性表有如下一些結(jié)構(gòu)特征：
(1)有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；
(2)有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；
(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。
考點(diǎn)7 線性表的順序存儲(chǔ)結(jié)構(gòu)
線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：
(l)線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；
(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。
假設(shè)線性表的每個(gè)元素需要占用k個(gè)存儲(chǔ)單元，并以所占的存儲(chǔ)位置ADR(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置ADR(ai)之間滿足下列關(guān)系：
ADR(ai+1)=ADR(ai)+k
線性表第i個(gè)元素ai的存儲(chǔ)位置為
ADR(ai)=ADR(a1)+(i-1)×k
式中ADR(ai)是線性表的第一個(gè)數(shù)據(jù)元素a，的存儲(chǔ)位置，通常稱做線性表的起始位置或基址。
線性表的這種表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像，這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。表中每一個(gè)元素的存儲(chǔ)位置都和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的位序成正比例的常數(shù)。如圖1-4所示。由此只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。