《认识结构》课件

认识结构结构是事物内部各部分之间的联系和排列方式结构是事物存在的本质特征课程介绍课程目标课程内容学习数据结构的基本概念和理论线性结构数组、链表、栈、队列掌握常用数据结构的实现方法树形结构二叉树、树、图培养学生分析问题和解决问题的能力结构的性质、表示、遍历什么是结构结构是数据组织、存储和访问的方式数据结构是一种数据元素之间的相互关系，它描述了数据的逻辑结构例如，一本书的章节结构是线性的，而网页的结构是树形的结构的分类线性结构非线性结构混合结构

1.

2.

3.123数据元素之间存在一对一关系，可以数据元素之间存在一对多或多对多关结合了线性结构和非线性结构的特性按照顺序访问系，例如树形结构和图结构，例如树形结构可以看作是线性结构和非线性结构的结合线性结构线性结构是最简单、最基本的数据结构之一线性结构中的元素按照一定的顺序排列，每个元素都有一个唯一的前驱和后继（除了第一个和最后一个元素）线性结构可以用数组或链表来实现，不同的实现方式会影响其性能和空间占用树形结构层级关系非线性结构广泛应用树形结构表示数据之间分层和从属关系树形结构是一种非线性结构，节点之间没有树形结构广泛用于文件系统、目录结构、数前后顺序据库等领域图形结构网络结构地图结构家族关系结构节点和边表示现实世界中的各种关系节点和边表示地理位置节点和边表示家庭成员关系例如社交网络、交通网络例如城市、道路、距离例如父母、子女、兄弟姐妹结构的性质逻辑性抽象性结构定义了元素之间的逻辑关系，例如包含结构是一种抽象的模型，不依赖于具体的实、顺序、层次等，使数据组织清晰且可理解现细节，可以用不同的数据结构来实现同一逻辑结构动态性共享性结构允许动态地添加、删除、修改元素，以结构可以被多个模块共享，提高程序代码的适应不断变化的数据需求可复用性结构的表示123图形表示文字表示数学表示图形表示法使用图形来直观地展示结构文字表示法使用文本描述结构关系例数学表示法使用数学符号和公式来表达关系例如，树状结构可以用树形图表如，可以采用树形结构的括号表示法，结构关系例如，可以用集合论的符号示，线性结构可以用线段表示或使用线性结构的列表表示法来描述结构元素之间的关系结构的遍历结构的遍历是指按照某种顺序访问数据结构中的所有节点的过程遍历是数据结构中最基础的操作之一，它是很多其他操作的基础深度优先遍历1先访问根节点，再依次访问其子节点广度优先遍历2先访问同一层级节点，再依次访问下一层级节点前序遍历3先访问根节点，再递归访问左子树，最后递归访问右子树中序遍历4先递归访问左子树，再访问根节点，最后递归访问右子树后序遍历5先递归访问左子树，再递归访问右子树，最后访问根节点线性表的定义有序的元素序列线性表是一个由零个或多个数据元素组成的有限序列，元素之间有顺序关系逻辑地址每个数据元素都拥有一个唯一的逻辑地址，用于区分不同的元素相同类型线性表中的所有数据元素都具有相同的类型，比如整型、浮点型或字符型线性表的特点有序性有限性线性表中的元素按其逻辑顺序排列线性表中的元素个数是有限的每个元素都有一个唯一的前驱和后继（除了第一个和最后一个元可以是空表，即没有任何元素素）线性表的基本操作插入1将一个新元素插入到线性表中指定位置删除2从线性表中删除指定位置的元素查找3在线性表中查找指定元素修改4修改线性表中指定位置的元素线性表的基本操作包括插入、删除、查找和修改，这些操作是线性表数据结构的常用功能这些操作的设计和实现必须满足数据结构的定义和要求线性表的实现顺序存储顺序存储结构是指用一组连续的内存单元存放线性表中的数据元素每个数据元素占用一个内存单元，数据元素在内存中按逻辑顺序存放链式存储链式存储结构是指用一组任意的内存单元存放线性表中的数据元素每个数据元素占用一个内存单元，数据元素在内存中不一定要按逻辑顺序存放，而是通过指针来链接选择合适的存储结构顺序存储结构适合存储数据元素数量固定且不需要频繁插入或删除元素的线性表；链式存储结构适合存储数据元素数量不固定且需要频繁插入或删除元素的线性表顺序存储结构连续存储将线性表中的所有元素存储在一段连续的内存空间中地址映射每个元素的地址可以由起始地址和元素在表中的位置计算得出随机访问可以通过索引直接访问任意元素，支持随机访问链式存储结构节点结构动态分配每个节点包含数据域和指针域节点在需要时动态分配内存，无需预先确定大小指针连接灵活高效节点通过指针域相互连接，形成链式存储结构灵活，可方便地插链表入或删除节点栈的定义后进先出数据访问

