当前位置：文档之家 › 数据结构绪论 PPT课件

数据结构绪论 PPT课件

  • 格式：ppt
  • 大小：649.00 KB
  • 文档页数：57

下载文档原格式

  / 57

合集下载

数据结构精选课件(ppt 82页)

数据结构精选课件(ppt 82页)
不同点
10.01.2020
11
1.2 数据结构的内容
逻辑结构 存储结构 运算集合
10.01.2020
12
逻辑结构
定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。
形式化描述： Data_Structure=（D,R）其中D是数据元素的
有限集，R是D上关系的有限集。
四类基本的结构 集合结构、线性结构、树型结构、图状结构。
10.01.2020
13
集合结构
定义： 结构中的数据元素之间除了同属于
一个集合的关系外，无任何其它关系。
例如：
集合
10.01.2020
14
线ቤተ መጻሕፍቲ ባይዱ结构
定义： 结构中的数据元素之间存在着一对
一的线性关系。
例如：
线性表
10.01.2020
15
树型结构
定义： 结构中的数据元素之间存在着一对
多的层次关系。
数据结构课件
用C语言描述
西北师范大学经济管理学院
----信息管理系
10.01.2020
1
第1章 绪 论
1.1 数据结构的基本概念(定义) 1.2 数据结构的内容（研究范围） 1.3 算法设计 1.4 算法描述工具 1.5 对算法作性能评价 1.6 数据结构与C语言表示
●1.7 关于学习数据结构
100001 张爱芬 女 345．67 145．45 30．00 451．12
100002 李 林 男 445．90 185．60 45．00 586．50
100003 刘晓峰 男 345．00 130．00 25．00 450．00
100004 赵 俊 女 560．90 225．90 65．00 721．80

数据结构 课件 第一章绪论

