第11章數(shù)組與鏈表（含代碼）知識(shí)點(diǎn)梳理高考信息技術(shù)二輪復(fù)習(xí)知識(shí)點(diǎn)梳理

第十一章數(shù)組與鏈表（含代碼）1.數(shù)組在內(nèi)存中的存儲(chǔ)方式為順序存儲(chǔ)，數(shù)組作為常用的數(shù)據(jù)結(jié)構(gòu)，有特定的數(shù)據(jù)組織、存儲(chǔ)結(jié)構(gòu)及操作特性。2.計(jì)算機(jī)中數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)。常見的順序存儲(chǔ)結(jié)構(gòu)是數(shù)組，常見的非順序存儲(chǔ)結(jié)構(gòu)是鏈表3.數(shù)字是由相同類型的變量構(gòu)成的一個(gè)序列。數(shù)組使用一個(gè)標(biāo)識(shí)符命名，并用編號(hào)區(qū)分?jǐn)?shù)組內(nèi)的各個(gè)變量，這個(gè)特殊的標(biāo)識(shí)符號(hào)稱為數(shù)組名，編號(hào)稱為下表或索引。由數(shù)組名和下標(biāo)組成數(shù)組的各個(gè)變量稱為數(shù)組的分量，也稱為數(shù)組元素。（數(shù)組的下標(biāo)一般從0開始）4.數(shù)組在內(nèi)存中的存儲(chǔ)結(jié)構(gòu)簡單，創(chuàng)建數(shù)組時(shí)系統(tǒng)會(huì)分配一塊連續(xù)的存儲(chǔ)空間，每個(gè)數(shù)組元素按照下標(biāo)順序依次存儲(chǔ)。如下圖圖1.15.一維數(shù)組適合用來表示具有線性特征的數(shù)據(jù)序列，因此只需要一個(gè)下標(biāo)來表示數(shù)據(jù)元素在該序列中的位置。如果要表示二維空間內(nèi)既有縱向聯(lián)系和又有橫向聯(lián)系的一批數(shù)據(jù)，那么采用二維數(shù)組會(huì)變得更形象、方便由于二維數(shù)組中的數(shù)組有行有列兩個(gè)維度的位置信息，因此需要兩個(gè)下標(biāo)。二維數(shù)組下標(biāo)詳見下圖：圖1.26.用二維數(shù)組表示的數(shù)據(jù)在內(nèi)存中的存儲(chǔ)方式也才用順序存儲(chǔ)，有行優(yōu)先存儲(chǔ)和列優(yōu)先存儲(chǔ)。一般默認(rèn)采用行優(yōu)先。7.數(shù)組的特性：1.數(shù)組元素的數(shù)據(jù)類型相同，2.通過數(shù)組名的下標(biāo)對數(shù)組元素的值進(jìn)行訪問，3.數(shù)據(jù)存儲(chǔ)空間不變8.動(dòng)態(tài)數(shù)組就是在聲明時(shí)沒有確定數(shù)據(jù)規(guī)模的數(shù)組，可以在任何時(shí)候改變數(shù)據(jù)規(guī)模。9.對數(shù)組的常見操作有：數(shù)組的創(chuàng)建、數(shù)組元素的訪問、數(shù)組元素的插入和刪除等。10.Python沒有數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，所以采用列表來實(shí)現(xiàn)。11.數(shù)組的和創(chuàng)建實(shí)質(zhì)是在系統(tǒng)內(nèi)存中劃分一塊連續(xù)區(qū)域，同來保存數(shù)組所含的所有數(shù)據(jù)元素12.數(shù)組元素的訪問指的是尋址到特定的數(shù)組元素，并根據(jù)存儲(chǔ)地址對該數(shù)據(jù)元素進(jìn)行讀取、修改等操作。因?yàn)閿?shù)組元素從0開始數(shù)，所以：例如s[5]訪問的是s數(shù)組的第六個(gè)元素13.Python列表常用函數(shù)與方法:圖1.314.鏈表指的是將需要處理的數(shù)據(jù)對象以節(jié)點(diǎn)的形式，通過指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)。鏈表中的每一個(gè)節(jié)點(diǎn)一般由“數(shù)據(jù)區(qū)域”和“指針區(qū)域”兩部分構(gòu)成（如下圖）。數(shù)據(jù)區(qū)域用于保存實(shí)際需要處理的數(shù)據(jù)元素，指針區(qū)域用來保存該節(jié)點(diǎn)相鄰節(jié)點(diǎn)的存儲(chǔ)地址，通過該地址指向（指針）來實(shí)現(xiàn)從當(dāng)前節(jié)點(diǎn)按順序走到相鄰的節(jié)點(diǎn)。某個(gè)節(jié)點(diǎn)前面的相鄰節(jié)點(diǎn)稱為該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，后面的相鄰節(jié)點(diǎn)稱為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。15.每個(gè)鏈表都擁有一個(gè)表頭head(也稱為頭指針)，頭指針的作用之一是鏈表的入口，只有通過頭指針才能進(jìn)入鏈表；作用之二是為循環(huán)鏈表設(shè)立一個(gè)邊界，便于數(shù)據(jù)處理時(shí)的邊界判斷和處理。16.鏈表可以根據(jù)每個(gè)節(jié)點(diǎn)中指針的數(shù)量分為兩類:只有一個(gè)指針的單向鏈表和有兩個(gè)指針的雙向鏈表（即每個(gè)節(jié)點(diǎn)有兩個(gè)指針區(qū)域，一個(gè)指向前驅(qū)節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)）。將第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)使用指針鏈接，就會(huì)形成循環(huán)鏈表17.單向鏈表中各個(gè)節(jié)點(diǎn)在內(nèi)存中可以非順序存儲(chǔ)，每個(gè)節(jié)點(diǎn)使用指針指向后繼節(jié)點(diǎn)的存儲(chǔ)地址。進(jìn)入鏈表只能通過頭指針head，其他節(jié)點(diǎn)則需要經(jīng)過所有在它之前的節(jié)點(diǎn)才可以訪問，尾節(jié)點(diǎn)的指針指向null,表示指向?yàn)榭眨ㄒ话闱闆r下，尾指針為1。當(dāng)尾指針指向head時(shí)，即為循環(huán)鏈表）18.鏈表的特性：1.同一鏈表中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)均相同，2.每個(gè)鏈表必定有一個(gè)頭指針，以實(shí)現(xiàn)對鏈表的引用和邊界處理，3.鏈表占用的空間不固定。19.鏈表的操作有：鏈表的創(chuàng)建、鏈表節(jié)點(diǎn)的訪問、鏈表節(jié)點(diǎn)的插入與刪除單向鏈表代碼實(shí)現(xiàn)給定一個(gè)鏈表a[]，其第一個(gè)元素代表的下標(biāo)為head。a[i]代表的元素是一個(gè)長度為2的數(shù)組，其中a[i][0]表示它的數(shù)據(jù)data（數(shù)據(jù)都是整數(shù)），a[i][1]表示它的下一個(gè)元素next，如果next為?1代表其是鏈表的最后一個(gè)元素。假設(shè)有如下代碼：a=[['A',2],['D',1],['B',3],['C',1]]head=0#刪除第一個(gè)元素head=a[head][1]#遍歷鏈表h=headwhileh!=1:print(a[h][0])h=a[h][1]#刪除中間元素,根據(jù)內(nèi)容Bh=headpre=headwhileh!=1:ifa[h][0]=='B':breakelse:pre=hh=a[h][1]a[pre][1]=a[h][1]#在頭部插入元素head=0a.append(['E',head])head=len(a)1#插入中間元素根據(jù)值#首先找到Bh=headwhileh!=1:ifa[h][0]=='B':breakelse:h=a[h][1]#然后插入Ea.append(['E',a[h][1]])a[h][1]=len(a)1鏈表相對于數(shù)組而言，更便于刪除和添加，數(shù)組相對于鏈表而言，更便于查找和修改 表1.1雙向鏈表代碼實(shí)現(xiàn)給定一個(gè)鏈表a[]，其第一個(gè)元素代表的下標(biāo)為head。a[i]代表的元素是一個(gè)長度為3的數(shù)組，其中a[i][0]表示當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)pre，a[i][1]表示它的數(shù)據(jù)data（數(shù)據(jù)都是整數(shù)），a[i][2]表示它的下一個(gè)節(jié)點(diǎn)next，如果next為?1代表其是鏈表的最后一個(gè)元素。假設(shè)有如下代碼：a=[[1,'A',2],[3,'D',1],[0,'B',3],[2,'C',1]]head=0pre=next1=head#遍歷鏈表(從前往后）whilenext1!=1:print(a[next1][1])next1=a[next1][2]#遍歷鏈表(從后往前）whilea[next1][2]!=1:#先找到最后一個(gè)節(jié)點(diǎn)next1=a[next1][2]pre=next1whilepre!=1:#從最后一個(gè)節(jié)點(diǎn)向前遍歷print(a[pre][1])pre=a[pre][0]#刪除中間元素,根據(jù)內(nèi)容Bwhilenext1!=1:ifa[next1][1]=="B":breakelse:pre=next1next1=a[next1][2]a[a[next1][2]][0]=a[next1][0]a[pre][2]=a[next1][2]#在頭部插入元素a.append([1,'E',head])head=len(a)1pre=next1=head 表1.2#插入中間元素根據(jù)值whilenext1!=1:ifa[next1][1]=="B":breakelse:pre=next1next1=a[next1][2]a.ap