一、基本概念、术语：
1.数据：计算机中可以操作的对象，能被识别、输入、处理的符号集合；（图像、音频等通过编码成为字符数据；
2.数据元素：组成数据、有一定意义的基本单位；（建立数据模型的着眼点）；
3.数据项：数据不可分割的最小单位；组成数据项；
4.数据对象：性质相同的数据元素的集合；（通常简称数据）；
5.数据结构：不同数据元素之间的关系；
是相互之间存在一种或多种特定关系的数据元素的集合；（数据的组织形式）
6.（1）逻辑结构：数据元素之间的互相关系：集合（平行）、线性（一对一）、树形（一对多）、图形（多对多）；
（2）物理结构（存储结构）：逻辑结构在计算机中的存储形式；
把数据元素 存储到存储器中；
·顺式存储：数据元素在连续存储单元（数据逻辑关系同物理关系）；
·链式存储：数据元素在任意存储单元；需要一个指针存放数据元素地址；
（3）逻辑结构面向问题，物理结构面向计算机；目标：将数据及其逻辑关系存储到计算机内存中；
7.数据类型：性质相同的值及其操作；
（1）原子类型：不可再分基本类型：整型、实型…；
结构类型：由若干个类型组合；整型数组；
（2）抽象数据类型（ADT）：数学模型及定义的操作；（仅取决于逻辑特性）
体现了问题分解、抽象、信息隐藏；（抽象：隐藏实现过程）
二、算法：
1.算法：解决问题求解步骤；计算机中为指令的有限序列；
2.算法五个基本特性：输入（0or多）、输出（1or多）、有穷性（非无限循环，时间有限）、确定性（无二义性）、可行性（每一步能通过执行有限次完成）；
3.算法设计要求：正确性、可读性、健壮性（输入不合法时，算法也能做出相关处理）、时间效率高存储量低；
4.算法效率度量方式：事后统计、事前分析估算（算法的好坏和输入规模）；
事前分析估算：测定对运行时间有消耗的基本操作的执行次数；（只分析算法或步骤）；
把基本操作表示成输入规模的函数；
5.函数的渐近增长：输入n没有限制时，超过N，函数总大于另一个函数，称这个函数渐近增长快于另一个；（即判断效率关注最高阶项的阶数即可）；
6.（渐近）时间复杂度：语句执行次数T（n）是问题规模n的函数；
T(n)=O(f(n))表示随n增大，执行时间增长率与F(n)相同；
时间复杂度一般指最坏时间复杂度；平均运行时间是期望运行时间；
7.空间复杂度：S(n)=O(f(n))，n为问题规模，f(n)为语句关于n所占存储空间的函数；
三、线性表：
1.线性表（List）：0or多个数据元素的有序序列；
2.（直接）前驱/后继；
3.元素个数n为线性表长度；n=0，空表；
（一）4.线性表顺序存储：（数组）
顺序存储结构三个属性：起始位置、最大存储容量、当前长度；
5.获取元素：
6.插入元素：
a.插入位置不合理（溢出、不在范围内）抛出异常；
b.从最后一个元素开始遍历到第i个位置，分别后移一位；
c.插入元素；
d.表长加一；
7.删除操作：
a.删除位置不合理：抛出异常；
b.取出删除元素；
c.从删除元素开始遍历到最后一个元素，分别前移；
d.表长减一；
8.线性表线性存储：
优点：无需为元素逻辑关系增加存储空间；快速存取；
缺点：插入删除需要移动大量元素；长度变化大时，难确定存储空间容量；存储空间碎片；
（二）线性表链式存储：将数据存在任意的存储单元中；为了表示元素与后继数据元素逻辑关系，则存储本身信息（数据域）和直接后继的存储位置信息（指针域：存储指针或链）；这两部分组成数据元素的存储映像，称为结点（node）；
9.线性表链式存储：n个结点链结成一个链表；链表中每个结点只包含一个指针域则称单链表；
10.头指针：链表中第一个结点的存储位置（若有头节点则指向头结点；头指针不为空）；最后一个结点指针为空NULL；
11.头结点：第一个结点前，可无数据域，指针域存储指向第一个结点的指针；（线性表为空则头节点指针域为空）；
12.结构链表定义：
13.单链表的获取：
a.声明结点p指向第一个结点；初始化j为1；
b.当j<i，遍历链表；p指针后移累加；
c.若到链表末位p空，则第i个元素不存在；
d.否则查找成功，返回p的数据域；
14.单链表的插入：
注意先换指针域后换数据域；
使用了malloc标准函数，生成一个新结点；类型同node；
15.单链表的删除：
a.声明结点p指向第一个结点，用j计数；
b.遍历链表，让p不断指向下一个结点；
c.若到链表末尾p为空，则第i个元素不存在；
d.查找成功，则引入中间结点q，将p->next给q，在将q->next(p->next->next)给p；即实现了原本指向的元素（即第i个元素）被跳过；
e.用c语言标准函数free回收节点、释放内存；
对于插入或删除数据 越频繁的操作，单链表的优势越明显；
16.单链表的整表创建：动态的，不需要预先划定、分配，从“空表”依次建立各元素结点逐个插入；
（1）头插法：
a.声明结点p和计数器变量i；
b.初始化空链表L；为L的地址内存放头节点；头结点指针指向NULL；
c.生成新结点（malloc）赋值给p，随机数字赋值给p的数据域；
把现在头结点指向给p，让头结点指向p；
（2）尾插法：把新结点放在最后；
a.初始化链表L；声明中间结点p和推移（始终指向末位）结点r；声明计数器变量；
b.循环：生成新结点p，随机赋值，让尾结点r指向新结点p；
c.现在p才是尾结点，故将p赋值给r；
d.循环外将尾结点指向赋NULL结束链表；
17.单链表的整表删除：在内存中释放；
a.声明递推结点q和释放节点p；
b.第一个结点赋值给p；未到表尾时循环：将p结点的指向（下一个节点）赋给q；释放p；
c.循环结束后需要将头结点指针域清空；
18.单链表与顺序的优缺点：
查找多时，用顺序；插入、删除多时，用单链表；
元素个数不确定时，用单链表；
（三）其他链表结构：
19.静态链表：用数组描述链表；数组元素由两个数据域data（存放数据）和cur（存放后继元素在数组中下标）组成；
（1）
通常建的比较大，防止溢出；
第一个和最后一个元素不存数据；未被使用的数组元素为备用链表；
数组的第一个元素（下标0）的元素的cur存放备用链表第一个下标；
最后一个元素的cur存放第一个有数值元素下标，相当于头结点；
第一个备用下标为7，第一个有值下标为1；
（2）静态链表插入：静态链表也要建立和释放，数组需要自己实现malloc和free函数；
a.malloc：返回第一个备用的下标（i）为首cur，且需要把这个的下一个空闲（即空闲i的cur）赋给首cur（它成为了第一个空闲）；
b.插入：获取最后一个元素下标k（它的
cur即为首数值元素的下标）；用malloc获取空闲分量的下标j；将插入值e赋给空闲j的数据域；
c.找到插入元素的前一位，用k定位（k本来是最后一个下标，把它的cur赋给它之后，就变成了第一个有值元素下标，再赋则后移直到i）；
d.让k指向新元素，新元素cur为原i指向的cur；
（3）静态链表删除：
a.通过函数实现free；即定位末位k，k指向第一个非空；定位删除结点j，让k的指向为j的指向，即j被跳过了，现在第一个非空元素是j指向（下一个）元素；
b.把空闲结点回收到备用链表；即把删除结点插入到头结点和头结点的指向之间；（删除结点k指向原备用链表头的指向，让备用结点指向k）
（4）listlength：返回l中数据元素个数；
a.用i（下标值）标记非空头结点；用j计数；i不断递推直到为零；
b.返回的j为元素个数；
（5）静态链表优缺点：只移下标不移元素，但表长难确定、难以随机存取；
（四）循环链表：
20.循环链表：将单链表终端结点的空指针改为指向头指针；头尾相接的单循环简称循环链表；原来判断p->next是否为空，现在判断p->next是否为头结点；
（1）关键：用尾指针（rear）而不是头指针指向链表；则头结点rear->next->next；
（2）合并两表：
把p作为中间结点，先保存a的头结点，让a的尾结点指向b的第一个结点（即不要b的头结点了，只保留a的）；再让b的尾结点指向p（a的头结点）；释放p；
（五）双向链表：
在单链表的每个结点中，再设置一个指向前驱结点的指针域；
求长度的listlength，查找元素的getflem，获得元素位置的locateelem与单链表相同，但插入和删除需要改变两个指针；
（1）插入：先将插入元素的前驱和后继插入（添指针，不改变其他元素）；后结点的前驱（p->next->prior）；前结点的后继（p->next）；
（2）删除：让欲删除结点被跳过就行；
四、栈与队列：
（一）栈（stack）：
1．栈：仅在表尾进行插入和删除的线性表；
2．栈顶(top)：允许删除和插入的一段；（表尾）
栈底(bottom)：另一端；（固定端）
栈又称后进先出，即LIFO结构；
插入=进栈、压栈、入栈；（push）
删除=出栈、弹栈；（pop）
3．栈的结构定义：
栈顶top指示栈顶元素在数组中位置，top小于stacksize，存在一个元素则top为0，空栈-1；
当stacksize为5时：
4.栈的顺序存储结构：进栈：
5.栈的顺序存储结构：出栈；
6.两栈共享空间：两个相同类型的栈，让一个栈为数组的始端（下标0），另一个栈为末端（下标为数组长度n-1）；
（1）结构定义：即两个指针，向中间聚拢，当两指针值差1时，栈满；用于此消彼长型；
（2）push操作：判断满否；判断在哪个栈中，前栈则将插入值赋给top1后元素，后栈则赋给前元素；
（3）pop：
7.栈的链式存储：（链栈）
（1）链栈结构：top（栈顶指针）为原表中的头指针，此时头结点也失去意义；
其中，stacknode用于创建结点，中有数据域和指向后继的指针域；linkstack中有一个指向结点的栈顶指针top和一个给它定位的数据count；
（2）进栈：
创建新结点s；把插入数值赋给新结点数据域；新结点指向现在的栈顶S；让新结点s成为栈顶；栈顶位置标记count++；
（3）出栈：
把栈顶结点赋给p；下移栈顶指针；释放结点p；标记count–；
（4）栈中元素变化不可预料则链栈；变化可控，顺序栈；
8.栈的应用——递归：
（1）斐波那契数列：
（2）递归函数：直接或间接调用自己的函数；
递归至少有一个条件，满足时不再引用自身而是返回值退出；
（3）迭代是循环结构，递归是选择结构；
（4）递归退回恢复前行过程中存储起来的数据；（先存储的后恢复）
即前行时，压入栈中；退回时，恢复调用；
9.栈的应用——四则运算表达式求值：
（1）后缀（逆波兰）表示法：所有符号在要运算数字之后；
换为
（2）计算：从左到右遍历，遇到数字进栈；遇到符号将栈顶两个数字出栈运算；运算结果再进栈；直到得到最终结果；
（3）中缀表达式转后缀表达式：从左到右遍历，数字则输出，符号则判断与栈顶符号的优先级；右括号（左括号得等配对）或优先级低于栈顶，则栈顶依次出栈并输出，当前符号进栈；输出后缀表达式为止；
本文地址：https://blog.csdn.net/ego_ib/article/details/107435073