数据结构与算法（一）
==前言：数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。==
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，我们把数据结构分为逻辑结构和物理结构。
逻辑结构：是指数据对象中数据元素之间的相互关系。
分为四种：集合结构、线性结构、树形结构、图形结构。
物理结构：是指数据的逻辑结构在计算机中的存储形式。
分为两种：顺序存储结构、链式存储结构
抽象数据类型：是指一个数据模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。
算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
具有五个基本特性：输入、输出、有穷性、确定性、可行性。
好的算法设计要求：正确性、可读性、健壮性、时间效率高和储存量低。
算法效率的度量方法：事后统计法(不科学、不准确)、事前分析估算法。
==大O阶方法==：1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
所得到的结果就是大O阶。
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n^2^+2n+1 | O(n^2^) | 平方阶 |
| 5log |
O(logn) | 对数阶 |
| 2n+3nlog |
O(nlogn) | nlogn阶 |
| 6n^3^+2n^2^+3n+4 | O(n^3^) | 立方阶 |
| 2^n^ | O(2^n^) | 指数阶 |
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)
线性表
定义：
零个或多个数据元素的有限序列。
其中数据元素的个数n定义为表的长度。
当n=0时称为空表
将非空的线性表记作：（a
1,…,ai-1,ai,ai+1,…an)==a
1为线性起点（起始节点），an为线性终点（终端节点）==
==ai-1是ai的直接前驱，ai+1是ai的直接后继，a1有且仅有一个直接后继，an有且只有一个直接前驱==
抽象表的数据类型：
线性表的顺序存储结构
顺序存储结构的插入与删除
线性表的链式存储结构
单链表的读取
单链表的插入与删除
单链表的整表创建
单链表的整表删除
单链表结构与顺序存储结构优缺点
静态链表
循环链表
双向链表
