1.1.1 基本概念
数据：数据是信息的载体，是描述客观事物属性的字、字符及所有能输入到计算机并且被计算机程序识别和处理的符号的集合。（数据是计算机程序加工的原料）
数据元素、数据项： 数据元素是数据的基本单位，一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。
数据对象： 是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构： 是互相之间存在的一种或多种特定关系的数据元素的集合。
总结：数据>数据对象>数据元素>数据项
多个数据项组成数据元素。
同样的数据元素可以组成不同的数据结构。不同的数据元素可以组成相同的数据结构。
比如：富豪排行榜可以有线性数据结构（财富顺序），也可以有网状数据结构（人际关系）
微博粉丝排行榜（粉丝数量） 微博好友关系（人际关系）
1.1.2 数据结构三要素
数据结构的三要素分为：
1.逻辑结构：（1）集合结构（2）线性结构（3）树形结构（4）图状结构。
2.数据的运算：
3.物理结构（存储结构）：
一、逻辑结构：
1.集合结构：各元素之间同属一个集合，无其他关系。
2.线性结构：数据元素之间是一对一的关系。（除第一个元素，所有元素都有唯一前驱，除最后一个元素，所有元素都有唯一后继。）
3.树形结构：数据元素之间是一对多的关系。
4.图状结构：数据元素之间是多对多的关系。（道路信息）
二、数据的运算： 针对于某种逻辑结构，结合实际需求，定义基本运算。（增删改查）
三、数据的物理结构（存储结构）
1.顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
2.链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
3.索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项成为索引项（一般形式是 关键字、地址）。
4.散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
注：
1.若采用顺序存储，则各个数据元素在物理上是必须连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
2.数据的存储结构会影响存储空间分配的方便程度。（找一大片的连续空位肯定不如见缝插针）
3.数据的存储结构会影响对数据运算的速度。（顺序存储需要重新排对，链式插入修改指向）
运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
四、数据类型、抽象数据类型:
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
（1）原子类型（bool类型 int类型）：其值不可再分的数据类型。
（2）结构类型（struct结构体）：其值可以再分解为若干成分的数据类型。
抽象数据类型（Abstract Data Type ADT）是u抽象数据组织及与之相关的操作。
数据类型的使用者只需要知道一个数据结构的抽象数据类型的描述就可以了。
数据类型的实现者关注逻辑结构在计算机内部如何表示以及各种运算如何在计算机内部如何实现。
1.2.1 算法的基本概念
程序=数据结构+算法。
一、算法（如何高效的处理计算机中的数据，解决实际问题）： 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或者多个操作。
二、算法的特性
1.有穷性：一个算法必须总在执行又穷步后结束，其每一步都在有穷时间内完成。（死循环不是算法） 注：算法必须是又穷的，而程序可以是无穷的。
2.确定性：算法中每条指令都必须有确切的含义，对于相同的输入只能得出相同的输出。
3.可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4.输入：一个算法有零个或者多个输入，这些输入取自于某个特定的对象的集合。
5.输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
三、好的算法的特质
1.正确性：能够正确的解决求解问题。
2.可读性：觉具有良好的可读性，帮助他人理解。
3.健壮性：输入非法数据时，能够适当的做出反应或进行处理，不会产生莫名其妙的输出结果。（或者适当的舍弃非法数据）
4.高效率与地存储量需求：花的时间少，时间复杂度低。不费内存，空间复杂度低。
1.2.2算法的时间复杂度
一、如何评估算法时间开销
1.事后统计（有问题）
（1）与机器性能有关。（超级计算机与单片机）
（2）编程语言有关。（越高级的语言执行效率越低）
（3）和编译程序产生的机器指令质量有关
（4）有些算法是不能事后统计的。（导弹控制算法）
二、时间复杂度
1.事前预估算法时间开销T（n）与问题规模n的关系（T表示 time）
（1）根据语句判断。 当问题规模n足够大时，可以只考虑阶数高的部分。
（2）大O表示法：表示“同阶”，当n趋近与无穷时，两者之比为常数。
(3)加法规则与乘法规则
结论1： 顺序执行的代码只会影响常数项，可以忽略。
结论2：只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。
结论3：如果有多层嵌套循环，则只关注最深层循环循环了几次。
（4）最坏时间复杂度：最坏情况下算法的时间复杂度。
平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间。
最好时间复杂度：最好情况下算法的时间复杂度。（一般不考虑）
总结：
1.2.3算法的空间复杂度
一、空间复杂度【空间开销（内存开销）与问题规模n之间的关系】
1.程序运行时的内存需求=程序代码（固定大小）+数据
无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法的空间复杂度为：
S（n）=O(1) S表示“Space”
算法原地工作----算法所需的内存空间为常量
算法与时间复杂度相同。
递归算法的空间复杂度： nK（常数）B S(n)=O(n) 空间复杂度=递归调用的深度
总结：运算法则与空间复杂度相同。判断是应注意循环、嵌套、判断等等。
2.1 线性表的定义和基本操作
一、线性表的定义（逻辑结构）
1.线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。若用L命名线性表，一般表示为： L=（a1,a2,,,,ai,ai+1,,,,,an）
（1）ai是线性表中的“第i个”元素线性表中的位序。
（2）a1是表头元素；an是表尾元素。
（3）除第一个元素外，每个元素有且仅有一个直接前驱；除去最后一个元素外，每个元素有且仅有一个直接后继。
二、线性表的基本操作
1. 初始化 InitList(&L)、销毁 DestroyList(&L)、插入ListInsert(&L,i,e)、删除ListDelete(&L,i,&e)、按值查找LocateElem(L,e)、按位查找(GetElem(L,i))、求表长、输出、判空等等。
注： 传参的时候要区分实参和形参。
2.为什么要实现对数据结构的基本操作？
（1）团队合作编程，自己定义的数据结构要让别人能够更方便的使用。（封装）
（2）将常用的操作/运算封装成函数，避免重复工作，降低出错风险。
总结：
2.2.1顺序表的定义
一、顺序表的定义
1.设线性表第一个元素的存放位置是LOC（L）,则第n个元素的存放地址为：
LOC（L）+n*数据元素的大小。（int 4B）
二、静态分配
1.如果没用设置数据元素的默认值，则内存会遗留“脏数据”。
如果设置的数组长度不够就只能GG。
三三、动态分配。
例子：1. 首先创建一片连续的存储空间，初始化顺序表（10个int数据）malloc返回第一个数据元素的地址并将其赋给data(同类型)。然后增加数组长度（5个），将data的值赋给*p(指向同一个位置),malloc申请更大的存储空间，再用循环将之前顺序表的数据挪过来，然后更改最大容量，再次调用free函数，释放之前的空间。
四、顺序表的特点
1.随机访问，即可以在O（1）时间内找到第i个元素。
2.存储密度高，每个节点只存储数据元素
3.拓展容量不方便（即使采用动态分配的方法实现，拓展长度的时间复杂度也比较高）
3.插入、删除操作不方便，需要移动大量的数据。
总结：
2.2.2-1顺序表的插入与删除
一、顺序表的插入
ListInser(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
首先判断顺序表是否存满等其他情况。（增强代码健壮性）利用循环，将需要插入位置之后的元素依次向后移动一位，再将e插入第i个位置。
（注意位序与数组下标的差别，并且插入后，位序应+1）
时间复杂度：
最好情况：O(1) 插入表尾
最坏情况：O(n) 插入表头
平均情况：O(n/2)=O(n)
二、顺序表的删除
1. 定义与顺序表存储元素相同的变量e，判断i的范围是否有效，将删除的元素内容存储到变量e中，利用循环，将i位置之后的元素前移。（注意形参与实参的区别）
2.时间复杂度：
最好情况：O(1) 删除表尾元素
最坏情况：O(n) 删除表头元素
平均：O(n)
总结：
2.2.2-2顺序表的查找
一、按位查找
1.代码实现
GetElem(L,i):按位查找的操作，获取表L中第i个位置的元素值。
静态分布：
动态分布：
因为顺序存储的原因，所以顺序查找只需要一个循环就能搞定，时间复杂度为O（1）
二、按值查找
1.LocateElem(L,e):按值查找操作，在表L中查找具有给定关键字的值的元素。
如果定义结构体，则需要比较结构体的各个分量。
最好情况:目标元素在表头循环1次；最好时间复杂度=0(1)
最坏情况:目标元素在表尾循环n次；最坏时间复杂度=O(n);
平均时间复杂度 =0(n)。
总结:
2.3.1单链表的定义
一、单链表的定义
1.什么是单链表（链式存储）：每个结点除了存放数据元素外，还要存储指向下一个节点的指针。
用代码定义一个单链表：定义类型，定义一片区域存放数据元素，然后定义指针，使指针指向下一个节点。
初始化不带头结点的单链表：
带头结点的单链表：定义结点类型，存放数据元素，初始化带头结点，使头结点指针指向下一个节点（NULL）
区别：带头结点更方便使用。
总结：
2.3.2-1单链表的插入与删除
一、按位序插入（带头结点）
1.ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。（找到第i-1个结点，将新结点插入其后）
逻辑： 首先进行判断，如果位序<1,直接返回。 使用while循环找到第i-1个结点，使用malloc申请一个空地址，将元素e输入空地址，将s指针指向的位置与p结点指针指向的位置相同，再将p结点指针指向s。 时间复杂为O（1）。如果插入结点大于表的长度，则返回false。
二、按位序插入（不带头结点）
区别： 循环开始时，将头指针指向进行相关修改。
结论： 不带头结点写代码更不方便，推荐用带头结点。除非特别声明，代码默认带头结点。
三、指定结点的后插操作
1. 首先申请空地址，将元素e放入空地址，找到p结点，将空地址指向p+1的地址，再将p指针指向新插入的地址。时间复杂度为O（1）
四、指定结点的前插操作
1.首先申请一个空地址，将这个空地址作为p结点的后继节点，再将p结点的数据复制到空地址中，然后将元素e存入p结点中，再修改空地址的后继结点。 时间复杂度为O（1）
五、按位序删除（带头结点）
1.首先根据循环找到删除结点的前驱结点，也就是p指向i-1的结点，定义指针q,也就是需要删除的结点。将q的数据元素复制到参数e中（需要把q的值带回调用者）再将p指针修改，使其指向q指针的后继结点，再调用free释放q结点。 时间复杂度O(n) 最好为O(1)。
六、指定结点的删除
1.//删除指点结点p。找到p结点的后一个结点q，将q结点的数据复制到p中，再修改p结点指针，使其指向q结点的之后的位置。再释放q结点。 时间复杂度为O（1）。（如果要删除最后一个结点，则只能从表头依次寻找其前驱，时间复杂度为O（n））。
总结：
2.3.2-2单链表的查找
一、按位查找。（只讨论带头结点的情况）
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
首先判断i是否<0，通过循环，遍历整个表，找到了则返回其值。（平均时间复杂度为：O(n)）。
二、按值查找
LocateElem(L,e):按值查找。获取表L中具有给定关键字值的元素。
给定e值，使p指针指向头结点的下一个结点（第一个结点），使用while循环，若不相同，则使其指向下一个结点，依次循环，直到找到相同结点的值。 若没有则返回。 （时间复杂度为O（n））
三、求表的长度
使p指针依次向后移动，定义一个值，依次相加，再返回这个值。（时间复杂度为0（n））
总结：
2.3.2-3单链表的建立
一、单链表的建立
初始化一个单链表，
每次取一个数据元素，插入到表尾/表头。
1.尾插法：首先定义一个单链表，设置一个变量length记录链表的长度，利用循环，每次将一个数据元素e插入链表尾部，再使链表长度++。（记得修改第length-1的结点的指针指向）
因为每次插入后都应当从头遍历链表，因此时间复杂度O(n*2) 时间复杂度太长。
改良后：
建立链表，设置一个表尾指针r，每当表尾插入一个元素后，使r指向至这个元素。因此，再次插入新元素时，只需要创建一个新的空地址，是r指针指向至厄瓜空地址，再修改前一个元素，使其next指针再次指向空地址就OK啦。
2.头插法：（逆序，链表的逆置）
简单来说，是对头结点进行后插操作：
创建一个头结点，使其next指针指向NULL，创建一个空地址，将空地址的next指针指向NULL，再修改头结点的next指针，使其指向这个空地址。（以次类推）
总结：
2.3.3双链表
一、单链表VS双链表
1.单链表：无法逆向检索，有时候不方便。
2.双链表：可进可退，存储密度低一丢丢。
3.初始化一个双链表：
初始化一个带头链表，分配一个头结点，使头结点的next和prior指针都指向NULL。
判断双链表是否为空： 查看带头结点的next指针是否指向NULL。若next指针指向NULL则为空。
4.双链表的插入： （将p结点后插入s结点）
创建空地址，存入元素e，使s的next指针指向p结点的next指针，p结点的next指针的结点的prior指针指向s，再使s结点的prior指针指向p结点，然后将p结点的next指针指向s。
5.双链表的删除：（删除p的后继结点q）
将p结点的next指针指向q结点的next指针指向的位置，再使q结点的next指针指向的结点的prior指针指向p，最后释放q结点。
6.双链表的遍历：
利用循环，定义一个指针，只要其不指向NULL，就一直++，中间可加入其他操作。
总结： 时间复杂度都为 O（n）。
2.3.4循环链表
一、循环单链表
1.修改单链表的最后一个结点的指针，使其从指向NULL，指向头结点。
判断是否为空，只需判断头结点的指针是否指向自己，若指向自己则为空。
利用循环，可从任意一个结点出发，找到其他任何一个结点。
如果需经常在首尾元素插入或删除，可使用循环双链表。
2.循环双链表的初始化
使头结点的next和prior指针都指向他自己。
判断p是否为双链表的尾部，只需判断p的next指针是否指向头结点，若指向，则是尾部。
3.双链表的插入
4.双链表的删除：（删除p的后继结点q）
使p的next指针指向q的next指向的地方，使q的next指向的结点的prior指针指向p，释放q结点。
总结：
2.3.5 静态链表
一、什么是静态链表
1.分配一整片连续的内存空间，各个结点集中安置。不需要顺序存放，因为会存储下一个结点的数组下标（游标）。
假设每个元素为4B，每个游标为4B。每个结点共8B。设起始地址为addr则第n个元素存放的地址为 addr+n*8*2。
二、如何定义一个静态链表
首先定义最大长度，定义结构类型，（存储数据元素和下一个元素的游标）。定义数组a为静态链表。
三、基本操作的实现
初始化一个静态链表：直接将a[0]=-1。（等价于将头结点的指针指向NULL）。
查找:(位序) 从头结点出发，遍历整个结点。O（n）
插入位序为i的结点： 找到一个空结点，存入数据，遍历链表，找到i-1的结点，修改 新结点的next，然后修改i-1的结点的next。
总结：
静态链表：用数组的方式实现的链表。
优点：增、删、操作不需要大量移动元素。
缺点：不能随机存取，只能从头结点开始依次遍历。容量不可变。
2.3.6顺序表和链表的比较
一、逻辑结构：都属于线性表，都是线性结构。
二、存储结构
顺序表（顺序存储）优点：支持随机存取、存储密度高。
缺点：大片连续空间分配不方便，改变容量不方便。
链表（链式存储）优点：离散的小空间分配方便，改变容量方便。
缺点：不可随机存取，存储密度低
随机存取（Random Access）是指在存储系统中，无论数据位于存储介质的哪个位置，访问任何数据所需的时间都是恒定的，与数据的物理存储位置无关。这种存取方式的特点是高效和灵活，因为它允许直接跳转到数据的存储位置进行读写操作，而不需要按顺序逐个访问其他数据。
三、基本操作
1.初始化：
顺序表：预分配大片连续空间。若分配空间较小，不方便拓展容量，若分配空间较大，则浪费内存。
链表： 只需分配一个头结点，之后方便拓展。只需申请空间，再用指针链接。
2.创建：
顺序表：（静态分配：容量不可改变。）（动态分配：容量可改变，需要移动大量元素，时间代价高）
3.销毁：
顺序表： 修改length=0；（静态分配;系统自动回收）（动态分配：free）
链表：依次删除各个结点（free）
4.增删：
顺序表：插入删除都需要对后续元素进行移动。O(n)移动元素。
链表：插入删除只需修改指针就行。O(n)查找元素。
5.查找：
顺序表：按位查找O(1)。按值查找--若表内元素有序，可在O(log2*n)时间内找到。
链表：按位查找O(n) 按值查找O(n)
总结：
3.1.1栈的基本概念
一、栈的定义
1.栈（stack）是只允许在一端进行插入或删除操作的线性表。
重要术语： 栈顶、栈底、空栈。
特点：后进先出。（LIFO）
二、栈的基本操作
1.Initstack(&s):初始化栈。构造一个空栈S，分配内存空间。
DestroyStack(&L):销毁栈。销毁并释放栈s所占用的内存空间。
Push(&s,x):进栈，若栈S未满，则将x加入使之成为新栈顶。
pop(&S,&x):出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(s,&x):读栈顶元素。若栈s非空，则用x返回栈顶)元素。
2常考题型： n个不同元素进栈，出栈元素不同排列的个数为：1/（n+1）Cn;2n。
总结：
3.1.2栈的顺序存储实现
一、用顺序存储方式实现的栈。
1.（与顺序表相似）定义最大元素，使用静态数组存放栈中的元素。定义栈顶指针（记录数组下标，指向栈顶元素）。初始化，栈顶指针指向-1。
法2：栈顶指针与栈顶元素相对应。（则先放入元素 再++）
法2：栈顶指针与栈顶元素相对应。（则先放入元素 再++）
二、基本操作。
1.进栈操作：（判断栈是否是满的），栈顶指针+1，将元素放入其指向的位置。依次类推
2.出栈操作：（如果栈空，返回false）定义一个空地址，将栈顶元素赋给这个空地址用于保存，栈顶指针-1，即可。
3.读取栈顶元素： 与取出栈顶操作的区别是，定义一个空地址，用于保存出栈元素。并不会使指针--。
4.共享栈：两个栈共享一片空间，物理上，共享同一片存储空间。提高资源利用率。
（栈满的条件是： top0+1==top1）
总结：
3.2.1队列的基本概念
一、队列的定义。
1.队列（Queue）：只允许在一端进行插入（入队），在另一端进行删除（出队）的线性表。
特点： 先进入队列的元素先出队。（队头（允许删除的一段）、队尾（允许插入的一端）、空队列） 先进先出。
二、基本操作。
1.InitQueue(&Q):初始化队列，构造一个空队列Q。
DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间
EnQueue(&a& :入队，若队列Q未满，将x加入，使之成为新的队尾
DeQueue(&Q,&x):出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给x。
总结：
3.2.2队列的顺序实现
一、用顺序存储实现队列
1.定义最大个数，用静态数组存放队列元素，定义对头front指针和队尾rear指针（指向队尾元素的下一个位置）。初始化时，首先判断是否为空，再使对头、队尾指针都指向同一个位置。
二、基本操作。
1.入队： 判断是否队满，将x放入队尾指针之向的位置，队尾指针++。（依次类推）
2.循环队列 （利用取余法，在逻辑上将其变成“环状”存储）值为0-9，加1取余的结果也是0-9。
3.循环队列--出队操作。 （先判断队空），将出队元素值传给x，然后将对头指针向后移动。
查询的话只需删除队头指针后移的代码即可。
方案一：判断队列已满/已空 （使对头和队尾指针指向相同区域，但会浪费一个内存空间）
方案二：判断队列已满/已空 （定义一个新元素记录队列当前长度）
方案三：判断队列已满/已空 （定义一个元素记录上一次进行的是插入还是删除，若是插入，则满。删除，则空）
4.其他
总结： 
3.2.3队列的链式实现
一、用链式存储实现队列。
1.带头结点
定义头尾结点，进行初始化，定义front与rear都指向头结点，并使头结点的下一个结点执向null。
2.不带头结点
定义front与rear都指向null。
二、基本操作
1.插入操作：申请新结点，放入元素，（在尾部插入）使新插入的结点指向null，将使rear指针结点的next指向新结点，最后使rear指针指向新结点。
不带头结点：申请新结点，放入元素，使新结点的下一个指针指向null（后插操作，新插入的都为最后一个结点）判断是否为第一个元素，（判断front是否指向null）若是则使front和rear指向新结点。若不是，则使rear的下一个指针指向新结点，再使rear指向新结点。
2。出队操作（带头结点）： 首先判断是否为空队（在头部出队），申请一个新指针(p)指向被释放结点，在用空地址将被释放结点数据取出保存。修改头结点的next指针使其指向申请的新指针(p)的next指针，如果此时rear指针指向新指针（p）,则使rear指针指向front指向的位置，然后释放p指针指向的结点。
（不带头结点）： 首先判断是否为空队。然后取出删除结点的元素。修改front指针指向删除节点的next指向的位置，如果此时为最后一个节点，则使front与rear都指向null，释放节点空间。
3.队列满的条件： 一般不关心。。。。。。。
总结： （灵活添加）
3.2.4双端队列
一、允许从两端插入、删除的线性表。（操作受限）
1.输入受限：只允许从一边进入，两边都可以输出。
2.输出受限：只允许从一边输出，两边都可以输入。
考点：判断输出序列的合法性。（栈中合法的序列，双端队列中一定也合法）
总结：
3.3.1 栈在括号匹配中的应用
一、括号匹配问题（最后出现的左括号最先被匹配，每出现一个右括号就会消耗一个左括号）
二、算法演示
1.遇到左括号就入栈，遇到右括号就“消耗”一个左括号。（判断括号是否匹配，不匹配就失败。右括号存在，栈空，则也失败。若左括号有剩余，则也失败。）
2.算法实现
初始化栈，扫描到左括号，就入栈，扫描到右括号（先判断栈是否为空）就使栈顶元素出栈与之匹配，若成功，则继续，失败则返回。检索完所有括号后，若栈空，则匹配成功。
总结：
3.3.1 栈在括号匹配中的应用（下）
一、中缀表达式转后缀表达式（机算）
1.初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。（只将运算符压入栈的方法）
从左到右处理各个元素，直到末尾。可能遇到三种情况:
①遇到操作数。直接加入后缀表达式。
② 遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意:“(”不加入后缀表达式。
③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
处理完所有字符后，将栈中剩余运算符依次弹出，加入后缀表达式。
二、中缀表达式的计算（用栈实现）
1.用栈实现中缀表达式的计算:
初始化两个栈，操作数栈和运算符栈
1.若扫描到操作数，压人操作数栈
2.若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈)
总结： 多写多练
3.3.4队列的应用
一、函数调用的特点：最后被调用的函数最先执行结束。
1.函数调用时，需要用一个栈存储： 调用返回地址、实参、局部变量。（调用结束后逐个释放）
例1：每进入一层递归，九江递归调用所需信息压入栈顶。
每退出一层递归，就从栈顶弹出相关信息。 （缺点：太多层递归可能导致栈溢出）
例二：
总结：
3.4特殊矩阵的压缩存储
一、数组的存储结构
1.一维数组：各元素大小相同，且物理上连续存放。a[i]=起始地址+i*siezof(数组元素大小)
2.二维数组：b[j][j]=起始地址+（i*N+j）*sizeof(数组元素大小)
二、特殊矩阵
1.普通矩阵的存储：使用二维数组来存储。
2.对称矩阵的压缩存储：若n阶方阵中任意一个元素a ij都有 aij-aji。则该矩阵为对称矩阵。（主对角线： i=j）
压缩存储策略：只存储主对角线+下三角区。
按行优先：
3.三角矩阵的压缩存储： 除主对角线和下三角区（或上三角区），其余的元素都相同。
4.三对角矩阵的压缩存储： 当Ii-jI>1时，有a ij =0。（1<=i,j<=n）
5.稀疏矩阵的压缩：非零元素远远少于矩阵元素的个数。
法1：
法二： 
总结：
4.1.1串的定义和基本操作
一、串的定义
1.串：即字符串(String)是由零个或多个字符组成的有限序列。一般记为S='a¡a,……an'(n 20)
其中，S是串名，单引号括起来的字符序列是串的值:ai可以是字母、数字或其他字符:串中字符的个数n称为串的长度。n=0时的串称为空串。
字串：串中任意个连续的字符组成的子序列。
主串：包含字串的串。
字符在主串中的位置：字符在串中的序号。（空格也是字符）
字串在主串中的位置：字串的第一个字符在主串中的位置。
空串： M=‘’
空格串： N=‘ ’（5个空格） 【N是由五个空格字符组成的空格串，每个空格字符占1B】
2.串VS 线性表
串是一种特殊的线性表，数据元素之间呈现线性关系。
串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点字符等。
串的基本操作，如增删改查等通常以子串为操作对象
二、串的基本操作
1.StrAssign(&Tchars):赋值操作。把串T赋值为chars。
StrCopy(&TS):复制操作。由串S复制得到串T。
StrEmpty(S):判空操作。若S为空串，则返回TRUE，否则返回FALSE。
StrLength(s):求串长。返回串S的元素个数。
ClearString(&s):清空操作。将S清为空串。
DestroyString(&S):销毁串。将串S销毁(回收存储空间)。
Concat(&TS1,S2):串联接。用T返回由S1和S2联接而成的新串
Substring(&sub,s,pos,len):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Index(S,T):定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置;否则函数值为0。
StrCompare(S,T):比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S<T，则返回值<0。
2.串的比较操作
StrCompare(S,T):比较操作。若S>T，则返回值>0;若S=T，则返回值=0:若S<T，则返回值<0。（只有两个串完全相同时，才能相等）
比较的是字符集编码： 背背背背背
乱码问题： 编码规则的不同导致的。
总结：
4.1.2 串的存储结构
一、顺序存储。
1.首先定一个静态数组，然后定义i记录串的实际长度。（缺点：长度不可变）
2.使用malloc申请动态空间，定义指针指向串的地址。（需手动ferr）
方案一： 数组末尾记录长度
方案二：ch[0]充当length。首位置记录（字符的位序与数组下标相同）
方案三：末尾放/0，
二、链式存储。
1.每个结点存一个字符，然后用指针指向下一个结点。（存储密度低。改良方法，每个结点存储多个字符。若存不满，用特殊字符来补充）
三、基于顺序存储实现的基本操作
1.StrAssign(&T,chars):赋值操作。把串T赋值为chars。
StrCopy(&TS):复制操作。由串S复制得到串T。
StrEmpty(S):判空操作。若S为空串，则返回TRUE，否则返回
FALSE.StrLength(s):求串长。返回串S的元素个数。
ClearString(&s):清空操作。将S清为空串。
DestroyString(&s):销毁串。将串S销毁(回收存储空间)
Concat(&TS1,S2):串联接。用T返回由S1和S2联接而成的新串
2.求字串，
串SubString（&Sub,S,pos,len）求子串。用Sub返回串S的第pos个字符起长度为len的子串.
首先判断子串的长度是否越界。然后使i等于要返回的子串的首位序，利用循环，依次遍历，找到位序为字串首位序加子串的长度的字母。存放至新串中，并使新串长度等于子串的长度，返回新串。
3.比较两个串的大小。
StrCompare(s,T):比较操作。若S>T，则返回值>0;若S=T,则返回值=0;若S<T，则返回值<0。
利用循环，依次遍历两个串的每一个字符，并比较。如果字符不相等，则相减，根据返回值来判断大小。如果相等，则比较下一个字符。如果所有字符都相等，则长度大的串更大。如果长度也相等，则两个字符串相同。
4.在主串中找到子串的位置。
Index(S,T):定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置;否则函数值为0。
利用前两个操作，利用while循环在主串中从头取出与子串相同大小的子串，再依次比较两个子串是否相同，相同则返回，不同则取出下一个大小相同的子串，再进行比较。
总结：
5.1.1树的定义和基本语术
一、树的定义和基本语术
1.基本概念：从根节点出发，依次长出各个分支，各个分支也能长出下级分支。（根节点无前驱，叶无后继）除根节点外，任何一个结点有且仅有一个前驱。
2.树的基本概念： 树是n(n20)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足
:1)有且仅有一个特定的称为根的结点。
2)当n>1时，其余结点可分为m(m>0个互不相交的有限集合T1,T2.……, ，其中每个集合本身又是一棵树，并且称为根结点的子树，
任何一个树都可以看成由一个根节点和若干个子树构成。
二、逻辑结构应用
1. 祖先结点： 子节点的所有前驱结点。
子孙结点：根节点的所有子节点。
双亲结点：子结点的直接前驱。
孩子结点：结点的直接后继。
兄弟结点（堂兄弟结点）：同一级的所有结点。
2.结点、树的属性描述
结点的层次（深度）--从上往下数。
结点的高度--从下往上数
数的高度（深度）--总共多少层
结点的度---（子分支）有几个孩子
树的度--各个结点的最大值
3.有序树VS无序树
有序树--逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
无序树--逻辑上看，树中结点的各子树从左至右是无次序的，可以互换。
4.树VS森林
森林。 森林是M（M>0）课互不相交的树的集合。
总结：
5.1.2 树的性质
考点1： 结点树=总度数+1；（结点的度——结点有几个孩子（分支））
考点2：度为m的树、m叉树的区别；
度为m的树：至少有一个结点有3度。
m叉树：所有结点的度都小于m。
考点3：度为m的树第i层至多有m^(i-1)个结点（i>=1）;
m叉树第i层至多有m^(i-1)个结点（i>=1).
考点4：高度为h的m叉树至多有m^h -1/m-1;
考点5： 高度为h的m又树至少有h个结点。
高度为h、度为m的树至少有 h+m-1 个结点。
考点6：具有n个结点的m叉树的最小高度为
总结：
5.2.1二叉树的定义和基本语术
一、基本概念
1.二叉树是n(n>=0)个结点的有限集合:
① 或者为空二叉树，即n=0。
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点： ①每个结点至多只有两棵子树。
②左右子树不能颠倒（二叉树是有序树）
（二叉树是递归定义的二叉树）
五种状态：
1.空二叉树 2.只有左子树 3.只有右子树 4.只有根节点 5.左右子树都有
二、几种特殊的二叉树
1.满二叉树：以可高度为h，且还有2^h-1个结点的二叉树。
特点：①只有最后一层有叶子结点
②不存在度为1的结点
③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1;结点i的父节点为[i/2](如果有的话,向下取整)--可以用顺序存储来实现。
2.完全二叉树：当且仅当其每个结点都与高度为h满二叉树中编号为1~n的结点一一对应时，称为完全二叉树
特点：①只有最后两层可能有叶子结点
②)最多只有一个度为1的结点
③同上③
④i<|n/2]为分支结点，i>|n/2]为叶子结点
（对于完全二叉树来说，如果某一个结点只有一个孩子，必然是左孩子。)
3.二叉排序树： 一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。（可用于元素的排序、搜索）
4.平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1.（有更高的搜素效率）
-----左边相比于右边，查找相同的数字，遍历的结点要少很多。
总结：