《数据结构》回顾

数据结构

数据结构：线性表，栈，队列
操作：排序，查找

数据结构对应分析	desp
逻辑结构	线性结构、树、图、集合
存储结构	顺序存储、链式存储、索引存储、哈希存储（直接存储）

评判标准

• 内存存储空间的利用率
• 访问数据的便捷性（随机访问，顺序访问）

线性表

唯一前驱，唯一后继

链式存储

基本分类

• 单链表
• 双链表
• 循环单链表（带尾指针）
• 循环双链表

操作

• 头插法，尾插法
• 双指针操作

单链表环路

快（两步走）慢（一步走）两指针，当存在环路时，必存在两指针相遇情况

变量	简要说明
a	链表起点至环路起点的距离
x	环路位置至相遇点位置的距离
r	环路长度
l	慢指针移动步数
g	相遇点至环路起点位置

2*L - L = n*r  (n为任意常数）
  L= n*r
  L= a+x

  a+x=n*r ==> a=n*r - x = （n-1）r + g

由于a = （n-1）r + g故可知: 从相遇点与起点同时相同速度出发的指针会相遇于环路起点