沈鑫剡编著《计算机基础与计算思维》第6章配套课件.ppt

《沈鑫剡编著《计算机基础与计算思维》第6章配套课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机基础与计算思维第六章第6章数据结构数据之间关系必须反映数据所表示的对象之间的关系数据存储方式必须反映数据之间的关系数据存储结构方便对数据的操作数据结构研究数据之间关系、数据存储结构和对数据的操作第6章难点和重点学习思路本章主要内容数据结构研究内容和定义数组和链表堆栈和队列二叉树图数据结构的启迪第6章数据结构6.1数据结构研究内容和定义本讲主要内容术语数据结构研究内容数据结构定义一、术语数据：是对客观事物的符号表示，计算机中的数据是所有能够输入到计算机中，并被计算机处理的符号总称。数据元素：是数据的基本单位，

2、在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干数据项组成，数据项是数据不可分割的最小单位。数据对象：是性质相同的数据元素的集合。二、数据结构研究内容描述数据元素之间的相互关系数据元素之间的相互关系称为结构，常见的结构有线性结构、树形结构和图形结构；如果两个相邻数据元素之间存在顺序关系，则称在前的数据元素为直接前驱，在后的数据元素为直接后继。线性结构中数据元素之间是一对一的关系；树形结构中数据元素之间是一对多的关系；图形结构中数据元素之间是多对多的关系。二、数据结构研究内容线性结构树形结构图形

3、结构设计存储结构存储结构不但需要实现数据元素的存储，而且需要体现数据元素之间的相互关系；数组和链表是目前用于实现数据元素存储功能的两种最常用的存储结构。二、数据结构研究内容实现对数据元素的操作操作是与数据结构相关的基本操作，如实现线性结构数据元素的插入和删除操作，树形结构数据元素的遍历操作等；存储结构必须便于实现与数据结构相关的数据元素的基本操作。二、数据结构研究内容三、数据结构定义数据结构的定义是：相互之间存在一种或几种特定关系的数据元素的集合。数据结构包含两个要素：一是数据元素的集合，通常记为D，二是D中各数

4、据元素之间的相互关系，记为R。数据结构B可以表示成B=（D，R）。6.2数组和链表本讲主要内容基本知识存储方式操作过程性能特性数组和链表的启迪一、基本知识数组由一组固定数量的数组元素组成，每一个数组元素用数组名和下标唯一标识；存放在不同的数组元素中的数据元素之间可以构成线性结构。链表由多个结点组成，每一个结点包含用于存储两种类型信息的变量，一是用于存储数据元素的变量，二是用于存储指向其他结点的地址的变量。存储指向其他结点的地址的变量称为指针；每一个结点可以包含多个指针；通过结点中指针的值给出该结点与其他结点之间的

5、关系。一、基本知识PP－＞num表示链表结构中某个结点中存储数据元素的变量；PP－＞P表示链表结构中某个结点中存储地址的指针；PP为指针变量，其值为该结点的地址；num用于标识该结点中存储数据元素的变量；P用于标识该结点中存储地址的指针。一、基本知识不能直接访问链表中某个结点的数据元素值，访问某个结点的数据元素值需要经过以下步骤：指针变量head存储指向链表第一个结点的地址；第一个结点的指针存储指向第二个结点的地址；通过结点指针之间的链接关系，最终得出表示存储指向该结点的地址的指针的表达式；通过存储指向该结点的地

6、址的指针实现对该结点中数据元素值的访问。一、基本知识二、存储方式确定数组长度（数组中数组元素数量）；按照数组长度在存储器中分配一组连续的存储单元；根据下标顺序在一组连续的存储单元中为数组中的每一个数组元素分配对应的存储单元。可以独立为每一个结点分配连续的存储单元，分配给某个结点的存储单元的地址与分配给其他结点的存储单元的地址无关，也与该结点在链表中的位置无关；结点之间的相互关系通过结点中指针的值实现。二、存储方式导出分配给结点C的两个存储单元中第一个存储单元的地址的过程如下。通过指针变量head，得到分配给结点A

7、的两个存储单元中第一个存储单元的地址m；通过结点A中指针的值（地址为m＋1的存储单元内容，链表中用head－＞P引用结点A中指针的值），得到分配给结点B的两个存储单元中第一个存储单元的地址i；通过结点B中指针的值（地址为i＋1的存储单元内容，链表中用（head－＞P）－＞P引用结点B中指针的值），得到分配给结点C的两个存储单元中第一个存储单元的地址n。二、存储方式三、操作过程数组操作过程访问x=a[3];a[3]=x;查找（折半查找算法）插入插入操作是在两个关系为（a，b）的相邻数据元素之间插入一个新的数据元素c

8、，使得三个数据元素之间的关系变为（（a，c），（c，b））。由于为数组在存储器中分配了固定长度的存储单元，数组中数组元素的数量无法动态增加；在a[2]和a[3]之间插入值为77的数据元素；a[3]、a[4]、a[5]下移一个存储单元，空出a[3]对应的存储单元；77赋值给a[3]。三、操作过程删除存储在数组元素a[3]中的数据元素；a[4]、a[5]、a[6]上移一个存储