《第3章_数据结构》由会员分享，可在线阅读，更多相关《第3章_数据结构（50页珍藏版）》请在金锄头文库上搜索。
1、1第三章第三章数 据 结 构2什么是数据结构什么是数据结构u数据结构是数据存在的形式。数据结构是数据存在的形式。u数据结构是在整个计算机科学与技术领域上广泛被使数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么数据由那些成分数据构成，以什么方式构成，呈什么结构结构 。u数据结构分为：数据结构分为：逻辑上的数据结构反映成分数据之间的逻辑关系；逻辑上的数据结构反映成分数据之间的逻辑关系；物理上的数据结构反映成分数据在计算机内部的存物理上的数据结构反映成分数据在计算机
2、内部的存储安排。储安排。3什么是数据结构什么是数据结构u数据结构是信息的一种组织方式，其目的是为了提高算数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。算法集合可以对数据结构中的数据进行某种操作。u数据结构作为一门学科主要研究数据的各种逻辑结构和数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：方面的内容：数据的逻辑结构数据的逻辑结构 线性线性( (线
3、性表，栈，队列，向量，线性表，栈，队列，向量， 字符串，多维字符串，多维数组，广义表数组，广义表) )，树树，图图，文件文件数据结构主要研数据结构主要研究什么？究什么？4什么是数据结构什么是数据结构数据的物理存储结构数据的物理存储结构顺序方法、索引方法、散列方法顺序方法、索引方法、散列方法对数据的操作（或算法）对数据的操作（或算法） 通常，算法的设计取决于数据的逻辑结构，算法的实通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。现取决于数据的物理存储结构。5为什么要学习数据结构为什么要学习数据结构u计算机的应用的飞速发展，计算机的应用已经不在局计算机的应用的飞速发展，计
4、算机的应用已经不在局限于科学计算，大量非数值计算的应用需要处理各种限于科学计算，大量非数值计算的应用需要处理各种具有一定结构的数据，为此需分析待处理对象的特征具有一定结构的数据，为此需分析待处理对象的特征以及各处理对象之间的关系。因此：以及各处理对象之间的关系。因此： 数据结构也可以认为是一门研究非数值计算的程序设数据结构也可以认为是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。作等等的学科。u程序程序 = 算法算法 + 数据结构数据结构 u同时数据结构也是计算机各有关专业核心基础课程同时数据结构也是计算机各
5、有关专业核心基础课程6为什么要学习数据结构为什么要学习数据结构u它研究了计算机需要处理的数据对象和对象之间的它研究了计算机需要处理的数据对象和对象之间的关系。关系。u它刻画了应用中涉及到的数据的逻辑组织。它刻画了应用中涉及到的数据的逻辑组织。u它描述了数据在计算机中如何存储、传送、转换。它描述了数据在计算机中如何存储、传送、转换。7主要内容内容：串表队列图数组栈树83.1 串一、应用领域一、应用领域二、定义二、定义三、存储结构三、存储结构四、运算四、运算93.1 3.1 串串一、应用领域一、应用领域非数值处理对象，由按一定顺序排列的各种字符非数值处理对象，由按一定顺序排列的各种字符组成组成在程
6、序中可以作为常量和变量，通过变量名可以在程序中可以作为常量和变量，通过变量名可以调用调用信息检索系统、文字编辑系统、问答系统、自然信息检索系统、文字编辑系统、问答系统、自然语言翻译系统、词法分析系统、音乐分析程序等语言翻译系统、词法分析系统、音乐分析程序等103.1 3.1 串串二、定义二、定义v由零个或多个字符组成的有限序列由零个或多个字符组成的有限序列, ,记作记作：S = a1 a2 anv子串子串有两个字串有两个字串S S1 1 = a = a1 1 a a2 2 a an n， S S2 2 = b = b1 1b b2 2 b bm m，如果存在整数如果存在整数i i，使得使得b
7、bj j = = a ai+ji+j j = 1, 2, , mj = 1, 2, , m则称则称S S2 2是是S S1 1的子串的子串串名串值113.1 3.1 串串三、存储结构三、存储结构v顺序存放顺序存放特点特点查询快查询快更新慢更新慢Howareyou?Howareyou?按字节编址Howareyou?按字编址无压缩按字编址压缩存放节省存储空间，单字节操作不方便Howdoyou?更新需移动多个存储单元123.1 3.1 串串v链式存放链式存放在每一字符串之后开辟一在每一字符串之后开辟一定大小的存储空间，用来定大小的存储空间，用来存放下一字符串所在存储存放下一字符串所在存储位置的起始地
8、址，这块附位置的起始地址，这块附加的存储空间称为指针域加的存储空间称为指针域特点特点不必把一组字符串存放在连不必把一组字符串存放在连续的存储单元中续的存储单元中删除或插入字符串时，仅需删除或插入字符串时，仅需改变相关指针改变相关指针查找速度慢查找速度慢Who20is30Wa ng40Fe nYu 50指针133.1 3.1 串串Who20is30Wa ng50Fe nWho20is30Wa ng40Fe nYu 50删除操作插入操作Li60143.1 3.1 串串四、运算四、运算v给一个字符串变量名赋值给一个字符串变量名赋值S abcS S1v比较两字符串是否相等比较两字符串是否相等strcm
9、p(S1, S2) v从一个字符串的指定位置截取一定长度的子串从一个字符串的指定位置截取一定长度的子串substr(S1,i, j)v将两字符串合并形成一个新的字符串将两字符串合并形成一个新的字符串S1 / S2 = a1 a2 anb1b2 bm153.2 数组一、定义一、定义二、表示二、表示三、存储方式三、存储方式163.2 3.2 数组数组一、定义一、定义一组具有相同属性的数据元素（数据类型、数据一组具有相同属性的数据元素（数据类型、数据长度相同）按一定方式进行排列，使得其中每一长度相同）按一定方式进行排列，使得其中每一数据元素都能由一个整数序列唯一确定它的位置，数据元素都能由一个整数序
10、列唯一确定它的位置，这样的数据结构称为数组。这样的数据结构称为数组。173.2 3.2 数组数组二、表示二、表示name(1)=“张三张三”name(2)=“李四李四”name(3)=“王五王五”name(4)=“马六马六”姓名姓名英语英语数学数学物理物理张三张三908688李四李四958482马六马六807572一维数组一维数组二维数组二维数组183.2 3.2 数组数组三、存储方式三、存储方式v用一组连续的存储单元来存放数组元素的值用一组连续的存储单元来存放数组元素的值 一维数组一维数组对于一个有对于一个有n n个元素组成的一维数组个元素组成的一维数组 a a1 1, a, a2 2, ,
11、 a, , an n 设每一个元素占用设每一个元素占用1 1个存储单元，若第一个数据元素存放的地址个存储单元，若第一个数据元素存放的地址是是addr(a(1)addr(a(1)，则第则第i i个数据元素的存放地址为个数据元素的存放地址为addr(a(iaddr(a(i) = addr(a(1) + (i ) = addr(a(1) + (i 1) 1)a(1)a(2)a(i)a(n)193.2 3.2 数组数组二维数组二维数组对于一个对于一个m m列列n n行的二维数组行的二维数组a(1, 1)a(1, 2)a(1,m)a(1, 1)a(1, 2)a(1,m)a(i, j)a(n, 1)a(n
12、, 2)a(n,m)a(1, 1)a(1, m)a(2, 1)a(2,m)a(n,1)a(n,m)a(1, 1)a(n, 1)a(1, 2)a(n, 2)a(1,m)a(n,m)按行存储按列存储按行存储addr(a(i, j) = addr(a(1, 1)+ (i 1)m + j -1按列存储addr(a(i, j) = addr(a(1, 1)+ (j 1)n + i -1203.3 表一、定义一、定义二、运算二、运算三、存储方式三、存储方式21数据数据项项3.3 3.3 表表一、定义一、定义表是一组有序的数据元素表是一组有序的数据元素每一数据元素包含一个或多个数据项每一数据元素包含一个或多
13、个数据项每一数据元素与唯一的关键字相关联每一数据元素与唯一的关键字相关联学号学号姓名姓名性别性别年龄年龄系别系别19808801赵仁赵仁男男28计算机系计算机系19901023钱广钱广男男23数学系数学系19701001李惠李惠女女25数学系数学系行：数行：数据元素据元素关键关键字字223.3 3.3 表表二、运算二、运算求出一个表所含数据元素个数求出一个表所含数据元素个数对于给定关键字，查找表中相应数据元素对于给定关键字，查找表中相应数据元素在表中指定位置上插入一个数据元素在表中指定位置上插入一个数据元素删除表中指定位置上的数据元素删除表中指定位置上的数据元素按某种要求对表中数据元素重新排序
14、按某种要求对表中数据元素重新排序233.3 3.3 表表三、存储方式三、存储方式v顺序存放顺序存放把表中元素依次存放在一组连续的单元内把表中元素依次存放在一组连续的单元内访问方便快捷，更新操作复杂访问方便快捷，更新操作复杂设表的基地址为设表的基地址为addr(aaddr(a1 1) )，假定每个数据元素占用假定每个数据元素占用k k 个存储单元，则的存储单元的首地址为个存储单元，则的存储单元的首地址为addrai = addr(a1) + (i - 1) k243.3 3.3 表表v链式存放链式存放表的每一记录增设一个指针，指明后继元素的表的每一记录增设一个指针，指明后继元素的存储单元的首地址
15、存储单元的首地址特点特点无须连续和顺序排放无须连续和顺序排放更新简单更新简单增加空间开销增加空间开销检索必须从链头开始，效率低检索必须从链头开始，效率低253.4 栈一、定义一、定义二、特性二、特性三、存储三、存储四、操作四、操作263.4 3.4 栈栈一、定义一、定义栈是一种操作受限的线性表栈是一种操作受限的线性表对于栈的插入和删除操作都限制在表的末端进行对于栈的插入和删除操作都限制在表的末端进行将表的末端称为栈顶，起始位置称为栈底将表的末端称为栈顶，起始位置称为栈底二、特性二、特性每次删除的总是最后插入的表目，而最先插入的表每次删除的总是最后插入的表目，而最先插入的表目则放在栈的底部，要到
16、最后才能删除，因此栈是目则放在栈的底部，要到最后才能删除，因此栈是“后进先出表后进先出表”或下推表或下推表食堂里的一叠盘子食堂里的一叠盘子算术表达式、递归算术表达式、递归273.4 3.4 栈栈三、存储三、存储用向量（由相同数据类型组成的线性序列）表示栈，用向量（由相同数据类型组成的线性序列）表示栈，并用指针指示栈顶的位置并用指针指示栈顶的位置aiai-1a2a1栈栈底底栈栈顶顶栈顶指示器栈顶指示器i283.4 3.4 栈栈四、操作四、操作push(ST, X)push(ST, X)：往栈往栈STST中压入一个值为中压入一个值为X X的表目的表目pop(ST)pop(ST)：从栈从栈STST中
17、弹出一个表目中弹出一个表目top(ST, X)top(ST, X)：把栈顶表目的值读到变量把栈顶表目的值读到变量X X中，栈保中，栈保持不变持不变sempty(STsempty(ST) )：判断栈是否为空判断栈是否为空栈空间大小是预先设定的，称为栈容量，如果栈栈空间大小是预先设定的，称为栈容量，如果栈已存满，再进行已存满，再进行pushpush操作，则栈将上溢出操作，则栈将上溢出(overflow)(overflow)；如果栈里已没有表目，再进行如果栈里已没有表目，再进行poppop操操作，则栈将下溢出作，则栈将下溢出(underflow)(underflow)293.5 队列一、定义一、定义
18、二、存储二、存储三、操作三、操作303.5 3.5 队列队列一、定义一、定义队列是一种操作受限的线性表队列是一种操作受限的线性表对于队列的插入在表的一端进行，删除操作在表的对于队列的插入在表的一端进行，删除操作在表的另一端进行另一端进行进行删除的一端称为队列的头，进行插入的一端称进行删除的一端称为队列的头，进行插入的一端称为队列的尾为队列的尾新来的成员总是加入到队尾，每次离开的总是队头新来的成员总是加入到队尾，每次离开的总是队头上的元素上的元素( (先进先出先进先出) )313.5 3.5 队列队列二、存储二、存储用顺序表实现，分配一块连续存储区域存放队列用顺序表实现，分配一块连续存储区域存放
19、队列中的元素，用两个指针分别指向队列的头尾中的元素，用两个指针分别指向队列的头尾当队列首尾指针相连时，发生队列溢出当队列首尾指针相连时，发生队列溢出aiai+1aj头指头指针针尾指尾指针针a an-1n-1a an n头指头指针针尾指尾指针针假溢假溢出出323.5 3.5 队列队列三、操作三、操作enq(QUenq(QU, X), X)：往队列往队列QUQU中插入一个值为中插入一个值为X X的表目的表目deq(QUdeq(QU) )：从队列从队列QUQU中删除一个表目中删除一个表目front(QU, X)front(QU, X)：把队列把队列QUQU头部表目的值读到变量头部表目的值读到变量X
20、X中中qempty(QUqempty(QU) )：判断队列是否为空判断队列是否为空a ai ia ai+1i+1a aj ja aj+1j+1头指头指针针尾指尾指针针a ai ia ai+1i+1a aj j头指头指针针尾指尾指针针 插插入入a aj+1j+1 删删除除a ai i333.6 树一、定义一、定义二、树的遍历二、树的遍历三、存储方式三、存储方式343.6 3.6 树树一、定义一、定义v树结构是节点之间有分支的、层次的关系的结构树结构是节点之间有分支的、层次的关系的结构v树结构是非线性结构树结构是非线性结构线性：线性：数据元素能按一定的顺序进行排列，其中除数据元素能按一定的顺序进行
21、排列，其中除第一和最后一个外，其它元素都有一个唯一的前驱第一和最后一个外，其它元素都有一个唯一的前驱元素和后继元素，即元素之间存在着唯一的关系元素和后继元素，即元素之间存在着唯一的关系v树树树是树是n个节点的有穷集合个节点的有穷集合K，满足：满足：有且仅有一个节点没有前驱，称为树的根有且仅有一个节点没有前驱，称为树的根除根之外，其他节点有且仅有一个前驱除根之外，其他节点有且仅有一个前驱任一节点都存在一个从根到该节点的节点序列任一节点都存在一个从根到该节点的节点序列353.6 3.6 树树树是包含树是包含n个节点的有限集合，满足个节点的有限集合，满足 有且仅有一个节点没有前驱，称为树的根有且仅有
22、一个节点没有前驱，称为树的根 除根之外的其他节点被分成除根之外的其他节点被分成m m个不相交的集合，而个不相交的集合，而且这些集合的每一个又都是树且这些集合的每一个又都是树树的一枝所含子节点的数目称为度，各节点度的最大树的一枝所含子节点的数目称为度，各节点度的最大值称为树的度值称为树的度数据结构数据结构线性结构线性结构非线性结构非线性结构数数组组串串表表栈栈队队列列树树图图根节根节点点内部内部节点节点叶节点叶节点363.6 3.6 树树ABCGHFDEJIABCGHFDEJI(A(B(D)(E(I)(J)(F)(C(G)(H)树形表示树形表示文氏图表示文氏图表示嵌套括号表嵌套括号表示示373.
23、6 3.6 树树二、树的遍历二、树的遍历v遍历：将树节点放入一个线性序列的过程遍历：将树节点放入一个线性序列的过程v按深度的方向遍历按深度的方向遍历先根次序先根次序访问头一棵树的根访问头一棵树的根在先根次序下遍历头一棵树树根的子树在先根次序下遍历头一棵树树根的子树在先根次序下遍历其他的树在先根次序下遍历其他的树ABCGHFDEJIA B D E I J F C G H383.6 3.6 树树后根次序后根次序在后根次序下遍历头一棵树树根的子树在后根次序下遍历头一棵树树根的子树访问头一棵树的根访问头一棵树的根在后根次序下遍历其他的树在后根次序下遍历其他的树ABCGHFDEJID I J E F B
24、 G H CA393.6 3.6 树树v按宽度的方向遍历按宽度的方向遍历首先访问层数为首先访问层数为0 0的节点，然后依次访问层数为的节点，然后依次访问层数为1 1的的节点，直到访问完最下一层的所有节点节点，直到访问完最下一层的所有节点ABCGHFDEJIABCDEFGHIJ403.6 3.6 树树三、存储方式三、存储方式v一般采用链表存储一般采用链表存储数据数据指针指针1指针指针2指针指针m指向直接指向直接后继节点后继节点ABCGHFDE数据数据指针指针1指针指针2指针指针3指针指针4ABCBDEFCGHDEFGH413.7 图一、定义一、定义二、存储二、存储423.7 3.7 图图一、定义
25、一、定义有限的节点集合有限的节点集合K K，对，对K K中节点的前驱和后继节点的个数不中节点的前驱和后继节点的个数不加限制，则就是图结构加限制，则就是图结构用用G=(V, E)G=(V, E)表示一个图，图的节点称为顶点，表示一个图，图的节点称为顶点，V V是有穷顶是有穷顶点的集合，节点的偶对称为边，点的集合，节点的偶对称为边，E E是边的集合是边的集合如果节点的偶对是无序的，则称为如果节点的偶对是无序的，则称为无向图无向图；如果节点的偶；如果节点的偶对是有序的，则称为对是有序的，则称为有向图有向图在无向图中，若顶点在无向图中，若顶点ViVi与与VjVj之间有一条边之间有一条边(Vi, (Vi
26、, VjVj) )，则称则称ViVi与与VjVj邻接，称边邻接，称边(Vi, (Vi, VjVj) )依附于顶点依附于顶点Vi, Vi, VjVj；依附于顶依附于顶点边的个数称为点边的个数称为度度在有向图中，进入该顶点的有向边的个数为入度，由该顶在有向图中，进入该顶点的有向边的个数为入度，由该顶点引出的有向边的个数为出度，点引出的有向边的个数为出度，度度= =入度入度+ +出度出度433.7 3.7 图图V2V1V3V4V=V1,V2,V3,V4E=(V1,V2), (V2,V3), (V1,V4), (V2,V4) (V3,V4)V2V1V3V4V=V1,V2,V3,V4E=(V1,V2),
27、 (V1,V4), (V2,V3), (V3,V2) (V4,V3)度为度为3度为度为2出度为出度为1入度为入度为2度为度为3443.7 3.7 图图二、存储二、存储v相邻矩阵表示法相邻矩阵表示法若若G G是一个具有是一个具有n n个节点的有向图，则个节点的有向图，则G G的相邻矩阵为：的相邻矩阵为：Ai, j =1 若(Vi,Vj)或(Vj,Vi)是图G的边0 若(Vi,Vj)或(Vj,Vi)不是图G的边V2V1V3V40101101101011110V2V1V3V40101001001000010453.7 3.7 图图v邻接表表示法邻接表表示法节点表节点表 + + 边表边表节点表：数据域
28、节点表：数据域 + + 指针域（指指针域（指向此节点的边表）向此节点的边表）边表：每个表目对应一条边，包边表：每个表目对应一条边，包括与此边相关联的另一个节点序括与此边相关联的另一个节点序号号 + + 指向下一个表目的指针指向下一个表目的指针V2V1V3V4V1V2V3V42413244123463.7 3.7 图图V2V1V3V4V1V2V3V424323V1V2V3V413241出出边边表表入入边边表表473.7 3.7 图图三、图的遍历三、图的遍历v遍历：遍历：从图中某一点出发访问图中其余顶点，或当从图中某一点出发访问图中其余顶点，或当给定的图是连通图，则从图中任意一点出发顺着某给定的图
29、是连通图，则从图中任意一点出发顺着某些边可以访问到该图中的所有的顶点，且使每一个些边可以访问到该图中的所有的顶点，且使每一个顶点仅被访问一次。顶点仅被访问一次。深度优先搜索：深度优先搜索：广度优先搜索：广度优先搜索：483.7 3.7 图图三、图的遍历三、图的遍历v深度优先搜索：深度优先搜索： 设从图（，）中某一顶点设从图（，）中某一顶点出发，出发，在访问了任意一个和在访问了任意一个和邻接的顶点邻接的顶点后，后，出发访问和出发访问和邻接且未被访问过的任意顶点邻接且未被访问过的任意顶点。然后，从。然后，从出发进行如上的访问。重出发进行如上的访问。重复这种访问，直到一个顶点的所有邻接点都复这种访问
30、，直到一个顶点的所有邻接点都被访问过为止，接着退回到尚有邻接点未被被访问过为止，接着退回到尚有邻接点未被访问过的顶点，再从该顶点出发，重复上述访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有的被访问过的顶点的邻搜索过程，直到所有的被访问过的顶点的邻接点都已被访问到为止。接点都已被访问到为止。12345678493.7 3.7 图图三、图的遍历三、图的遍历v广度优先搜索广度优先搜索从图中某一顶点从图中某一顶点0 0出发，首先依次访出发，首先依次访问问0 0的邻接的顶点的邻接的顶点， ，。然后，再顺序访问。然后，再顺序访问， ，的所有的邻接点（已被访问过的的所有的邻接点（已被访问过的顶点除外），再从这些被访问的点出发，顶点除外），再从这些被访问的点出发，逐次进行访问，依次类推，直到所有顶逐次进行访问，依次类推，直到所有顶点都被访问到为止。点都被访问到为止。 1234567850
