数据结构实用教程讲课教案

《数据结构实用教程讲课教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、这次由本人主讲的数据结构（本科）IP课程共分为10讲，每讲大致为50分钟。第一讲数据结构概述第二讲集合与线性表第三讲栈和队列第四讲二叉树第五讲二叉搜索树和堆第六讲平衡二叉树第七讲图的概念和存储结构第八讲二分查找和散列查找第九讲选择排序第十讲快速排序和归并排序83第一讲数据结构概述一、数据结构的分类二、数据结构的定义三、数据结构的图形表示四、数据结构的二元组表示五、数据结构的应用实例六、算法的时间复杂度一、数据结构的分类数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑结构简称为数据结构，而在讨论数据

2、的存储结构时则必须指明是数据的存储结构。数据结构的分类：这里是指数据的逻辑结构的分类。总体来说数据的逻辑结构被分为集合结构、线性结构、树结构和图结构等四种基本类型。对于一些复杂的数据结构可以由这四种基本的数据结构，根据实际需要进行组合或嵌套所构成。数据的存储结构分类：被分为顺序、链接、索引和散列四种，由它们的组合和嵌套可以构成更复杂的存储结构。广义的数据结构的概念还包含对数据进行的各种运算，通常有插入、删除、查找、更新、排序、遍历等运算。二、数据结构的定义1、集合结构集合结构是指数据中各元素之间没有任何次序。如一个容器中的所

3、有乒乓球，一个俱乐部里的所有成员，可以认为它们之间没有任何次序，它们均为集合结构。2、线性结构线性结构是指数据中各元素之间具有1对1的先后次序关系。如在一个列车时刻表中，各车次记录之间是按照发车时间的先后次序排列的；在一个人事职工表中，各职工记录之间是按照职工编号的先后次序排列的。所以，它们的表结构都是线性结构。3、树结构树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经

4、理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。所以，企业的组织结构是一个树结构。4、图结构图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。三、数据结构的图形表示各种数据结构类型的图形表示如下：83从图形表示中可以清醒地看出：集合结构中的元素是各自独立的，元素之间没有联系。线性结构中的元素是一个接一个串联起来的，它有一个头元素A和一个

5、尾元素G，其余为中间元素；每个中间元素既有前驱元素，又有后继元素，如B的前驱元素为A，后继元素为C；C的前驱元素为B，后继元素为D，…,头元素A没有前驱元素，只有后继元素B；尾元素G只有前驱元素F，没有后继元素。树结构的图形表示象倒着画的一棵树，树中有一个树根元素A，它有3个后继元素，又称为A的孩子结点B、C和D，C结点有两个孩子E和F，D结点有一个孩子G，由于B、E、F、G没有孩子，所以称它们为叶子结点，而A、C、D被称为树枝结点或分支结点，同时A又是唯一的一个树根结点。在树结构中，树根结点只有后继结点，而没有前驱结点；如

6、A为树根结点，它没有前驱结点，或者说其前驱结点为空，它有后继结点为B、C和D；除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点；如C的前驱结点为A，G的前驱结点为D，每个结点的前驱结点即双亲结点，从图形中都能够很容易得到。在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。如(d)图所示的图中，顶点A没有前驱结点，或者说它有0个前驱结点，A有3个后继结点B、C和G；G有2个前驱结点A和D，有一个后继结点F；E有一个前驱结点C和0个后继结点，或者说，E没有后继，对于图形中的其他结点都能够

7、很容易得到其前驱和后继结点。从数据结构的图形表示中还可以清楚地看出：树结构是图结构的特例，若在图结构中，每个结点的前驱不能有任意多个，而只能有一个，并且只能有一个结点没有前驱，则就成为了树结构；线性结构是树结构的特例，若在树结构中，每个结点不能有任意多个后继，而只能有一个后继，则就成为了线性结构。为了区别于线性结构，时常把树结构和图结构称为非线性结构。四、数据结构的二元组表示83数据结构的二元组表示采用B=(K，R)的形式，其中第一元K给出数据结构中所有元素的集合，第二元R给出数据结构中所有元素具有的二元关系的集合，通常对每

8、个二元关系分别进行讨论，所以直接用R表示这一种二元关系，该二元关系是有序对的集合，又称是序偶的集合，每个有序对（即序偶）是用一对尖括号括起来的、具有前驱和后继关系的两个元素。对于前面图形中给出的四种数据结构，下面分别讨论它们的二元组表示。集合结构中的元素集合K和二元关系R分别为：K={A，