《数据结构》PPT课件

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

1、数据结构严蔚敏吴伟民编著课程内容：计算机软件的基础知识———数据结构课时安排：周二晚上上机——锡昌科技楼402周四1、2节（单周）——锡昌科技楼505周五下午——锡昌科技楼505第1章绪言§1.1什么是数据结构1.程序=数据结构+算法2.例子：例1图书馆的书目检索自动化系统登录号：书名：作者名：分类号：：：书目卡片书目文件按书名按作者名按分类号索引表线性表例2计算机和人对奕问题树……..……..…...…...…...…...例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图（a）五叉路口（b）表示通路的图3.数据结构定义:是一门研究非

2、数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科4.《数据结构》所处的地位：★它是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。★在计算机科学中，它不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它程序和大型应用程序的重要基础。§1.2基本概念和术语1.数据元素和数据项：1)数据（data)—是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2)数据元素（dataelement）—数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元

3、素又为元素、结点、顶点或记录。3)数据项（dataitem）—是数据不可分割的最小单位。通常作为数据元素的分量，数据项又称为字段或域。2.数据的数据结构（datastructure）—相互之间存在一种或多种特定关系的数据元素的集合。1）根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图2）数据结构的形式定义：一个二元组Data_Structure(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。3.数据的逻辑结构:1

4、)逻辑关系--数据元素间的关联方式或称‘邻接关系’。2)逻辑结构--数据元素间逻辑关系的整体。它只抽象反映数据元素的逻辑关系。数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系4.数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现。5.数据类型—一个值的集合和定义在这个值集上的一组操作的总称。(操作是指数据结构上需要或能够进行的处理。)原子类型――非结构。例如C语言中的整型等基本类型数据类型结构类型――可

5、以分解，成分可以是结构、非结构。例如数组6.抽象数据类型—一个数学模型以及定义在该模型上的一组操作。1）抽象数据类型:原子类型――不可分解。固定聚和类型――其值由确定数目的成分按某种结构组成。例如复数可变聚和类型――“值”的成分的数目不确定。例如可定义“有序整数序列”的抽象数据类型，其中序列的长度是可变的。2）抽象数据类型的形式定义：一个三元组Data_Structure(D,S，P)其中：D是数据对象，S是D上关系集，P是对D的基本操作集。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i

6、-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构小结：数据结构的三个方面：例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型type

7、defstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;§1．3抽象数据类型的表示与实现（略）§1．4算法和算法分析1.4.1算法的概念：算法是特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。★算法具有以下重要特性：★算法的描述—采用C语言算法的评价1.4.2.算法设计的要求――衡量算法优劣的标准1)正确性(correctness)—应满足具体问题的需求。2)可读性(readability