山东大学《数据结构》讲义02线性表.docx

线性表是一种基础且重要的数据结构，它由n（n>0）个数据元素组成，这些元素之间存在一对一的前后关系，形成一个有序的序列。线性表的特征包括：一个唯一的首元素和尾元素，每个非尾元素都有且仅有一个直接前驱和一个直接后继，而首元素没有前驱，尾元素没有后继。 线性表有两种常见的存储结构：顺序存储和链式存储。 1. **顺序存储**：线性表的数据元素存储在一块连续的内存区域中，通过数组来实现。优点是访问速度快，因为数组支持随机访问，时间复杂度为O(1)。但插入和删除操作较为复杂，通常需要移动大量元素，时间复杂度为O(n)。 2. **链式存储**：线性表的数据元素通过一系列节点链接起来，每个节点包含数据元素和指向下一个节点的指针。链式存储在插入和删除操作上有优势，因为只需改变指针关系，时间复杂度为O(1)，但访问元素需要从头节点开始遍历，时间复杂度为O(n)。 线性结构与非线性结构的根本区别在于元素之间的关系。线性结构的元素呈线性排列，每个元素有确定的前后关系；而非线性结构如树、图等，元素之间的关系更为复杂，可能有多个父节点或子节点。 在单链表中，可以从当前节点出发访问其后继节点，但不能直接访问前驱节点，需要通过遍历来实现。而在双向链表中，不仅可以访问后继节点，还可以访问前驱节点。 对于频繁进行存取操作而不常进行插入和删除的线性表，采用顺序存储结构较为合适，因为存取速度快。反之，如果插入和删除操作频繁，应选择链式存储结构，以减少元素移动。 设置头结点的主要作用是方便操作。在单链表中，头结点不存储实际数据，而是用于标识链表的起始位置，这样在插入和删除操作时可以直接操作头结点，简化了代码实现。 逆置单链表的算法可以通过三个指针p、q、r实现，初始时p指向头结点，q指向p的后继，r指向q的后继，然后依次将p、q、r的指针互换，直到q为空，最后将p指向的结点设为新的头结点。 删除单链表中重复元素的算法可以遍历链表，比较当前节点与前一个节点的元素是否相等，如果相等则删除当前节点，确保相邻的元素不重复。 线性表的抽象数据类型定义包括数据元素的类型、线性表的操作集合以及这些操作的定义。了解这些基础知识是理解和使用线性表的关键，也是进一步学习其他复杂数据结构的基础。