线性表的基本操作及在顺序存储及链式存储的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了线性表的基本操作及在顺序存储及链式存储的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

线性表的基本操作：

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过其基本操作来实现。线性表的主要操作如下

    - InitList(&L):初始化表。构造一个空的线性表
    - Length（L）：求表长 。 返回线性表L的长度，即L中数据元素的个数
    - LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值e的元素
    - GetElem（L，i）：按位查找操作。操作表L中第i个位置的元素的值
    - ListInsert（&L，i，e）：插入操作。在表中的第i个位置的元素的值
    - LIstDelete（&L，i，&e）：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
    - PrintList（L）：输出操作。按前后顺序输出线性表L的所有元素值
    - Empty（L）：判空操作。若L为空表，则返回true，负责返回false
    - DestroyList（&L）：销毁操作。销毁线性表，并释放线性表L所占用的内存空间

注意：1：基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同
2：“&” 表示c++中的引用调用。若存入的变量是指针变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型。在c中采用指针的指针也可达到同样的效果

线性表的在顺序存储上的实现

线性表的顺序存储又称为顺序表。他是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理元素上也相邻。第1个元素存储在线性表的起始位置，第i个位置的存储位置后面紧接存储着的是i+1个元素，称 i 为元素的 αi 在线性表的位序。因此，顺序表的特点是表中元素的逻辑结构与其物理结构

 注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的

假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为

#define MaxSize 50 // 定义线性表的最大长度
typedef struct {
ElemType data[MaxSize]; // 顺序表的元素
int length ; // 顺序表的当前长度
}SqList；  // 顺序表的类型定义

以为数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，在加入新的数据将会产生溢出，进而导致程序崩溃

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间

注意：动态分配并不是链式存储，它同样属于存储结构，物理结构没有变化，依然是随机存储方式，只是分配的空间大小可以在运行时决定

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O（1）内找到指定的元素，
顺序表的存储密度高，每个节点值存储数据元素
顺序表逻辑上相邻的元素物理上也相邻，所以插入个删除操作需要移动大量元素文章来源地址https://www.toymoban.com/news/detail-638708.html

到了这里，关于线性表的基本操作及在顺序存储及链式存储的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！