数据结构课件NO.1基本概念

因此，数据结构的内容包括三个层次 的五个“要素”，如下图所示：
2020/10/4
17
数据结构课程内容体系
方面 层次
抽象
数据表示 逻辑结构
数据处理 基本运算
实现 存储结构
算法
评价 不同结构的比较及算法分析
2020/10/4
18
4、学习的目的
计算机内的数值问题依靠方程，而非 数值问题（如表、树、图等）则要依 靠数据结构。
2020/10/4
22
1、数据与数据结构
数据：数据是信息的载体，是描述客观事 物的数、字符、以及所有能输入到计算机 中，被计算机程序识别和处理的符号的集 合。是计算机操作的对象的总称。
数据元素：是数据的基本单位，具有完整 确定的实际意义。在程序中常作为一个整 体进行考虑和处理。一个数据元素可由若 干个数据项组成。
2020/10/4
23
数据项：是数据不可分割的最小单 位，是构成数据元素的项目。
数据对象：数据的子集。具有相同 性质的数据成员（数据元素）的集 合。
整数数据对象 N = { 0, 1, 2, … }
字母字符数据对象 C={ ‘A’,’B’,……‘Z’}
2020/10/4
24
数据结构：是相互之间存在一种或多种 特定关系的数据元素的集合
程序设计＝好算法＋好结构
2020/10/4
19
5、学习目标
对每个数据结构加强对存在代价与效益 的观念
掌握常用的数据结构——将常用的数据 结构放入你的工具包
理解怎样去衡量一个数据结构或程序的 代价
2020/10/4
20
6、怎样学习数据结构
重基础(牢固准确掌握)讲实际(实现、分析算法)

设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排：
(a1，b1)(a2，b2)…(an，bn) 其中(ai，bi)(i=1，2…n) 分别表示某人的名字和对应 的电话号码。要求设计一个算法，当给定任何一个人 的名字时，该算法能够打印出此人的电话号码，如果 该电话簿中根本就没有这个人，则该算法也能够报告 没有这个人的信息。
随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系
统程序和应用程序的规模很大，结构又相当复杂。因此，为了编
写出一个“好”的程序，必须分析待处理的对象的特征及各对象
之间存在的关系，这就是数据结构这门课所要研究的问题。
1.1 什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大
多数情况下，这些信息并不是没有组织的，信息（数 据）之间往往具有重要的结构关系，这就是数据结构 的内容。什么是数据结构呢？ 例子： 例1、电话号码查询系统
|an|*|xn|+|an-1|*|xn-1|+…+|a1|*|x1|+|a0|*|x0| ≦ |an|*|xn|+|an-1|*|xn|+…+|a1|*|xn|+|a0|*|xn|
=(|an|+|an-1|+…+|a1|+|a0|)|xn|=c|xn| 其中：n0=1, c= |an|+|an-1|+…+|a1|+|a0|, g(n)=xn
即时间复杂度为平方阶。
例５ for(i=0;i<=n-1;++i) for(j=0;j<=i;++j) a[i][j]=0;
i=0: 赋值１次
i=1: 赋值 2 次 i=2: 赋值3次 …………….. + i=n-1:赋值n次

二分查找
二分查找法
将有序数据集分成两个部分，每次取中间位置的值与目标值进行比较，根据比 较结果缩小查找范围，直到找到目标值或确定目标值不存在。
优缺点
查找速度快，但要求数据集必须是有序的。
哈希查找
哈希表
利用哈希函数将数据元素映射到内存中的地址，实现数据的 快速查找。
优缺点
查找速度快，但需要解决哈希冲突问题，并可能存在哈希表 过大或过小的问题。
。
数据结构的基本概念
数据结构的基本概念包括：数据、数据 元素、数据类型、数据结构等。
数据结构是指数据的组织形式，即数据 元素之间的相互关系。
数据类型是指一组具有相同特征和操作 的数据对象（如整数、实数、字符串等 ）。
数据是信息的载体，是描述客观事物的 符号记录。
数据元素是数据的基本单位，一个数据 元素可以由若干个数据项组成。
稳定排序
归并排序是一种稳定的排序算法，即相等的元素在排序后 保持其原有的顺序。
非递归算法
归并排序是一种非递归算法，即通过迭代方式实现算法过 程。
需要额外的空间
归并排序需要额外的空间来存储中间结果和临时变量。
查找算法
06
线性查找
顺序查找
逐一比对数据元素，直到找到目 标值或遍历完整个数据集。
优缺点
简单易懂，但效率较低，适用于 数据量较小的情况。
拓扑排序的应用
拓扑排序是一种对有向无环图进行排序的算法， 它按照拓扑关系将图的节点排列成一个线性序列 。
有向无环图是一种没有环路的有向图，拓扑排序 可以有效地解决有向无环图的排序问题。
拓扑排序的应用非常广泛，包括确定任务的执行 顺序、确定事件的发生顺序等。
拓扑排序的基本思路是从有向无环图的任一节点 开始，删除该节点，并记录下该节点的所有后继 节点的编号，然后按编号从小到大的顺序重复以 上步骤。

第一讲数据结构概述一、数据结构的分类二、数据结构的定义三、数据结构的图形表示四、数据结构的二元组表示五、数据结构的应用实例六、算法的时间复杂度一、数据结构的分类数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。

数据结构的分类：这里是指数据的逻辑结构的分类。

总体来说数据的逻辑结构被分为集合结构、线性结构、树结构和图结构等四种基本类型。

对于一些复杂的数据结构可以由这四种基本的数据结构，根据实际需要进行组合或嵌套所构成。

数据的存储结构分类：被分为顺序、链接、索引和散列四种，由它们的组合和嵌套可以构成更复杂的存储结构。

广义的数据结构的概念还包含对数据进行的各种运算，通常有插入、删除、查找、更新、排序、遍历等运算。

二、数据结构的定义1、集合结构集合结构是指数据中各元素之间没有任何次序。

如一个容器中的所有乒乓球，一个俱乐部里的所有成员，可以认为它们之间没有任何次序，它们均为集合结构。

2、线性结构线性结构是指数据中各元素之间具有1对1的先后次序关系。

如在一个列车时刻表中，各车次记录之间是按照发车时间的先后次序排列的；在一个人事职工表中，各职工记录之间是按照职工编号的先后次序排列的。

所以，它们的表结构都是线性结构。

3、树结构树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。

如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。

所以，企业的组织结构是一个树结构。

4、图结构图结构是指数据中各元素之间具有多对多的关系。

这是数据结构中最复杂的结构。

如在一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。