浮雕模东莞网站建设,小x导航正品,网站关键字在哪里设置,佛山新网站建设机构该系列属于计算机基础系列中的《数据结构基础》子系列#xff0c;参考书《数据结构考研复习指导》(王道论坛 组编)#xff0c;完整内容请阅读原书。 2.线性表的顺序表示
2.1 顺序表的定义 线性表的顺序存储亦称为顺序表#xff0c;是用一组地址连续的存储单元依次存储线性表…该系列属于计算机基础系列中的《数据结构基础》子系列参考书《数据结构考研复习指导》(王道论坛 组编)完整内容请阅读原书。 2.线性表的顺序表示
2.1 顺序表的定义 线性表的顺序存储亦称为顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素使得逻辑上相邻的两个元素在物理位置上也相邻 第111个元素存储在线性表的起始位置第iii个元素的存储位置后面紧接存储的是第i1i1i1个元素称iii为元素aia_iai在线性表中的位序 顺序表的特点表中元素的逻辑顺序与其物理顺序相同 假设线性表LLL存储的起始位置为LOC(A)sizeof(ElemType){\rm LOC(A)sizeof(ElemType)}LOC(A)sizeof(ElemType)是每个数据元素所占用存储空间的大小则表LLL对应的顺序存储如下图所示 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数 线性表中的任一数据元素都可以随机存取线性表的顺序存储结构是一种随机存取的存储结构 高级语言中通常用数组描述线性表的顺序存储结构且数组中元素的下标从000开始线性表中元素的位序是从111开始 假定线性表的元素类型为ElemType{\rm ElemType}ElemType则线性表的顺序存储类型描述为 #define MaxSize 50 // 定义线性表最大长度
typedef struct{ElemType data [MaxSize]; // 顺序表的元素int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义一维数组可以是静态分配的亦可是动态分配的 静态分配由于数组的大小和空间事先固定一旦空间占满再加入新的数据会产生溢出进而导致程序崩溃 动态分配存储数组的空间是在程序执行过程中通过动态存储分配语句分配的一旦数据空间占满会令开辟一块更大的存储空间代替原来的存储空间达到扩充存储数组空间的目的 动态分配描述线性表 #define InitSize 100 // 表长度的初始定义
typedef struct{ ElemType *data; // 指示动态分配数组的指针int MaxSize,length; // 数组的最大容量和当前个数
}SeqList; // 动态分配数组顺序表的类型定义// C语言的初始动态分配语句
L.data(ElemType*)malloc(sizeof(ElemType)*InitSize);// C初始动态分配语句
L.datanew ElemType(InitSize);顺序表主要特点随机访问即通过首地址和元素序号可在时间O(1)O(1)O(1)内找到指定的元素 顺序表的存储密度高每个结点只存储数据元素 顺序表逻辑上相邻的元素物理上也相邻故插入和删除操作需要移动大量元素
2.2 顺序表上基本操作实现
2.2.1 顺序表插入操作 在顺序表L{\rm L}L的第i(1iL.length1){\rm i(1iL.length1})i(1iL.length1)个位置插入新元素e{\rm e}e 插入原理若i{\rm i}i的输入不合法则返回false{\rm false}false表示插入失败否则将第i{\rm i}i个元素及其后的所有元素依次往后移动一个位置腾出一个空位置插入新元素e{\rm e}e顺序表长度增加111插入成功返回true{\rm true}true 插入操作核心代码 bool ListInsert(SqList L,int i,ElemType e){// 判断i的范围是否有效if(i1||iL.length1)return false;// 当前存储空间已满不能插入if(L.lengthMaxSize)return false;// 将第i个元素及之后的元素后移for(int jL.length;ji;j--)L.data[j]L.data[j-1];L.data[i-1]e; // 在位置i处插入eL.length; // 线性表长度加1return true;
}顺序表插入操作时间复杂度分析 最好情况在表尾插入即in1{ in1}in1元素后移语句不执行时间复杂度为O(1)O(1)O(1) 最坏情况在表头插入即i1{i1}i1元素后移语句将执行nnn次时间复杂度为O(n)O(n)O(n) 平均情况假设pi(pi1/(n1))p_i(p_i1/(n1))pi(pi1/(n1))是在第iii个位置上插入一个结点的概率则在长度为nnn的线性表中插入一个结点所需移动结点的平均次数为 ∑i1n1pi(n−i1)∑i1n11n1(n−i1)1n1∑i1n1(n−i1)1n1n(n1)2n2\sum_{i1}^{n1}p_i(n-i1)\sum_{i1}^{n1}\frac{1}{n1}(n-i1)\frac{1}{n1}\sum_{i1}^{n1}(n-i1)\frac{1}{n1}\frac{n(n1)}{2}\frac{n}{2} i1∑n1pi(n−i1)i1∑n1n11(n−i1)n11i1∑n1(n−i1)n112n(n1)2n 故线性表插入算法的平均时间复杂度为O(n)O(n)O(n)
2.2.2 顺序表删除操作 删除顺序表L{\rm L}L中第i(1iL.length){\rm i(1iL.length)}i(1iL.length)个位置的元素用引用变量e{\rm e}e返回 顺序表删除操作原理若i{\rm i}i的输入不合法则返回false{\rm false}false否则将被删除元素赋给引用变量e{\rm e}e并将第i1{\rm i1}i1个元素及其后的所有元素依次往前移动一个位置返回true{\rm true}true。 删除操作核心代码 bool ListDelete(SqList L,int i,Elemtype e){// 判断i的范围是否有效if(i1||iL.length)return false;// 将被删除的元素赋值给eeL.data[i-1];// 将第i个位置后的元素前移for(int ji;jL.length;j)L.data[j-1]L.data[j];// 线性表长度减1L.length--;return true;
}顺序表删除操作时间复杂度分析 最好情况删除表尾元素即ininin则无须移动元素时间复杂度为O(1)O(1)O(1) 最坏情况删除表头元素即i1i1i1则需要移动除表头元素外的所有元素时间复杂度为O(n)O(n)O(n) 平均情况假设pi(pi1/n)p_i(p_i1/n)pi(pi1/n)是删除第iii个位置上结点的概率则在长度为nnn的线性表中删除一个结点时所需移动结点的平均次数为 ∑i1npi(n−i)∑i1n1n(n−i)1n∑i1n(n−i)1nn(n−1)2n−12\sum_{i1}^np_i(n-i)\sum_{i1}^n\frac{1}{n}(n-i)\frac{1}{n}\sum_{i1}^n(n-i)\frac{1}{n}\frac{n(n-1)}{2}\frac{n-1}{2} i1∑npi(n−i)i1∑nn1(n−i)n1i1∑n(n−i)n12n(n−1)2n−1 故线性表删除算法的平均时间复杂度为O(n)O(n)O(n)
2.2.3 顺序表插入和删除操作图解 顺序表插入和删除操作的时间主要耗费在移动元素上移动元素的个数取决于插入和删除元素的位置 顺序表的插入和删除操作图解如下所示
2.2.4 顺序表按值查找 在顺序表L{\rm L}L中查找第一个元素值等于e{\rm e}e的元素并返回位序 按值查找操作核心代码 int LocateElem(SqList L,ElemType e){int i;for(i0;iL.length;i)if(L.data[i]e)return i1; // 下标为i的元素值等于e其位序为i1return 0;
}按值查找操作时间复杂度分析 最好情况查找的元素在表头仅需比较一次时间复杂度为O(1)O(1)O(1) 最坏情况查找的元素在表尾或不存在需要比较nnn次时间复杂度为O(n)O(n)O(n) 平均情况假设pi(pi1/n)p_i(p_i1/n)pi(pi1/n)是查找的元素在第i(1iL.length){\rm i(1iL.length)}i(1iL.length)个位置上的概率则在长度为nnn的线性表中查找值为e{\rm e}e的元素所需比较的平均次数为 ∑i1npi×i∑i1n1n×i1nn(n1)2n12\sum_{i1}^{n}p_i\times{i}\sum_{i1}^n\frac{1}{n}\times{i}\frac{1}{n}\frac{n(n1)}{2}\frac{n1}{2} i1∑npi×ii1∑nn1×in12n(n1)2n1 故线性表按值查找操作的平均时间复杂度为O(n)O(n)O(n)
