线性表数据结构详解：定义与基本操作

"该资源是严蔚敏教授关于数据结构课程的课件，重点讲解了线性表这一数据结构。内容涵盖了线性表的类型定义、顺序表示与实现、链式表示与实现，以及一元多项式的表示和相加。在讲解中，提到了线性结构的特点，如唯一开始结点、唯一终端结点、每个数据元素有唯一前驱和后继。此外，还介绍了线性表的基本操作，包括初始化、求长度、取元素、按值查找、插入和删除等。" 线性表是数据结构的基础概念之一，它由n个数据元素组成的有限序列，每个元素都有唯一的前驱和后继。线性结构的特点确保了数据元素之间的顺序关系。线性表可以被表示为(D,R)，其中D是数据元素的集合，R是数据元素之间的关系集合，即线性序列。线性表的长度定义为数据元素的个数n，当长度为0时，称为空表。 在定义结构体类型的同时定义结构体变量是C语言中常见的做法。例如，在描述学生信息时，可以创建一个名为`student`的结构体类型，包含`num`（学号）、`name`（姓名）、`sex`（性别）、`age`（年龄）、`score`（成绩）和`addr`（地址）等成员。然后可以定义`stu1`和`stu2`两个结构体变量，它们都是`student`类型的实例。 线性表的顺序表示通常使用数组实现，每个元素在内存中是连续存储的，方便进行随机访问和元素操作。顺序表的基本操作，如初始化、求长度、获取元素、查找、插入和删除，都有相应的算法。例如，初始化线性表`InitList(&L)`会创建一个空表，而`ListLength(L)`返回表的长度。`GetElem(L,i,&e)`函数用于获取第i个元素的值并存储在`e`中，`LocateElem(L,e)`则是按值查找元素，返回其位序。`ListInsert(&L,i,e)`在第i个位置插入元素`e`，`ListDelete(&L,i,&e)`则删除第i个元素，并将被删除元素的值返回。 线性表的链式表示通常用链表实现，每个元素（节点）包含数据域和指针域，指针域指向下一个元素。链式表示的优点在于插入和删除操作通常只需要改变几个指针，而不需要移动大量元素，因此在某些情况下效率更高。但是，链式表示不支持随机访问，获取第i个元素可能需要遍历前i-1个元素。 线性表的操作效率取决于具体实现。例如，对于按值查找`LocateElem()`，在顺序表中查找的时间复杂度为O(ListLength(A)*ListLength(B))，因为可能需要遍历两个列表的全部元素。而在链表中，如果采用顺序查找，时间复杂度也是线性的；如果采用哈希表等索引结构，查找速度可以提高到常数级别。 合并两个线性表A和B通常涉及到遍历和插入操作，算法2.2中将LA和LB合并到LC中，需要对LA和LB的每个元素执行插入操作，所以总的时间复杂度与插入操作的执行次数相同，即O(ListLength(LA) + ListLength(LB))。 这个资源深入介绍了线性表这一数据结构，不仅讲解了理论知识，还给出了具体的算法实现和操作示例，是学习数据结构和算法的好材料。