DaJiU04--数据与数据结构解析.pptVIP

课程简介 课程定位 核心通识课， 计算机基础教学公共核心基础课程 授课对象 非计算机专业本科生 教学目标 深入理解计算科学在科学研究和知识创新中的地位和作用。 全面培养个人的信息素养和计算思维能力。 了解计算发展的基本过程，理解发展中的主要发明 掌握问题求解的一般思想和方法，理解常用的问题求解算法。 理解数据的概念，理解数据结构的含义和作用 理解计算机程序、计算机程序设计语言的概念，理解程序编写和程序运行的基本内涵 理解通信和计算机网路的思想，了解常用的网络设备及其功能，理解主要的互联网应用 了解目前计算机学科的发展前沿，体会学科交叉在科研中的价值和意义 第1章 绪论 第2章 计算与计算机 第3章 问题求解与算法 第4章 数据与数据结构 第5章 计算机程序 第6章 计算机网络 第7章 计算科学前沿 U4.1 数据结构的概念 数据与数据结构的概念 数据的逻辑结构 数据的存储结构 顺序存储结构 链式存储结构 数据与数据类型 数据 数据是对客观事物的符号表示，他是一组表示数量、行动和目标的非随机的可鉴别的符号。它可以是数字、字母等符号。 数据通常是指一切可以输入到计算机中并能被计算机程序处理的所有符号的总称 数据类型 数据类型是具有同类性质的数据的抽象 数据类型决定了数据在计算机中所占的存储空间大小 数据类型还决定了数据的性质，如：数据的取值范围、操作运算等 简单类型 整数，浮点数，字符，布尔 构造类型 数组，结构 数据结构的概念 数据结构 数据 数据之间的关系 抽象数据类型 数据 数据间的关系 在相应存储结构下对数据的操作运算，即算法 数据的逻辑结构 数据之间的逻辑关系称为数据的逻辑结构 集合：数据元素的关系非常松散，只描述数据元素是否同在一个集合中 线性结构：数据元素之间存在线性关系，也称先后关系，每个元素都有一个唯一的前导元素和一个唯一的后继元素，第一个元素没有前导，最后一个元素没有后继。 树形结构：数据元素之间呈现层次关系，在树形结构中，每一个元素通常称为一个结点，每个结点（根结点除外）有一个父结点，一个结点可以有多个子结点 图状结构，元素呈多对多的关系，在图状结构中每个元素称为一个结点，图状结构又称网状结构。图结构可表达元素之间的任意关系。 数据的存储结构 数据结构在计算机中的表示称为数据的存储结构，又称物理结构 存储数据 存储关系 顺序存储 用一组地址连续的存储单元依次存储数据集合中的元素 借助于数据在存储器中的相对位置表示数据之间的关系 不足 如果元素集合很大，顺序存储要求一块很大的连续的内存空间，这在操作系统的存储管理上可能无法满足 链式存储 指针表示了结点（数据元素）之间的逻辑关系 不足 利用指针表达元素之间的关系，指针增加了数据结构的存储空间要求 对元素的许多操作算法，在实现上也变得较为麻烦，效率较低。 U4.2 线性结构 什么是线性结构 线性表 线性表的概念 线性表的基本操作 线性表的存储结构 堆栈 堆栈的概念 栈的基本操作 栈的表示和实现 队列 队列的概念 队列的基本操作 队列的表示和实现 什么是线性结构 线性结构是一种描述元素先后关系的数据结构 线性结构特点 （1）存在一个唯一的称为“第一个”的数据元素，存在一个唯一的称为“最后一个”数据元素； （2）除了“第一个”元素以外，每一个元素都有一个唯一的前导元素，第一个元素没有前导；除“最后一个”数据元素外，每一个元素都有一个唯一的后继元素，最后一个元素没有后继。 线性表 线性表（Linear list）是一个具有n（n?0）个数据元素的有序序列。在不同的应用情况下，数据元素的含义不同，它可以是一个数、字符或一个任意的对象。 线性表的形式定义 线性表的基本操作 （1）Length(L)：求线性表的长度，返回线性表中数据元素的个数。 （2）Get(L,i)：取元素操作，返回线性表L中的第i个元素 （3）Locate(L,x)：定位操作，给定值x，判断线性表中是否有和x相同的元素。如果存在，返回第一个和x相同的元素在线性表中的位序；否则，返回0。 （4）Prior(L,e)：前导函数，返回线性表L中元素e的前导元素。如果e为第一个元素，返回空。 （5）Next(L,e)：后继函数，返回线性表L中元素e的后继元素。如果e为最后一个元素，返回空。 （6）Insert(L,i,e)：插入操作，在线性表L的第i个元素的前面插入一个元素e。（7）Delete(L,i)：删除操作，将线性表L的第i个元素删除。 线性表的顺序存储结构 线性表的顺序存储结构可以用数组来表示 例4-1：设线性表采用顺序存储结构，写出其主要操作的实现算法 算法4-1：顺序存储结构中的线性表操作算法 顺