第6章 数据结构基础

1、6.1 数据结构概述数据结构概述6.2 几种经典的数据结构介绍几种经典的数据结构介绍第第6 6章章 数据结构基础数据结构基础6.1 数据结构概述数据结构概述w 数据结构课程的地位：数据结构课程的地位：n数据结构课程是计算机专业的一门核心专业数据结构课程是计算机专业的一门核心专业基础课程。基础课程。n数据结构几乎是所有计算机核心课程的必修数据结构几乎是所有计算机核心课程的必修先行课，如数据库概论、软件工程、编译原先行课，如数据库概论、软件工程、编译原理、操作系统等，此外更是高层次的计算机理、操作系统等，此外更是高层次的计算机应用处理技术及科学的根基所在，如人工智应用处理技术及科学的根基所在，如人

2、工智能、模式识别和机器学习，网络信息处理及能、模式识别和机器学习，网络信息处理及安全、多媒体技术安全、多媒体技术(图像、音视频和文本图像、音视频和文本)等。等。6.1.2 基本概念和术语基本概念和术语 数据：客观事物的符号表示，在计算机中是指所有能输入计算机并能被计算机处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据的逻辑结构是数据元素之间逻辑上的联系，是从逻辑关系上来描述数据，通常把数据的逻辑结构简称为数据结构。n数据结构分为两大类：线性结构和非线性结构6.1.2 基本概念和术语基本概念和术语w 线性结构n如果一个非空的数据结构满足下列两个条

3、件l有且只有一个根结点；l每一个结点最多有一个前驱，也最多有一个后继。n则称该数据结构为线性结构。线性表、栈、队列都属于线性结构。w 非线性结构n如果一个数据结构不是线性结构，则称为非线性结构。树、图等都属于非线性结构。6.1.2 基本概念和术语基本概念和术语w 常用的数据结构有集合、线性结构、树、图常用的数据结构有集合、线性结构、树、图 集合 线性结构 树 图6.1.2 基本概念和术语基本概念和术语 数据的存储结构：数据的逻辑结构在计算机存储设备中的映像，包括数据元素的表示和关系的表示。n数据的存储结构有两种：顺序结构和链式存储结构w顺序存储结构w是将逻辑上相邻的元素存储在物理位置上相邻的存

4、储单元里，元素之间的逻辑关系由存储单元的邻接关系来体现，如图所示6.1.2 基本概念和术语基本概念和术语w链式存储结构w链式存储结构借助于指示数据元素地址的指针表示数据元素之间的逻辑关系。如图2所示6.1.2 基本概念和术语基本概念和术语 数据的运算不同的数据结构各有其相应的若干运算，常用的运算有插入、删除、修改、查找、排序等。6.2 几种经典的数据结构介绍几种经典的数据结构介绍w6.2 几种经典的数据结构介绍几种经典的数据结构介绍6.2.1 线性表6.2.2栈和队列6.2.3 树6.2.4 图6.2.1 线性表线性表w6.2.1 线性表线性表w 复杂的线性表学号学号姓名姓名性别性别专业专业出

5、生日期出生日期201307024114张慧媛女计算机1994-2-25201307024126柳青女电子信息1996-4-8201405034209韩旭男会计1995-12-12201405034208赵琳琳女英语1995-10-10201405034213袁小梅女安全工程1996-2-196.2.1 线性表线性表w 非空线性表有如下特征：n有且只有一个根结点无前驱；n有且只有一个终端结点无后继；n除根结点与终端结点外，其它结点有且只有一个前驱，也有且只有一个后继；w 线性表结点的个数n称为线性表的长度。当n=0时，称为空表。6.2.1 线性表线性表w6.2.1 线性表线性表w 顺序表的基本运

6、算（2）删除w 线性表的删除运算是指将表的第i个元素删去，使长度为n的线性表变成长度为n-1的线性表，如图6.6所示。6.2.1 线性表线性表w 顺序表的基本运算（3）查找 查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与被查找的元素相比较，若相等则查找成功，否则返回失败信息。6.2.1 线性表线性表w(a)插入前插入前(b)插入插入后后6.2.1 线性表线性表w 单链表的基本运算（2）删除w 单链表的删除运算是指删除第i个位置的结点，删除操作也需要从单链表的头地址开始遍历，直到找到第i个位置的结点。(a)删除删除前前(b)删除后删除后6.2.1 线性表线性表w 单链表的基本

