数据结构讲义第1章-绪论PPT课件

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

1、数据结构DATASTRUCTURE教材2数据结构（C语言篇）－－习题与解析李春葆清华大学出版社参考教材1数据结构题集（C语言版）严蔚敏吴伟民清华大学出版社数据结构（C语言版）严蔚敏吴伟民清华大学出版社2002课程学时课程总学时数：72（讲课：56，实验：16）课程设计（1周）目录第一章绪论第二章线性表第三章栈与队列第五章数组和广义表第七章图第八章查找第九章排序第六章树与二叉树C语言相关知识回顾数据处理输入、输出、加工、存储模块化函数声明与调用参数传递其它typedef使用指针操作：malloc，free第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的

2、表示和实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求非数值问题1.1什么是数据结构例1学生信息检索系统学号姓名性别专业年级980001吴承志男计算机科学与技术98级980002李淑芳女信息与计算科学98级990301刘丽女数学与应用数学99级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术99级000801何文颖女计算机科学与技术2000级000802赵胜利男数学与应用数学2000级000803崔文靖男信息与计算科学2000级010601刘丽女计算机科学与技术2001级0106

3、02魏永鸣男数学与应用数学2001级1.1什么是数据结构1968年美国唐·欧·克努特（DonaldE.Knuth）教授开创了数据结构的最初体系：它所著的《计算机程序设计技巧》（TheArtofComputerProgramming）第一卷《基本算法》是第一本系统阐述数据的逻辑结构和存储结构及其操作的著作。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。1.2基本概念和术语数据(Data):是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数值数据、非数值数据（文字、图像、声音等）

4、数据元素(DataElement)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。1.2基本概念和术语数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。－－－－数据的逻辑结构1.2基本概念和术语数据结构的分类：一、线性结构：结构中的数据元素之间存在一对一的关系。二、树型结构：结构中的数据元素之

5、间存在一对多的关系。三、图状结构或网状结构：结构中的数据元素之间存在多对多的关系。（a）线性结构（b）树型结构（c）图形结构三类基本结构的示意图1.2基本概念和术语例：某班学生基本情况登记表，学号姓名专业政治面藐001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员007巩力计算机团员008孔令辉计算机团员学生间学号顺序关系是一种线性结构关系1.2基本概念和术语例：家族的族谱假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE1.

6、2基本概念和术语对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现。1.2基本概念和术语一、数据（逻辑）结构的表示图示表示001003002004006005008007学生基本情况表的图示表示JIACBDHGFE家族树的图示表示1.2基本概念和术语一、数据（逻辑）结构的表示二元组表示Data_Structrue=（D，S）其中:D是数据元素集合，S是D上关系的集合。001003002004006005008007D={001，002，003，004，005，006，007，008}S={R}R={<

7、001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}1.2基本概念和术语一、数据（逻辑）结构的表示数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关1.2基本概念和术语二、数据的存储结构1定义数据结构在计算机中的表示或实现称为数据的物理结构，又称为存储结构。包括数据元素的表示及元素间关系的表示。1.2基本概念和术语二、数据的存储结构2表示i)数据元素的表示在计算机中，可用二进制位串表示一个数据元素