《数据结构》实验指导：线性表的顺序与链式存储

"山东大学《数据结构》实验指导02线性表.docx" 实验二线性表涉及的是数据结构中的核心概念——线性表。线性表是一个包含n（n>=0）个数据元素的集合，这些元素之间具有逻辑上的线性关系，即每个元素都有一个前驱元素和一个后继元素，除了第一个元素没有前驱，最后一个元素没有后继。在数据结构领域，线性表的抽象数据类型（ADT）定义了它的基本操作和数据对象。 线性表的ADT定义如下： - 数据对象D由元素集合{aj|aj∈elemSet, i=1,2,...,n}组成，其中n表示元素的个数。 - 数据关系Ri定义了元素之间的线性关系，即对于所有aj-1和aj，如果它们都属于D，那么aj-1在aj之前。 线性表的基本操作包括： 1. CreatList(&L)：创建一个空的线性表L。 2. ListLength(L)：返回线性表L中元素的个数。 3. ListInsert(&L,i,e)：在L的第i个位置插入元素e，线性表长度增加1。 4. ListDelete(&L,i,&e)：删除L的第i个元素，用e返回其值，线性表长度减少1。 5. GetElem(L,i,&e)：获取线性表L中第i个元素的值并存入e。 6. LocateElem(L,e,compare())：返回L中第一个与e满足特定比较条件的元素的索引，若不存在则返回0。 7. ListEmpty(L)：检查L是否为空，若为空则返回TRUE，否则返回FALSE。 8. ClearList(&L)：将线性表L清空。 9. DestroyList(&L)：销毁线性表L。 线性表有两种常见的存储方式：顺序存储和链式存储。 - 顺序存储：顺序表是最简单的数据结构，它使用一段连续的内存空间存储线性表的所有元素。这种存储方式的优点是访问速度快，因为内存的连续性使得随机访问变得简单。但插入和删除操作可能涉及大量的元素移动，效率较低。 - 链式存储：链式表不依赖于元素在内存中的物理位置，而是通过指针链接元素。每个元素（节点）包含数据部分和指向下一个元素的指针。链式存储提供了更大的灵活性，插入和删除操作通常更快，但访问速度相对较慢，因为需要遍历指针。 实验的目标是让学生理解和掌握这两种表示方法，以及如何用C语言实现它们。通过完成实验，学生将能够熟练地进行线性表的操作，包括创建、查询、插入、删除等，同时理解这两种存储结构的优缺点。这有助于他们深入理解数据结构的基础，为后续更复杂的算法和数据结构的学习打下坚实基础。