考研系列-数据结构第二章、线性表
目录
一、线性表的基本概念
1.定义
2.线性表的一些操作
(1).基本操作（增删改查）
(2).线性表其他常用操作
(3)在定义这些操作时的注意事项
3.重要考点总结
4.易错题总结
二、顺序表
1.顺序表定义
2.顺序表实现方式
3.顺序表元素的插入和删除
(1)插入元素
(2)删除元素
4.顺序表查找
(1)按数组下标查找
(2)按元素值查找
5.易错题总结
(1)选择题
(2)简答题
三、链表
1.单链表
(1)单链表的结构体定义
(2)插入元素
①带头结点插入
②不带头结点插入
(3)删除元素
①按位序删除
②指定结点删除
(4)查找元素
①按位查找
②按值查找
③遍历链表求链表长度
(5)根据给定元素创建单链表
①头插法
②尾插法
③总结
2.双链表
(1)初始化
(2)插入元素
(3)删除元素
(4)遍历
3.循环链表
4.静态链表
四、顺序表和链表对比
1.对比角度
(1)逻辑结构
(2)存储结构
(3)基本操作
(4)选用场景
2.总结
五、易错题总结
1.选择题
2.简答题
六、本章归纳总结
七、参考
一、线性表的基本概念
1.定义
这里线性表是指的逻辑结构，它可以使用顺序存储也可以使用链式存储，和物理结构区分开。
2.线性表的一些操作
这些操作是数据结构中线性表的基础，掌握它们对于理解和应用线性表至关重要。
(1).基本操作（增删改查）
初始化表 (InitList(&L)) ：这个操作用于构造一个空的线性表L，并为其分配必要的内存空间。这是从无到有的过程，为后续的操作提供一个空的框架。
销毁操作 (DestroyList(&L)) ：这个操作用于销毁线性表，并释放线性表L所占用的内存空间。这是从有到无的过程，确保内存的有效管理和释放。
插入操作 (ListInsert(&L, i, e)) ：在表L中的第i个位置上插入指定的元素e。这个操作实现了线性表的“增”功能，可以根据需要在任意位置添加元素。
删除操作 (ListDelete(&L, i, &e)) ：删除表L中第i个位置的元素，并通过参数e返回被删除元素的值。这个操作实现了线性表的“删”功能，可以根据需要移除元素。
按值查找操作 (LocateElem(L, e))）：在表L中查找具有给定关键字值的元素。这个操作用于检索特定值的元素，实现“查”的功能。
按位查找操作 (GetElem(L, i)) ：获取表L中第i个位置的元素的值。这也是“查”功能的一种，通过位置索引来获取元素。
(2).线性表其他常用操作
求表长 (Length(L)) ：返回线性表L的长度，即L中数据元素的个数。
输出操作 (PrintList(L)) ：按前后顺序输出线性表L的所有元素值。
判空操作 (Empty(L)) ：判断线性表L是否为空，若为空则返回true，否则返回false。
(3)在定义这些操作时的注意事项
命名要有可读性：函数名和参数应该具有明确的含义，方便理解和使用。
参数传递：在某些情况下，如需要修改参数的值并返回到调用者时，需要使用引用（如C/C++中的&）来传递参数。
3.重要考点总结
4.易错题总结
问题：
02. 以下( )是一个线性表。
A.由"个实数组成的集合 B.由100个字符组成的序列
C.所有整数组成的序列 D.邻接表
解答：
02. B
线性表定义的要求为：相同数据类型、有限序列。选项C的元素个数是无穷个，错误；选项A集合中的元素没有前后驱关系，错误；选项D属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈。只有选项B符合线性表定义的要求。
二、顺序表
顺序表就是一种顺序表示的线性表，形式上就是我们常说的数组。
在考察顺序表时，其实就是对数组的操作（数据结构的选择题和算法大题常考察），在本章中我们着重对选择题的知识点进行总结，算法大题常考查的是查找和排序，这部分后面会有专题总结。
※选择题知识点主要是掌握顺序表的基本操作：初始化、增、删、改、查。
👇🏻👇🏻👇🏻顺序表基本操作C++代码实现可以参考下面文章👇🏻👇🏻👇🏻：
顺序表相关代码-CSDN博客文章浏览阅读20次。【代码】顺序表相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235748
1.顺序表定义
2.顺序表实现方式
//顺序表静态分配结构体定义
typedef struct{
int data[InitSize];
int length;
}SeqListStatic;
//顺序表动态分配结构体定义
typedef struct{
int *data;
int MaxSize;
int length;
}SeqList;
3.顺序表元素的插入和删除
(1)插入元素
//顺序表的插入元素,在第i个位置处插入元素elem
//平均时间复杂度O(n)
bool InsertElem(SeqList &L,int i,int &elem){
if(iL.length+1){
return false;
}
if(L.length==L.MaxSize){//顺序表满
return false;
}
for(int j=L.length;j>=i;j--){//从最后一个元素开始
L.data[j]=L.data[j-1];//元素后移，直到第i个位置
}
L.data[i-1]=elem;
L.length++;//不要忘记修改顺序表的长度
return true;
}
(2)删除元素
删除第i个位置的元素，i+1以后的所有元素前移动一位，注意从i+1位置开始往前移动。
//顺序表删除元素,删除第i个位置元素
//平均时间复杂度O(n)
bool deletElem(SeqList &L,int i,int &deletedelem){
if(iL.length){
return false;
}
deletedelem=L.data[i-1];
for(int j=i-1;j
