2023CSP初赛备考 || 复习 -数据结构-链表

线性表

线性表是由同种数据类型的数据元素组成的有序序列

线性表一般用于存储有顺序关系的数据序列

线性表操作

插入元素：在线性表的指定位置插入一个元素

删除元素：在线性表的指定位置删除一个元素

访问元素：访问线性表中指定位置的一个元素

线性表种类

1 数组 (array)

数组是有序的元素序列，其特点是相邻的两个元素在物理内存上也是相邻的，整个数组是一段连续的内存空间

优点

检索效率高

缺点

随机增删效率较低，数组无法存储大数据量 --需要提前预估存储多少数据

2 链表 (lined list)

链表不同于数组，链表是一种链式的数据结构

链表由若干个节点相连而成，每个节点内部分为数据域和链接域，数据域即该节点保存的具体数据，链接域是指向其他节点的指针

优点

在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素

缺点

没有解决连续存储分配带来的表长难以确定的问题 --需要提前预估存储多少数据

失去了顺序存储结构随机存取的特性

3 队列(queue)

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作

队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头

队列可以理解成我们平时的排队，先进入的先出去

4 栈(stack)

栈又名堆栈，是一种限定仅在表尾进行插入和删除操作的线性表，这一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出的原则。

向一个栈插入新元素又称作进栈、入栈或压栈，使之成为新的栈顶元素，从一个栈删除元素又称作出栈或退栈

链表种类

1 单向链表

一种最简单的结点结构如图所示，它是构成单链表的基本结点结构

在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。

因为只有一个指针结点，称为单链表

插入元素

在节点a和节点c之间插入b

删除元素

2 双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点

如下图所示

插入元素

c的前面插入b

删除元素

删除b节点

3 循环链表

单项链表最好一个节点的指针指向链表的第1个节点，整个链表形成一个环，从表中任意节点出发均可找到其他点

上述添加删除也可能是头尾指针，可思考有什么不同？

2023暑假班数学思维大纲

●高斯算法    ●图中填数    ●算式谜语    ●平均数问题        ●植树问题

●妙算技巧    ●拆数技巧    ●页码问题    ●高级鸡兔同笼     ●年龄问题

●行程问题    ●行走路线问题    ●组合图形   ●工程问题   ●整除与剩余问题

●周期问题    ●天平问题     ●买卖问题    ●非十进制    ●牛吃草

说明:实际课程根据上课进度略有调整。