7、运算（3）查找 单链表中的按值查找是指在表中查找其值满足给定值的结点。查找运算同样还是从头地址开始遍历，依次将被遍历到的结点的值与给定值比较，若相等，则返回查找成功信息，否则返回失败信息。6.2.2 栈和队列栈和队列w 栈n栈（Stack）也可称为堆栈，是一种特殊的线性表，这种线性表只允许在线性表的一端（称为栈顶，Top）进行插入和删除运算，而栈的另一端则称为栈底（Bottom）。当栈中没有元素时，称为空栈。n栈的基本运算有三种：入栈、出栈与读栈顶元素栈的基本运算栈的基本运算（1）入栈运算n入栈运算是指在栈顶位置插入一个新元素，这个运算有两个基本操作：首先将栈顶指针加1（top+1），然后将新

8、元素插入到栈顶指针指向的位置。若栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不能进行入栈操作。（2）出栈运算n出栈运算是指取出栈顶元素并赋值给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素赋值给指定的变量，然后将栈顶指针减1（top-1）。若栈顶指针为0时，说明栈空，不能进行出栈操作。（3）读栈顶元素n读栈顶元素是指将栈顶元素赋值给一个指定的变量，注意：这个运算不删除栈顶元素，因此栈顶的指针不变。当栈顶指针为0时，说明栈空，读不到栈顶元素。6.2.2 栈和队列栈和队列w 队列n队列是另一种特殊的线性表，在这种表中，删除运算限定在表的一端进行，而插入操作在表的另一端进行。约

9、定把允许插入的一端称为队尾（rear），把允许删除的一端称为队首（front）。位于队首和队尾的元素分别叫做队首元素和队尾元素。n队列又被称为先进先出表（First In First Out，FIFO）n队列的基本运算有三种：入队、出队队列的基本运算队列的基本运算（1）入队运算n入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针加1，当rear=m+1时置rear=1，然后将新元素插入到队尾指针指向的位置。n当循环队列非空（s=1）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。（2）出队运算n出队运算是指在循环队列的队首位置退出一个元素并赋值给指

10、定的变量。这个运算有两个操作：首先将队头指针加1，并当front=m+1时置front=1，然后将队头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行出队运算。6.2.3 树树树（tree）是由n（n0）个有限结点组成的一个具有层序关系的集合。把它叫做“树”是因为它看起来像一颗倒置的树。w 树具有以下特点。n每个结点有零个或多个子结点；n每个子结点只有一个父结点；n没有前驱的结点为根结点；n除了根结点外，每个子结点可以分为m个不相交的子树。树树树的相关术语（1）结点：结点包含一个数据元素及描述与其它结点关系的信息（如前驱、后继指针），一般出现在链式存储结构中。（2）结点的度：

11、一个结点含有的子树的个数称为该结点的度。（3）树的度：一棵树中，最大的结点的度称为树的度树树树的相关术语（4）叶结点或终端结点：度为零的结点称为叶结点，也称为叶子结点，叶子结点是无后继结点的。（5）非终端结点或分支结点：度不为零的结点称为非终端结点或分支结点。（6）双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点或双亲结点。孩子结点和双亲结点是相对的。树树树的相关术语（7）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点或孩子结点。（8）结点的层数：树中规定根的层数为1，其余结点的层数等于其双亲结点的层数加1。（9）树的深度：树中结点层数的最大值称为该树的深

12、度或高度二叉树二叉树w二叉树二叉树(a) 满二叉树满二叉树(b) 完全完全二叉树二叉树二叉树的存储结构二叉树的存储结构w 二叉树的结构是非线性的，每个结点最多可有两个后继。通常用链式存储结构对二叉树进行存储。二叉树的遍历二叉树的遍历w 二叉树的遍历是指按照一定的规则访问二叉树的各个结点，使每个结点都被且只被访问一次。w 二叉树遍历的实质是将非线性结构的数据线性化的过程。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。根据访问根结点的次序二叉树遍历可以分为三种：前序遍历、中序遍历和后序遍历。二叉树的遍历二叉树的遍历(1) 前序遍历访问根结点；前序遍历左子树；前序遍历右子树；前序遍历结点的次序为：A、B、D、E、H、I、C、F、J、G。(2) 中序遍历中序遍历左子树；访问根结点；中序遍历右子树；中序遍历结点的次序为：D、B、H、E、I、A、F、J、C、