- day1
- 1.数据结构基础知识
- 1.1 什么是数据结构
- 数据结构就是数据的逻辑结构以及存储操作(数据的运算) 。数据结构没有想象的那么复杂，它就教会你一件事：如何更有效的存储数据
- 1.2 数据
- 数据：不再是单纯的数字了，而是类似于集合的概念。
- 数据元素：是数据的基本单位，由若干个数据项组成。
- 数据项：数据的最小单位，描述数据元素的有用信息。
- 数据元素又叫节点
- 例如：
- 数据：图书
- 数据元素：每一行也就是每本书
- 数据项：编号、书名、作者、出版社等
- 1.3 逻辑结构
- (1).线性关系
- 线性结构 ==> 一对一 ==>线性表：顺序表、链表、栈、队列
- (2).层次关系
- (3).网状关系
- 1.4 存储结构
- 数据的逻辑结构在计算机中的具体实现(数据的运算)
- 1.4.1 顺序存储
- 数组：连续存储
- 特点：内存连续、随机存取、每个元素占用空间较少
- 1.4.2 链式存储
- 通过指针实现
- 特点：内存不连续，通过指针实现，每个元素占用空间相对较大
- 1.4.3 索引存储
- 在存数据的同时，建立一个附加的索引表。 也就是索引存储 = 索引表 + 数据文件 可以提高查找速度，特点检索速度快，但是占用内存多，删除数据文件要及时更改索引表。
- 1.4.4 散列存储
- 数据存储按照和关键码之间的关系进行存取。关系由自己决定，比如关键码是key, 存储位置也就是关系是key+1。获取关键数据，通过元素的关键码方法的返回值来获取。 存的时候按关系存，取的时候按关系取。
- 1.5 操作
- 2.算法基础知识
- 2.1 什么是算法
- 算法就是解决问题的思想方法，数据结构是算法的基础。
- 数据结构 + 算法 = 程序
- 2.2 算法的设计
- 算法的设计： 取决于数据逻辑结构
- 算法的实现：依赖于数据的存储结构
- 2.3 算法的特点
- 有穷性：步骤是有限的
- 确定性：每一个步骤都有明确的含义，无二义性。
- 可行性：规定实现可以完成
- 输入
- 输出
- 2.4 评价算法好坏
- 正确性
- 易读性
- 健壮性：容错处理
- 高效性：执行效率，通过重复执行语句的次数来判断，也就是时间复杂度(通过时间处理函数)来判断。
- 2.5时间复杂度
- 语句频度：用时间规模函数表达
- 时间规模函数: T(n)=O(f(n))
- T(n) //时间规模的时间函数
- O //时间数量级
- n //问题规模，例如：a[100], n=100
- f(n) //算法可执行重复语句的次数
- 称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
- 渐进时间复杂度用大写O来表示，所以也被称为大O表示法。直白的讲，时间复杂度就是把时间规模函数T(n)简化为一个数量级，如n，n^2，n^3。
- 计算大O的方法：
- (1)根据问题规模n写出表达式f(n)
- (2)如果有常数项，将其置为1 //当f(n)的表达式中只有常数项的时候，例如f(n)=8 ==> O(1)
- (3)只保留最高项，其他项舍去。
- (4)如果最高项系数不为1，则除以最高项系数。//f(n) = 3*n^4 + 2*n^3 + 6*n^7 +10;==> O(n^7)
- 3.线性表
- 3.1什么是线性表
- 线性表是最基本、最简单、也是最常用的一种数据结构，可以存储逻辑关系为线性的数据。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
- 包含：顺序表(数组)、链表(单向链表、单向循环链表、双向链表、双向循环链表)、栈(顺序栈、链式栈)、队列(循环队列、链式队列)
- 逻辑结构：线性结构
- 存储结构：可以是顺序(数组)或链式存储(通过指针)
- 3.2顺序表
- 3.2.1概念
- 顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。
- 3.2.2特性
- 逻辑结构：线性结构
- 存储结构：顺序存储
- 特点：内存连续，可以用数组实现，大小固定
- 操作: 增删改查
- 3.2.3数组操作
- (1)普通操作
- (2)添加全局遍历last表示最后一个有效元素下标
- (3)顺序表编程实现
