计算机科学导论数据结构与算法.ppt

教学目的
理解数据结构的概念,理解数据结构的逻辑和存储结构:
理解算法的概念和算法的基本特性,了解算法复杂度的度
量方法
理解线性数据结构,理解顺序存储和链式存储的存储方法
描述栈和队列、串和数组这几个线性数据结构的概念
·了解非线性的数据结构,了解树、二叉树以及图的概念和
数据结构
理解排序的概念,描述插入、选择、气泡和快速排序的算
理解査找的概念,描述顺序査找和折半査找的算法,并能
够比较它们
理解递归的概念,能够在实践中了解递归的应用。
学****重点
数据结构的基本概念
算法的描述、流程图的使用以及算法的复杂度的
衡量
顺序存储和链式存储的方法
栈、队列、串和数组的概念和用法
二叉树数据结构
查询、排序和递归算法
第一节数据结构概述

11《数据结构》研究的对象
(1)对所加工的对象进行逻辑组织
(2)如何把加工对象存储到计算机中去
-(3)数据运算
G数据结构正是讨论非数值类问题的对象描述、信息组织
方法及其相应的操作
[例51]设有一个电话号码薄,有N个人的姓名和电话号码
要求设计一个程序,按人名查找号码,若不存在则给出
不存在的信息。


①②③④⑤⑥
集合结构。在集合结构中,数据元素间的关系是
属于同一个集合”。集合是元素关系极为松散
0-00099-
的一种结构,各元素间没有直接的关联
线性结构。该结构的数据元素之间存在着一对
的关系
树型结构。该结构的数据元素之间存在着一对多
的关系
图形结构。该结构的数据元素之间存在着多对多
的关系,图形结构也称作网状结构

例5-2]线性数据结构=(D,S)
D={1,2,3,4,5,6,7,8,9,10}
S={1,2>,<2,3),<3,4>,<4,5),<5,6),<6,7>,<7,8),
8,9》,<9,10》}
⊙-(---○-(-○-
数据结构概述
[例5-3]图形数据结构=(DR)
D={1,2,3,4,5,6,7,8,9}
R={1,2><1,3>24><2,5>2,6><2,8>3,2><3,4>
<45><5,7><6,7><6,9><7,9><89>}

[例5-4树形结构=(DR)
D=a, b, c,d,e,f, g, h, i,j,k, I
R={<a,b>,<a,C>,a,d>,b,e>,b>,b,g>,<c,h>,<c,>,<C>,
<dk>,<db>}