严蔚敏版数据结构(C语言版)PPT-第一章

数据结构课程内容：计算机软件的基础知识———数据结构课时安排：数据结构——56学时上机——32学时课程设计——24学时机房教材：《数据结构》c语言版本参考书：数据结构严蔚敏清华大学出版社数据结构的基本概念（第1章绪论）基本的数据结构线性结构非线性结构基本的数据处理技术查找技术（第9章）关于本书内容编写说明基本结构（三部分）排序技术（第10章）线性表（第2章）栈和队列（第3章）串（第4章）数组和广义表（第5章）树（第6章）图（第7章）数据结构考研的考试形式和试卷结构

试卷满分及考试时间本试卷满分为150分，考试时间为180分钟答题方式：答题方式为闭卷、笔试试卷内容结构：数据结构45分计算机组成原理45分操作系统35分计算机网络25分试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70数据结构考研大纲【考查目标】1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储数据结构考研大纲三、树与二叉树（一）树的概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树（三）树、森林1.书的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树的应用1.等价类问题2.哈夫曼（Huffman）树和哈夫曼编码数据结构考研大纲四、图 （一）图的概念 （二）图的存储及基本操作

1.邻接矩阵法

2.邻接表法 （三）图的遍历

1.深度优先搜索

2.广度优先搜索 （四）图的基本应用及其复杂度分析

1.最小（代价）生成树

2.最短路径

3.拓扑排序

4.关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树（五）散列（Hash）表及其查找（六）查找算法的分析及应用六、内部排序 （一）排序的基本概念 （二）插入排序

1.直接插入排序

2.折半插入排序 （三）气泡排序（bubblesort） （四）简单选择排序 （五）希尔排序（shellsort） （六）快速排序 （七）堆排序 （八）二路归并排序（mergesort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用数据结构的基本概念（第1章绪论）基本的数据结构线性结构非线性结构基本的数据处理技术查找技术（第9章）关于本书内容编写说明基本结构（三部分）排序技术（第10章）线性表（第2章）栈和队列（第3章）串（第4章）数组和广义表（第5章）树（第6章）图（第7章）第一章绪言1.1什么是数据结构

程序=数据结构+算法例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2人机对奕问题树……..……..…...…...…...…...多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图

结构静力分析计算例如:数值计算的程序设计问题─━线性代数方程组─━环流模式方程

(球面坐标系)全球天气预报数据模型数据模型非数值计算的程序设计问题例一:求一组(n个)整数中的最大值基本操作是“比较两个数的大小”取决于整数值的范围算法：?模型：?例二：计算机对弈（跳棋）算法：?模型：?对弈的规则和策略棋盘及棋盘的格局计算数学需要研究的问题数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科1.2基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。音频和图像等数据（Data）定义：数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。C编译程序源程序（.c）目标程序（.obj）可执行程序（.exe）C链接程序例如对C源程序是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位

数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是称之为组合项数据结构：带结构的数据元素的集合假设用三个

4位的十进制数表示一个含

12位数的十进制数。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3

之间存在着“次序”关系

a1,a2

、

a2,a3

3214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

数据结构：带结构的数据元素的集合再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{<ai,ai+1>|i=1,2,3,4,5}

或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构：带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h

数据的逻辑结构

数据的存储结构数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构数据结构的三个方面：数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;抽象数据类型

(AbstractDataType

简称ADT)

是指一个数学模型以及定义在此数学模型上的一组操作。假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果ADT有两个重要特征:数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；

S是D上的关系集；

P是对D的基本操作集。ADT

抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}ADT

抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

赋值参数只为操作提供输入值。引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。例如，抽象数据类型复数的定义：

数据对象：

D＝{e1,e2｜e1,e2∈RealSet}

数据关系：

R1＝{<e1,e2>|e1是复数的实数部分

|e2

是复数的虚数部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex§1.3抽象数据类型的表示和实现

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存储结构的定义//-----基本操作的函数原型说明void

Assign(complex&Z,

floatrealval,floatimagval)；//

构造复数Z,其实部和虚部分别被赋以参数//realval

和imagval

的值float

GetReal(cpmplexZ)；

//返回复数Z的实部值float

Getimag(cpmplexZ)；