数据基础及结构 8

第1章绪论1本章目录01问题导入：数据结构无处不在02基本概念：数据结构的三大要素03算法分析：时间与空间复杂度04应用案例：AI大模型背后的数据结构05本章小结问题导入：数据结构无处不在短视频回退刷抖音时，顺滑的回退体验背后，是数据结构对历史记录的高效管理。海量搜索搜索引擎在毫秒级内从海量网页中找到结果，依赖于高效的索引结构。社交推荐分析好友关系链并推荐新朋友，图结构在这里发挥了核心作用。精准推荐电商网站总能猜中你的喜好，背后是复杂的排序与关联数据结构。路径规划无人驾驶汽车规划最佳路径，需要高效的图搜索算法支持。核心答案这些看似复杂的问题背后，都隐藏着数据结构的智慧。数据结构的研究内容数据结构是计算机专业的核心课程，是程序设计与系统开发的基石，主要研究数据的组织、存储与操作。逻辑结构研究数据元素之间的抽象关系（如集合、线性、树形、图形结构），决定了数据的组织方式。存储结构研究数据在计算机内存中的物理实现方式（如顺序存储、链式存储），是逻辑结构的具体映射。数据运算定义在数据上的操作（如增删改查、排序、检索），其效率直接依赖于逻辑与存储结构的设计。数据结构的研究内容逻辑结构集合线性结构树形结构图形结构存储结构顺序存储链式存储索引存储散列存储运算：插入、删除、查找、排序、遍历等数据结构基本概念和术语数据(Data)计算机处理的符号总称，是程序加工的“原料”。例如：数字、文字、图像、声音等。数据元素(DataElement)数据的基本单位，处理和操作的最小单元。例如：一条学生记录、一个图的顶点。数据项(DataItem)数据元素的最小标识单位，不可分割。例如：学生记录中的“姓名”、“学号”字段。数据结构(DataStructure)是指组成数据的元素之间的结构关系，即数据的组织形式。它一般包括以下三个方面的内容：（1）数据元素之间的逻辑关系，也称为数据的逻辑结构；（2）数据元素及其关系在计算机内的表示，称为数据的存储结构；（3）数据的运算，即对数据施加的操作。数据的逻辑结构集合结构(SetStructure)元素间除了同属一个集合外，无任何其他关系，如同一个袋子里的球。线性结构(LinearStructure)元素间存在一对一的线性关系，形成一个有序序列，如链表或数组。树形结构(TreeStructure)元素间存在一对多的层次关系，结构像一棵倒置的树，如家族族谱。图形结构(GraphStructure)元素间存在多对多的任意关系，是最复杂的结构，如社交网络关系。逻辑结构示例：集合与线性集合结构示例图书馆里所有的书籍构成一个集合待排序的所有学生成绩构成一个集合

特点：元素之间无序，没有特定关系线性结构示例抖音的浏览历史，按时间顺序排列回退操作就是从这个线性表中取出前一个元素

特点：元素之间有明确的先后顺序逻辑结构示例：树形与图形树形结构(TreeStructure)搜索引擎索引(Trie树)用于快速检索，利用层级关系缩小查找范围。公司组织架构体现上下级的层次关系，一个节点可指向多个子节点。核心特点：呈现一对多的层级关系，结构清晰，路径唯一。图形结构(GraphStructure)社交网络模型用户作为节点，关注/好友关系作为边，关系错综复杂。城市交通路网路口是节点，道路是边，用于复杂的路径规划算法。核心特点：多对多的任意关系，非常灵活，能很好地模拟现实世界。数据的存储结构1.顺序存储逻辑相邻的元素，物理地址也相邻（如数组）。就像排队一样，位置是连续的。2.链式存储逻辑相邻的元素，物理地址不一定相邻，通过指针连接（如链表）。3.索引存储建立索引表，通过关键字快速查找元素地址。类似于书的目录。4.散列存储通过哈希函数直接计算元素的存储地址（如哈希表），查找速度极快。

由于数据的运算也是数据结构不可分割的一个方面，在给定了数据的逻辑结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。

例如，若对线性表的插入、删除运算限制在表的一端进行，则该线性表称为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。数据的操作实现数据的操作与抽象数据类型(ADT)数据运算定义在逻辑结构上的一组操作（如插入、删除、查找），其定义与具体的物理实现无关。抽象数据类型(ADT)一个数学模型及定义在该模型上的一组操作。强调“做什么”而非“怎么做”。数据对象(D)+数据关系(S)+基本操作(P)数据的操作与抽象数据类型(ADT)ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}ADT

