线性表线性表是由n(n0)个数据元素结点a1,a2,…,an组成的有限序列其中数据元素的个数n定义为表的长度当n0时成为空表若线性表的名字为L则非空的线性表n0记作L a1,a2,…,an同一个线性表的数据元素类型一般要求相同称为同构线性表的相邻元素之间存在着前后顺序关系其中第一个元素无前驱最后一个元素无后继其余每个元素有且仅有一个直接前驱和直接后继所以线性表是一种线性结构对线性表的基本操作常见的有以下几种初始化求表长读表元定位插入删除我们在这里只讨论这6种基本操作的实现其他的一些操作可以通过这6种操作来进行组合实现线性表顺序实现在《数据结构》这篇博客中我们讲解物理结构的两种实现方式有顺序存储和链式存储我们先对顺序存储进行讲解因为顺序存储的时候数据在计算机中的物理关系和逻辑关系一致这像我们在学习C语言时候使用到的数组所以这里我们可以使用数组来存储线性表中的内容当然我们还需要一个变量用来存放数组中存放的线性表的长度这样会便于我们进行操作这里需要对数组的长度和线性表的长度进行区分数组的长度是我们之前分配好的一段空间大小不变当然可以通过编程手段来实现动态分配数组但是这样会带俩性能上的损耗所以我们提前分配好的数组长度一般是不会变化的线性表的长度是指线性表中存储的内容的多少我们对线性表进行增删改查的操作后线性表的长度肯定会发生改变所以线性表的长度一定是可变的这里需要对这两个概念进行区分我们先通过C语言来初始化一个线性表# define MAXSIZE 20 //给线性表的存储空间的初始分配量 typedef int ElemType; //ElemType就是线性表中的元素的类型这里设置为int typedef struct { ElemType data[MAXSIZE]; //数组data它的存储位置就是线性表的存储位置 int length; //线性表当前的长度 }SqList;我们可以看到顺序存储的线性表的三个属性数组data数组长度MAXSIZE线性表当前的长度length在线性表的顺序存储中因为使用到了数组来进行线性表的存储我们可以快速计算出数组中每个元素的地址假设线性表中的每个元素的内存大小为c我们可以快速计算出每个元素在计算机中的地址一步到位按照我们之前讲解的时间复杂度概念来讲存取时间性能为O(1)顺序表获得元素的操作# define OK 1 # define ERROR 0 # define TRUE 1 # define FALSE 0 typedef int Status; Status GetElem(SqList L, int i, ElemType *e){ if(L.length 0 || i 1 || i L.length){ return ERROR; } *e L.data[i - 1]; return OK; }这个方法的参数我们传入的是一个结构体变量也就是顺序表本身考虑到顺序表内容较大按值传递比较费时所以在时间应用中我们通常传递的是顺序表的指针顺序表插入操作我们要考虑几点插入位置不合理抛出异常线性表长度大于数组长度抛出异常插入要将插入点以后直到线性表末尾的所有元素都向后移动一个位置将元素插入表长1实现代码Status ListInsert(SqList *L, int i, ElemType e){ int k; if(L-length MAXSIZE){ return ERROR; } if(i length 1 || i 1){ return ERROR; } if(i length){ for(k L-length-1; k i - 1; k--){ L-data[k 1] L-data[k]; } } L-data[i - 1] e; L-length; return OK; }线性表删除元素的操作删除元素时我们需要考虑如果删除位置不合理抛出异常取出删除元素从删除位置直到线性表末尾的所有元素全部向前移动一个位置表长-1代码实现Status ListDelete(SqList *L, int i, ElemType *e){ int k; if(L-length0){ return ERROR; } if(i 1 || i L-length){ return ERROR; } *e L-data[i-1]; if(i L-length){ for(k i; k L-length; k){ L-data[k-1] L-data[k]; } } L-length--; return OK; }以上就是对线性表的顺序实现的讲解其他操作可以由基本操作组合实现
