高中信息技術選擇性必修一《線性結構》知識清單

高中信息技術選擇性必修一《線性結構》知識清單一、課程導引：數據組織的基石與計算思維的錨點【核心概念】線性結構是數據結構中最基礎、最常用的一類邏輯結構，其特征是數據元素之間存在著“一對一”的線性關系。在高中信息技術課程中，學習線性結構不僅是為了掌握幾種具體的存儲和操作方法，更是為了培養同學們的計算思維——即如何通過抽象、分解和建模來高效地處理現實世界中的復雜問題。本章內容是后續學習樹、圖等復雜數據結構的基石，也是算法設計與程序實現的必經之路。【學習目標】理解線性表的邏輯結構定義；掌握順序表和鏈表兩種基本存儲結構及其主要操作的算法實現；理解棧和隊列作為受限線性表的特殊性和應用場景；能夠根據實際問題，從時間復雜度、空間復雜度等角度，選擇并設計合適的線性結構來組織數據，并編寫相應的程序代碼解決問題。二、核心知識模塊詳解（一）線性表：線性結構的邏輯模型【基礎】★1、線性表的定義與邏輯特征...（LinearList）是由n（n≥0）個數據元素（結點）a1,a2,...,an組成的有限序列。當n=0時，稱為空表。其邏輯特征主要體現在兩個方面：（1）有且僅有一個開始結點（表頭元素a1），它沒有前驅，有且僅有一個后繼a2；（2）有且僅有一個終端結點（表尾元素an），它沒有后繼，有且僅有一個前驅a(n1)；（3）其余的內部結點ai（2≤i≤n1）都有且僅有一個直接前驅a(i1)和一個直接后繼a(i+1)。這種一對一的鄰接關系，是判斷一個數據結構是否為線性結構的根本標準。2、線性表的抽象數據類型定義線性表主要支持一組抽象的、與具體存儲結構無關的操作。理解這些操作是學習后續實現的基礎。（1）初始化：構造一個空的線性表。（2）判空：檢查線性表是否為空。（3）求長度：返回線性表中數據元素的個數。（4）遍歷：按序訪問線性表中的每個元素。（5）查找：根據給定值，查找其在線性表中的位置。（6）獲取元素：獲取第i個位置的元素值。（7）插入操作：在線性表的第i個位置插入一個新元素。（8）刪除操作：刪除線性表的第i個位置的元素，并返回其值。（9）銷毀操作：銷毀已存在的線性表。3、考點與考向【基礎】（1）【高頻考點】判斷題或選擇題中，給出若干組數據，判斷其是否能構成線性表。關鍵點在于“有限”和“序列”，以及元素間的前后邏輯關系。（2）【高頻考點】區分線性表的邏輯結構和物理（存儲）結構。邏輯結構是抽象的“一對一”關系，與計算機硬件無關；物理結構是數據在內存中的實際存放方式，如順序存儲和鏈式存儲。（二）順序表：基于數組的線性表實現【重要】▲▲1、順序表的存儲結構順序表（SequentialList）是用一組地址連續的存儲單元依次存儲線性表的各個元素。在高級語言中，通常借助數組來實現。（1）特點：邏輯上相鄰的元素，在物理存儲位置上也是相鄰的。（2）地址計算：假設每個元素占用c個存儲單元，元素ai的存儲地址LOC(ai)=LOC(a1)+(i1)c。這種計算方式決定了它可以實現隨機存取。2、順序表的基本操作與算法實現（1）插入操作【核心操作】★★★L.length表的第i（1≤i≤L.length+1）個位置插入一個新元素e。需要將第i個至最后一個元素全部后移一個位置，然后將新元素e放入第i個位置，最后將表長增加1。算法描述（類C語言）：StatusListInsert(SqListL,inti,ElemTypee){L.length1||i>L.length+1)returnERROR;//判斷插入位置是否合法L.lengthL.length>=L.listsize){//當前存儲空間已滿，增加分配//...增加空間代碼...}for(intj=L.length1;j>=i1;j){L.elem[j+1]=L.elem[j];//從最后一個元素開始后移}L.elem[i1]=e;//插入新元素L.length++;//表長增1returnOK;}【難點與易錯點】（1）元素移動的方向：必須從最后一個元素開始向后移動，如果從第i個開始向前移動，會造成數據覆蓋。（2）下標與位序的轉換：位序（第1個）通常對應數組下標0，第i個元素存儲在數組下標為i1的位置。（3）邊界條件判斷：插入位置i的合法性，以及表滿時的處理。（2）刪除操作【核心操作】★★★算法思想：刪除順序表的第i（1≤i≤L.length）個位置的元素，并將被刪除元素的值賦給e。需要將第i+1個至最后一個元素全部前移一個位置，覆蓋掉第i個元素，表長減1。算法描述（類C語言）：StatusListDelete(SqListL,inti,ElemTypee){if(i<1||i>L.length)returnERROR;//判斷刪除位置是否合法e=L.elem[i1];//取出被刪除元素for(intj=i;j<=L.length1;j++){L.elem[j1]=L.elem[j];//從第i+1個元素開始前移}L.length;//表長減1returnOK;}【難點與易錯點】（1）元素移動的方向：從刪除位置的后繼元素開始，依次向前移動。（2）邊界條件判斷：刪除位置i的合法性，以及空表不能刪除。3、順序表的算法效率分析（時間復雜度）【高頻考點】▲▲▲（1）插入操作的平均移動次數：在長度為n的順序表中插入一個元素，平均要移動n/2個元素。因此，插入操作的平均時間復雜度為O(n)。（2）刪除操作的平均移動次數：在長度為n的順序表中刪除一個元素，平均要移動(n1)/2個元素。因此，刪除操作的平均時間復雜度也為O(n)。（3）按值查找（如查找值為e的元素）：最好情況是第一個，時間復雜度O(1)；最壞情況是最后一個或不存，時間復雜度O(n)；平均時間復雜度為O(n)。（4）按位查找（如查找第i個元素）：由于隨機存取特性，可以直接通過地址計算得到，時間復雜度為O(1)。這是順序表相較于鏈表的主要優勢。4、順序表的優缺點總結（1）優點：支持隨機存取，存儲密度高（無需額外空間存儲元素間的關系），實現簡單。（2）缺點：插入和刪除操作需要移動大量元素，效率低；需要預先分配固定大小的存儲空間，容易造成空間浪費或溢出。5、常見題型與解題步驟【題型1】給定一個順序表，要求在第i個位置插入/刪除元素，畫出插入/刪除前后內存狀態圖。【解題步驟】（1）明確順序表的起始地址和每個元素占用的字節數。（2）確定插入/刪除操作涉及的元素范圍。（3）按規則（后移或前移）逐個畫出元素地址的變化。（4）特別注意表長（length）和最后一個元素的位置。【題型2】編程實現兩個有序順序表的合并，合并后依然有序。【解題要點】（1）分別從兩個表的第一個元素開始比較，將較小的元素放入新表。（2）當某一表比較完后，將另一表的剩余元素全部放入新表。（3）需要注意新表的空間要足夠大。（三）鏈表：基于指針的線性表實現【重要】▲▲▲1、鏈表的存儲結構鏈表（LinkedList）是用一組任意的存儲單元（可以連續，也可以不連續）來存儲線性表中的數據元素。為了表示每個元素ai與其直接后繼元素a(i+1)之間的邏輯關系，對于元素ai，除了存儲其本身的信息（數據域）外，還需存儲一個指示其直接后繼存儲位置的指針（指針域）。這兩部分信息組成數據元素ai的存儲映像，稱為結點（Node）。2、單鏈表（1）結點結構|數據域|指針域|指向鏈表中第一個結點的指針稱為頭指針。為了操作方便，通常在單鏈表的第一個結點之前附加一個結點，稱為頭結點。頭結點的數據域可以不存儲任何信息，也可以存儲如鏈表長度等附加信息，其指針域指向第一個元素結點（首元結點）。【易錯點辨析】頭指針、頭結點、首元結點（1）頭指針：是指向鏈表中第一個結點（有頭結點時，指向頭結點；無頭結點時，指向首元結點）的指針，是鏈表的必要元素，用于標識一個鏈表。（2）頭結點：是附加在第一個元素結點之前的結點，其指針域指向首元結點。頭結點不是鏈表的必須要素，但引入它可以簡化插入和刪除操作的邊界條件（例如，在第一個位置插入或刪除時，操作邏輯與其他位置一致）。（3）首元結點：指鏈表中存儲第一個數據元素a1的結點。（2）單鏈表的基本操作【核心操作】★★★（1）初始化（帶頭結點）：生成一個新結點作為頭結點，用頭指針指向該頭結點，并將頭結點的指針域置空。StatusInitList(LinkListL){L=(LNode)malloc(sizeof(LNode));//生成頭結點if(!L)exit(OVERFLOW);//存儲分配失敗L>next=NULL;//指針域置空returnOK;}（2）求表長：設置一個計數器，從首元結點開始，依次遍歷鏈表，直到指針域為空。intListLength(LinkListL){LNodep=L>next;//p指向首元結點intcount=0;while(p){count++;p=p>next;}returncount;}（3）按位查找：查找第i個元素。設置一個指針p指向首元結點，計數器j從1開始。當j<i且p不為空時，指針p不斷后移。循環結束后，如果p為空或j>i，則第i個元素不存在；否則p所指結點即為第i個結點。StatusGetElem(LinkListL,inti,ElemTypee){LNodep=L>next;//p指向首元結點intj=1;//計數器while(pj<i){p=p>next;j++;}if(!p||j>i)returnERROR;//第i個元素不存在e=p>data;returnOK;}（4）按值查找：查找數據域等于給定值e的結點。從首元結點開始，依次遍歷鏈表，比較數據域的值。LNodeLocateElem(LinkListL,ElemTypee){LNodep=L>next;while(pp>data!=e){//假設ElemType支持!=比較p=p>next;}returnp;//找到則返回結點指針，未找到返回NULL}（5）插入操作（在第i個位置之前插入元素e）【核心難點】▲▲▲算法思想：首先找到第i1個結點（前驅結點），由指針p指向它。然后生成一個數據域為e的新結點s。最后將新結點s的指針域指向第i個結點（即p>next），并將p的指針域指向新結點s。關鍵步驟：s>next=p>next;p>next=s;【易錯點】插入步驟的順序非常關鍵。如果先執行p>next=s，那么p>next原本指向第i個結點的指針就會丟失，導致無法正確鏈接到后面的結點。StatusListInsert(LinkListL,inti,ElemTypee){LNodep=L;intj=0;//尋找第i1個結點while(pj<i1){p=p>next;j++;}if(!p||j>i1)returnERROR;//i小于1或大于表長+1LNodes=(LNode)malloc(sizeof(LNode));s>data=e;s>next=p>next;//步驟1p>next=s;//步驟2returnOK;}（6）刪除操作（刪除第i個結點）【核心難點】▲▲▲算法思想：首先找到第i1個結點（前驅結點），由指針p指向它。然后讓指針q指向要刪除的第i個結點（即p>next）。接著修改指針，將p的指針域指向q的后繼結點（即q>next）。最后釋放結點q的內存。關鍵步驟：q=p>next;p>next=q>next;free(q);【易錯點】必須用指針q暫存待刪結點，以便最后釋放內存，防止內存泄漏。同時要確保待刪結點存在（即p>next不為空）。StatusListDelete(LinkListL,inti,ElemTypee){LNodep=L;intj=0;//尋找第i1個結點while(p>nextj<i1){p=p>next;j++;}if(!(p>next)||j>i1)returnERROR;//刪除位置不合理LNodeq=p>next;//q指向待刪結點p>next=q>next;//修改指針，將待刪結點從鏈中斷開e=q>data;//保存被刪元素的值free(q);//釋放結點內存returnOK;}3、循環鏈表與雙向鏈表（1）循環鏈表（CircularLinkedList）循環鏈表是另一種形式的鏈式存儲結構。它的特點是表中最后一個結點的指針域不再為空，而是指向頭結點（或首元結點），整個鏈表形成一個環。（1）優點：從表中任一結點出發，都能訪問到鏈表中的所有其他結點。（2）操作：判斷循環鏈表是否為空的條件是頭結點的指針域是否指向它自身。（2）雙向鏈表（DoubleLinkedList）在單鏈表中，每個結點只有一個指向后繼的指針，因此從某結點出發只能向后查找。雙向鏈表則是在單鏈表的每個結點中，再增加一個指向其前驅的指針域prior。（1）結點結構|prior|data|next|（2）特點：可以方便地找到結點的前驅和后繼，插入和刪除操作雖然略微復雜（需同時修改兩個方向的指針），但操作本身的時間復雜度仍為O(1)（前提是已定位到操作點）。（3）【高頻考點】雙向鏈表的插入與刪除操作。插入操作（在p指向的結點之后插入s指向的新結點）：s>prior=p;s>next=p>next;p>next>prior=s;p>next=s;刪除操作（刪除p指向的結點）：p>prior>next=p>next;p>next>prior=p>prior;free(p);4、鏈表的算法效率分析與對比（與順序表）【高頻考點】▲▲▲（1）查找操作：按位查找和按值查找的平均時間復雜度均為O(n)。鏈表不具有隨機存取特性，只能通過遍歷實現順序存取。（2）插入與刪除操作：在已知待插入/刪除位置（即已定位到該位置或其前驅）的前提下，其指針修改操作本身的時間復雜度是O(1)。但通常我們還需要一個查找操作來定位該位置，因此綜合時間復雜度也是O(n)。（3）空間性能：鏈表不需要預先分配連續的大塊空間，可以按需動態申請和釋放，空間利用率高（但每個結點需要額外空間存儲指針，存儲密度低于順序表）。5、常見題型與解題步驟【題型1】單鏈表的逆置。【難點】▲▲【解題思路】（方法一：頭插法）遍歷原鏈表，依次將每個結點取出，用頭插法插入到一個新鏈表中。或者，采用就地逆置的方法，使用三個輔助指針pre,cur,next，依次改變指針方向。【解題步驟（就地逆置）】（1）將鏈表視為兩部分：已處理好的部分和未處理的部分。（2）初始化三個指針：pre=NULL,cur=L>nex=NULL。（3）循環遍歷鏈表，條件為cur!=NULL：a.先用next保存cur的后繼結點（next=cur>next），以防鏈表斷開后丟失。b.修改cur的指針域指向其前驅pre（cur>next=pre）。c.指針pre和cur整體后移，準備處理下一個結點（pre=cur;cur=next;）。（4）循環結束后，pre指向新的首元結點。將頭結點L的next指針指向pre。【題型2】判斷單鏈表中是否有環。【拓展思維】【解題思路】使用快慢指針法。定義兩個指針slow和fast，均從鏈表頭部開始。slow每次走一步，fast每次走兩步。如果鏈表中有環，那么fast指針最終一定會追上slow指針（二者相遇）；如果fast指針走到了鏈表末尾（NULL），則鏈表無環。【題型3】編程實現兩個有序鏈表的合并。【解題要點】與順序表類似，通過比較結點值的大小，將結點逐個鏈接到一個新鏈表上。需要注意指針的移動，以及最后處理剩余結點。（四）棧和隊列：受限的線性表【重要】▲▲▲棧和隊列是兩種特殊的線性表，它們的運算被限制在表的一端或兩端進行，因此是操作受限的線性表。1、棧（Stack）（1）棧的定義與邏輯特征棧是限定僅在表尾進行插入和刪除操作的線性表。表尾端稱為棧頂（Top），表頭端稱為棧底（Bottom）。不含元素的空表稱為空棧。棧的修改是按后進先出（LastInFirstOut,LIFO）的原則進行的。（2）棧的順序存儲結構——順序棧利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，通常用數組實現。附設一個指針top（通常指向棧頂元素的下一個位置或棧頂元素本身）來指示棧頂位置。基本操作（top指向棧頂元素的下一個位置）：（1）初始化：base=top=數組基址；stacksize=最大容量。（2）判空：top==base。（3）判滿：topbase==stacksize。（4）入棧（push）：top++=e;先將e放入top指向的位置，然后top加1。（5）出棧（pop）：e=top;先將top減1，然后取出該位置的元素。【易錯點】務必注意top指針的含義。不同的實現方式，入棧出棧的操作符略有差異，但核心都是要檢查棧空和棧滿。（3）棧的鏈式存儲結構——鏈棧鏈棧是運算受限的單鏈表，其插入和刪除操作只能在鏈頭（棧頂）進行。通常用單鏈表的頭指針作為棧頂指針，不需要頭結點。鏈棧基本不存在棧滿的問題，除非內存耗盡。（4）棧的應用場景【高頻考點】▲▲▲（1）函數調用與遞歸實現：系統用一個棧來保存每次函數調用的返回地址、參數和局部變量。遞歸調用本質就是函數調用自身，因此也是通過棧來實現的。（2）括號匹配檢驗：編譯器在檢查程序中的括號是否匹配時，會使用棧。遇到左括號則入棧，遇到右括號則檢查棧頂的左括號是否與之匹配，若匹配則出棧，否則報錯。（3）表達式求值：中綴表達式轉后綴表達式，以及后綴表達式的計算，都需要借助棧來實現。這是棧的經典應用。（4）瀏覽器的“后退”功能：用戶訪問的頁面依次被壓入棧中，點擊“后退”按鈕，即執行出棧操作，返回到上一個頁面。（5）撤銷操作（Undo）：在文本編輯器或繪圖軟件中，每一次操作被記錄并壓入“操作棧”，執行撤銷時，從棧頂彈出一個操作并恢復其狀態。（5）常見題型【題型1】一個棧的入棧序列為a,b,c,d，則出棧序列不可能的是？【解題思路】牢記棧的LIFO特性。可以用模擬法，嘗試每個可能的入棧和出棧時機。例如，如果a第一個出棧，說明a入棧后立即出棧，此時棧空，然后b、c、d依次入棧出棧，可得序列a,b,c,d。如果b第一個出棧，說明a先入棧，b入棧后出棧，此時a還在棧底，然后c、d操作，a最后出棧，可得b,c,d,a或b,a,c,d等，但b,c,a,d是可能的（b出，c入出，a出，d入出）。不可能的出棧序列通常違反了“后入先出”的原則，如d,a,b,c就不可能，因為d出棧時，棧底有a、b、c，它們只能按c、b、a的順序出棧。【題型2】編程實現括號匹配檢驗。【解題步驟】（1）遍歷輸入的字符串。（2）如果遇到左括號（如'(','[','{'），則將其壓入棧中。（3）如果遇到右括號，先檢查棧是否為空。若為空，則說明右括號多余，匹配失敗。（4）若棧不為空，則取出棧頂元素。檢查該棧頂左括號是否與當前右括號匹配（如'('與')'匹配）。若匹配，則將棧頂元素出棧，繼續處理下一個字符；若不匹配，則匹配失敗。（5）遍歷結束后，檢查棧是否為空。若為空，則所有括號匹配成功；否則，說明有左括號未被匹配，匹配失敗。2、隊列（Queue）（1）隊列的定義與邏輯特征隊列是只允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端叫隊尾（rear），允許刪除的一端叫隊頭（front）。隊列的修改是按先進先出（FirstInFirstOut,FIFO）的原則進行的。（2）隊列的順序存儲結構——循環隊列用一組地址連續的存儲單元依次存放從隊頭到隊尾的元素，通常用數組實現。附設兩個指針front和rear分別指示隊頭元素和隊尾元素的位置。為了充分利用數組空間，克服“假溢出”現象，通常將順序隊列臆造為一個環狀的空間，即循環隊列。【核心難點】循環隊列的隊空和隊滿判定條件。（1）約定：初始化時，front=rear=0。（2）隊空條件：front==rear。（3）隊滿條件：(rear+1)%MAXQSIZE==front。即犧牲一個元素空間來區分隊空和隊滿。如果隊尾指針加1后（取模）等于隊頭指針，則認為隊滿。（4）入隊（enqueue）：q.rear=(q.rear+1)%MAXQSIZE;q.data[q.rear]=e;（5）出隊（dequeue）：q.front=(q.front+1)%MAXQSIZE;e=q.data[q.front];【易錯點】（1）務必理解取模運算（%）在循環隊列中的作用，它實現了指針的循環移動。（2）求隊列長度公式：(q.rearq.front+MAXQSIZE)%MAXQSIZE。（3）隊列的鏈式存儲結構——鏈隊列鏈隊列是用鏈表表示的隊列，通常用兩個指針分別指向隊頭和隊尾。一個鏈隊列顯然需要兩個分別指向隊頭和隊尾的指針（頭指針和尾指針）才能唯一確定。（4）隊列的應用場景【高頻考點】▲▲▲（1）操作系統中的作業排隊：當多個進程需要獲取CPU時間時，它們被放入就緒隊列，按照先來先服務的原則被調度。（2）打印任務緩沖：當多個文檔需要打印時，它們被放入打印隊列，打印機按提交順序依次打印。（3）消息隊列：在多線程或分布式系統中，用于線程間或服務間的異步通信。（4）廣度優先搜索（BFS）：在圖或樹的遍歷算法中，需要使用隊列來記錄每一層待訪問的結點。（5）常見題型【題型1】循環隊列中，已知front和rear指針的值及隊列容量，求隊列中元素個數或判斷隊空/隊滿。【解題步驟】直接套用公式：(rearfront+MAXQSIZE)%MAXQSIZE計算長度。判斷隊滿條件：(rear+1)%MAXQSIZE==front。【題型2】編程實現用兩個棧模擬一個隊列。【解題思路】使用兩個棧，一個棧（stack1）作為輸入棧，用于處理入隊操作；另一個棧（stack2）作為輸出棧，用于處理出隊操作。（1）入隊（enqueue）：直接將元素壓入stack1。（2）出隊（dequeue）：如果stack2不為空，則直接從stack2彈出元素；如果stack2為空，則將stack1中的所有元素依次彈出并壓入stack2，然后從stack2彈出棧頂元素。這樣就實現了元素的先進先出順序。三、算法效率分析與選擇策略（一）時間復雜度與空間復雜度回顧【基礎】★1、時間復雜度：衡量算法執行時間隨輸入規模增長而增長的度量，通常用大O記法表示。常見復雜度有O(1)、O(n)、O(n2)、O(logn)等。2、空間復雜度：衡量算法在執行過程中臨時占用的存儲空間大小隨輸入規模增長而增長的度量。（二）線性結構的選擇策略【綜合應用】▲▲▲在實際問題中，選擇合適的線性結構是至關重要的。以下是決策時的參考維度：（1）基于操作頻率的選擇（1）如果應用需要頻繁地進行按位置查找（隨機存取），而對插入和刪除操作要求不高，應優先選擇順序表。（2）如果應用需要頻繁地進行插入和刪除操作，尤其是在表的中間位置，而對查找的實時性要求不高，應優先選擇鏈表。（2）基于存儲空間的選擇（1）如果能夠預先估計數據量的最大規模，并且對存儲空間利用要求較高（不希望有額外的指針開銷），可以選擇順序表。（2）如果數據量變化較大，難以估計最大規模，或者希望動態管理內存，避免空間浪費或溢出，應優先選擇鏈表。（3）基于應用場景的匹配（1）如果需要實現“后進先出”的邏輯，如函數調用、表達式求值、撤銷操作等，應選擇棧。（2）如果需要實現“先進先出”的邏輯，如任務排隊、緩沖處理、廣度優先搜索等，應選擇隊列。四、學習難點突破與易錯點警示（一）核心概念理解誤區（1）邏輯結構與存儲結構混淆：邏輯結構解決的是“元素之間是什么關系”的問題（如線性、樹形、圖形），而存儲結構解決的是“這種關系如何在計算機內存中表示”的問題（如順序、鏈式、索引、散列）。同一個邏輯結構（如線性表）可以用多種存儲結構（順序表、鏈表）來實現。（2）指針的理解偏差：鏈表中的指針存儲的是下一個結點的內存地址，而非結點本身。指針的賦值和修改，改變的是“指向”關系。對于鏈表的操作，本質就是對指針變量的操作。（3）棧頂指針的含義不清：在不同的教材或實現中，棧頂指針可能指向棧頂元素，也可能指向棧頂元素的下一個空位置。這會影響判空、判滿、入棧、出棧的具體代碼，但在邏輯上都是正確的。（二）算法實現常見錯誤（1）鏈表操作中指針丟失：在插入