大话数据结构 读书笔记1（概念到栈）

一、基本概念、术语：

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