定义
零个或者多个数据元素的有限序列；
顺序储存结构
指的是用一段地址连续的储存单元依次存储线性表的数据元素；
- 线性表的长度：是线性表中数据元素的个数，随着表的插入和删除操作的进行，这个量是变化的；
- 数据的长度：是存放线性表的存储空间长度，存储分配后这个量是一般不变的；
- 存储器中的每一个存储单元都有自己的编号，这个编号称为地址；
获得元素
enum Status{
case Error
case OK
}
func getElem(list:Array<Any>, i:Int, e:Any) -> Status{
if list.count == 0 || i < 1 || i > list.count {
return .Error
}
e = list[i - 1]
return.OK
}
插入操作
func listInsert(L:SqList, i:Int, e:Any) -> Status{
var j : Int
if L.length == MAXSIZE {
return .Error
}
if i < 1 || i > L.length + 1 {
return .Error
}
if i <= L.length {
for j in (i-1 ... L.length-1).reversed() {
L.data[j + 1] = L.data[j]
}
}
L.data[i - 1] = e
L.length += 1
return .OK
}
删除
func delet(L:SqList, i:Int) -> Status{
if L.length == 0 {
return .Error
}
if i < 1 || i > L.length + 1 {
return .Error
}
if i <= L.length {
for j in (i ... L.length) {
L.data[j-1] = L.data[j]
}
}
L.length -= 1;
return .OK;
}
顺序存储结构的优缺点
-
优点：
1、 无须为表中元素之间的逻辑关系而增加额外的存储空间；
2、可以快速的存取表中任一位置的元素 -
缺点
1、 插入和删除元素操作需要移动大量元素；
2、 当线性表的长度变化比较大时，难以确定存储空间的容量；
3、 造成存储空间的碎片；
链式存储结构
- 我们把存储数据元素信息的域为数据与，把存储直接后继位置的域称为指针域；
- 指针域中存储的信息称作指针或者链；
- 指针域和数据域组成数据元素的存储映像，称为结点；
- 链表中每一个结点中只包含一个指针域，称为单链表；
- 链表中，第一个节点的存储位置称为头指针；
- 在单链表的第一个结点前附设一个结点，称为头结点；
| 头指针 | 头结点 |
|---|---|
| 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针 | 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度。） |
| 头指针具有标识作用，所以常用头指针冠以链表的名字 | 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作就统一了 |
| 无论链表是否为空，头指针均不为空。头指针是链表的必要元素 | 头结点不一定是链表必须要素 |
单链表的插入和删除 （算法复杂度 O(n)）
对于插入或者删除数据越频繁的操作，单链表的效率优势就越明显；
插入
假设有结点 p， p 的下一个结点为 p->next, 需要将结点s插入到结点p之后；
算法思路： 将p的指向下个结点的指针地址更改为结点s的地址， 将结点s指向下个结点的指针地址更改为p->next的地址即可；
删除
假设有连续的三个结点 p,q,r；现要删除q;
算法思路：将p的存储指针更改为r的指针地址；将q释放；
单链表的整表创建
单链表的创建过程就是一个动态生成链表的过程，即从“空表”的初始状态起依次建立各元素结点，并逐个插入链表；
- 头插法：始终让新结点在第一位置；
- 尾插法：每次把新结点都插在终端结点的后面；
单链表的整表删除
算法思路
1、 声明结点p,q;
2、 将第一个结点赋值给p；
3、 循环
* 将下一结点赋值给q；
* 释放p；
* 将q赋值给p；
单链表结构和顺序存储结构优缺点
1、 存储分配方式
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素；
2、时间性能
- 查找
. 顺序存储结构O(1);
. 单链表O(n); - 插入和删除
. 顺序存储结构需要平均移动表长一半的元素 时间为O(n);
. 单链表在线出某位置的指针后，插入和删除的时间为O(1);
3、 空间性能
- 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢；
- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制；
4、 总结
- 若线性表需要频繁的查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁的插入个删除的时，宜采用单链表结构。
- 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样不需要考虑存储空间大小的问题。而如果事先知道线性表的大致长度，顺序存储效率较高；
网友评论