,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,6.1,数据结构概述,6.2,几种经典的数据结构介绍,第,6,章 数据结构基础,6.1 数据结构概述第6章 数据结构基础,6.1 数据结构概述,数据结构课程的地位：,数据结构课程是计算机专业的一门核心专业基础课程。,数据结构几乎是所有计算机核心课程的必修先行课，如数据库概论、软件工程、编译原理、操作系统等，此外更是高层次的计算机应用处理技术及科学的根基所在，如人工智能、模式识别和机器学习，网络信息处理及安全、多媒体技术,(,图像、音视频和文本,),等。,6.1 数据结构概述数据结构课程的地位：,6.1.2 基本概念和术语,数据：,客观事物的符号表示，在计算机中是指所有能输入计算机并能被计算机处理的符号的总称。,数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。,数据的逻辑结构是数据元素之间逻辑上的联系，是从逻辑关系上来描述数据，通常把数据的逻辑结构简称为数据结构。,数,据结构分为两大类：线性结构和非线性结构,6.1.2 基本概念和术语数据：客观事物的符号表示，在计算机,6.1.2 基本概念和术语,线性结构,如果一个非空的数据结构满足下列两个条件,有且只有一个根结点；,每一个结点最多有一个前驱，也最多有一个后继。,则称该数据结构为线性结构。线性表、栈、队列都属于线性结构。,非线性结构,如果一个数据结构不是线性结构，则称为非线性结构。树、图等都属于非线性结构。,6.1.2 基本概念和术语线性结构,6.1.2 基本概念和术语,常用的数据结构有集合、线性结构、树、图,集合,线性结构,树,图,6.1.2 基本概念和术语常用的数据结构有集合、线性结构、树,6.1.2 基本概念和术语,数据的存储结构：,数据的逻辑结构在计算机存储设备中的映像，包括数据元素的表示和关系的表示。,数据的存储结构有两种：顺序结构和链式存储结构,顺序存储结构,是将逻辑上相邻的元素存储在物理位置上相邻的存储单元里，元素之间的逻辑关系由存储单元的邻接关系来体现，如图所示,6.1.2 基本概念和术语数据的存储结构：数据的逻辑结构在计,6.1.2 基本概念和术语,链式,存储结构,链式存储结构借助于指示数据元素地址的指针表示数据元素之间的逻辑关系。,如图,2,所示,6.1.2 基本概念和术语链式存储结构,6.1.2 基本概念和术语,数据的运算,不同的数据结构各有其相应的若干运算，常用的运算有插入、删除、修改、查找、排序等。,6.1.2 基本概念和术语数据的运算,6.2,几种经典的数据结构介绍,6.2 几种经典的数据结构介绍,6.2,几种经典的数据结构介绍,6.2.1,线性表,6.2.2,栈和队列,6.2.3,树,6.2.4,图,6.2 几种经典的数据结构介绍6.2.1 线性表,6.2.1,线性表,6.2.1 线性表,6.2.1,线性表,复杂的线性表,学号,姓名,性别,专业,出生日期,201307024114,张慧媛,女,计算机,1994-2-25,201307024126,柳青,女,电子信息,1996-4-8,201405034209,韩旭,男,会计,1995-12-12,201405034208,赵琳琳,女,英语,1995-10-10,201405034213,袁小梅,女,安全工程,1996-2-19,6.2.1 线性表复杂的线性表学号姓名性别专业出生日期201,6.2.1,线性表,非空线性表有如下特征：,有且只有一个根结点无前驱；,有且只有一个终端结点无后继；,除根结点与终端结点外，其它结点有且只有一个前驱，也有且只有一个后继；,线性表结点的个数,n,称为线性表的长度。当,n=0,时，称为空表。,6.2.1 线性表非空线性表有如下特征：,6.2.1,线性表,6.2.1 线性表,6.2.1,线性表,顺序表的基本运算,（,2,）删除,线性表的删除运算是指将表的第,i,个元素删去，使长度为,n,的线性表变成长度为,n-1,的线性表，如图,6.6,所示。,6.2.1 线性表顺序表的基本运算,6.2.1,线性表,顺序表的基本运算,（,3,）,查找,查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与被查找的元素相比较，若相等则查找成功，否则返回失败信息。,6.2.1 线性表顺序表的基本运算,6.2.1,线性表,(a),插入前,(b),插入,后,6.2.1 线性表(a)插入前(b)插入后,6.2.1,线性表,单链表的基本运算,（,2,）删除,单链表的删除运算是指删除第,i,个位置的结点，删除操作也需要从单链表的头地址开始遍历，直到找到第,i,个位置的结点。,(a),删除,前,(b),删除后,6.2.1 线性表单链表的基本运算(a)删除前(b)删除后,6.2.1,线性表,单链表的基本运算,（,3,）,查找,单链表中的按值查找是指在表中查找其值满足给定值的结点。查找运算同样还是从头地址开始遍历，依次将被遍历到的结点的值与给定值比较，若相等，则返回查找成功信息，否则返回失败信息。,6.2.1 线性表单链表的基本运算,6.2.2,栈和队列,栈,栈（,Stack,）也可称为堆栈，是一种特殊的线性表，这种线性表只允许在线性表的一端（称为栈顶，,Top,）进行插入和删除运算，而栈的另一端则称为栈底（,Bottom,）。当栈中没有元素时，称为空栈。,栈的基本运算有三种：入栈、出栈与读栈顶元素,6.2.2 栈和队列栈,栈的基本运算,（,1,）入栈运算,入栈运算是指在栈顶位置插入一个新元素，这个运算有两个基本操作：首先将栈顶指针加,1,（,top+1,），然后将新元素插入到栈顶指针指向的位置。若栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不能进行入栈操作。,（,2,）出栈运算,出栈运算是指取出栈顶元素并赋值给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素赋值给指定的变量，然后将栈顶指针减,1,（,top-1,）。若栈顶指针为,0,时，说明栈空，不能进行出栈操作。,（,3,）读栈顶元素,读栈顶元素是指将栈顶元素赋值给一个指定的变量，注意：这个运算不删除栈顶元素，因此栈顶的指针不变。当栈顶指针为,0,时，说明栈空，读不到栈顶元素。,栈的基本运算（1）入栈运算,6.2.2,栈和队列,队列,队列是另一种特殊的线性表，在这种表中，删除运算限定在表的一端进行，而插入操作在表的另一端进行。约定把允许插入的一端称为队尾（,rear,），把允许删除的一端称为队首（,front,）。位于队首和队尾的元素分别叫做队首元素和队尾元素。,队列又被称为先进先出表（,First In First Out,，,FIFO,）,队列,的基本运算有三种：入,队,、出,队,6.2.2 栈和队列队列,队列的基本运算,（,1,）入队运算,入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针加,1,，当,rear=m+1,时置,rear=1,，然后将新元素插入到队尾指针指向的位置。,当循环队列非空（,s=1,）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。,（,2,）出队运算,出队运算是指在循环队列的队首位置退出一个元素并赋值给指定的变量。这个运算有两个操作：首先将队头指针加,1,，并当,front=m+1,时置,front=1,，然后将队头指针指向的元素赋给指定的变量。当循环队列为空（,s=0,）时，不能进行出队运算。,队列的基本运算（1）入队运算,6.2.3,树,树（,tree,）是由,n,（,n,0,）个有限结点组成的一个具有层序关系的集合。把它叫做“树”是因为它看起来像一颗倒置的树。,树具有以下特点。,每个结点有零个或多个子结点；,每个子结点只有一个父结点；,没有前驱的结点为根结点；,除了根结点外，每个子结点可以分为,m,个不相交的子树。,6.2.3 树树（tree）是由n（n0）个有限结点组成的,树,树的相关术语,（,1,）结点：结点包含一个数据元素及描述与其它结点关系的信息（如前驱、后继指针），一般出现在链式存储结构中。,（,2,）结点的度：一个结点含有的子树的个数称为该结点的度。,（,3,）树的度：一棵树中，最大的结点的度称为树的度,树树的相关术语,树,树的相关术语,（,4,）叶结点或终端结点：度为零的结点称为叶结点，也称为叶子结点，叶子结点是无后继结点的。,（,5,）非终端结点或分支结点：度不为零的结点称为非终端结点或分支结点。,（,6,）双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点或双亲结点。孩子结点和双亲结点是相对的。,树树的相关术语,树,树的相关术语,（,7,）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点或孩子结点。,（,8,）结点的层数：树中规定根的层数为,1,，其余结点的层数等于其双亲结点的层数加,1,。,（,9,）树的深度：树中结点层数的最大值称为该树的深度或高度,树树的相关术语,二叉树,二叉树,二叉树,(a),满二叉树,(b),完全,二叉树,二叉树(a)满二叉树(b)完全二叉树,二叉树的存储结构,二叉树的结构是非线性的，每个结点最多可有两个后继。通常用链式存储结构对二叉树进行存储。,二叉树的存储结构二叉树的结构是非线性的，每个结点最多可有两个,二叉树的遍历,二叉树的遍历是指按照一定的规则访问二叉树的各个结点，使每个结点都被且只被访问一次。,二叉树遍历的实质是将非线性结构的数据线性化的过程。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。根据访问根结点的次序二叉树遍历可以分为三种：前序遍历、中序遍历和后序遍历。,二叉树的遍历二叉树的遍历是指按照一定的规则访问二叉树的各个结,二叉树的遍历,(1),前序遍历,访问根结点；前序遍历左子树；前序遍历右子树；,前序遍历结点的次序为：,A,、,B,、,D,、,E,、,H,、,I,、,C,、,F,、,J,、,G,。,(2),中序遍历,中序遍历左子树；访问根结点；中序遍历右子树；,中序遍历结点的次序为：,D,、,B,、,H,、,E,、,I,、,A,、,F,、,J,、,C,、,G,。,(3),后序遍历,后序遍历左子树；后序遍历右子树；访问根结点；,后序遍历结点的次序为：,D,、,H,、,I,、,E,、,B,、,J,、,F,、,G,、,C,、,A,。,二叉树的遍历(1)前序遍历,6.2.4,图,图（,Graph,）是非空的顶点集合和描述顶点之间关系边或弧的集合的组成，如图,6.21,所示。图的定义形式为：,G=(V,E),，其中，,G,表示图，,V,表示顶点的集合，,E,表示边或弧的集合。,6.2.4 图图（Graph）是非空的顶点集合和描述顶点之间,6.2.4,图,图的相关术语,无向图,有向图,顶点的度,6.2.4 图图的相关术语,小 结,1.,数据结构的基本术语,2.,线性表,3.,栈,4.,队列,5.,树,6.,图,小 结1.数据结构的基本术语,