文档介绍：这次由本人主讲的数据结构(本科)IP课程共分为10讲,每讲大致为50分钟。
第一讲数据结构概述
第二讲集合与线性表
第三讲栈和队列
第四讲二叉树
第五讲二叉搜索树和堆
第六讲平衡二叉树
第七讲图的概念和存储结构
第八讲二分查找和散列查找
第九讲选择排序
第十讲快速排序和归并排序
第一讲数据结构概述
一、数据结构的分类
二、数据结构的定义
三、数据结构的图形表示
四、数据结构的二元组表示
五、数据结构的应用实例
六、算法的时间复杂度
一、数据结构的分类
数据结构又分为数据的逻辑结构和数据的存储结构这两个方面,我们时常把数据的逻辑结构简称为数据结构,而在讨论数据的存储结构时则必须指明是数据的存储结构。
数据结构的分类:这里是指数据的逻辑结构的分类。总体来说数据的逻辑结构被分为集合结构、线性结构、树结构和图结构等四种基本类型。对于一些复杂的数据结构可以由这四种基本的数据结构,根据实际需要进行组合或嵌套所构成。
数据的存储结构分类:被分为顺序、链接、索引和散列四种,由它们的组合和嵌套可以构成更复杂的存储结构。
广义的数据结构的概念还包含对数据进行的各种运算,通常有插入、删除、查找、更新、排序、遍历等运算。
二、数据结构的定义
1、集合结构
集合结构是指数据中各元素之间没有任何次序。如一个容器中的所有乒乓球,一个俱乐部里的所有成员,可以认为它们之间没有任何次序,它们均为集合结构。
2、线性结构
线性结构是指数据中各元素之间具有1对1的先后次序关系。如在一个列车时刻表中,各车次记录之间是按照发车时间的先后次序排列的;在一个人事职工表中,各职工记录之间是按照职工编号的先后次序排列的。所以,它们的表结构都是线性结构。
3、树结构
树结构是指数据中各元素之间具有1对多的先后次序关系,并且只有一个元素称为树根结点,其余均为树枝结点和树叶结点。如在一个企业的组织机构中,总经理只有一个,相当于是树根;它下属多个部门,每个部门又各有一个部门经理,相当于是树枝;每个部门又有多名员工,属于部门经理领导,相当于是树叶。所以,企业的组织结构是一个树结构。
4、图结构
图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在一个城市交通图中,所有道路连接成一个复杂的图结构,交叉路口就是图中的顶点,每条道路就是图中的边,从一个交叉路口可以到达与其连接的其他交叉路口。
三、数据结构的图形表示
各种数据结构类型的图形表示如下:
从图形表示中可以清醒地看出:
集合结构中的元素是各自独立的,元素之间没有联系。
线性结构中的元素是一个接一个串联起来的,它有一个头元素A和一个尾元素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又是唯一的一个树根结点。
在树结构中,树根结点只有后继结点,而没有前驱结点;如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没有后继,对于图形中的其他结点都能够很容易得到其前驱和后继结点。
从数据结构的图形表示中还可以清楚地看出:树结构是图结构的特例,若在图结构中,每个结点的前驱不能有任意多个,而只能有一个,并且只能有一个结点没有前驱,则就成为了树结构;线性结构是树结构的特例,若在树结构中,每个结点不能有任意多个后继,而只能有一个后继,则就成为了线性结构。为了区别于线性结构,时常把树结构和图结构称为非线性结构。
四、数据结构的二元组表示
数据结构的二元组表示采用B=(K,R)的形式,其中第一元K给出数据结构中所有元素的集合,第二元R给出数据结构中所有元素具有的二元关系的集合,通常对每个二元关系分别进行讨论,所以直接用R表示这一种二元关系,该二元关系是有序对的集合,又称是序偶的集合,每个有