宿州网站建设网站,网站备案在哪个网,贵州网站推广公司,无锡百度seo优化归纳编程学习的感悟#xff0c; 记录奋斗路上的点滴#xff0c; 希望能帮到一样刻苦的你#xff01; 如有不足欢迎指正#xff01; 共同学习交流#xff01; #x1f30e;欢迎各位→点赞 #x1f44d; 收藏⭐ 留言#x1f4dd; 看到美好#xff0c;感受美好 记录奋斗路上的点滴 希望能帮到一样刻苦的你 如有不足欢迎指正 共同学习交流 欢迎各位→点赞 收藏⭐ 留言 看到美好感受美好屏蔽阴霾
一起加油 目录 一、顺序表 二、顺序表基本运算的实现
顺序表的初始化
插入运算
☘️顺序表的数据元素的插入算法
删除运算
☘️顺序表的数据元素的删除算法
按值查找 :
☘️顺序表的数据元素查找算法:
三、顺序表的其他运算举例
例1
☘️顺序表的划分算法 例2
☘️顺序表的合并算法 例3
☘️两个顺序表的比较算法
四、总结
五、共勉 一、顺序表 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表中的各数据元素用这种存储形式存储的线性表称为顺序表。因为内存中的地址空间是线性的所以用物理位置关系上的相邻性实现数据元素之间的逻辑相邻关系既简单又自然。线性表的顺序存储示意图如图 A所示设 a 的存储地址为 Loc(a)每个数据元素占 d 个存储单元则第 i个数据元素的地址为: Loc(a)Loc(a)(i-1)*d 1in 图A 线性表的顺序存储示意图 这就是说只要知道顺序表首地址和每个数据元素所占存储单元的个数就可求出第 i 个数据元素的地址这也是顺序表具有按数据元素的序号随机存取的特点。 在程序设计语言中一维数组在内存中占用的存储空间就是一组连续的存储区域因此用一维数组来表示顺序表的数据存储区域是再合适不过的了。考虑到线性表有插入、删除等运算即表长是可变的因此数组的容量要设计得足够大,设用 data[MAXSIZE]来表示其中 MAXSIZE是一个根据实际问题定义的足够大的整数线性表中的数据元素从 data[0]开始依次顺序存放但当前线性表中的实际数据元素个数可能未达到 MAXSIZE 个因此需用变量 last 记录当前线性表中最后一个数据元素在数组中的位置即 last 具有指针的作用始终指向线性表中最后一个数据元素因此表空时 last -1。这种存储思想的具体描述可以是多样的如可以是: datatype data[MAXSIZE];int last; 这样表示的顺序表如图 A 所示表长为 last1数据元素分别存放在 data[0]到 data[last]中这样使用简单方便但有时不便于管理。 从结构性上考虑通常将 data 和 last 封装成一个结构作为顺序表的数据类型: typedef struct{datatype data[MAXSIZE];int last;
}SeqList; 定义一个顺序表: SeqList L 这样表示的线性表如图(a) 所示。表长 L.last1线性表中的数据元素 a1至 an分别存放在 L.data[0]至 L.data[L.last]中.其实有时定义一个指向 SeqList 类型的指针更为方便: SeqList *L L是一个指针变量线性表的存储空间通过 Lmalloc(sizeof(SeqList)运算来获得。L 中存放的是顺序表的地址这样表示的线性表如图 (b) 所示。表长表示为(*L).last1 或 L-last1线性表的存储区域为 L-data线性表中数据元素的存储空间为: L-data[0] ~ L-data[L-last] 二、顺序表基本运算的实现 根据以上线性表顺序存储结构定义确定了其存储方式之后就可以讨论其基本运算的实现方法(即实现算法)了同时还要对算法进行初步的分析。
顺序表的初始化 顺序表的初始化即构造一个空表这对顺序表是一个加工型的运算因此将L设为指针参数,首先动态分配存储空间然后将表中 last 指针置为-1表示顺序表中没有数据元素。算法如下: SeqList *init_SeqList(){ SeqList *L;Lmalloc(sizeof(SeqList));L-last-1;return L;
} 设调用函数为主函数主函数对初始化函数的调用如下: main(){SeqList *L;Linit_SeqList();……
} 插入运算 线性表的插入是指在表的第 i个位置上插入一个值为x 的新数据元素插入后使原表长为 n的线性表 (ai, a2,…,ai-1,ai, ai1,…,an) 成为表长为n1 的线性表 (a1,a2,…,ai-1,x,ai, ai1,…,an)。i的取值范围为1in1。 在顺序表上完成插入运算通过以下步骤进行: ✨将 ai~an顺序向后移动为新数据元素让出位置; ✨将x置入空出的第i个位置; ✨修改 last 指针 (相当于修改表长)使之仍指向最后一个数据元素。 图B所示为顺序表中的插入运算示意图。 图B 顺序表中的插入运算示意图 ☘️顺序表的数据元素的插入算法 int Insert_SeqList(SeqList *L,int i,datatype x){int j;if(L-lastMAXSIZE-1){printf(表满);return -1;//表空间已满不能插入 }if(iL-last2||i1){//检查插入位置的正确性 printf(位置错);return 0; } for(jL-last;ji-1;j--){L-data[j1]L-data[j];//节点移动 } L-data[i-1]x;//新数据元素插入 L-last;//last指针仍指向最后一个数据元素 return 1;
} 在本算法中应注意以下问题: ⚡顺序表中数据区域有 MAXSIZE 个存储单元所以向顺序表中插入新数据元素时应先检查表空间是否满了在表满的情况下不能再进行插入运算否则会产生溢出错误。⚡要检验插入位置的有效性这里i的有效范围是 1in1其中 n 为原表长。⚡注意数据的移动方向。 插入算法的时间复杂度分析:顺序表的插入运算时间主要消耗在数据的移动上在第i个位置上插入X从ai到an都要向后移动一个位置共需要移动n-i1个数据元素而i的取值范围为1in1即有n 1个位置可以插入。设在第i个位置上进行插入运算的概率为 pi则平均移动数据元素的次数为: 假设在第i个位置进行插入运算的可能性为等概率情况即pi1/(n1),则 这说明在顺序表上进行插入运算需平均移动表中一半的数据元素。显然其时间复杂度为O(n). 删除运算 线性表的删除运算是指将表中第i个数据元素从线性表中去掉删除后使原表长为 n的线性表 (a1,a2,…,ai-1,ai,ai1,…,an)成为表长为n-1的线性表 (a1,a2,…,ai-1,ai1,…,an)i的取值范围为1in。 在顺序表上完成删除运算的步骤如下: ✨将ai1~an顺序向前移动; ✨修改 last 指针(相当于修改表长)使之仍指向最后一个数据元素。 图C所示为顺序表中的删除运算示意图。 图C 顺序表中的删除运算示意图 ☘️顺序表的数据元素的删除算法 int Delete_SeqList(SeqList *L,int i){int j;if(i1||iL-last1){printf(不存在第i个数据元素);return 0;//检查空表及删除位置的合法性 }for(ji;jL-List;j){L-data[i-1]L-data[i];//向上移动 }L-last--;return 1;//删除成功
} 本算法注意以下问题: ⚡删除第i个数据元素i的取值为1in否则第个数据元素不存在因此要检查删除位置的有效性。 ⚡当表空时不能进行删除运算因表空时 L-last 的值为-1条件(1 L-last1)也包括了对表空的检查。 ⚡删除a之后该数据已不存在如果需要先取出 a再进行删除。 删除算法的时间复杂度分析: 与插入运算相同删除运算的时间主要消耗在移动表中数据元素上删除第i个数据元素时其后面的数据元素 ai1~an都要向前移动一个位置共移动了n-i 个数据元素所以平均移动数据元素的次数为: 同样在删除位置等概率情况下pi1/n则 这说明在顺序表上做删除运算时大约平均需要移动表中一半的数据元素。显然该算法的时间复杂度为 O(n)。 按值查找 : 线性表中的按值查找是指在线性表中查找与给定值 x 相等的数据元素。在顺序表中完成该运算最简单的方法是:从第一个数据元素 a 起依次和x进行比较直到找到一个与x相等的数据元素则返回它在顺序表中的存储下标或序号(二者差一);或者查遍整个表都没有找到与x相等的数据元素返回-1。 ☘️顺序表的数据元素查找算法: int Location_SeqList(SeqList *L,datatype x){int i0;while(iL.lastL-data[i]!x){i;}if(iL-last){return -1; }else return i;//返回的是存储位置
} 本算法的主要运算是比较显然比较的次数与 x 在表中的位置有关也与表长有关。当 a1x时比较一次成功。当 anx 时比较n 次成功。其平均比较次数为(n1)/2时间复杂度为 O(n)。 三、顺序表的其他运算举例
例1 将顺序表 (a1, a2,…,an)重新排列为以a1为界的两部分: a1前面的值均比 a1 小,a1后面的值均比 a1大(这里假设数据元素的类型具有可比性不妨设为整型)运算前后如图D 所示。这一运算称为划分a1称为基准。 划分的方法有多种下面介绍的划分算法思路简单但性能较差。 基本思路:从第二个数据元素开始到最后一个数据元素逐一向后扫描。 ✨当前数据元素 ai比 a1大时表明它已经在 a1的后面不必改变它与 a1之间的位置继续比较下一个。 ✨若当前数据元素比 a1小说明它应该在 a1的前面此时将它前面的数据元素依次向后移动一个位置然后将它置于最前面。 ☘️顺序表的划分算法 void partition(SeqList *L){int i,j;datatype x,y;xL-data[0];//将基准置于x中 for(i1;iL-last;i){if(L-data[i]x){//当前数据元素小于基准 yL-data[i];for(ji-1;j0;j--){//移动 L-data[j1]L-data[j];}L-data[0]y;}}
} 例2 设有顺序表 A 和 B其数据元素均按从小到大的顺序排列将它们合并成一个顺序表 C要求C的数据元素也从小到大排列。 算法思路:依次扫描 A和B 的数据元素比较 A、B 当前数据元素的值将值较小的数据元素赋给 C如此直到一个线性表扫描完毕最后将未扫描完顺序表中的余下部分赋给 C 即可。C的容量要能够容纳 A、B两个线性表长度的和。 ☘️顺序表的合并算法 void merge(SeqList A,SeqList B,SeqList *C){int i,j,k;ijk0;while(iA.lastjB.last){if(A.data[i]B.data[i]){C-data[k]A.data[i];}else{C-data[k]B.data[j];}}while(iA.last){C-data[k]A.data[i];}while(jB.last){C-data[k]B.data[j];}C-lastk-1;
} 上述算法的时间复杂度是 O(mn)其中m是A的表长n是 B 的表长。 例3 两个线性表的比较运算。假定两个线性表的比较方法如下:设A、B 是两个线性表表长分别为 m和n。A和 B分别为 A 和B 中除去最大共同前缀后的子表。例如A (x,y,y,z,x,z)B (x,y,y,z,y,x,x,z)两表最大共同前缀为 (x,y,y,z)。则A(x,z)B (y,x,x,z)。若AB空表则AB。若A空表且B!空表或两者均不为空表且A的首数据元素小于 B’的首数据元素则AB;否则AB。 算法思路: 首先找出A、B 的最大共同前缀然后求出 A和 B再按比较规则进行比较AB函数返回1;AB 返回0:AB 返回-1。 ☘️两个顺序表的比较算法 int compare(int A[],int B[],int m,int n){int i0,j,AS[],BS[],ms0,ns0;//AS,BS作为AB while(A[i]B[i]){//找出最大共同前缀 i;}for(ji;jm;j){//求A,ms为A的长度 AS[j-i]A[j];ms;}for(ji;jn;j){//求B,ns为B的长度 BS[j-i]B[j];ns;}if(msnsms0){return 0;}else if(ms0ns0||ms0ns0AS[0]BS[0]){return -1;}else{return 1;}
} 上述算法的时间复杂度是 O(mn)。 四、总结 学会顺序标的初始化熟练掌握顺序表各种算法了基本结构。
五、共勉 以上就是我对线性表——(2)线性表的顺序存储及其运算的实现的理解希望本篇文章对你有所帮助也希望可以支持支持博主后续博主也会定期更新学习记录记录学习过程中的点点滴滴。如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对线性表的理解请持续关注我哦
