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