北京邮电大学-数据结构讲义.ppt

数据结构

;题型(1);题型(2);第一章绪论;根本概念;学习数据结构的意义;;;数据元素之间的逻辑关系，与计算机无关。

可用一个二元组表示：Data_Structure=(D,R)

D：数据元素的有穷集合，R：集合D上关系的有穷集合。

[例]设有数据结构B=(D,R)，

其中D={d1,d2,d3,d4,d5,d6}，

R={r}，

r={d1,d2,d1,d3,

d1,d4,d3,d5,d3,d6}，

试画出其逻辑结构图。;〔以班级学生关系为例〕

(1)集合结构数据元素除了“属于同一集合〞的联系之外，没有其它的关系。

(2)线性结构数据元素之间存在一对一的关系。

(3)树型结构数据元素之间存在一对多的关系。

(4)图状结构或网状结构数据元素之间存在多对多的关系。;数据的逻辑结构;存储结构：数据的逻辑结构在计算机中如何表示。

数据元素的映象

用二进制位(bit)的位串表示数据元素。

每个数据元素的映象称为结点

每个数据项的映象称为数据域

关系的映象

两种根本方法及其组合使用。

顺序映象：以相对的存储位置表示关系

链式映象：以附加信息(指针)表示关系

注意：数据的逻辑结构和存储结构的关系

可以用数组等线形存储的方式存储逻辑上的树形结构

也可以用树状的复杂的存储结构来存储逻辑上的集合关系以到达提高检索速度的目的;

数据的逻辑结构+运算的定义-------面向用户，需求分析

〔抽象数据类型〕概念层

数据的存储结构+运算的实现-------面向计算机

实现层;抽象数据类型;算法和算法分析;算法的概念

建立在数据结构根底上的、求解问题的一系列确切的步骤。

一个算法必须满足以下五个重要特性

有穷性：对任何合法输入执行有穷步后能结束。

确定性：每条指令必须有确切的含义。

可行性：算法的每一条指令均能执行。

输入：有零个或多个输入。

输出：有一个或多个输出。;正确性〔最重要的标准〕

算法应满足具体问题的需求

对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果

健壮性

算法应具有容错处理。当输入非法数据时，算法应对其作出反响，而不是产生莫名其妙或随机的输出结果

可读性

算法应该好读。以有利于阅读者对程序的理解和维护

高效性：时间复杂度

算法执行占用的CPU时间，随问题规模n的变化函数

高效性：空间复杂度

算法执行占用的内存总量，随问题规模n的变化函数;算法效率的度量;算法执行的时间;时间复杂度;时间复杂度曲线;空间复杂度;第二章线性表;线性结构的特点;

顺序表;

;线性表的顺序存储结构的优缺点;线性表的单向链式存储;线性表的链式存储结构与实现;线性表的链式存储结构;单链表的类型定义;带头节点的单链表;带头结点的单链表插入运算;带头结点的单链表插入算法;带头结点单链表的删除算法;带头结点单链表的删除算法;不带头单链表的转置;单链表的缺点;线性表的双向链式存储;双向链表;带头结点双向循环链表的插入;带头结点双向循环链表的删除;第三章栈和队列;插入和删除操作受限的线性表;栈的定义和根本操作;栈的根本操作;栈的存储结构;顺序表方式的堆栈操作;顺序表方式的堆栈操作;栈的链式存储结构以及操作;队列;队列的定义;队列的操作;队列的存储结构和实现;链式队列;链式队列的其它算法;使用顺序表方式实现队列;循环队列(1);循环队列(2);第五章数组和广义表;数组;数组的顺序表示和实现;数组的顺序存储方式〔续〕;稀疏矩阵;广义表;广义表的定义;广义表的长度和深度;广义表操作;第六章树和二叉树;;树的定义;;;;二叉树;二叉树的定义(1);二叉树的定义(2);二叉树的性质(1);二叉树的性质(2);二叉树的性质(3);二叉树的性质(4);二叉树的存储结构(1);二叉树的存储结构(2);二叉树的存储结构(3);二叉树的存储结构(4);遍历二叉树;遍历二叉树;遍历方法

先序遍历：ABDEC

中序遍历：DBEAC

后序遍历：DEBCA;利用遍历结果确定二叉树问题

先序序列+中序序列

中序序列+后序序列

先序序列+后序序列(x，为什么？)

先序序列:ABCDEFGH

中序序列:BDCEAFHG;;voidPre