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

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

树结构

2024/11/992.

树结构用倒置的树形示意一个树2024/11/9102.

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

由多个互不相交的树构成2024/11/9112.

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

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

图结构钢筋焊接起来的平面架中的焊点：a,b,c,d,e2024/11/9143.

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

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

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

2024/11/9163.

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

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

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

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

集合集合A中的元素除了同属一个集合外，无其它任何关系，即关系集合是空集合，可表示为(A,∅)（∅是A×A的空子集）2024/11/919对于(A,R)，计算机程序在存储空间中存放集合A的节点（结点，顶点，元素）的形式，称为A的节点（结点，顶点，元素）的物理结构，也称为A的存储结构。1.2物理结构比如，对于一个线性表，可根据需要采用顺序存储（节点的物理地址是依次相邻的）或链式存储（节点的物理地址不必是相邻的）。常用的存储结构有顺序存储、链式存储和哈希存储等，有关细节见后续的章节，例如，第4章至第11章2024/11/920实施于集合上的算法，在其执行完毕后，必须保持集合的逻辑结构不变，比如，对于线性表，实施了增加或删除节点的操作后，要保证新的节点构成的集合仍然是线性结构，否则算法必须对当前的线性表的节点进行