2.1线性表的定义和基本操作2.1.1线性表的定义1.线性表是n个相同数据结构的元素所组成的有限序列n为表长。2.线性表的特点元素个数有限有明确先后次序每个元素的数据类型相同这意味着每个元素占据着相同大小的储存空间2.1.2线性表的基本操作1.简而言之增删查改初始化求表长输出判空销毁initList(L)length(L)printList(L)empty(L)destroyList(L)Listinsert(L,i,e)Listdelete(L,i,e)locateElem(L,e) 按值查找getElem(L,i)按位查找一般都像如上那样命名2.2线性表的顺序表示2.2.1顺序表的定义即线性表的顺序存储1.顺序表的静态分配//静态分配 #includestdio.h #define MAXSIZE 10 typedef struct{ int data[MAXSIZE]; int length; }sqlist; void initlist(sqlist L) { for(int i0;iMAXSIZE;i) L.data[i]0; L.length0; } int main() { sqlist L; initlist(L); for(int i0;iMAXSIZE;i) { printf(data[%d]%d\n,i,L.data[i]); } return 0; }运行结果2.顺序表的动态分配1扩容#includestdio.h #includestdlib.h #define initSize 10 //默认最大长度 typedef struct{ int *data; //只是动态数组的指针 int maxsize; //顺序表的最大容量 int length; //顺序表的当前长度 }seqList; void initList(seqList L){ //用malloc函数申请一遍连续的储存空间 L.data(int *)malloc(initSize*sizeof(int)); L.length0; L.maxsizeinitSize; } //增加动态数组长度 void increaseSize(seqList L,int len) { int *pL.data; L.data(int *)malloc((L.maxsizelen)*sizeof(int)); for(int i0;iL.length;i){ L.data[i]p[i]; } L.maxsizeL.maxsizelen; free(p); } int main() { seqList L; initList(L); increaseSize(L,5); for(int i0;i15;i){ L.data[i]i1; } for(int i0;i15;i) { printf(L.data[%d]%d\n,i,L.data[i]); } return 0; }运行结果2插入void Listinsert(seqList L,int i,int e){ for(int jL.length;ji;j--) { L.data[j]L.data[j-1]; } L.data[i-1]e; L.length; }想在第i个位置插入一个元素先把第i个元素及其后面的所有元素都往后移一位然后再将插入元素添加到第i个位置插入操作的时间复杂度:最好O1最坏On平均i1,循环n次in1,循环0次故平均循环次数np(n-1)*p(n-2)*p...1*p(1/(1n))*(n*(n1)/2)n/2,即O(n)3删除bool Listdelete(seqList L,int i,int e){ if(i1||iL.length) //判断i的范围是否有效 { return false; } eL.data[i-1]; //将被删除的元素赋值给e for(int ji;jlength;j)//将第i个位置后的元素前移 { L.data[j-1]L.data[j]; } L.length--; return true; }int main() { seqList L; initList(L); for(int i0;i10;i){ L.data[i]i1; } L.length10; int e0; if(Listdelete(L,3,e)) printf(已删除第三个元素删除元素是%d\n,e); else printf(位序不合法删除失败\n); return 0; return 0; }删除操作的时间复杂度:最好O10次最坏Onn-1次平均p1/n(n-1)*p(n-2)*p(n-3)*p...0*pn*(n-1)/2*p即O(n)4查找1.按位查找int getElem(seqList L,int i){ return L.data[i-1]; }int main() { seqList L; initList(L); for(int i0;i10;i){ L.data[i]i1; } L.length10; printf(%d,getElem(L,3)); return 0; }时间复杂度O12.按值查找int locateElem(seqList L,int e){ for(int i0;iL.length;i) if(L.data[i]e) return i1; return 0; }int main() { seqList L; initList(L); for(int i0;i10;i){ L.data[i]i1; } L.length10; printf(%d,locateElem(L,3)); return 0; }时间复杂度最好O1最坏On平均p1/n1*p2*p3*p...n*pn,j即On 
长河君 · 2026/10/11 8:40:31 · 阅读 1.2k 数据结构|第二章 线性表
2.1线性表的定义和基本操作2.1.1线性表的定义1.线性表是n个相同数据结构的元素所组成的有限序列n为表长。2.线性表的特点元素个数有限有明确先后次序每个元素的数据类型相同这意味着每个元素占据着相同大小的储存空间2.1.2线性表的基本操作1.简而言之增删查改初始化求表长输出判空销毁initList(L)length(L)printList(L)empty(L)destroyList(L)Listinsert(L,i,e)Listdelete(L,i,e)locateElem(L,e) 按值查找getElem(L,i)按位查找一般都像如上那样命名2.2线性表的顺序表示2.2.1顺序表的定义即线性表的顺序存储1.顺序表的静态分配//静态分配 #includestdio.h #define MAXSIZE 10 typedef struct{ int data[MAXSIZE]; int length; }sqlist; void initlist(sqlist L) { for(int i0;iMAXSIZE;i) L.data[i]0; L.length0; } int main() { sqlist L; initlist(L); for(int i0;iMAXSIZE;i) { printf(data[%d]%d\n,i,L.data[i]); } return 0; }运行结果2.顺序表的动态分配1扩容#includestdio.h #includestdlib.h #define initSize 10 //默认最大长度 typedef struct{ int *data; //只是动态数组的指针 int maxsize; //顺序表的最大容量 int length; //顺序表的当前长度 }seqList; void initList(seqList L){ //用malloc函数申请一遍连续的储存空间 L.data(int *)malloc(initSize*sizeof(int)); L.length0; L.maxsizeinitSize; } //增加动态数组长度 void increaseSize(seqList L,int len) { int *pL.data; L.data(int *)malloc((L.maxsizelen)*sizeof(int)); for(int i0;iL.length;i){ L.data[i]p[i]; } L.maxsizeL.maxsizelen; free(p); } int main() { seqList L; initList(L); increaseSize(L,5); for(int i0;i15;i){ L.data[i]i1; } for(int i0;i15;i) { printf(L.data[%d]%d\n,i,L.data[i]); } return 0; }运行结果2插入void Listinsert(seqList L,int i,int e){ for(int jL.length;ji;j--) { L.data[j]L.data[j-1]; } L.data[i-1]e; L.length; }想在第i个位置插入一个元素先把第i个元素及其后面的所有元素都往后移一位然后再将插入元素添加到第i个位置插入操作的时间复杂度:最好O1最坏On平均i1,循环n次in1,循环0次故平均循环次数np(n-1)*p(n-2)*p...1*p(1/(1n))*(n*(n1)/2)n/2,即O(n)3删除bool Listdelete(seqList L,int i,int e){ if(i1||iL.length) //判断i的范围是否有效 { return false; } eL.data[i-1]; //将被删除的元素赋值给e for(int ji;jlength;j)//将第i个位置后的元素前移 { L.data[j-1]L.data[j]; } L.length--; return true; }int main() { seqList L; initList(L); for(int i0;i10;i){ L.data[i]i1; } L.length10; int e0; if(Listdelete(L,3,e)) printf(已删除第三个元素删除元素是%d\n,e); else printf(位序不合法删除失败\n); return 0; return 0; }删除操作的时间复杂度:最好O10次最坏Onn-1次平均p1/n(n-1)*p(n-2)*p(n-3)*p...0*pn*(n-1)/2*p即O(n)4查找1.按位查找int getElem(seqList L,int i){ return L.data[i-1]; }int main() { seqList L; initList(L); for(int i0;i10;i){ L.data[i]i1; } L.length10; printf(%d,getElem(L,3)); return 0; }时间复杂度O12.按值查找int locateElem(seqList L,int e){ for(int i0;iL.length;i) if(L.data[i]e) return i1; return 0; }int main() { seqList L; initList(L); for(int i0;i10;i){ L.data[i]i1; } L.length10; printf(%d,locateElem(L,3)); return 0; }时间复杂度最好O1最坏On平均p1/n1*p2*p3*p...n*pn,j即On