数据结构课件基本概念.ppt

文档介绍：第一章 数据结构
数据结构课件基本概念
主要内容

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

(1)数据：信息载体，能够被计算机识别、存储和加工处理。可以使数值数据(整数、实数)，也可以是非数值数据(声音、图像等) 。
(2)数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理(又称结点、记录)。
数据项：一个数据元素由若干数据项组成，数据的不可分割的最
小单位。
关键码：其值能唯一确定一个数据元素的数据项。
举例：图书管理系统 数据元素 数据项 关键码
(一本书)书目信息 书目信息每一项 书号(唯一确定一本书)
学号
姓名
系别
住址
电话
981111
李洪
机械
六舍
982111
王刚
电子
四舍
983211
王将
计算机
五舍
983212
张强
机械
六舎
4个数据元素
5个数据项
1个数据项
1个数据元素
(3)数据对象：具有相同性质的数据元素的集合。数据元素是数据对象类的一个实例。
学号
姓名
系别
住址
电话
981111
李洪
机械
六舍
982111
王刚
电子
四舍
983211
王将
计算机
五舍
983212
张强
机械
六舎
关键码：值唯一能区别不同的　
　　　　数据元素的数据项
数据对象-由4个记录组成,表中每行是一个记录,每个记录由5个数据项组成.
(4)数据结构
定义:相互之间存在着一种或多种关系的数据元素的集合。
研究内容:
①数据的逻辑结构：各数据元素之间的逻辑关系
②数据的存储结构：各数据元素在计算机中的存储关系
③对各种数据结构进行的运算：添加，删除，排序等。

四类基本逻辑结构
(1)集合结构：数据元素间的关系是“属于同一个集合”
(2)线性结构：数据元素之间存在一个对一个的关系。
(3)树形结构：数据元素之间存在一个对多个的关系。
(4)图形结构：数据元素之间存在多个对多个的关系。
学号
姓名
语文
数学
C语言
1001
张三
85
54
92
1002
李四
92
84
64
1003
王五
87
74
73
...
集合结构
线性结构
树型结构
图形结构：数据元素之间存在多个对多个的关系，图形结构也称作网状结构。