数据结构基础概述课件.ppt

《数据结构基础概述课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1.3算法和算法的描述1.1什么是数据结构1.2基本概念和术语1.1什么是数据结构一、什么是数据结构二、数据结构的发展背景三、数据结构的地位一、什么是数据结构定义：是一门研究非数值计算的程序设计问题中，计算机操作的对象以及它们之间的关系和操作的学科。任务：讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及实现各种操作的算法问题。目的：使学生掌握如何组织数据、如何存储数据和如何处理数据的基本方法，从而为以后进行软件开发和应用、为进一步学习后续专业课程打下坚实的基础。线性表例1学生档案管理系统非

2、数值计算的例子例2人机对奕问题树……..……..…...…...…...…...例3制定教学计划图课程先后关系的图形描述形式：c1c9c4c2c12c10c11c5c3c6c7c8计算机应用领域从科学计算到非数值计算起初数据结构内容在其它课程中表述1968才作为一门独立的课程在国外开始设立1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。二、数据结构的发展背景“数据结构”在计算机科学中是一门综合

3、性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。本课程的前继课程：离散数学，C语言本课程的后续课程：操作系统、编译程序、数据库系统、人工智能等三、数据结构的地位1.2基本概念和术语一、基本概念二、数据类型三、抽象数据类型数据:所有能被输入到计算机中，且能被计算机处理的符号的集合。不仅包括数字、字符串，还包括图形、图像、

4、声音、动画、视频等数据形式。数据元素:数据的基本单位，是数据集合中的元素。数据项:是数据结构中讨论的最小单位。一个数据元素可由若干数据项组成。数据对象：是性质相同的数据元素的集合。数据元素数据项一、基本概念5数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。（通常将数据的逻辑结构称为数据结构）例如，在一维数组{a1,a2,a3,a4,a5,a6}中的数据元素之间存在如下的次序关系:{

5、i=1,2,3,4,5}又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素

6、之间存在两个关系:行的次序关系:列的次序关系:row={,,,}col={,,}结构：关系（用表示)集合松散的关系线性结构一对一的关系树型结构一对多的关系图状结构或网状结构多对多的关系。数据之间的关系分为四类：数据结构的形式定义：Data-Structure=(D，S)D是数据元素的有限集S是D上关系的有限集例如，DS1=(D,S),S={r}D={a1,a2,a3,a4,a5,a6}r={

7、+1>

8、i=1,2,3,4,5}DS2=(D,S),S={row,col}D={a1,a2,a3,a4,a5,a6}row={,,,}col={,,}6.存储结构（物理结构）：数据在计算机中的存储表示。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。(可以占用不连续的存储单元）分为两种：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。(占用连续的存储单元）head99018

9、0990290990375NULLa0123456789顺序存储结构链式存储结构二、数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称。在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。三、抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上

10、的一组算法。例如，抽象数据类型复数的定义：数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{

11、e1是复数的实数部分

12、e2是复数的虚数部分}ADTComplex{基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&r