数据结构 课件 第一章绪论
2010-112010-11-18 4
1.1 数据结构(续) 数据结构(
很多问题求解最后都转化为求解数学方程或数学方程组。 很多问题求解最后都转化为求解数学方程或数学方程组。 在房屋设计或桥梁设计中的结构应力分析 结构应力分析计算可化解为 在房屋设计或桥梁设计中的结构应力分析计算可化解为 线性代数方程组求解的问题 的问题, 线性代数方程组求解的问题, 天天看到的天气预报 它的数学模型是一个环流模式方 天气预报, 天天看到的天气预报,它的数学模型是一个环流模式方 程。 预报人口增长情况的数学模型为微分方程。 情况的数学模型为微分方程 预报人口增长情况的数学模型为微分方程。 当计算机进入非数值计算领域 非数值计算领域, 当计算机进入非数值计算领域,特别是用在管理上的时 候,计算机的操作对象之间的关系就无法用数学方程加以 描述了。 描述了。
按书名
高等数学 理论力学 线性代数 ……
S01 L01 S01 S02 ……
索引表
分类号: 001，003…… 001，003…… 出版单位: 樊映川 002，…….. 002，…….. 出版时间: 华罗庚 004， 004，…… 栾汝书 价格:
…….. ……..
……. …….
按作者名
001,… 001,… 002,…. 002,… 004,… 004,…. ……. …….
2010-112010-11-18
7
例2 - 1
人机对奕问题
树形的数据结 构
……..
……..
2010-112010-11-18
…...
…...
…...
…...
8
例2 - 2
学校问题
树形的数据结 构
刘志刚
部门
…….. ..

数据结构讲义精品PPT课件

数据结构讲义精品PPT课件

003 陈诚 02 男 19840910 638
… … … ……
…
数据元素
数据结构 具有结构的数据元素的集合。它包 括数据元素的逻辑结构、存储结构和相适应的 运算。
逻辑结构
数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。
《The Art of Computer Programming》
Art Evans
数据结构在计算机科学中是一门综合性的专业基础课， 也是计算机专业的必修课，是其它许多课程的先修课程， 是设计编译程序、操作系统、数据库系统等系统程序和 大型应用程序的重要基础。
1.2 基本概念和术语
基本术语
数据 被计算机加工处理的对象。 数据元素（记录、表目） 数据的基本单位，
几种常用的运算有： (1)建立数据结构 (2)清除数据结构 (3)插入数据元素 (4)删除数据元素 (5)排序
(6)检索* (7)更新 (8)判空和判满* (9)求长*
*操作为引用型操作，即数据值不发生变化； 其它为加工型操作。
抽象数据类型
抽象数据类型 ADT（ Abstract Data Type ）： 数据类型概念的引伸。指一个数学模型以及在其上定义的操作集 合，与计算机无关。 数据类型：一组值的集合和定义在其上的一组操作的总称。
抽象数据类型的描述方法
ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名
其中基本操作的定义格式为:
基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

数据结构课件：绪论

数据结构课件：绪论
typedef StudentType DataType11
按照数据元素之间的相互联系方式， 数据的逻辑结构 可分为线性结构、 树结构和图结构。 线性结构是指除第一 个和最后一个数据元素外每个数据元素只有一个前驱数据元 素和一个后继数据元素。 表1 - 1中的数据元素就是一个线性 结构的数据元素。 线性结构也可表示为图1 - 1(a)。 由于线 性结构的数据元素呈现为线性序列， 所以有些教科书把线 性结构称为线性序列， 或简称序列。 树结构是指除根结点 外每个数据元素只有一个前驱数据元素和若干个后继数据元 素， 其典型例子如图1 - 1(b)所示， 其中， 数据元素A有两 个后继数据元素， 分别为B和C。
17
图 1 - 2 基本存储结构形式
(a) 顺序存储结构； (b) 链式存储结构
18
顺序存储结构和链式存储结构是两种最基本、 最常用 的存储结构。 除此之外， 还有仿真指针(也称作静态数组) 和间接地址存储结构。 仿真指针和间接地址存储结构实际 上分别是顺序存储结构和链式存储结构的某种形式的结合。
9
例如， 像下面这样定义后就表示变量a和b所属的数据
类型为StudentType：
StudentType a， b;
表示变量a的name数据项
的语法是， 表示变量b的age数据项的语法是b.age。
没有定义具体数据类型的数据元素称作抽象数据元素。
上述学生情况数据元素的数据类型定义为StudentType，
12
图结构是指每个数据元素可有若干个前驱数据元素和若干 个后继数据元素， 其典型例子如图1 - 1(c)所示， 其中， 数 据元素E有两个前驱数据元素， 分别为B和C。
13
图 1 - 1 基本的数据逻辑结构形式 (a) 线性结构； (b) 树结构； (c) 图结构

绪论(数据结构教程PPT课件)

绪论(数据结构教程PPT课件)
缓冲处理
在网络传输或文件读写过程中，使 用队列作为缓冲区，暂时存储待处 理的数据，以提高处理效率。
04
串、数组和广义表
串定义及基本操作
串的基本操作包括
赋值操作、连接操作、求串长、比较操作、定位操作等。
串的存储结构包括
顺序存储结构和链式存储结构。
串模式匹配算法
串模式匹配算法是指在一个主串中寻找一个子串（模式串）的位置。
函数调用
在程序执行过程中，使用 栈来保存函数调用的信息， 如函数参数、局部变量和 返回地址等。
队列定义及基本操作
01
队列（Queue）是一种特殊的线性数据结构，其操作在表 的两端进行。一端称为队头（front），另一端称为队尾 （rear）。
02
队列的基本操作包括
03
入队（enqueue）：在队尾插入一个元素。
3
线性表的抽象数据类型描述
数据类型名称、数据对象集合、操作集合等
线性表顺序存储结构
01
顺序存储结构的定义
用一段地址连续的存储单元依次存储线性表的数据元素
02
顺序存储结构的基本操作实现
创建、初始化、销毁、判空、清空、求长度、获取元素、修改元素等操
作的实现方法
03
顺序存储结构的优缺点
无需为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速
线索二叉树
线索二叉树是对二叉树的每个结点增设两个标志位以及一条线索而得到的。根据线索性质的不同，线索二叉树可分为前序线 索二叉树、中序线索二叉树和后序线索二叉树三种。这里以中序线索二叉树为例来说明线索二叉树的构造方法。
中序线索二叉树的构造规则是：若将二叉树的中序遍历序列中的每个结点都看作是相应指针域为空的指针，则称这些指针为 线索，而指向其前驱或后继的指针称为线索指针。加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树 (Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种 。

数据结构绪论 ppt课件

数据结构绪论 ppt课件
ppt课件 27 27
1.4 算法和算法分析
2019年3月2日星期六
算法和程序的主要区别：程序是用某种程序设计语言所书 写的一个计算过程。而算法并不一定表现为一个计算机程 序。它可以用不同方式和不同语言来描述。
BEGIN
1t 算法 2i DO UNTIL i>5 t×i t i＋1i ENDDO PRINT t
作为描述工具。其描述语法见P10-11。
但上机时要用具体语言实现，如C或C++等
ppt课件 25 25
1.4 算法和算法分析
2019年3月2日星期六
Q1. 什么是算法？
Q2. 算法设计的要求？
Q3. 时间复杂度如何表示？
Q4. 空间复杂度如何表示？
ppt课件 26
26
1.4 算法和算法分析
2019年3月2日星期六
2019年3月2日星期六
【例1】数据管理问题—线性问题
ppt课件 8
8
1.1 什么是数据结构
2019年3月2日星期六
【例2】棋类对弈问题—树型结构
初始棋盘格局
第一步
x
x
x x
第二步
x0
x 0
x
0
x 0
第 N 步
x x x 0x 0x 0 x 0
ppt课件 9
x 0x x0
x 0x x 0
9
1.1 什么是数据结构
ppt课件 30
30
1.4 算法和算法分析
2019年3月2日星期六
3 算法分析
Q3. 时间复杂度如何表示？
• 算法分析方法
• 算法分析的两个主要方面

时间复杂度：算法对时间的需求。 T(n)=O(f(n))

数据结构第一章 绪论PPT课件


28.11.2020
21
算法设计的要求
算法的正确性 l 可读性 l 健壮性 l 高效率和低存储量
例如要求n个数的最大值问题 给出算法如下：
max:=0; for（i=1 ；i<= n ;i++） { scanf("%f", x);
if (x>max) max=x; }
28.11.2020
22
算法描述的工具
算法可用自然语言、框图或高级程序设计语言 进行描述。
类语言是接近于高级语言而又不是严格的高级 语言，具有高级语言的一般语句设施，撇掉语言中 的细节，以便把注意力主要集中在算法处理步骤本 身的描述上。
28.11.2020
23
设计实现算法过程步骤
1. 找出与求解有关的数据元素之间的关系
2. 确定在某一数据对象上所施加运算 3. 考虑数据元素的存储表示 4. 选择描述算法的语言 5.设计实现求解的算法，并用程序语言加以描述。
例如：
树
28.11.2020
8
图状结构或网状结构
定义： 结构中的数据元素之间存在着多对
多的任意关系。
例如：
图
28.11.2020
9
逻辑结构
定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。
l形式化描述： Data_Structure=（D,R）其中D是数据元素的
有限集，R是D上关系的有限集。
28.11.2020
5
集合结构
定义： 结构中的数据元素之间除了同属于
一个集合的关系外，无任何其它关系。
例如：
集合
28.11.2020
6
线性结构
定义： 结构中的数据元素之间存在着一对

数据结构-基本概念与术语ppt课件


col = {<a1,a4>,<a2,a5>,<a3,a6>}
假设在 6 个数据元素{a1, a2, a3, a4, a5, a6} 之间存在如下的次序关系:
{<ai, ai+1>| i=1, 2, 3, 4, 5}
那么构成一维数组的定义。 可见，不同的“关系〞构成不同的“构造〞
数据构造是相互之间存在着某种逻辑关 系的数据元素的集合。
是如数:整据的数不“可5分〞割,字的最符小“单N位〞。等。 ----是不可分割的“原子〞
数据元素也可以由假设干款项构成。 例如： 描画一个学生的数据元素
其中每个款项称为一个“数据项〞
它是数据构造中讨论的最小单位
姓 名学 号班 号性别出生日期入学成果 年月日
原子项
称之为组合项
数据对象是性质一样的数据元素的集合， 是数据的一个子集。
例二 笼统数据类型三元组的定义：
ADT Triplet { 数据对象：D＝{e1,e2,e3｜e1,e2,e3∈ElemSet } 数据关系：R1＝{<e1,e2> , <e2,e3>} 根本操作：
InitTriplet( &T, v1, v2, v3 ) 操作结果：构造三元组T,元素e1,e2和e3分别被赋以参数v1,v2和v3的值。
DestroyTriplet( &T ) 操作结果：三元组T被销毁。
Get( T, i, &e ) 初始条件：三元组T已存在，1≤i≤3。 操作结果：用e前往T的第i元的值。
Put( &T, i ,e ) 初始条件：三元组T已存在，1≤i≤3。 操作结果：改动T的第i元的值为e。
IsAscending( T ) 初始条件：三元组T已存在。 操作结果：假设T的三个元素按升序陈列
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

清华大学出版社
数据结构(C++版)第2版
1.2 本书讨论的主要内容
例1-3 人——机对弈问题 如何实现对弈? 各格局之间是什么关系？
清华大学出版社
数据结构(C++版)第2版
1.2 本书讨论的主要内容
例1-4 七巧板涂色问题 如何表示区域之间的邻接关系？
清华大学出版社
数据结构(C++版)第2版
1.2 本书讨论的主要内容
清华大学出版社
数据结构(C++版)第2版
课程性质
• 数据结构是计算机专业的专业基础课
公共基础课、专业基础课、专业方向课、专业选修课
• 在教学计划中的地位：核心、承上启下
前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理……
• 属于武术中的“练功”科目
“练武不练功，到头一场空”
数据结构(C++版)第2版
学编程的境界
• • • • • 学会写程序 学会高效地写程序 学会写高效的程序 学会设计算法 学会设计有用的算法
清华大学出版社
数据结构(C&躁
提高课外学习的时间和内容 理解科学而不是背诵科学→读书 正确对待考试
• 作习题
华罗庚：“学数学不做习题等于入宝山而空返”
• 考研：专业课必考
清华大学出版社
数据结构(C++版)第2版
教学目标
掌握基本的数据结构
工具箱→复用、修改、重组
培养算法设计能力、程序设计能力
算法——程序的灵魂 问题求解过程：问题→想法→算法→程序 程序设计研究的层次：算法→方法学→语言→工具
培养算法分析能力
评价算法、改进算法
清华大学出版社
数据、数据元素、数据项之间的关系
包含关系：数据由数据元素组成，数据元素由数据项组成。 数据元素是讨论数据结构时涉及的最小数据单位，其中的 数据项一般不予考虑。
数据 结构
数据元素 关系
清华大学出版社
• 作实验
计算机学科是一门科学性与工程性并重的学科， 表现为理论和实践紧密结合的特征。
清华大学出版社
数据结构(C++版)第2版
大学生“混”的最高境界 (考试版)
– – – – – – 人：什么？明天要考高数？？ 得道：什么？下节课要考高数？？ 入仙：什么？刚才考的是高数？？ 成佛： 什么？昨天有考试？？ 高级佛爷：高数？刚才考的不是英语？？ 我寝室一哥们：高数是什么树？？
计算机不能分析问题并产生问题的解决方案，必须由人来分 析问题，确定问题的解决方案，编写程序，然后让计算机执 行程序最终获得问题的解。
清华大学出版社
数据结构(C++版)第2版
1.1 数据结构在程序设计中的作用
例1-1 手机电话号码查询问题
将电话号码集合组织成线性结构和树结构，查找操作的效 率不同，当数据量较大时差别就更大。
学 号 0001 0002 0003 姓 名 陆 宇 李 明 汤晓影 性 别 男 男 女 出生日期 1986/09/02 1985/12/25 1986/03/26 政治面貌 团员 党员 团员
数据元素
数据项：构成数据元素的不可分割的最小单位。
清华大学出版社
数据结构(C++版)第2版
1.3 数据结构的基本概念
本书讨论非数值问题的数据组织和处理，主要内容如下：
（1）数据的逻辑结构：线性表、树、图等数据结构，其核 心是如何组织待处理的数据以及数据之间的关系；
（2）数据的存储结构：如何将线性表、树、图等数据结构 存储到计算机的存储器中，其核心是如何有效地存储数据以 及数据之间的逻辑关系； （3）算法：如何基于数据的某种存储结构实现插入、删除、 查找等基本操作，其核心是如何有效地处理数据；
清华大学出版社
数据结构(C++版)第2版
1.2 本书讨论的主要内容
计算机求解问题: 问题→抽象出问题的模型→求模型的解 问题——数值问题、非数值问题 数 值 问 题→数学方程 非数值问题→数据结构
清华大学出版社
数据结构(C++版)第2版
1.2 本书讨论的主要内容
例1-2 学籍管理问题 完成什么功能?各表项之间是什么关系？
清华大学出版社
数据结构(C++版)第2版
数据结构的创始人——克努思
1938年出生，25岁毕业于加州理工学 院数学系，博士毕业后留校任教，28 岁任副教授。30岁时，加盟斯坦福大 学计算机系，任教授。从31岁起，开 始出版他的历史性经典巨著：The Art of Computer Programming，他计划共 写7卷，然而出版三卷之后，已震惊 世界，使他获得计算机科学界的最高 荣誉——图灵奖，此时，他年仅36岁。
清华大学出版社
数据结构(C++版)第2版
成绩组成
• 平时成绩
20％：出勤＋作业＋报告
• 实验成绩
10％：出勤＋程序＋报告
• 期末考试成绩
70％
清华大学出版社
数据结构(C++版)第2版
第1章 绪 论
本章的基本内容是：
数据结构在程序设计中的作用 本书讨论的主要内容 数据结构的基本概念 算法及算法分析
清华大学出版社
数据结构(C++版)第2版
1.1 数据结构在程序设计中的作用
程序设计的实质是什么? 数据表示：将数据存储在计算机（内存）中 数据处理：处理数据，设计方案（算法） 数据结构问题起源于程序设计
清华大学出版社
数据结构(C++版)第2版
1.1 数据结构在程序设计中的作用
利用计算机求解问题的一般过程?
清华大学出版社
数据结构(C++版)第2版
关于教材
主教材
王红梅, 胡明, 王涛. 数据结构（C++版）第2版. 清华大学出版社
辅导及实验教材
王红梅等.数据结构（C++版）学习辅导与实验指导（第2版）. 清华大学出版社
参考教材
1. 严蔚敏. 数据结构. 清华大学出版社. 1997 2. 张铭.数据结构与算法. 高等教育出版社. 2008 3. 曹宏庆译. 如何求解问题. 中国水利水电出版社. 2003
（4）常用数据处理技术：查找技术、排序技术、索引技术 等。
清华大学出版社
数据结构(C++版)第2版
1.3 数据结构的基本概念
数据结构的基本概念
数据：所有能输入到计算机中并能被计算机程序识别和处理 的符号集合。 数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个 整体进行考虑和处理。 数据项