西北工业大学《数据结构》课件，由计算机学院王庆老师制作

《数据结构》课程概述本课程将深入探讨数据结构的概念、应用和实现，并帮助学生理解数据结构在计算机科学中的重要性数据结构的定义数据元素的集合数据元素之间关系

1.

2.12数据结构是相互之间存在数据元素之间关系称为逻特定关系的数据元素的集辑结构，描述数据元素的合组织形式存储结构操作

3.

4.34存储结构是指数据结构在数据结构的操作是指对数计算机中的存储方式，包据元素进行的插入、删除括顺序存储和链式存储、查找等操作数据结构的分类线性结构非线性结构顺序表树••链表图••栈•队列•算法的定义和特性定义特性算法是指解决特定问题的一系列明确明确性•、有限的指令它描述了完成任务的有限性•具体步骤可行性•输入•输出•算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算时间时间复杂度常用大O符号表示，例如On表示算法的执行时间与输入数据的大小成正比，On^2表示算法的执行时间与输入数据大小的平方成正比算法的空间复杂度算法的空间复杂度是指算法在运行过程中所占用的内存空间大小空间复杂度通常用一个函数来表示，该函数描述了算法所占用的内存空间大小与输入数据规模之间的关系O1On常数级线性级On^2Ologn平方级对数级空间复杂度是算法效率的一个重要指标，它反映了算法在运行过程中对内存空间的消耗程度一般来说，空间复杂度越低，算法的效率越高顺序表的概念和存储结构顺序表是一种线性表，数据元素在内存中按顺序存储，数据元素的逻辑顺序和物理顺序一致顺序表的存储结构可以采用数组，数组的起始地址作为顺序表的起始地址，每个元素占用连续的存储空间，方便随机访问顺序表存储结构的优点是存储效率高，易于访问元素缺点是插入和删除操作需要移动元素，效率较低顺序表的基本操作插入1在指定位置插入新元素删除2删除指定位置的元素查找3查找特定元素的位置修改4修改指定位置元素的值顺序表的基本操作包括插入、删除、查找和修改等操作，这些操作是基础，也是后续其他操作的基础链表的概念和存储结构链表是一种线性数据结构，它是一种动态数据结构链表中的数据元素在内存中并非连续存储的每个数据元素称为节点，每个节点包含数据域和指针域数据域存储数据元素的信息，指针域指向下一个节点的地址链表的存储结构分为单链表、双链表和循环链表单链表中每个节点只有一个指向下一个节点的指针双链表中每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点循环链表中最后一个节点的指针指向第一个节点，形成闭环单链表的基本操作插入节点1将新节点插入到单链表中，需要找到目标位置，修改指针链接删除节点2删除节点时需要找到目标节点，修改前一个节点的指针，断开目标节点的链接查找节点3从头节点开始遍历链表，比较节点的值，找到目标节点并返回双链表的基本操作插入节点双链表的插入操作需要修改前后节点的指针指向，与单链表相比，需要更新两个指针删除节点删除操作同样需要修改前后节点的指针指向，以确保链表结构的完整性查找节点从头节点开始遍历链表，比较节点数据，找到目标节点遍历链表双链表可以通过向前和向后遍历，访问所有节点栈的概念和存储结构先进后出栈的存储结构栈的基本操作栈是一种线性数据结构，遵循先进后栈可以用数组或链表实现，数组实现入栈将元素添加到栈顶•出的原则，类似于一个装满盘子的架通常称为静态栈，链表实现通常称为出栈从栈顶移除元素•子，最先放进去的盘子最后被取出来动态栈取栈顶元素获取栈顶元素但不移•除判断栈空检查栈是否为空•栈的基本操作入栈1将新元素压入栈顶出栈2弹出栈顶元素获取栈顶元素3查看栈顶元素判断栈空4判断栈是否为空栈是一种先进后出的数据结构，基本操作包括入栈、出栈、获取栈顶元素和判断栈空这些操作遵循LIFO原则，确保数据按照顺序进出栈队列的概念和存储结构队列是一种先进先出（）的数据结构FIFO队列的存储结构可以采用顺序存储或链式存储顺序存储使用数组实现，元素按顺序存储•链式存储使用链表实现，元素之间通过指针连接•队列的基本操作入队1将一个新元素添加到队列尾部，称为入队操作入队操作的时间复杂度通常为O1出队2从队列头部删除一个元素，称为出队操作出队操作的时间复杂度通常为O1取队头元素3获取队列头部的元素，但不删除它取队头元素操作的时间复杂度通常为O1树的概念和基本术语根节点子节点父节点叶子节点树的最高层节点，没有父节树中除根节点以外的节点都一个节点包含的子节点被称树中没有子节点的节点被称点，但可以有子节点称为子节点，有父节点，可为其子节点，该节点为其子为叶子节点，没有子节点，以有子节点节点的父节点但有父节点二叉树的存储结构二叉树的存储结构是实现二叉树操作的基础常用的存储结构包括顺序存储结构和链式存储结构二叉树的遍历先序遍历先访问根节点，再依次遍历左子树和右子树递归实现，符合根左右顺序“”中序遍历先遍历左子树，再访问根节点，最后遍历右子树递归实现，符合左根右顺序，适合有序二叉树“”后序遍历先依次遍历左子树和右子树，最后访问根节点递归实现，符合左右根顺序，适合表达式树“”线索二叉树存储结构线索化操作线索二叉树是一种特殊的二将二叉树转化为线索二叉树叉树，它在二叉树的每个结的过程称为线索化操作，主点中增加两个指向线索的指要包括增加线索指针和修改针，以便快速找到结点的直指向左右孩子的指针接前驱和直接后继中序线索二叉树中序线索二叉树是最常用的线索二叉树，它将二叉树的节点按照中序遍历的顺序串联起来，方便快速找到某个节点的前驱和后继哈夫曼树定义构造方法应用哈夫曼树是一种带权路径长度最小的哈夫曼树的构造过程需要根据每个节哈夫曼树在数据压缩中非常重要，它二叉树它在数据压缩、编码等领域点的权值，依次选取权值最小的两个可以用于构建前缀码，提高压缩效率有广泛应用节点合并成一个新节点图的概念和基本术语图是一种非线性数据结构，由节点和边组成节点代表对象，边代表对象之间的关系图的类型包括无向图和有向图无向图的边没有方向，有向图的边有方向图的应用非常广泛，例如社交网络、地图导航、交通网络等图的基本术语包括顶点、边、度、路径、回路、连通图、树、生成树、最小生成树等图的存储结构邻接矩阵邻接表十字链表边表用一个二维数组表示图，数用一个一维数组存储顶点信在邻接表的基础上，每个顶用一个数组存储边信息，每组元素的值表示对应顶点之息，每个顶点对应一个链表点有两个链表，分别存储该个数组元素包含边的两个端间是否有边或边的权重，链表存储与该顶点相邻的顶点指向的顶点和指向该顶点信息以及边的权重信息顶点信息点的顶点信息图的遍历深度优先搜索1从一个顶点出发，沿着一条路径一直走到底，再返回到上一个节点，然后从另一个路径继续走，直到所有节点都被访问到广度优先搜索2从一个顶点出发，访问该顶点的所有相邻顶点，然后依次访问这些顶点的所有相邻顶点，直到所有节点都被访问到拓扑排序3对有向无环图（）进行遍历的一种特殊的算法DAG图的遍历指的是对图中所有节点进行访问的过程，它用于解决各种图论问题，比如寻找最短路径、判断图是否连通以及生成最小生成树等最小生成树概念应用算法最小生成树是指连接图中所有顶在网络设计、通信网络、交通网常见的最小生成树算法有普里姆点，且总边权最小的树络等领域，可以应用最小生成树算法和克鲁斯卡尔算法来优化网络结构和降低成本最短路径算法算法算法算法Dijkstra Bellman-Ford Floyd-Warshall123用于计算单源点到图中其他所用于计算单源点到图中其他所用于计算图中任意两点之间的有顶点的最短路径该算法适有顶点的最短路径该算法可最短路径该算法适用于带负用于无负权边的图以处理带负权边的图，并能检权边的图，但不能检测负权回测负权回路路拓扑排序定义应用拓扑排序是指将有向无环图（）的所有顶点排成一个线拓扑排序在很多领域都有着广泛的应用，例如任务调度DAG性序列，使得对于图中任意两个顶点和，若到存在、课程安排、软件工程中的依赖关系分析等u vu v路径，则在序列中排在的前面u v排序算法概述排序算法排序算法12指将一组无序数据按照特定顺序排列的过程，例如从小到大在数据处理和检索中发挥着至关重要的作用，例如数据库管或从大到小理、搜索引擎和推荐系统等排序算法排序算法34根据不同的排序策略和实现方式，可以分为插入排序、交换在选择合适的排序算法时，需要综合考虑数据的规模、数据排序、选择排序、归并排序和基数排序等类型和时间复杂度等因素插入排序选择第一个元素1将第一个元素视为已排序的子序列从第二个元素开始2遍历每个元素，与已排序子序列的元素比较插入到正确位置3找到合适位置，插入元素，维持排序顺序插入排序是一种简单直观的排序算法，通过逐个将未排序元素插入已排序子序列中实现排序它是原地排序算法，空间复杂度低插入排序在数据规模较小或基本有序的情况下表现良好希尔排序增量序列1希尔排序采用增量序列进行排序分组排序2根据增量对元素进行分组排序插入排序3对分组后的元素进行插入排序递减增量4不断减小增量，直至增量为1希尔排序是一种改进的插入排序算法，通过将数组分成多个子数组，对每个子数组进行插入排序，然后再逐步减小增量，将子数组合并起来进行排序与直接插入排序相比，希尔排序在效率上有了很大的提高其时间复杂度取决于增量序列的选取，一般情况下，时间复杂度为On^

1.5，比直接插入排序的On^2要快得多快速排序选择基准元素从数组中选择一个元素作为基准元素，例如第一个元素划分数组将数组划分为两个子数组，一个子数组包含小于基准元素的元素，另一个子数组包含大于基准元素的元素递归排序对两个子数组递归地应用快速排序算法，直到每个子数组只包含一个元素合并子数组将排序后的子数组合并成一个排序好的数组综合实践《数据结构》课程学习的最终目的是将理论知识应用于实际问题解决综合实践环节旨在帮助学生巩固所学知识，锻炼实际问题分析和解决能力。