低价网站建设优化公司,找客户在公司做网站,搜索引擎优化的流程,天津建设发展集团有限公司文章目录一、线性表的定义和基本操作线性表顺序表1.插入操作2.删除操作3.按值查找#xff08;顺序查找#xff09;二、单链表1. 头插法2. 尾插法3. 按序号查找4. 按值查找5. 插入结点6. 删除结点7. 求表长三、 双链表1. 插入2. 删除四、循环链表五、静态链表六、顺序表和链表…
文章目录一、线性表的定义和基本操作线性表顺序表1.插入操作2.删除操作3.按值查找顺序查找二、单链表1. 头插法2. 尾插法3. 按序号查找4. 按值查找5. 插入结点6. 删除结点7. 求表长三、 双链表1. 插入2. 删除四、循环链表五、静态链表六、顺序表和链表的比较七、特殊矩阵的压缩储存数组的定义数组的存储结构矩阵的压缩存储1. 对称矩阵2. 三角矩阵3. 三对称矩阵带状矩阵4. 稀疏矩阵八、广义表广义表的定义广义表的操作一、线性表的定义和基本操作
线性表
线性表是具有相同数据类型的n个数据元素的有限序列其中n为表长n0是为一个空表。除第一个元素外每一个元素有且仅有一个直接前驱除最后一个元素外每一个元素有且仅有一个直接后驱。
顺序表
线性表的顺序存储称为顺序表是用一组地址连续的存储单元一次存储线性表中的数据结构从而使得逻辑上相邻的两个元素在物理位置上也相邻。 线性表的位序是从1开始的而数组元素的下标从0开始。
1.插入操作
最好情况表尾插入时间复杂度O(1) 最坏情况表头插入时间复杂度O(n) 平均情况n/2 平均时间复杂度O(n)
2.删除操作
最好情况删除表尾元素时间复杂度O(1) 最坏情况删除表头元素时间复杂度O(n) 平均情况(n-1)/2 平均时间复杂度O(n)
顺序表插入和删除的时间主要耗费在移动元素上而移动元素的个数取决于插入删除元素的位置。
3.按值查找顺序查找
最好情况查找的元素在表头时间复杂度O(1) 最坏情况查找的元素在表尾或不存在时间复杂度O(n) 平均情况(n1)/2 平均时间复杂度O(n)
二、单链表
线性表的链式存储又称单链表指通过一组任意的存储单元来存储线性表中的数据元素。对每个链表结点除存放元素自身信息外还需要存放一个指向其后继节点的指针。 利用单链表可以解决顺序表需要大量连续存储单元的缺点但单链表附加指针域存在浪费空间的缺点。由于单链表的元素离散地分布在存储空间中所以单链表是非随机存取的存储结构。
如果要访问某个结点的前去前驱结点只能从头开始遍历。
头节点在单链表的第一个结点前附加一个结点。头结点可以不设任何信息也可以记录表长等信息。引入头结点可以带来两个优点
链表的第一个位置的操作可以和其他位置相统一。无论链表是否为空其头指针都指向头结点因此空表和非空表的操作得到统一。
1. 头插法
将新结点插入当前链表的表头即头结点之后。 读入数据的顺序和生成链表中的元素顺序是相反的总时间复杂度为O(n)
2. 尾插法
增加一个尾指针使其始终指向当前链表的尾结点。可使导入数据和链表元素的顺序一致总时间复杂度为O(n)。
3. 按序号查找
时间复杂度O(n)
4. 按值查找
时间复杂度O(n)
5. 插入结点
插入结点的代码片段如下
p getElem(L, i-1); // 移动到插入位置前一个结点
s-next p-next;
p-next s;算法时间开销主要在于查找第i-1个元素时间复杂度为O(n)如果在给定结点后插入时间复杂度仅为O(1)。
6. 删除结点
代码片段如下
p getElem(L, i-1);
q p-next;
p-next q-next;
free(q);
// 第二、三步顺序不能颠倒该算法的时间复杂度也耗费找查找操作上时间复杂度为O(n)。
7. 求表长
时间复杂度O(n)
三、 双链表
双链表结点有两个指针分别指向其前驱结点和后继结点。
1. 插入
在p所指结点之后插入*s
s-next p-next;
p-next-prior s;
s-prior p;
p-next s;
/// 第一、二步必须在第四步之前2. 删除
在p后删除q
p-next q-next;
q-next-prior p;
free(q);四、循环链表
将单链表最后一个结点的指针改为指向头结点形成循环单链表。判空条件是头结点的指针是否指向自身。
循环单链表可以从表中任意一个结点开始遍历整个链表。 有时单链表常用操作是在表头和表尾进行的此时不设头指针而仅设尾指针。
五、静态链表
借助数组来描述线性表的链式结构结点也有数据域和指针域。与链表的指针不同静态链表的指针是结点的相对地址数组下标又称游标。 静态链表需要预先分配一块连续的内存空间。
六、顺序表和链表的比较
——————顺序表链表存取读写方式既可以顺序存取也可以随机存取只能从表头顺序存取元素逻辑结构与物理结构逻辑上相邻的元素对应的物理存储位置也相邻逻辑上相邻的元素物理存储位置不一定相邻其对应的逻辑关系通过指针链接来表示按值查找顺序表有序时可采用折半查找时间复杂度为O(log2n)O(log_2n)O(log2n)若无序时间复杂度为O(n)时间复杂度为O(n)按序号查找顺序表支持随机访问时间复杂度仅为O(1)时间复杂度为O(n)插入、删除平均需要移动半个表长的元素只需修改相关结点的指针域空间分配在静态存储分配情形一旦存储空间装满就不能扩充加入新元素会导致内存溢出因此需要预先分配足够大的空间。但预先分配过大会导致后部空间大量闲置动态存储分配虽然存储空间可以扩充但需要移动大量元素导致操作效率降低若内存没有更大块的连续存储空间则会导致分配失败。链式存储的结点空间只需在需要是申请只要内存有空间就可以分配操作灵活、高效。
如何选取存储结构
基于存储考虑难以估计线性表的长度或存储规模时不宜采用顺序表链表实现不用估计存储规模但链表的存储密度较低。基于运算考虑如经常做的运算时按序号访问元素则顺序表优于链表如经常进行插入、删除操作链表较优。基于环境考虑任何高级语言都有数组类型顺序表较容易实现链表的操作是基于指针的。
通常较稳定的线性表选择顺序存储而频繁进行插入、删除操作的线性表动态性强宜选择链式存储。
七、特殊矩阵的压缩储存
数组的定义
数组是由nn ≥\ge≥ 1个相同类型的数据元素构成的有序序列。 每个元素在线性关系中的序号称为该元素的下标下标的取值范围称为数组的维界。 数组是线性表的推广一维数组可视为一个线性表二维数组可视为其元素也是定长线性表的线性表。 数组一旦被定义。其维数和维界就不再改变因此除初始化和销毁外数组只有存取元素和修改元素的操作。
数组的存储结构
对于多维数组有按行优先和按列优先两种映射方法。
设二维数组Ah1×h2A_{h_1\times h_2}Ah1×h2的行下标和列下标范围分别为[l1,h1][l2,h2][l_1,h_1][l_2, h_2][l1,h1][l2,h2]。 其按行优先存储时LOC(ai,j)LOC(al1,l2)[(i−l1)×(h2−l21)(j−l2)]×LLOC(a_{i,j})LOC(a_{l_1,l_2})[(i-l_1)\times (h_2-l_2 1)(j-l_2)]\times LLOC(ai,j)LOC(al1,l2)[(i−l1)×(h2−l21)(j−l2)]×L其按列优先存储时,LOC(ai,j)LOC(al1,l2)[(j−l2)×(h1−l11)(i−l1)]×LLOC(a_{i,j})LOC(a_{l_1,l_2})[(j-l_2)\times (h_1-l_11)(i-l_1)]\times LLOC(ai,j)LOC(al1,l2)[(j−l2)×(h1−l11)(i−l1)]×L
矩阵的压缩存储
为多个值相同的元素只分配一个存储空间对零元素不分配存储空间目的是节省空间。
1. 对称矩阵
将对称矩阵A[1…n][1…n]存放在一维数组B[n(n1/2)]中只存放下三角部分的元素。
2. 三角矩阵
下三角矩阵中上三角区的所有元素均为同一常量其储存思想与对称矩阵类似不同之处在于储存完下三角区和主对角线上的元素后在储存上三角取的常量一次。
943 2019年选择第9题默认矩阵下标从0开始
3. 三对称矩阵带状矩阵
三对角线上的元素ai,ja_{i,j}ai,j在一维数组中的下标为k23(i-1)(j-i1)-12ij-1数组和元素下标均从0开始。
4. 稀疏矩阵
矩阵中非零元素个数远小于矩阵元素的矩阵。 通常将非零元素及其相应的行和列构成一个三元组然后按照一定规则储存这些三元组。 稀疏矩阵压缩存储后便失去了随机存储的特性。
八、广义表
c中union关键字详见
广义表的定义
广义表的操作
getHead()获得广义表的第一个元素 getTail()获得以广义表出第一个元素外的其余元素构成的广义表。
如A(a), B(b,c,d)C(()),那么 getHead(A)a, getHead(B)b, getHead(C)() getTail(B)(), getTail(B)(c,d), getTail(C)()
