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