数据结构笔记1

来自《Python数据结构学习笔记》（张清云 编著）

第一章 数据结构基础

1.逻辑结构

• 集合：结构中的数据元素除了同属于一种类型外，别无其他关系
• 线性结构：数据元素之间一对一的关系
• 树形结构：数据元素之间一对多的关系
• 图状结构或网状结构：结构中的数据元素之间存在多对多的关系

2.物理结构

• 顺序存储结构
• 链接存储结构
• 数据索引存储结构
• 数据散列存储结构（Hash存储）

3.常用数据结构

• 数组(Array)
• 栈(Stack)
• 队列(Queue)
• 链表(Linked List)
• 树(Tree)
• 图(Graph)
• 堆(Heap)
• 散列表(Hash)

第二章 算法

1.算法的五个重要特征：

• 有穷性
• 确切性
• 输入
• 输出
• 可行性

2.算法是程序的灵魂

数据结构+算法=程序

程序=算法+数据结构+程序设计方法+语言环境

3.表示算法的方法

• 流程图
• N-S流程图
• 计算机语言

4.时间复杂度和空间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n的平方)<O(n3)<O(2的n次方)<O(n!)<O(n的n次方)

内置模块库timeit，用来检测和比较python代码运行时间。

class timeit.Timer(stmt='pass',setup='pass',timer=<timer function>)

• Timer：测量小段代码执行速度的类
• stmt：要测试的代码语句（statment）
• setup：运行代码时需要的设置
• timer：定时器函数，与平台有关

第三章 Python内置的几种数据结构

1.列表

2.元组

3.字典

第四章 线性表

1.线性表

两个基本特征：

• 集合中必存在唯一的“第一元素”和唯一的“最后元素”。
• 除最后元素之外，均有唯一的后继；除第一元素之外，均有唯一的前驱。

结构特点：

• 均匀性：同一线性表的各数据元素必须有相同的类型和长度。
• 有序性：各元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前驱，后面只有一个直接后继。

基本操作：

2.顺序表

以数组形式保存。

主要操作功能：

• 计算顺序表的长度
• 清空操作
• 判断线性表是否为空
• 判断顺序表是否为满
• 附加操作
• 插入操作
• 删除操作
• 获取单元
• 按值查找

3.链表

通过“链”建立起数据元素之间的次序关系。主要有单链表、循环链表、双向链表、双向循环链表。