线性表详解：定义、操作与实现

"该资源是严蔚敏教授关于数据结构课程的第二章——线性表的讲解，主要涵盖了线性表的类型定义、顺序表示与实现、链式表示与实现，以及一元多项式的表示和相加。核心知识点包括线性结构的特点、线性表的定义、线性表的操作算法等。" 线性表是一种基本的数据结构，由n(n≥0)个数据元素组成有限序列，每个元素都有其唯一的位置，即位序。线性结构的特点包括：单个开始结点、单个终端结点、每个非首元素有一个前驱，每个非尾元素有一个后继。线性表可以表示为(a1, ..., ai, ai+1, ..., an)，其中ai表示第i个数据元素。 在类型定义中，线性表由数据集合D及其上的关系R构成，D包含所有数据元素，而R定义了元素之间的前后关系。线性表的长度是数据元素的个数n，长度为0的表称为空表。线性表中的元素具有均匀性和有序性。 线性表的操作包括初始化、求长度、取元素、按值查找、插入和删除等。初始化操作InitList(&L)用于创建一个空表；ListLength(L)返回线性表的长度；GetElem(L,i,&e)获取第i个元素并赋值给e；LocateElem(L,e)查找值为e的元素并返回其位序；ListInsert(&L,i,e)在第i个位置插入元素e；ListDelete(&L,i,&e)删除第i个元素并返回其值。这些操作是线性表操作的基础。 在实际应用中，如例2-1所示，合并两个线性表A和B的时间复杂度取决于线性表的长度，LocateElem()的操作次数可能达到O(ListLength(A)*ListLength(B))，因为可能需要遍历每个元素进行查找。例2-2中，将LA和LB合并到LC中的时间复杂度取决于ListInsert()的执行次数，这通常为O(ListLength(LA)+ListLength(LB))，因为每个元素都需要插入一次。 线性表的顺序表示通常使用数组实现，这种表示方式存储效率高，但插入和删除操作需要移动大量元素，因此不适用于频繁修改的情况。链式表示则通过链节点连接元素，插入和删除操作相对高效，但需要额外的存储空间来保存指针。 对于一元多项式的表示，可以使用线性表来存储系数和对应的幂次，实现多项式的加法操作。这展示了线性表在数学问题上的应用。 总结来说，线性表是数据结构中的基础，它的理论和实现方法对于理解和处理各种数据问题至关重要。无论是顺序表示还是链式表示，都有其适用的场景和优缺点，需要根据实际需求选择合适的数据结构。