抽象数据类型名在本书中抽象数据类型的定义格式为：基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉其中基本操作定义格式为：抽象数据类型举例：一元多项式的定义ADTComplex{数据对象：

D＝{pi｜pi∈ElemSet，i=1,2,...,n,n≥0}数据关系：R1＝{<pi-1,pi>|pi-1,pi∈D,i=2,...,n}基本操作：PolyCreat(p)操作结果：构造一个多项式p。PolyDestroy(p)操作结果：多项式p被销毁。PolyAdd(p1,p2)初始条件：p1,p2已存在。操作结果：返回p1加p2的结果。PolyMinus(p1,p2)初始条件：p1,p2已存在。操作结果：返回p1减p2的结果。PolyMulti(p1,p2)初始条件：p1,p2已存在。操作结果：返回p1乘以p2的结果。}ADTComplex

算法分析：算法的定义与特性什么是算法？算法是对特定问题求解步骤的一种描述，是指令的有限序列。它代表着用系统的方法描述解决问题的策略机制。有穷性：在有限步骤后必须结束，不能无限循环。确定性：每一步骤的含义明确，无二义性，相同输入必有相同输出。输入与输出：有零个或多个输入，至少一个输出，且与输入相关。可行性：描述的操作可以通过基本运算有限次实现。算法的5个重要特性：算法分析：算法的定义与特性通常设计一个算法应考虑到以下目标：（1）正确性：算法应当能够正确地求解问题。（2）可读性：算法应当具有良好的可读性，便于人们阅读与理解。（3）健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。（4）效率与低存储量的要求：效率是指算法的运行时间，存储量要求是指算法运行过程中所需要的最大存储空间。算法分析：时间复杂度算法的执行时间

当算法转换为程序之后，每条语句执行一次所需的时间取决于机器的硬件性能、速度以及编译所产生的代码质量，这是很难确定的。同时，给10个数据排序和给10000个数据排序所需要的执行时间肯定是不同的。如何排除这些影响因素呢？

假设每条语句执行一次所需的时间均是单位时间。一个算法的时间消耗就是该算法中所有语句的频度之和。于是，我们就可以独立于机器的软硬件系统来分析算法的时间耗费。即T（时间）正比于f（频度）。

一般地，我们将算法求解问题的输入量称为问题的规模，并用一个整数n表示。算法分析：时间复杂度核心定义衡量算法执行时间随问题规模n增长的变化趋势，关注的是时间效率而非具体耗时。度量与表示统计基本操作频度，使用大O表示法T(n)=O(f(n))描述渐近复杂度。常见阶数O(1)常数阶|O(n)线性阶|O(n²)平方阶代码复杂度示例解析左图展示了三种典型的代码结构对应的时间复杂度。单层循环通常对应O(n)，而嵌套循环往往意味着O(n²)的指数级增长。常见时间复杂度对比复杂度增长排序(从快到慢)O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)算法性能评估高效区：O(1),O(logn),O(n),O(nlogn)适用于大数据量场景。低效区：O(n²),O(n³)在数据量较大时性能会显著下降。避免使用：O(2ⁿ)为指数级增长，随着n增大计算量将爆炸式上升。复杂度增长趋势可视化算法分析：空间复杂度核心定义指算法执行过程中所需存储空间随问题规模n增长的趋势，记为S(n)=O(f(n))。分析重点主要关注算法执行时所需的“辅助存储空间”，不包含输入数据本身占用的空间。原地工作(In-place)若算法的辅助存储空间为常数O(1)，即不随数据规模增长，则称为原地工作。时空权衡(Trade-off)在算法设计中，我们经常需要在时间效率和空间消耗之间寻找平衡，通常可以用空间换时间，或用时间换空间。应用案例：AI大模型背后的数据结构核心背景千亿参数模型（如GPT、ViT）的高效运行，离不开底层数据结构的支撑。关键应用场景张量：存储海量权重参数，支持并行计算。哈希表：实现词嵌入向量的O(1)快速查找。图结构：构建自注意力矩阵，建模复杂关系。树结构：管理特征金字塔，加速图像处理。数据结构是连接理论与应用的桥梁，是构建高性能AI系统的基石。本章小结数据结构三要素逻辑结构：集合、线性