考研系列-数据结构第二章、线性表

目录

一、线性表的基本概念

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(i<1||i>L.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(i<1||i>L.length){
        return false;
    }
    deletedelem=L.data[i-1];
    for(int j=i-1;j-1;j++){//后一元素前移
        L.data[j]=L.data[j+1];
    }
    L.length--;
    
    return true;
}

4.顺序表查找

(1)按数组下标查找

(2)按元素值查找

注意：在if(L.data[i]==e)这里，基本数据类型可以直接用“==”来比较，但是结构类型元素不行，要么重载运算符，要么一个属性一个属性的去比较。

5.易错题总结

(1)选择题

题目：

        02.线性表的顺序存储结构是一种(        )        易错题！！！

        A.随机存取的存储结构                 B.顺序存取的存储结构

        C.索引存取的存储结构                 D.散列存取的存储结构

解答：

        A

        本题易误选B。注意，存取方式是指读写方式。顺序表是一种支持随机存取的存储结构，根据起始地址加上元素的序号，可以很方便地访问任意一个元素，这就是随机存取的概念。

题目：

        05. 一个线性表最常用的操作是存取任意一个指定序号的元素并在最后进行插入、删除操作，则利用(        )存储方式可以节省时间。

        A.顺序表                                   B.双链表

        C.带头结点的双循环链表         D.单循环链表

解答：

        A

        只有顺序表可以按序号随机存取，且在最后进行插入和删除操作时不需要移动任何元素。

(2)简答题

题目：

解答：

        和第5题一样，用变量k记录重复个数，后面的值往前移动k个单位即可

题目：

解答：

        通过这个题目记住这种算法思想，用一个值记录前面重复元素的个数k，后面元素前移k个位置即可！

题目：

解答：

        比较基础，需要掌握代码和思想！！

题目：

解答：

重要！逆序的思想

题目：

解答：

题目：

解答：

        主要先掌握算法思想

三、链表

         链表就是一种线性表的链式表示，链表有多种形式：单链表、双链表、循环单链表、循环双链表。

        在考察链表时，对链表的结构定义和操作进行考察（数据结构的选择题和算法大题常考），在本章中我们着重对选择题的知识点进行总结，算法大题常考查的是链表的结构定义以及链结点的增删操作。

        ※选择题知识点主要是掌握上面四种形式链表的基本操作：增、删、改、查。

        👇🏻👇🏻👇🏻链表基本操作C++代码实现可以参考下面文章👇🏻👇🏻👇🏻

        单链表：

链表相关代码-CSDN博客文章浏览阅读87次。【代码】链表相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235780        双链表：

双向链表相关代码-CSDN博客文章浏览阅读147次。【代码】双向链表相关代码。https://blog.csdn.net/hehe_soft_engineer/article/details/134235868

1.单链表

(1)单链表的结构体定义

C++实现链表定义：

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;
//LinkList L;声明一个指向单链表第一个节点的指针
//LNode *L;声明一个指针，指向单链表的第一个节点

链表可以分为带头结点和不带头结点：

①不带头结点的单链表初始化

②带头结点的单链表初始化

(2)插入元素

①带头结点插入

• 在链头插入

• 在链表中间插入：先找到第i个结点，然后在i结点后面加入新结点

• 在链尾插入

• 插入的时间复杂度：O(n)

②不带头结点插入

• 在链头插入

• 在链表中间插入

        指定结点后面插入元素：

        指定节点的前插操作：

        ※已知头指针可以遍历然后插入

        ※如果未知头指针，则前驱结点不可知，所以可以通过移动数据的方式

(3)删除元素

①按位序删除

②指定结点删除

        这样写是有点问题的：

(4)查找元素

①按位查找

②按值查找

③遍历链表求链表长度

(5)根据给定元素创建单链表

①头插法

②尾插法

③总结

2.双链表

(1)初始化

(2)插入元素

(3)删除元素

(4)遍历

3.循环链表

(1)循环单链表

①循环单链表的初始化代码实现：

②单链表和循环单链表对比

循环单链表从一个结点出发，就能向后遍历到全部的结点：

(2)循环双链表

①循环双链表初始化

②循环双链表的插入结点

③循环双链表的删除删除结点

④总结

4.静态链表

(1)静态链表定义代码实现

(2)静态链表的初始化

(3)查找、插入、删除元素操作

(4)静态链表的知识总结及特点说明

四、顺序表和链表对比

1.对比角度

(1)逻辑结构

都属于线性表，属于线性结构

(2)存储结构

(3)基本操作

(4)选用场景

2.总结

五、易错题总结

1.选择题

问题：

解答：

问题：

解答：

2.简答题

问题：

        1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。

解答：        

问题：

        3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

解答：

        思路：可以先逆置，然后输出；这个题目也可以用递归算法：

问题：

        8.给定两个单链表，编写算法找出两个链表的公共结点。

解答：

        这里的公共结点是指的，在某个结点处两个链表重合了，呈现Y字型；这里注意第二种算法，很巧妙：

问题：

解答：

问题：

解答：

问题：

解答：

问题：

解答：

问题：

解答：

        这个设置快慢指针的方式要注意：

六、本章归纳总结

既是知识点小结，也是算法题方法小结。

七、参考

        📚课件来源：王道考研

        📚课本及题目：《2024数据结构考研复习指导-王道论坛》

---

欢迎大家交流学习，如有错误请批评指正！

下一章：栈、队列和数组

考研系列-数据结构第三章：栈、队列和数组-CSDN博客文章浏览阅读91次。本文详细总结了王道考研视频课内关于栈、队列的结构、常用操作以及应用场景，还对二维矩阵中特殊矩阵的压缩存储进行总结归纳。文章中还整理了常见的错题和知识归纳总结，是考研复习的好帮手！https://blog.csdn.net/hehe_soft_engineer/article/details/139584178

---