高中信息技术选择性必修一《线性结构》知识清单

高中信息技术选择性必修一《线性结构》知识清单一、课程导引：数据组织的基石与计算思维的锚点【核心概念】线性结构是数据结构中最基础、最常用的一类逻辑结构，其特征是数据元素之间存在着“一对一”的线性关系。在高中信息技术课程中，学习线性结构不仅是为了掌握几种具体的存储和操作方法，更是为了培养同学们的计算思维——即如何通过抽象、分解和建模来高效地处理现实世界中的复杂问题。本章内容是后续学习树、图等复杂数据结构的基石，也是算法设计与程序实现的必经之路。【学习目标】理解线性表的逻辑结构定义；掌握顺序表和链表两种基本存储结构及其主要操作的算法实现；理解栈和队列作为受限线性表的特殊性和应用场景；能够根据实际问题，从时间复杂度、空间复杂度等角度，选择并设计合适的线性结构来组织数据，并编写相应的程序代码解决问题。二、核心知识模块详解（一）线性表：线性结构的逻辑模型【基础】★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(n²)、O(logn)等。2、空间复杂度：衡量算法在执行过程中临时占用的存储空间大小随输入规模增长而增长的度量。（二）线性结构的选择策略【综合应用】▲▲▲在实际问题中，选择合适的线性结构是至关重要的。以下是决策时的参考维度：（1）基于操作频率的选择（1）如果应用需要频繁地进行按位置查找（随机存取），而对插入和删除操作要求不高，应优先选择顺序表。（2）如果应用需要频繁地进行插入和删除操作，尤其是在表的中间位置，而对查找的实时性要求不高，应优先选择链表。（2）基于存储空间的选择（1）如果能够预先估计数据量的最大规模，并且对存储空间利用要求较高（不希望有额外的指针开销），可以选择顺序表。（2）如果数据量变化较大，难以估计最大规模，或者希望动态管理内存，避免空间浪费或溢出，应优先选择链表。（3）基于应用场景的匹配（1）如果需要实现“后进先出”的逻辑，如函数调用、表达式求值、撤销操作等，应选择栈。（2）如果需要实现“先进先出”的逻辑，如任务排队、缓冲处理、广度优先搜索等，应选择队列。四、学习难点突破与易错点警示（一）核心概念理解误区（1）逻辑结构与存储结构混淆：逻辑结构解决的是“元素之间是什么关系”的问题（如线性、树形、图形），而存储结构解决的是“这种关系如何在计算机内存中表示”的问题（如顺序、链式、索引、散列）。同一个逻辑结构（如线性表）可以用多种存储结构（顺序表、链表）来实现。（2）指针的理解偏差：链表中的指针存储的是下一个结点的内存地址，而非结点本身。指针的赋值和修改，改变的是“指向”关系。对于链表的操作，本质就是对指针变量的操作。（3）栈顶指针的含义不清：在不同的教材或实现中，栈顶指针可能指向栈顶元素，也可能指向栈顶元素的下一个空位置。这会影响判空、判满、入栈、出栈的具体代码，但在逻辑上都是正确的。（二）算法实现常见错误（1）链表操作中指针丢失：在插入