群组
Flutter,iOS,Android,Python等,闲聊工作&技术&问题;
个人主页:https://waitwalker.cn
telegram群链接:https://t.me/joinchat/Ej0o0A1ntlq5ZFIMzzO5Pw
表的简单定义:
我们将处理一般的形如A1,A2,A3,…An的表,称这个表的大小是N.我们称大小为0的表为空表.表是一种线性的数据结构集合.对于除空表外的任何表,我们称Ai+1是Ai的后继,Ai-1是Ai的前驱.
表常见的操作:
Find返回关键字首次出现的位置例程,Delete删除某个关键字例程,Insert在某个位置插入例程,遍历等
表的实现方式:
1.数组
对于表的所有操作都可以通过数组来实现,数组实现表有一定的局限性,数组的大小事先要指定;数组的插入和删除操作会对插入和删除以后的所有元素都要调整,这种时间复杂度最坏为O(n).但是数组的查找和遍历是线性时间复杂度,而查找某个位置上的元素时间复杂度仅为常数时间,这些可以算作数组的优势.
因为插入和删除的运行时间以及表的大小还要事先已知,因此对于插入和删除操作比较多的情况,一般不用数组来实现表结构.
2.链表
链表由一系列不必在内存中相连的结构组成.每一个结构均含有表元素和指向包含该元素后继元的结构的指针,即next指针.最后一个结构的next指针指向NULL.遍历和查找某个元素链表的时间复杂度为线性时间,我们只要将一个指针传递到该表的第一个元素,然后用一些next指针穿越该表即可.而查找某个位置上的元素其优势不如数组效率高.
删除操作可以将待删除结构前驱的next指针指向待删除结构的后继即可.插入操作需要先实例化创建一个结构,然后获取插入位置的结构的前驱,将其next指针指向新创建的结构,然后新创建的结构next指针指向插入位置结构后继.
3.链表结构类型
链表分为单链表,双链表,循环链表,块链表等.
双链表比单链表多了一个previous指针,指向前驱.
循环链表是将首尾连接起来,这种方式在单向和双向链表中皆可实现.要转换一个循环链表,你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点.再来看另一种方法,循环链表可以被视为“无头无尾”.
块状链表本身是一个链表,但是链表储存的并不是一般的数据,而是由这些数据组成的顺序表.每一个块状链表的节点,也就是顺序表,可以被叫做一个块.
[图片上传失败…(image-e79610-1554800955920)])
链表的构造
/// 节点元素的值
var value:T
/// 节点元素的next指针
var next:NodeList?
/// 链表节点元素的构造函数
///
/// - Parameter val: 值
init(val:T) {
self.value = val
}
链表的遍历
遍历链表用next指针穿越整个表,创建一个临时节点,把当前节点赋值给临时节点.如果当前节点不为nil,将当前节点的next赋值给临时节点.
/// 遍历链表
///
/// - Parameter nodeList: 链表
/// - Returns: 链表长度
func traverse(with nodeList:NodeList?) -> Int {
var nodeListLength:Int = 0
var tmpNode = nodeList
while tmpNode != nil {
nodeListLength += 1
tmpNode = tmpNode!.next
}
return nodeListLength
}
根据给定索引查找对应节点的值
查找例程还是基于遍历思想,用next指针穿越.如果当前节点不为空,比较当前索引与指定索引事都相等,相等返回当前节点的值;不相等则递增当前索引并且将当前节点的后继赋值给当前节点,直到当前索引与指定索引相等.
/// 根据指定索引查找某个链表节点的值
///
/// - Parameters:
/// - nodeList: 链表
/// - index: 要查询的节点
/// - Returns: 某个索引节点的值
func find(with nodeList:NodeList?, index:Int) -> T? {
var tmpNode = nodeList
var currentIndex:Int = 0
while tmpNode != nil {
if currentIndex == index {
return tmpNode?.value
}
currentIndex += 1
tmpNode = tmpNode?.next
}
return nil
}
根据指定值查找某个链表节点的索引
/// 根据指定值查找某个链表节点的索引
///
/// - Parameters:
/// - nodeList: 链表
/// - value: 值
/// - Returns: 值对应节点的索引
func find(with nodeList:NodeList?, value:T?) -> Int? {
var tmpNode = nodeList
var currentIndex:Int = 0
while tmpNode != nil {
if tmpNode?.value == value {
return currentIndex
}
currentIndex += 1
tmpNode = tmpNode?.next
}
return nil
}
在指定位置插入新的节点
先判断当前链表是否存在,然后获取插入位置的前一个节点previousN,把previousN的后继赋值给插入节点的next指针;把插入节点赋值给previousN的next指针;
/// 在链表指定位置插入新的节点并返回新的链表
///
/// - Parameters:
/// - nodeList: 链表
/// - node: 待插入节点
/// - index: 插入位置
/// - Returns: 新的链表
func insert(with nodeList:NodeList?, node:NodeList, index:Int) -> NodeList? {
guard let nodeL = nodeList else { return node }
if traverse(with: nodeL) <= index {
return node
}
var previousN:NodeList?
if index != 0 {
previousN = nodeL.find(with: nodeL, at: index - 1)
node.next = previousN!.next
previousN!.next = node
return nodeL
} else {
node.next = nodeL
return node
}
}
删除操作
删除指定位置的节点先要找到当前节点currentN和当前节点的前驱previousN,然后把previousN的next指针指向currentN的后继.
/// 删除指定位置的节点并返回新的列表
///
/// - Parameters:
/// - nodeList: 链表
/// - index: 待删除的位置
/// - Returns: 删除后的链表
func delete(with nodeList:NodeList?, index:Int) -> NodeList? {
guard let nodeL = nodeList else { return nil }
if nodeL.traverse(with: nodeL) <= index {
return nodeL
}
if index == 0 {
return nodeL.next
}
let previousN = nodeL.find(with: nodeL, at: index - 1)
let currentN = nodeL.find(with: nodeL, at: index)
previousN?.next = currentN?.next
return nodeL
}
源码地址
这里的实现代码已放到GitHub,测试用例详见DataStructureAlgorithmTests.swift文件
参考文献
《数据结构与算法分析C语言描述》(Data Structures and Algorithm Analysis in C:Second Edition)–译者: 冯舜玺
