数据结构课件no.1基本概念

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

1、第一章数据结构主要内容1.1数据结构的基本概念与算法1.2线性表1.3栈和队列1.4树和二叉树1.5查找1.6排序数据结构国家等级考试大纲要求1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

2、7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。1.1数据结构的基本概念与算法1.1.1数据结构的基本概念1.数据结构的定义(1)数据：信息载体，能够被计算机识别、存储和加工处理。可以使数值数据(整数、实数)，也可以是非数值数据(声音、图像等)。(2)数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理(又称结点、记录)。数据项：一个数据元素由若干数据项组成，数据的不可分割的最小单位。关键码：其值能唯一确定一个数据元素的数据项。举例：图书管理系统数据元素数据项关键码(一本书)书目信息书目信息

3、每一项书号(唯一确定一本书)学号姓名系别住址电话981111李洪机械六舍5371111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎53722214个数据元素5个数据项1个数据项1个数据元素(3)数据对象：具有相同性质的数据元素的集合。数据元素是数据对象类的一个实例。学号姓名系别住址电话981111李洪机械六舍5371111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎5372221关键码：值唯一能区别不同的数据元素的数据项数据对象

4、-由4个记录组成,表中每行是一个记录,每个记录由5个数据项组成.(4)数据结构定义:相互之间存在着一种或多种关系的数据元素的集合。研究内容:①数据的逻辑结构：各数据元素之间的逻辑关系②数据的存储结构：各数据元素在计算机中的存储关系③对各种数据结构进行的运算：添加，删除，排序等。2.数据的逻辑结构四类基本逻辑结构(1)集合结构：数据元素间的关系是“属于同一个集合”(2)线性结构：数据元素之间存在一个对一个的关系。(3)树形结构：数据元素之间存在一个对多个的关系。(4)图形结构：数据元素之间存在多个对多个的关系。学号姓名语文数学C语言1001张三

5、8554921002李四9284641003王五877473...集合结构线性结构树型结构图形结构：数据元素之间存在多个对多个的关系，图形结构也称作网状结构。线性结构与非线性结构概念结点:组成数据结构的数据元素称为一个结点。前后件关系:数据元素之间的固有关系可以用前后件关系(前驱与后继关系)描述。举例：家庭成员辈分关系(父亲、儿子、女儿)，“父亲”是“儿子”和“女儿”的前件，“儿子”和“女儿”是“父亲”后件。线性结构有且只有一个根结点每个结点最多有一个前件，也最多有一个后件非线性结构一个数据结构如果不是线性结构，则称之为非线性结构。数据元素的

6、前后关系复杂，一个结点既可以有多个前件，也可以有多个后件。树型、图形结构属于非线性结构。3.数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。实现方式：(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。顺序存储结构的线性表线性表(a1,a2,a3,a4)存储单元的地址即物理地址(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。链式存储结构

7、的线性表线性表(a1,a2,a3,a4)存储单元的地址即物理地址指针域：存放下一个结点的地址a1,a2在逻辑上相邻,而在机内存储时,存储单元的地址(100,105)并不相邻.链式存储结构的特点每个结点由两部分组成：一部分存放数据，另一部分存储指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。数据运算(插入和删除等)灵活。(3)索引存储方法和散列存储方法(为了查找方便)4.数据结构的表示(1)二元关系表示B=(D,R)B：数据结构D：数据元素的集合R：D上的关系(反映数据元素前后件关系)家庭成员数据结构B=(D,R)D={父亲,儿子,

8、女儿}R={(父亲,儿子),(父亲,女儿)}(2)图形表示D中每个数据元素用标有元素值的方框表示,简称结点。R中每个二元组,用一条有向线段从前件结点指向后件结点。根