数据结构—chapter 1- 绪论

数据结构,时间复杂度

教材及参考书目 教材： – 《数据结构——使用C语言(第3版)》,朱战立编著，西安交 通大学出版社 – 《数据结构实习指导书》 中国地质大学(武汉)计算机科学与 技术系 – 《C语言程序设计(第二版)》,谭浩强，清华大学出版社 主要参考书目： – 《数据结构》(C语言版),严蔚敏等编著，清华大学出版社 ； – 《计算机程序设计技巧》,D.E.克努特[美]著，管纪立等译，第 一卷 基本算法，第三卷 排序与查找； – 《数据结构题集》(C语言版),严蔚敏、吴伟民编著，清华大 学出版社； – 《数据结构习题与解析》(C语言篇),李春葆编著，清华大学

数据结构,时间复杂度

学习数据结构的意义数据结构是为研究和解决如何有效地组 织和处理非数值数据而产生的理论、技 术和方法。 数据结构是软件设计技术的理论基础， 是计算机学科的核心专业基础课程，也 是所有应用计算机的其他学科所必须掌 握的课程。

数据结构,时间复杂度

学习这门课程的目的 训练复杂程序设计技能，提高编程能力：–掌握常用的基本数据结构； – 培养分析问题的能力：培养数据抽象能力，学会 分析研究具体问题中的数据特性； – 培养解决问题的能力：能够根据实际问题的需要 选择合适的数据结构和算法

初步掌握算法效率的度量——时间复杂度分 析技巧

数据结构,时间复杂度

教学内容

研究八大基本数据结构——线性表、栈、队列、 (串)、数组、树、二叉树、图– 逻辑特性 – 在计算机中的存储方式

学 习 的 主 线

– 操作集和在不同存储方式下操作的算法实现(重点、难点)– 各种算法的性能分析 – 各种数据结构的应用(重点、难点)

研究两大基本操作——查找和排序– 各种实现算法及其效率分析

数据结构,时间复杂度

数据结构课程的特点及学习方法 特点1:内容广，概念多 – 学习方法1:注重各章节间的联系与衔接，抓住主线， 融会贯通 特点2:实践性强、动手编程难 – 学习方法2:数据结构是一门实践性很强的课程，上 机实习是其中很重要的一个环节。因此，学习一个阶 段后要及时上机实习。 要求： (1) 认真地完成课后习题以及上机实习

(2) 编写的程序正确、结构清楚、易读，符合软件 工程的规范(P25)。

数据结构,时间复杂度

第一次课阅读：

朱战立，第1-13、14-18、18-25页 谭浩强练习 ： 作业1

数据结构,时间复杂度

Chapter 1 绪论1.1-2 基本术语数据结构

抽象数据类型

1.3 算法与算法分析算法 时间复杂度

数据结构,时间复杂度

1.1 基本术语● 数据(Data)

凡是能输入到计算机，由计算机进行加工处理 的数字、字母、文字和其它符号均叫做数据。 含义极为广泛，如图形、声音等都属数据的范 畴。● 数据元素(Data

Element)

数据的基本单

位，即数据集合中的一个个体。 有时，一个数据元素可由若干数据项组成，数据项 是具有独立含义的最小单位。

数据结构,时间复杂度

例、图书自动检索系统的数据

登录号

书名

作者名

分类号

出版单位

出版时间

001002

高等数学理论力学

樊映川罗远详

S01L01

高等教育出版社 ┅ ┅┇

┅┅

003┇

数据结构┇

严蔚敏┇

J01┇

┅┇

数据结构,时间复杂度

● 数据结构(Data

Structure)

◆ 元素之间的关系称为结构。数据结构，简单地

说，就是数据元素的集合加上数据元素之间的相 互关系的集合，可形式化地描述成一个二元组： Data Structure=(D,S) 其中，D:数据元素的集合， S:D上关系的集合。 ◆ 1968年唐 欧 克努特[美]:

数据结构=数据的逻辑结构+数据的存储结 构+数据的运算

数据结构,时间复杂度

◆

数据的逻辑结构数据元素之间抽象化的相互关系。二元组形式化 定义中的S即指的逻辑结构。

三类基本结构： 线性结构 树形结构 图形结构 也可简单分为： 线性结构：线性表、栈、队列、 串、 数组 非线性结构：树、二叉树、图

数据结构,时间复杂度

例1、图书自动检索系统(建立、查找、插入/删除)

登录号

书名

作者名

分类号

出版单位

出版时间

001002

高等数学理论力学

樊映川罗远详

S01L01

高等教育出版社 ┅ ┅┇

┅┅

003┇

数据结构┇

严蔚敏┇

J01┇

┅┇

数据结构,时间复杂度

例2、一个大学的人事档案处理系统学校 一院(系) 二院(系) … n院(系)

一专业 二专业 … m专业教师 学生

档案 档案…档案

数据结构,时间复杂度

例3、交通管理信息系统

数据结构,时间复杂度

◆

数据的物理结构(存储结构)

逻辑结构到计算机存储器的映象。映象方法：

顺序分配

元素 内 存 序号

a0 a1 a2┇

ai┇

an–1

0 1 2 ┇ i ┇ n–1

h a1

链式分配 … a2

ai

…

an ∧

数据结构,时间复杂度

◆ 数据的运算(操作)逻辑操作 和 具体操作 ：逻辑结构 逻辑操作

抽象 只知道"做什么",而无须考虑"如何做"具体

存储结构 具体操作

常用的逻辑操作有：(1)建立一个数据结构 (2)销毁一个数据结构 (3)插入一个新元素到一个指定的数据结构 (4)删除一个元素 (5)修改一个元素(或其中的数据项)的内容 (6)排序 (7)查找