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

目录

一、线性表的基本概念

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符合线性表定义的要求。

二、顺序表

        顺序表就是一种顺序表示的线性表，形式上就是我们常说的数组。

        在考察顺序表时，其实就是对数组的操作（数据结构的选择题和算法大题常考察），在本章中我们着重对选择题的知识点进行总结，算法大题常考查的是查找和排序，这部分后面会有专题总结。

        ※选择题知识点主要是掌握顺序表的基本操作：初始化、增、删、改、查。

        

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/702639