数据结构学习（考研408）

数据结构学习笔记，若有任何问题欢迎大家评论指出

其他

1.存取包括存和取
2.第i个元素指下标为i-1的位置
3.注意题干，注意题干中的陷阱

开端

有关概念：一个数据元素由若干个数据项组成，数据对象是具有相同性质的的数据元素的集合。 抽象数据元素可以理解为抽象成员，他是没有实际含义的数据元素，当实际使用时才确定他的数据类型
数据结构是相互存在一种或多种特定关系的数据元素的集合（数据之间的关系）
数据结构三要素： 存储结构（顺序，链式，索引，散列） 数据运算（与或非加减乘除等等）
逻辑结构：集合，线性，树形，图或网（主要分为线性和树状，图形） 线性是除了首尾外唯一前驱后继，树是除了根外唯一前驱不限后继数。图不限前驱后继数
逻辑结构+存储结构=物理结构，例：线索二叉树是物理结构
抽象数据类型包含逻辑结构和数据运算，可以定义一个完整的数据结构（实现则要用到存储结构）
是从基本数据类型中抽象出来的，即几种类型混合使用的类型，例如表，队列，堆等等
算法具有的特性：确定性：即运算结果是唯一的，每一步是确定的不是模棱两可的
有穷性，至少一个输出，有效性
最坏情况下某语句的频度指某一语句出现的频率（执行次数最大的时候）
时间和空间复杂度
时间复杂度：T（n） 一般表示程序执行次数T和传入的参数n的关系
一般只关注n的最高阶数，即如果T（n）=6n³+10n²+100000000，一般我们都假设T（n）=O（n³）
o(1)<o(log2ⁿ)<O(n)<o(nlog2ⁿ)<O(n²)<o(n³)<o(2ⁿ)<O(n!)<O(nⁿ)
例：传入i=1;i<n i=2i 则i=1,2,4,8,16 所以2^x=n，即x=log2ⁿ,所以时间复杂度为log2ⁿ
空间复杂度:S（n） 一般表示动态容器扩容问题
无论问题的规模怎么变，算法运行所需的内存空间都是固定的常量，则空间复杂度S（n）=O(1),这种情况我们成为“原地工作”

线性表

注意：1.头指针不等于头结点，头指针指头结点的指针域，指向第一个结点，
所以设置尾指针的链表指尾结点存在指针域，其值一般设置为NULL
2.带头结点的单链表，头结点不是第一个元素
线性表：是一种最简单的线性结构。相同数据类型的m个数据元素的有限序列，以下都是线性表
顺序表:指用顺序存储（数组）的方式实现的顺序表
位序：数据元素位序是从1开始的，即下标为0的数
特点：不易扩容，易查找，不易插入和删除，为随机存取结构
单链表：每一个结点中包含数据域和指针域，指针域指向下一个结点的地址
每一个结点有自己的地址（包含 一个结点的空间）在这个空间中有两个小块空间，一个空间是存储数据的空间，一个空间是存储指针的空间
特点：易扩容，不易查找，易插入和删除，为非随机存取结构（不能直接找到某个特定的点）
如何在单链表的某一个节点（p）前插入元素呢？（单链表访问不到前一个节点）
删除某个结点：删除结点p,无法使p的前驱指向p的后继，所以直接使p等于p的后继即可
(创建指针L,L=p;p=p.next;free(L)声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】