顺序表Sequential List)用顺序存储方式实现线性表把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中。顺序表的特点随机访问即可以在O(i)时间内找到第i个元素。存储密度高每个节点只存放数据元素容量拓展不方便插入删除元素不方便#声明一个顺序表静态分配实现#defineMaxSize10typedefstruct{ElemType data[MaxSize];//用静态的“数组”存放数据元素intlength;//顺序表长度}SqList;分配的存储空间是静态的不可变的#声明一个顺序表动态分配实现#defineInitSize10//顺序表的初始长度typedefstruct{ElemType*data;//指示动态分配数组的指针intMaxSize;//顺序表的最大容量intlenth;//顺序表的当前长度}SeqList;//顺序表的定义//c语言实现 malloc,freeL.data(ElemType*)malloc(sizeof(ElemType)*InitSize);//malloc函数返回一个指针要用强制类型转换转换为你定义的数据元素类型指针//C---new,delete关键字#初始化一个顺序表初始化静态分配的顺序表voidInitList(SqListL){for(inti0;iMaxSize;i)L.data[i]0;//设置默认值L.length0;}初始化动态分配的顺序表voidInitList(SeqListL){L.data(ElemType*)malloc(InitSize*sizeof(ElemType));L.length0;L.MaxSizeInitSize;#增加动态数组的长度voidIncreaseSize(SeqListL,intlen){int*pL.data;L.data(ElemType*)malloc((L.MaxSizelen)*sizeof(int));for(inti0;iL;i){L.data[i]p[i];//将数据复制到新区域}L.MaxSizeL.MaxSizelen;//顺序表最大长度增加lenfree(p)//释放原来的内存空间//相当于重新开辟了一段内存而不是在原有的空间上增加}如果静态分配不设置初始值呢会存在脏数据程序变得不可控一些编译器会初始化但不是所有编译器都会初始化#插入操作在表L中的第i个位置上插入指定元素e。voidListInsert(SqListL,inti,inte)//在位序i处插入元素e{if(i1||iL.length1)returnfalse;//判断输入值是否合法if(L.lengthMaxSize)returnfalse;//当存储空间已满不能再插入for(intjL.length;ji;j--){L.data[j]L.data[j-1];//将第i个元素之后的元素后移}L.data[i-1]e;//在i处放入eL.length;}最好情况新元素插入到表尾不需要移动元素- i n1循环0次最好时间复杂度 O(1)最坏情况新元素插入到表头需要将原有的 n 个元素全都向后移动i 1循环 n 次最坏时间复杂度 O(n);平均情况假设新元素插入到任何一个位置的概率相同即 i 1,2,3,…,length1 的概率都是p1n1p\dfrac{1}{n1}pn11​i1循环 n 次i2 时循环 n-1 次i3循环 n-2 次 …… i n1时循环0次平均循环次数np(n−1)p(n−2)p⋯1⋅pn(n1)2⋅1n1n2np (n-1)p (n-2)p \dots 1\cdot p\dfrac{n(n1)}{2}\cdot\dfrac{1}{n1}\dfrac{n}{2}np(n−1)p(n−2)p⋯1⋅p2n(n1)​⋅n11​2n​平均时间复杂度O(n)#删除操作boolListDelete(SqListL,inti,inte){//删除第i个元素并用e把删除的元素“带回来”if(i1||iL.length)//判断i的范围是否有效returnfalse;eL.data[i-1];//将被删除的元素赋值给efor(intji;jL.length;j)//将第i个位置后的元素前移L.data[j-1]L.data[j];L.length--;returntrue;}//调用实例if(ListDelete(L,3,e)){print(已经删除第三个元素删除元素为%d\n,e);elseprint(位序i不合法,删除失败\n);return0;}最好情况删除表尾元素不需要移动其他元素i n循环 0 次最好时间复杂度 O(1)最坏情况删除表头元素需要将后续的 n-1 个元素全都向前移动i 1循环 n-1 次最坏时间复杂度 O(n);平均情况假设删除任何一个元素的概率相同即 i 1,2,3,…,length 的概率都是p1np\dfrac{1}{n}pn1​i1循环 n-1 次i2 时循环 n-2 次i3循环 n-3 次 …… in 时循环0次平均循环次数(n−1)p(n−2)p⋯1⋅pn(n−1)2⋅1nn−12 ⟹ (n-1)p (n-2)p \dots 1\cdot p\dfrac{n(n-1)}{2}\cdot\dfrac{1}{n}\dfrac{n-1}{2} \implies(n−1)p(n−2)p⋯1⋅p2n(n−1)​⋅n1​2n−1​⟹平均时间复杂度 O(n)#按位查找ElemTypeGetElem(SqList L,inti){returnL.data[i-1];}#按值查找intLocateElem(SqList L,ElemType e){for(inti0;iL.length;i)if(L.data[i]e)returni1;return0;}最好情况目标元素在表头循环1次最好时间复杂度 O(1)最坏情况目标元素在表尾循环 n 次最坏时间复杂度 O(n);平均情况假设目标元素出现在任何一个位置的概率相同都是1n\dfrac{1}{n}n1​目标元素在第1位循环1次在第2位循环2次……在第 n 位循环 n 次平均循环次数1⋅1n2⋅1n3⋅1n⋯n⋅1nn(n1)2⋅1nn121\cdot\dfrac{1}{n}2\cdot\dfrac{1}{n}3\cdot\dfrac{1}{n}\dotsn\cdot\dfrac{1}{n}\dfrac{n(n1)}{2}\cdot\dfrac{1}{n}\dfrac{n1}{2}1⋅n1​2⋅n1​3⋅n1​⋯n⋅n1​2n(n1)​⋅n1​2n1​