数据结构基础：线性表的定义与操作

"这篇笔记主要介绍了数据结构中的线性表，包括其定义、抽象数据类型以及两种不同的存储结构——顺序存储结构和静态链表。笔记内容来自小甲鱼的视频教程，涵盖了线性表的基本操作，如初始化、判断空表、元素的插入和删除等。此外，还详细讨论了顺序存储结构的属性以及静态链表的特点和操作。" 在数据结构中，线性表是一种基础且重要的数据组织形式，由零个或多个有序的数据元素组成。线性表的特点在于每个元素都有且仅有一个直接前驱和后继（除了首尾元素）。抽象数据类型（ADT）用于描述线性表的操作，包括初始化、判断空表、清空表、获取元素、查找元素、插入元素、删除元素以及获取表的长度。 线性表的抽象数据类型定义了如下操作： 1. Initlist(*L)：初始化线性表L，创建一个空表。 2. ListEmpty(L)：检查线性表L是否为空，返回布尔值。 3. ClearList(*L)：清除线性表L的所有元素。 4. GetElem(L,i,*e)：获取线性表L中位置i的元素值并赋值给e。 5. LocateElem(L,e)：查找线性表L中值为e的元素，返回其位置，找不到则返回0。 6. ListInsert(*L,i,e)：在L的第i位置插入元素e。 7. ListDelete(*L,i,*e)：删除L的第i位置元素，并用e返回其值。 8. ListLength(L)：返回线性表L的元素数量。 线性表的顺序存储结构是通过数组实现的，包含三个关键属性：数组data（起始存储位置）、最大存储容量（数组长度MaxSize）以及当前长度（元素个数length）。数组长度通常在初始化后保持不变，而当前长度随元素的增减而变化。插入和删除操作在顺序存储结构中可能涉及元素的移动。 链表元素的插入操作涉及修改指针，例如，在节点P和P->next之间插入节点S，需要先保存P的后继节点，然后更新P的next指向新插入的节点S。 静态链表是一种特殊的链表，其中元素的数据部分不直接存储元素值，而是存储其后继元素的位置（游标）。静态链表的初始化需要设置每个元素的游标值，对于第一个元素，游标值为第一个无数据元素的下标；对于最后一个元素，游标值为第一个有数据元素的下标；中间元素的游标值为其后继元素的下标。删除操作在静态链表中只需修改游标，无需移动元素，提高了效率。 静态链表的优点在于插入和删除操作时只需要改变游标，避免了元素移动，但其缺点是没有解决连续存储分配的问题，仍然需要预先分配固定大小的存储空间，可能导致空间利用率不高。