2023计算机考研：数据结构中线性表的核心考点（上）

今天小编为大家整理了数据结构中线性表的核心考点介绍，帮助大家梳理考试内容，提高备考效率，更好地掌握相关知识，以下是详细介绍。

核心1：线性表的顺序定义

顺序表是指用一组连续的存储单元，依次存储线性表中的各个元素，从而使得逻辑上相邻的元素在物理位置上也相邻，因此可以随机存取(根据首元素地址和元素序号)表中任一元素。其结构体定义是：

核心2：顺序表的插入操作

对于插入算法，若表长为n，则在第i位置插入元素，则从an到ai都要向后移动一个位置，共需移动n-i+1个元素，平均时间复杂度为O(n)。其核心代码是：

核心3：顺序表的删除操作

对于删除算法，若表长为n，当删除第i个元素时，从ai+1到an都要向前移动一个位置，则共需移动n-i个元素，平均时间复杂度为O(n)。其核心代码是：

核心4：顺序表的查找

(1)按序号查找，顺序表具有随机存取的特点，时间复杂度为O(1)。

(2)按值x查找，主要运算是比较操作，比较的次数与值x在表中的位置有关，也与表长有关，平均比较次数为(n+1)/2，时间复杂度为O(n)。

核心5：单链表的定义

单链表是指通过一组任意的存储单元来存储线性表中的元素。为了建立元素之间的线性关系，对每个链表结点，除了存放元素自身的信息，还需要存放一个指向其后继的指针。其定义格式是：

核心6：单链表的查找

单链表的存储单元是不连续的，因此无论是查找第i个结点，还是查找给定值x的结点，都只能从表中第一个结点出发，顺指针next域逐个往下搜索，直到找到满足条件的结点为止。时间复杂度为O(n)。

核心7：头插法建立单链表

从一个空表开始，然后将新结点插入当前链表的表头，即头结点之后，采用头插法建立单链表的算法虽然简单，但读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，总的时间复杂度为O(n)。

详细的实现过程，大家可以参考考点讲解。

核心8：尾插法建立单链表

若希望读入数据的顺序与生成的链表中元素的顺序一致，可采用尾插法。即将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

详细的实现过程，大家可以参考考点讲解。