文档介绍：第2章常用数据结构及其运算
概述
图
查找
排序
本章主要内容
概述
树与二叉树
数组
栈与队
线性表
算法和数据结构是计算机科学的两大支柱。
数据结构概述
早期定义为:研究算法的科学
近期定义为:研究数据的科学
数据结构是程序设计的基础。
例1:
040105467392756257061370502821126326
0401 班级
05467392756 电话号码
257061 邮政编码
370502821126326 身份证号码
结论:杂乱的数据不能表达信息
什么是数据结构
例2:电话号码薄:(a1,b1)(a2,b2)…(an,bn)
其中:ai为姓名,bi为电话号码
要求:设计一个算法,给定一个人的姓名时,能查出此人电话号码。
如果姓名和电话号码是无规律的,则只能逐个比较姓名和电话号码
如果姓名按照字典顺序排列,查找就快捷多了。
结论:数据之间是有联系的,这些联系常常影响算法的效率。
数据结构就是研究数据之间的联系
什么是数据结构
例3:大学生管理机构:
大学
学院1
学院3
学院2
…
学院n
1班
n班
2班
一年级
三年级
二年级
张三
四年级
…
李四
…
结论:数据是有结构的
数据结构就是研究数据的各类结构
什么是数据结构
例2:电话号码薄:(a1,b1)(a2,b2)…(an,bn)
其中:ai为姓名,bi为电话号码
对电话号码薄的操作:
查找:给定一个人的姓名时,能查出此人电话号码。
插入:插入新的联系人和电话号码
删除:删除无用的项
结论:在某种数据结构上可以定义一组运算
数据结构就是要研究各类数据结构上各类运算
什么是数据结构
概述
数据结构的基本概念和术语
数据(Data):所有能被计算机处理的符号的集合。
数据元素(Data Element):是数据的基本单位,也称之为结点(node)或记录(record),在计算机程序中通常作为一个整体进行考虑和处理。
如数据集合N={1,2,3,4,5}中1-5均为数据元素。
一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。
个人书库
数据元素
概述
数据结构的基本概念和术语
数据对象(Data Object):是性质相同的数据元素的集合。是数据的一个子集。
数据对象可以是有限的,也可以是无限的。
例:整数的数据对象是{…-3,-2,-1,0,1,2,3,…}
英文字符类型的数据对象是{A,B,C,D,E,F,…}
数据结构(Data Structure):是指带有结构的数据元素的集合。
结构: 数据元素之间存在的关系。
集合论方法定义结构S为一个二元组: S=(D,R)
其中:D是数据元素的非空有限集,R是定义在D上关系的非空有限集。
如n维向量的数据元素集合为D={x1,x2,…,xn},D上的关系R={<x1,x2>,<x2,x3>,…,<xn-1,xn>},即为线性表。
概述
数据结构的基本概念和术语
数据的逻辑结构:数据元素及其关系的数学特性(逻辑关系),建成数据结构
数据的物理结构(存储结构):是逻辑结构在计算机中的存储表示(映象)。也就是具体实现。分为顺序存储结构、链式存储结构。
数据类型(Data type):在一种程序设计语言中,变量所具有的数据种类。在C中数据类型:基本类型和构造类型;
基本类型:整型、浮点型、字符型;
构造类型:数组、结构、联合、指针、枚举型、自定义。