数据结构与算法（Python语言版）课件 第1章 数据结构简介

第1章数据结构简介2025/6/111主要内容逻辑结构物理结构算法与结构1.1逻辑结构逻辑结构是指有限多个节点（结点，顶点，元素）之间的逻辑关系，不涉及节点（结点，顶点，元素）在计算机中的存储位置。2025/6/112主要的逻辑结构有线性结构，树形结构，图结构和集合这四种结构。⒈线性结构2025/6/113在实际生活中，经常遇到具有线性结构的一组数据，比如，中国农历的二十四节气：立春、雨水、惊蛰、春分、清明、谷雨、立夏、小满、芒种、夏至、小暑、大暑、立秋、处暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒2025/6/114⒈线性结构2025/6/115⒈线性结构2025/6/116⒈线性结构2025/6/1172025/6/1182.

树结构

2025/6/1192.

树结构用倒置的树形示意一个树2025/6/11102.

树结构一个树T=(A,R)

由多个互不相交的树构成2025/6/11112.

树结构树的每个结点至多有2个子结点，称这样的树是二叉树二叉查询树，特点是，每个结点上的值都大于等于它的左子树上的结点里的值、小于它的右子树上结点里的值。首先猜m是上面的二叉树的根结点中的数，如果猜测错误，反馈信息给你，你猜测的比根结点中的数大，那你就继续猜测这个数是当前结点的右子结点，如果告知你，你猜测的数不大于根结点中的数，那你就继续猜测这个数是当前节点的左子结点，依次类推，您可以较快的猜测到这个数。2025/6/11122.

树结构树的层从上至下，从0层开始根结点没有父结点，非根、非叶结点有且只有一个父结点，但有一个或多个子结点，叶结点有且只有一个父结点，但没有子结点。根据树结构的这个特点，可以把树的结点按层次分类：树的结点按层次分类，从根开始定义，根为第0层，根的子结点为第1层，以此类推。每一层上的结点只能和上一层中的至多一个结点有关系，但可能和下一层的0个或多个结点有关系。2025/6/11133.

图结构钢筋焊接起来的平面架中的焊点：a,b,c,d,e2025/6/11143.

图结构钢筋焊接起来的平面架中的焊点：a,b,c,d,e

这个图结构中，人们规定(a,b)和(b,a)是一样的（都代表同一根钢筋），即(a,b)和(b,a)都是没有方向的“标量”边，这样的图结构称作无向图2025/6/11153.

图结构当V×V的子集E满足下列①和②时，称E是V上的图关系，记作G=(V,E)

2025/6/11163.

图结构当V×V的子集E满足下列①和②时，称E是V上的图关系，记作G=(V,E)

对于G=(V,E)，如果(a,b)是边，那么默认(b,a)也就是边，并规定(a,b)边等于(b,a)边，这样规定的G=(V,E)是无向图，简称V是无向图，即无向图的边是没有方向的。无向图2025/6/11173.

图结构当V×V的子集E满足下列①和②时，称E是V上的图关系，记作G=(V,E)

如果(a,b)，(b,a)都是边，就规定(a,b)边不等于(b,a)边，这样规定的G=(V,E)是有向图，简称V是有向图，即有向图的边是有方向的。2025/6/11184.

集合集合A中的元素除了同属一个集合外，无其它任何关系，即关系集合是空集合，可表示为(A,∅)（∅是A×A的空子集）2025/6/1119对于(A,R)，计算机程序在存储空间中存放集合A的节点（结点，顶点，元素）的形式，称为A的节点（结点，顶点，元素）的物理结构，也称为A的存储结构。1.2物理结构比如，对于一个线性表，可根据需要采用顺序存储（节点的物理地址是依次相邻的）或链式存储（节点的物理地址不必是相邻的）。常用的存储结构有顺序存储、链式存储和哈希存储等，有关细节见后续的章节，例如，第4章至第11章2025/6/1120实施于集合上的算法，在其执行完毕后，必须保持集合的逻辑结构不变，比如，对于线性表，实施了增加或删除节点的操作后，要保证新的节点构成的集合仍然是线性结构，否则算法必须对当前的线性表的节点进行调整，使得当前线性表在逻辑上仍然是一个线性结构。1.3算法与结构有关细节见后续的章节，例如，第4章至第11章。算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据的存储结构2025/6/1121使用的是Python3.11.5。为调试代码方便每章的例子的代码均保存在一个各自独立的目录中（例如第2章的例子1的代码按utf-8编码保存在“ch2\例子1”目录中），并采用命令行行方式运行Python程序。需要根据Python的安装目录设置，在系统环境中添加python.exe的所在的目录为环境变量path的一个值。1.4Python版本算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据的存储结构可以根据本机