数据结构：线性结构、堆栈和队列

（数据结构与算法总是联系在一起）

－数据结构简介

eg：图书摆放 新书的插入与旧书的查取（随便放：新书插入方便、但查取书困难？按书名首字母放、二分法查找：但怎么将新书插入？先将书分为几类、在不同类别中按首字母排放书籍）所以：解决问题的效率与数据的组织方式直接相关。

递归？输入十万用递归函数或循环函数一次打印1～10万，循环函数打印成功而递归函数未打印任何数就跳出了程序，因为递归更吃内存。所以：解决问题方法的效率还跟空间利用率有关。

（C语言中函数 clock（）用于计时，计算程序所用时长；解决问题的效率跟算法的简便程度有关；线形结构、树形结构、图结构）

抽象数据类型

数据类型：数据对象集，数据集合相关联的操作集（面向对象语言中 这两个集分开处理对应不同的类，C语言中一起处理）；抽象：描述数据类型的方法不依赖于具体实现，与存放数据的机器无关，与数据存储的物理结构无关，与实现操作的算法和编程语言均无关。只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

－算法简介

一个有限指令集 接收一定输入（有时不需要输入）产生输出 有限步骤后终止，每一条指令必须有明确的目标、在计算机处理的范围之内、描述不依赖于任何一种计算机语言以及具体的实现手段

评价一个算法的好坏有两点：空间复杂度S(n)：占用存储单元的长度；时间复杂度T(n)：耗费时间的长度，时间与空间都与n有关。

分析一般算法的效率时关注的两种复杂度：最坏情况复杂度和平均复杂度；一般考虑随着n的增大，复杂度增大的趋势即可判断两种算法的复杂度比较

复杂度的渐进表示法：T(n) = O( f(n) ) 表示存在常熟C>0,n0>0使得当n>=n0时有T(n)<=C*f(n) 上界 下界。。。

复杂度分析：for循环的时间复杂度等于循环次数乘以循环体复杂度，if－else结构的复杂度取决于if条件判断复杂度和两个分支部分的复杂度 总体复杂度取三者中最大值

－线性结构

是最基础最简单的数据类型，多项式表示有以下三种方式：

顺序存储结构表示直接表示：

利用数组下标表示x的指数，对应的value表示系数；缺点：若有很多零项会导致内存的极大浪费

顺序存储结构表示非零项：

可以将每个项看成：用结构数组表示、按指数大小有序存储

链表结构存储非零项：

链表中每个节点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域

同一个问题可以有不同的表示（存储）方法，有序线性序列的组织和管理。

线性表：由同类型数据元素构成有序序列的线性结构，表中元素个数称为线性表的长度，线性表没有元素时称为空表，表起始位置称表头、表结束位置称表尾。

基本操作：初始化一个空线性表 根据位序返回相应元素在线性表中查找x第一次出现的位置，在位序i前插入一个新元素并删除指定位序的元素，返回线性表的长度。

数组（value和下标）／链表（value和指针），对于插入删除来说，链表相对方便，

广义表：是线性表的推广，对于线性表而言 n个元素都是基本的单元素，广义表中这些元素不仅可以是单元素也可以是另一个广义表。

多重链表：多重列表中节点的指针域会有多个，但包含两个指针域的链表并不一定是多重链表，比如双向链表不是多重链表；树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

典型的多重链表：十字链表

－堆栈

（前缀、中缀、后缀表达式；从左向右扫描 逐个处理运算数和运算符号）

堆栈具有一定操作约束的线性表，只在一端（栈顶，Top）做插入、删除；插入数据：入栈（Push）删除数据：出栈（Pop）后入先出（Last In First Out，LIFO）

堆栈的抽象数据类型描述：类型名称：堆栈，数据对象集：一个有0个或多个元素的有穷线性表，操作集：长度为MaxSize的堆栈，堆栈元素item

1.生成空堆栈，其最大长度为MaxSize 2.判断堆栈S是否已满 3.将元素item压入堆栈 4.判断堆栈S是否为空 5.删除并返回栈顶元素

Push和Pop可以穿插交替进行

－队列

具有一定操作约束的线性表，插入和删除操作只能在一端插入，而在另一端删除，先进先出

判断队列是否已满，判断队列是否为空