郑州公司企业网站建设,wordpress子页面不显示,美食网页制作教程,国际最新新闻热点事件数据结构 引用文章第一章#xff1a;绪论1.0 数据结构在学什么1.1 数据结构的基本概念1.2 数据结构的三要素1.3 算法的基本概念1.4 算法的时间复杂度1.4.1 渐近时间复杂度1.4.2 常对幂指阶1.4.3 时间复杂度的计算1.4.4 最好与最坏时间复杂度 1.5 算法的空间复杂度1.5.1 空间复… 数据结构 引用文章第一章绪论1.0 数据结构在学什么1.1 数据结构的基本概念1.2 数据结构的三要素1.3 算法的基本概念1.4 算法的时间复杂度1.4.1 渐近时间复杂度1.4.2 常对幂指阶1.4.3 时间复杂度的计算1.4.4 最好与最坏时间复杂度 1.5 算法的空间复杂度1.5.1 空间复杂度1.5.2 函数递归调用未总结1.5.3 存储地址1.5.3.1 内存高低地址与高低位1.5.3.2 用户程序虚拟地址空间分布 引用文章
在此基础上增加自己的学习过程: 《王道》数据结构笔记整理2022
1.2数据结构三要素——逻辑结构和物理结构与数据运算之间的关系 1.3抽象数据结构: 抽象数据
第一章绪论
1.0 数据结构在学什么
计算机组成原理、操作系统、数据结构和计算机网络之间的关系
如何使用程序代码把现实世界的问题信息化如何使用计算机高效地处理这些信息从而创造价值 信息化的世界数据结构是对数据的处理对现实世界的数字化生成数字文件再由操作系统完成对这些文件的管理。计算机组成原理又是完成这一切的硬件基础。
1.1 数据结构的基本概念
数据数据是信息的载体是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。数据是计算机程序加工的原料计算机处理的函数的入口传递的参数数据元素
数据元素是数据的基本单位通常作为一个整体描述现实世界的一个真实存在的个体进行考虑和处理。一个数据元素可由若干数据项组成数据项是构成数据元素的不可分割的最小单位。例如学生记录一个个体就是一个数据元素它由学号、姓名、性别等数据项组成。若一个数据项由多个更细分的属性组成则称为组合项
结构各个元素之间的关系数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合数据对象数据对象是具有相同性质的数据元素的集合是数据的一个子集 数据结构与数据对象之间的关系 同样的数据元素可以根据不同的逻辑组成不同的数据结构 不同的数据元素可以根据一样的逻辑组成相同的数据结构 1.2 数据结构的三要素 数据的逻辑结构 逻辑结构是指数据元素之间的逻辑关系即从逻辑关系上描述数据。
集合结构 各个数据元素同属一个集合别无其它关系线性结构 数据元素之间是一对一关系前驱后继首尾除外图形结构 数据元素之间是一对多的关系树形结构 数据元素之间是多对多的关系
数据的物理结构存储结构 通过计算机表示数据元素的逻辑关系存储结构是指数据结构在计算机中的表示又称映像也称物理结构。
存储结构
顺序存储把逻辑上相邻的元素存储在物理位置也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。链式存储逻辑上相邻的元素在物理位置上可以不相邻借助指示元素存储地址的指针来表示元素之间的逻辑关系。索引存储在存储元素信息的同时还建立附加的索引表索引表中的每项称为索引项索引项的一般形式是**关键字地址**散列存储根据元素的关键字直接计算出该元素的存储地址又称哈希Hash存储。 ps: 若采用顺序存储则各个数据元素在物理上必须是连续的若采用非顺序存储则各个数据元素在物理上可以是离散的。 数据的存储结构会影响存储空间分配的方便程度和对数据运算的速度。 数据的运算 施加在数据上的运算包括运算的定义和实现。 运算的定义是针对逻辑结构的指出运算的功能运算的实现是针对存储结构的指出运算的具体操作步骤。 三要素之间的关系
1.2数据结构三要素——逻辑结构和物理结构与数据运算之间的关系
1.确定一种存储结构就意味者在计算机中表示出数据的逻辑结构计算机中数据结构的映射。2.存储结构不同例如下边的例子顺序跟链表存储的运算方式的实现不同但是运算方式的定义是相同的也会导致运算的具体实现不同。 3.确定了存储结构才能实现数据结构。
逻辑结构
运算会和逻辑结构有关和物理结构无关。
物理结构
这四种结构各有优缺点顺序虽然可以实现直接存取但是对于空间的利用不充分链式虽然很好利用了空间但是得到元素只能顺序存取这样很不方便并且还要有额外的空间给指针索引虽然是结合了上面两种的优缺点但额外的索引表增加了内存损耗散列结构不可避免会有冲突的危险。
数据运算
运算包括定义和实现。运算的定义是针对逻辑结构的运算的实现是针对存储结构的。如果逻辑结构是线性的A-B-C物理结构是链式的addr0[A]-addr2[B]-addr1[C]运算的定义是找到B的前一个元素。B的前一个元素是A但是如果实现起来必须先找到addr0再找addr2确认了addr2中是B就得到了A这个结果。但是如果这里的物理结构是顺序的直接可以从addr0得到B的前一个地址是addr0。很明显两种不同的链式结构同一种运算实现的方法是不同的。 5. 数据类型、抽象数据类型
数据类型是一个值的集合和定义再此集合上的一组操作的总称。
原子类型其值不可再分的数据类型。如bool 和int 类型。结构类型其值可以再分解为若干成分分量的数据类型struct)
抽象数据类型Abstract Data Type,ADT抽象数据组织及与之相关的操作。 ADT用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关
抽象数据结构: 抽象数据 5.探讨数据结构的方式
1.3 算法的基本概念
程序数据结构原料算法方法步骤 算法algorithm)是对特定问题求解步骤的一种描述它是指令的有限序列其中的每条指令表示一个或多个操作。 算法的特性必要性而不是算法的定义即不满足则不是算法满足不一定是算法 1.有穷性一个算法必须总在执行有穷步之后结束且每一步都可在有穷时间内完成。 2.确定性算法中每条指令必须有确定的含义对于相同的输入只能得到相同的输出。 3.可行性算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 4.输入一个算法有零个或多个输入可以没有输入这些输入取自于某个特定的对象的集合。 5.输出一个算法有一个多个输出不能没有输出这些输出是与输入有着某种特定关系的量。 好的算法达到的目标 1.正确性算法应能够正确的求接问题。 2.可读性算法应具有良好的可读性以帮助人们理解。 3.健壮性输入非法数据时算法能适当地做出反应或进行处理而不会产生莫名奇妙地输出结果。 4.效率与低存储量需求效率是指算法执行的时间时间复杂度存储量需求是指算法执行过程中所需要的最大存储空间空间复杂度这两者都与问题的规模有关。 1.4 算法的时间复杂度
1.4.1 渐近时间复杂度
一般情况下算法中基本操作重复执行的次数是问题规模n的某个函数f(n)算法的时间量度记作Tn)O(n)它表示随问题规模n的增大而增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐近时间复杂度简称时间复杂度。
大O表示“同阶”同等数量级。即当 n-∞时二者之比为常数
1.4.2 常对幂指阶 表示图 1.4.3 时间复杂度的计算
顺序执行的代码只会影响常数项可以忽略挑选循环中的一个基本操作分析执行次数与n的关系即可对于多层嵌套循环只需要关注最深层的循环嵌套最深的即将每个循环执行次数相乘
1.4.4 最好与最坏时间复杂度 1.5 算法的空间复杂度
1.5.1 空间复杂度
无论问题规模怎么变换算法与运行所需的内存空间都是固定的常量则空间复杂度为S(n) O(1)在计算空间复杂度时只需关注存储空间大小与问题规模相关的变量 1.5.2 函数递归调用未总结
参考链接: 函数调用栈
1.5.3 存储地址
1.5.3.1 内存高低地址与高低位
参考: 内存高地址与低地址、变量的高位和低位 大端法就是数据的前部对于int型就是数据的高位存在低地址
1.5.3.2 用户程序虚拟地址空间分布 Eg分析代码中的常量、 变量所属的段 本地编译结果 结果分析
i1是已经初始化的全局变量故i存于数据段且类型为int四字节三十二位。i2是未初始化的全局变量未设置初始值故为0BSS段全部置零类型为int且由于BSS段在数据段上方故i2407A20地址大于i1403010。i3是已经初始化的静态全局变量所以i3存于数据段类型为int并且因为在i1之后声明所以i3403014的地址高于i1403010的地址四个字节。i4是在fun里定义的局部变量所以至于该函数的栈且栈段位于最上方所以i4的地址大于之前定义的i1 i2 i3。i5同i4是位于fun里定义的局部变量所以i5同样位于栈段由于栈段是向下延申的所以i562FDDC的地址小于i462FE00的地址。i6是在fun里声明的静态局部变量所以位于数据段又因为是在i3之后声明在数据段里的所以i6403018地址比i3403014高四个字节。Str1是在fun里声明的局部指针变量char*所以str1变量本身存放在栈段但是变量中指向的字符串常量”ABCDE”地址因此%P的形式打印出来的是str140400所存储字符串的地址所以打印出来的是一个位于数据段地址。又因为在i6403018之后声明所以地址高于i6。Str2是在fun里声明的局部变量所以位于栈段且因为栈段向下延申所以str262FDD0的地址小于i562FDDC的地址。Pi是在fun里声明的局部指针变量并且为它分配了空间指针本身位于栈段但是它不同于str1str1所指向的是位于数据段里的字符串”ABCDE”的地址。它指向malloc动态申请的地址空间申请的空间位于堆段所以%P打印出来的是位于堆段的地址所以地址位于BSS段与栈段之间。