1.

2.12栈是一种线性数据结构，遵循只能在栈顶进行数据的插入和后进先出的原则删除操作数据存储应用广泛

3.

4.34栈中的数据元素按照线性顺序栈在函数调用、表达式求值、存储浏览器历史记录等方面有着广泛应用栈的基本操作入栈1将元素压入栈顶出栈2弹出栈顶元素获取栈顶元素3查看栈顶元素，不改变栈结构判断栈是否为空4检查栈中是否包含元素栈的基本操作可以看作是数据的进出管理，入栈相当于添加元素，出栈相当于移除元素，获取栈顶元素方便查看最新添加的元素，判断栈是否为空可以避免程序出现异常栈的应用表达式求值函数调用12栈可以用于将中缀表达式转换为后缀表栈用于存储函数调用时的参数、局部变达式，然后进行求值，这在编译器和解量和返回地址，以确保函数调用和返回释器中非常有用的正确执行撤销操作浏览器历史记录34在文本编辑器或图形软件中，栈可以用浏览器使用栈来存储用户访问过的网页来存储用户的操作历史记录，以便用户，以便用户可以轻松地返回到之前访问可以撤销之前的操作过的页面队列的定义先进先出队列是一种线性数据结构，遵循“先进先出FIFO”原则等待队列它就像一个排队等候的队伍，先加入队列的元素将先被处理基本操作队列的基本操作包括入队enqueue和出队dequeue队列的基本操作入队将新元素添加到队列的尾部新元素成为队尾出队从队列的头部删除元素队头元素被移除获取队头元素返回队列的队头元素，但不删除该元素判断队列是否为空检查队列是否为空返回真值或假值队列的应用超市收银打印机任务网页请求处理顾客排队结账，先到先服务，符合FIFO原打印机按顺序执行打印任务，确保先提交的服务器接收并处理网页请求，按顺序执行，则任务先完成提高效率树的定义非线性结构层次结构树是一种非线性数据结构，它由节点和边组成，节点之间通过边连树具有层次结构，每个节点最多有一个父节点，可能有多个子节点接，形成一个树形结构根节点叶节点树结构中只有一个根节点，没有父节点，其他节点都从根节点开始没有子节点的节点称为叶节点，是树结构中最底层的节点往下延伸树的基本术语根节点子节点父节点叶子节点树的顶端节点，没有父节点，树中除根节点外，每个节点都树中具有子节点的节点，它位没有子节点的节点，是树的末是树的起点它代表着树的起只有一个父节点，可以拥有多于子节点之上父节点与子节端节点，代表着数据结构的最始位置，其他节点都可从根节个子节点子节点是从父节点点之间的关系反映了数据结构终元素它们通常是树的最底点开始访问衍生出来的，代表着数据结构的层次关系层，表示着数据结构的最小单的分支关系位树的遍历先序遍历1根节点-左子树-右子树中序遍历2左子树-根节点-右子树后序遍历3左子树-右子树-根节点树的遍历指的是按照某种顺序访问树中的所有节点，并对每个节点执行某种操作常见的树的遍历方法包括先序遍历、中序遍历和后序遍历，它们的区别在于访问根节点的时机二叉树的定义节点关系二叉树节点之间的关系用父子关系来描述，根节点没有父节点，其他节点只有一个父节点树状结构二叉树是一种特殊的树结构，每个节点最多有2个子节点，分别称为左子节点和右子节点二叉树的特点层次结构递归定义根节点位于顶层，子节点位于下一层，形成清二叉树由一个根节点和至多两个子树组成，子晰的层次结构树也都是二叉树节点关系路径唯一每个节点最多有两个子节点，分别称为左子节从根节点到任意节点的路径是唯一的，不存在点和右子节点重复的路径二叉树的应用表达式计算数据库索引

1.

2.12二叉树可以有效地表示算术表二叉搜索树可以快速查找数据达式，方便计算机进行解析和，提高数据库查询效率计算游戏开发编译器设计

3.

4.34二叉树可以用于构建游戏场景二叉树可以用于构建语法分析和管理游戏对象，例如角色移树，帮助编译器识别代码结构动路径和游戏地图，完成编译过程总结与思考知识应用团队合作实践创新理解结构的本质和分类，将理论知识运用到与同学交流学习心得，互相帮助，共同进步通过实践项目，锻炼编程能力，提升解决问实际问题中题的能力。