第4 章 链式存储的表、堆栈和队列
- 格式:ppt
- 大小:410.50 KB
- 文档页数:81
数据结构--栈和队列基础知识⼀概述栈和队列,严格意义上来说,也属于线性表,因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据,但由于它们⽐较特殊,因此将其单独作为⼀篇⽂章,做重点讲解。
既然栈和队列都属于线性表,根据线性表分为顺序表和链表的特点,栈也可分为顺序栈和链表,队列也分为顺序队列和链队列,这些内容都会在本章做详细讲解。
使⽤栈结构存储数据,讲究“先进后出”,即最先进栈的数据,最后出栈;使⽤队列存储数据,讲究 "先进先出",即最先进队列的数据,也最先出队列。
⼆栈2.1 栈的基本概念同顺序表和链表⼀样,栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构,如下图所⽰。
从上图我们看到,栈存储结构与之前所了解的线性存储结构有所差异,这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求:1. 栈只能从表的⼀端存取数据,另⼀端是封闭的;2. 在栈中,⽆论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。
拿图 1 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。
因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。
因此,我们可以给栈下⼀个定义,即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。
通常,栈的开⼝端被称为栈顶;相应地,封⼝端被称为栈底。
因此,栈顶元素指的就是距离栈顶最近的元素,拿下图中的栈顶元素为元素 4;同理,栈底元素指的是位于栈最底部的元素,下中的栈底元素为元素 1。
2.2 进栈和出栈基于栈结构的特点,在实际应⽤中,通常只会对栈执⾏以下两种操作:向栈中添加元素,此过程被称为"进栈"(⼊栈或压栈);从栈中提取出指定元素,此过程被称为"出栈"(或弹栈);2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构,因此栈的具体实现有以下两种⽅式:1. 顺序栈:采⽤顺序存储结构可以模拟栈存储数据的特点,从⽽实现栈存储结构。
《数据结构》课程标准学时:72学时(其中:讲课学时:36 上机学时:36 )先修课程:高等数学、C语言程序设计后续课程:软件开发相关的应用性课程(Android应用开发、软件工程等)适用专业:软件技术、移动应用开发、软件与信息服务等开课部门:信息工程与大数据学院一、课程的性质《数据结构》是面向软件技术相关专业的一门专业基础课,课程要求:熟练掌握线性表、栈和队的存储结构及基本操作,并能在相应的应用中正确地选用,培养学生用链式结构编写程序的能力;了解串和广义表的定义和存储结构;掌握数组的存储结构,熟悉稀疏矩阵的两种压缩存储方法的特点及适用范围;了解树的存储结构及特点,掌握二叉树和图的存储结构及其相应算法,培养学生用非线性结构解决实际问题的能力;掌握各种查找、排序方法,培养学生灵活应用已有排序方法的能力,开拓思路编写新的排序算法。
二、课程设计理念数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
精心选择的数据结构可以带来更高的运行或存储效率,数据结构往往同高兴的检索算法和索引技术有关。
1、课程地位理念在许多类型的程序设计中,数据结构的选择是一个基本的设计考虑因素。
许多大型的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。
许多时候,确定了数据结构后,算法就容易得到了。
有些时候事情也会反过来,我们根据特定算法来选择数据结构与之适应。
不论哪种情况,选择合适的数据结构都是非常重要的。
选择了数据结构,算法随之确定,是数据而不是算法是系统构造的关键因素。
2、课程学情理念本课程开设在嵌入式系统工程专科第一学期,学生在学习本课程前已具备计算机基础、C语言基础等知识,本课程力图让学生学会在C语言环境下,运用面向对象的思想编写规范的代码,实现经典的数据结构和算法。
熟悉常用的数据结构和算法,使学生初步具备一个优秀的软件开发人员所应有的基本能力。
顺序存储结构、链式存储结构、索引存储结构、散列存储结构介绍存储结构是指数据在计算机内存或磁盘等存储介质中的组织方式。
在数据结构中,常见的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列存储结构。
下面将分别对这四种存储结构进行详细介绍。
一、顺序存储结构(Sequential Storage Structure):顺序存储结构是将数据元素按照其逻辑次序依次存储在一片连续的存储空间中,即在内存或磁盘上连续存放数据元素。
数据元素之间的逻辑关系通过其在存储空间中的物理位置来表示。
特点:顺序存储结构的存取速度较快,可以通过下标直接访问元素。
插入和删除操作需要移动大量元素,效率较低。
适用于元素数量固定、随机访问频繁的场景,如数组。
二、链式存储结构(Linked Storage Structure):链式存储结构通过使用指针将数据元素存储在不连续的存储空间中,并通过指针将它们连接起来。
每个数据元素中都包含一个指向下一个元素的指针,从而构成了一个链表结构。
特点:链式存储结构的插入和删除操作效率较高,只需要修改指针的指向。
访问某个元素需要从头节点开始遍历,效率较低。
适用于元素数量不固定、插入和删除频繁的场景,如链表。
三、索引存储结构(Indexed Storage Structure):索引存储结构是在顺序存储结构的基础上,为数据元素建立一个索引表,该索引表中的每个索引项包含了一个关键字和对应数据元素在存储空间中的地址。
特点:索引存储结构可以通过索引表快速定位数据元素,减少了遍历的时间。
插入和删除操作需要同时修改索引表和存储空间,效率相对较低。
适用于大型数据库等场景,可以提高查询效率。
四、散列存储结构(Hash Storage Structure):散列存储结构是通过将数据元素的关键字映射到一个散列地址来进行存储和访问的。
具体的映射函数称为散列函数,它将关键字转换为一个固定长度的散列地址。
特点:散列存储结构可以快速定位数据元素,查找效率高。
数据结构(C语言版)(第2版)课后习题答案数据结构课后习题答案李冬梅目录第第第第第第第第1章绪论 ................................................ ................................................... ............... 1 2章线性表 ................................................ ................................................... ........... 5 3章栈和队列................................................. ................................................... ..... 14 4章串、数组和广义表 ................................................ ......................................... 27 5章树和二叉树 ................................................ ................................................... .. 34 6章图 ................................................ ................................................... ................... 44 7章查找 ................................................ ................................................... ............. 55 8章排序 ................................................ ................................................... . (66)II第1章绪论1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
数据结构(⼀)——线性表、栈和队列数据结构是编程的起点,理解数据结构可以从三⽅⾯⼊⼿:1. 逻辑结构。
逻辑结构是指数据元素之间的逻辑关系,可分为线性结构和⾮线性结构,线性表是典型的线性结构,⾮线性结构包括集合、树和图。
2. 存储结构。
存储结构是指数据在计算机中的物理表⽰,可分为顺序存储、链式存储、索引存储和散列存储。
数组是典型的顺序存储结构;链表采⽤链式存储;索引存储的优点是检索速度快,但需要增加附加的索引表,会占⽤较多的存储空间;散列存储使得检索、增加和删除结点的操作都很快,缺点是解决散列冲突会增加时间和空间开销。
3. 数据运算。
施加在数据上的运算包括运算的定义和实现。
运算的定义是针对逻辑结构的,指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。
因此,本章将以逻辑结构(线性表、树、散列、优先队列和图)为纵轴,以存储结构和运算为横轴,分析常见数据结构的定义和实现。
在Java中谈到数据结构时,⾸先想到的便是下⾯这张Java集合框架图:从图中可以看出,Java集合类⼤致可分为List、Set、Queue和Map四种体系,其中:List代表有序、重复的集合;Set代表⽆序、不可重复的集合;Queue代表⼀种队列集合实现;Map代表具有映射关系的集合。
在实现上,List、Set和Queue均继承⾃Collection,因此,Java集合框架主要由Collection和Map两个根接⼝及其⼦接⼝、实现类组成。
本⽂将重点探讨线性表的定义和实现,⾸先梳理Collection接⼝及其⼦接⼝的关系,其次从存储结构(顺序表和链表)维度分析线性表的实现,最后通过线性表结构导出栈、队列的模型与实现原理。
主要内容如下:1. Iterator、Collection及List接⼝2. ArrayList / LinkedList实现原理3. Stack / Queue模型与实现⼀、Iterator、Collection及List接⼝Collection接⼝是List、Set和Queue的根接⼝,抽象了集合类所能提供的公共⽅法,包含size()、isEmpty()、add(E e)、remove(Object o)、contains(Object o)等,iterator()返回集合类迭代器。
第4章链式栈和链式队列4.1 指针与链式结构(Pointers and Linked Structures)4.2 链式栈(Linked Stacks)4.3 带保护的链栈(Linked Stacks with Safeguards)4.4 链式队列(Linked Queues)4.5 应用:多项式的表示和实现(Application: Polynomial Arithmetic)4.6 抽象数据类型及其实现(Abstract Data Types and Implementations)4.1 指针与链式结构4.1.1指针n指针类型(也称为存取类型,或访问类型,或引用类型)是这样的数据类型,其值集由指向其它数据对象的指针(即地址)构成。
指针的概念最初是在PL/I语言提出的,目前已被广泛地用于各种高级程序设计语言,如Pascal、C、Modula、Ada等语言。
n用指针类型可以建立和使用任意复杂的数据结构,动态地分配内存,从而提高程序执行效率。
但指针类型的使用使得程序的可读性有所降低,并且使得程序可靠性降低。
n在许多高级程序设计语言中,对指针的定义与引用都是类似的。
在C++中,一个指针也被称为一个链(link),或一个引用(reference)。
n1. 指针变量的定义n在C语言中,指针变量是通过单目运算符"*"来定义的。
指针定义的一般形式为:n<类型名> * <指针变量名>n2.指针变量的引用n在C语言中,有关指针的运算符有两个单目运算符"*"及"&"。
n单目运算符"*"称为指针运算符,或称为间接访问运算符,其运算对象只能是地址或指针。
它的功能是对它所操作的地址空间的间接引用,即表示引用其后的地址或指针所指的单元内容n3.指针变量的应用n用指针变量可以构造链表。
在链表是使用过程中,要应用到动态“存储分配”的概念。
第1xx绪论5.选择题(1)在数据结构中,从逻辑上可以把数据结构分成()。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。
A.存储结构B.存储实现C.逻辑结构D.运算实现(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着()。
A.数据具有同一特点B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等(4)以下说法正确的是()。
A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构说明:注意几个概念:数据项是数据的最小单位而不是基本单位,数据元素才是数据的基本单位,数据结构是带有结构的数据元素的集合而不是数据项的集合。
(5)以下与数据的存储结构无关的术语是()。
A.顺序队列B.链表C.有序表D.链栈说明:数据的存储结构只有数组(或称为顺序存储)和链表两种。
顺序队列是用数组存储的队列,链表和链栈都是用链表。
(6)以下数据结构中,()是非线性数据结构A.树B.字符串C.队D.栈第2xx线性表1.选择题(1)一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。
A.110B.108C.100D.120说明:计算公式:A+(i-1)*L,A为起始地址,i是元素序号,L是元素长度。
(2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是()。
A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D.将n个结点从小到大排序(3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动的元素个数为()。
数据结构( Java 版) 习题解答与实验指导目录第1 章绪论11.1 数据结构的基本概念11.2 算法2第2 章线性表32.1 线性表抽象数据类型32.2 线性表的顺序存储和实现42.2.1 线性表的顺序存储结构42.2.2 顺序表52.2.3 排序顺序表72.3 线性表的链式存储和实现92.3.1 单链表9【习题2-8】单链表结点类问题讨论。
9【习2.1 ]使用单链表求解Josephu环问题。
12【习2.2】集合并运算,单链表深拷贝的应用。
142.3.2 双链表16【习2.3] 循环双链表的迭代方法。
19【习2.4] 循环双链表合并连接。
19第3 章串213.1 串抽象数据类型213.2 串的存储和实现223.2.1 串的存储结构223.2.2 常量字符串类22【习3.1 ] C/C++语言,str in g.h 中的strcpy()和strcat()函数存在下标越界错误。
22【思考题3-1】逆转String串,分析算法效率。
24【实验题3-1】MyString 类,比较串大小,忽略字母大小写。
25【例3.2思考题3-2] Mylnteger整数类,返回value的radix进制原码字符串。
26【实验题3-9] 浮点数类。
273.2.3 变量字符串类30【实验题3-11]删除变量串中的所有空格。
4-样卷303.3 串的模式匹配313.3.1 Brute-Force模式匹配算法313.3.2 模式匹配应用32【思考题3-4,实验题3-13 ] MyString 类,replaceAII(pattern,s)改错。
323.3.3 KMP模式匹配算法33第4 章栈和队列364.1 栈364.2 队列384.3 递归41【习4.1 】打印数字塔。
41第5 章数组和广义表435.1 数组435.2 特殊矩阵的压缩存储445.2.1 三角矩阵、对称矩阵和对角矩阵的压缩存储445.2.2 稀疏矩阵的压缩存储465.3 广义表48第6 章树和二叉树496.2 二叉树496.3 线索二叉树566.4 Huffman 树616.5 树的表示和实现62第7 章图637.1 图及其抽象数据类型637.2 图的表示和实现647.3 图的遍历657.4最小生成树677.5最短路径69 第8章查找728.1查找的基本概念728.2二分法查找738.4散列748.5二叉排序树7676【实验8-1】判断一棵二叉树是否为二叉排序树,改错。
第4章栈和队列一、复习要点本章主要讨论3种线性结构:栈、队列与优先级队列。
这3种结构都是顺序存取的表,而且都是限制存取点的表。
栈限定只能在表的一端(栈顶)插入与删除,其特点是先进后出。
队列和优先级队列限定只能在表的一端(队尾)插入在另一端(队头)删除,不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整,令优先级最高的对象调整到队头,其特点是优先级高的先出。
而队列不调整,其特点是先进先出。
这几种结构在开发各种软件时非常有用。
本章复习的要点:1、基本知识点要求理解栈的定义和特点,栈的抽象数据类型和在递归和表达式计算中的使用,在栈式铁路调车线上当进栈序列为1, 2, 3, , n时,可能的出栈序列计数,栈的顺序存储表示和链接存储表示,特别要注意,链式栈的栈顶应在链头,插入与删除都在链头进行。
另外,需要理解队列的定义和特点,队列的抽象数据类型和在分层处理中的使用,队列的顺序存储表示(循环队列)和链接存储表示,需要注意的是,链式队列的队头应在链头,队尾应在链尾。
还需要理解优先级队列的定义和特点。
优先级队列的最佳存储表示是堆(heap),本章介绍的表示看懂即可。
2、算法设计➢栈的5种操作(进栈、退栈、取栈顶元素、判栈空、置空栈)的在顺序存储表示下的实现,以及在链接存储表示下的实现。
➢使用栈的后缀表达式计算算法➢循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现➢链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现二、难点和重点1、栈:栈的特性、栈的基本运算➢栈的数组实现、栈的链表实现➢栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用:用后缀表示计算表达式,中缀表示改后缀表示3、队列:队列的特性、队列的基本运算➢队列的数组实现:循环队列中队头与队尾指针的表示,队满及队空条件➢队列的链表实现:链式队列中的队头与队尾指针的表示、三、习题的解析4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台,如右图所示。
第1-3章习题一、选择题1.若进栈序列为a,b,c,d,进栈过程中可以出栈,则 c 不可能是一个出栈序列。
A) a,d,c,b B) b,c,d,a C) c,a,d,b D) c,d,b,a6.设用一维数组A[1,…,n]来存储一个栈,令A[n]为栈底,用整型变量T指示当前栈顶位置,A[T]为栈顶元素。
当从栈中弹出一个元素时,变量T将变化为 A 。
A)T=T + 1 B) T=T – 1 C) T不变D) T= n7. 一个栈的入栈序列为a,b,c,d,e,则栈不可能的出栈序列是 C 。
A) e d c b a B) d e c b a C) d c e a b D) a b c d e8.若语句S的执行时间为O(1),那么下列程序段的时间复杂度为 B 。
For(i = 0; i <= n ; i++)For(j = 0; j <=n ;j++)sA) O(n) B)O(n*n) C) O(n*log2n) D) O(n*i)18.设计一个判断表达式中左右括号是否配对的算法,采用 C 数据结构最佳。
A) 队列B) 堆栈C)二叉树D) 链表24.一个队列的入队序列是1,2,3,4,则队列的输出序列是 C 。
A) 1,4,3,2 B) 4,3,2,1 C) 1,2,3,4 D) 3,2,4,129.在一个单链表中,若要删除P结点的后续结点,则应执行 A 。
A) P->next = P->next->next B) p = P->next; P->next = P->next->next C) delete(P->next) D) p = P->next->next30.在计算递归函数时,如不使用递归过程,则一般情况下必须借助于 A 数据结构。
A)栈B) 树C) 双向队列D) 广义表41.下列叙述中,正确的是 B 。
A) 用指针的方式存储一棵有n个结点的二叉树最少需要n+1个指针B)不使用递归,也可以实现二叉树的前序、中序和后序遍历C) 已知树的前序遍历并不能唯一确定一棵树,因为不知道树的根结点是哪一个D) 任一棵树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间50.以下有关数据结构的叙述,正确的是 C 。
数据结构栈和队列知识点总结一、栈的基本概念栈是一种线性数据结构,具有后进先出(LIFO)的特点。
栈有两个基本操作:入栈(push)和出栈(pop)。
入栈指将元素压入栈中,出栈指将最近压入的元素弹出。
二、栈的实现方式1. 数组实现:利用数组来存储元素,通过一个变量来记录当前栈顶位置。
2. 链表实现:利用链表来存储元素,每个节点包含一个数据域和一个指向下一个节点的指针。
三、应用场景1. 表达式求值:使用两个栈分别存储操作数和运算符,按照优先级依次进行计算。
2. 函数调用:每当调用一个函数时,就将当前函数的上下文信息压入调用栈中,在函数返回时再弹出。
3. 浏览器历史记录:使用两个栈分别存储浏览器前进和后退的网页地址。
四、队列的基本概念队列是一种线性数据结构,具有先进先出(FIFO)的特点。
队列有两个基本操作:入队(enqueue)和出队(dequeue)。
入队指将元素加入到队列尾部,出队指从队列头部删除元素。
五、队列的实现方式1. 数组实现:利用数组来存储元素,通过两个变量分别记录队列头和队列尾的位置。
2. 链表实现:利用链表来存储元素,每个节点包含一个数据域和一个指向下一个节点的指针。
六、应用场景1. 广度优先搜索:使用队列来保存待访问的节点,按照层次依次访问。
2. 线程池:使用队列来保存任务,线程从队列中取出任务进行处理。
3. 缓存淘汰策略:使用队列来维护缓存中元素的顺序,根据一定策略选择删除队首或队尾元素。
七、栈和队列的比较1. 栈是一种后进先出的数据结构,而队列是一种先进先出的数据结构。
2. 栈只能在栈顶进行插入和删除操作,而队列可以在两端进行操作。
3. 栈可以用于回溯、函数调用等场景,而队列适合于广度优先搜索、缓存淘汰等场景。
八、常见问题及解决方法1. 栈溢出:当栈空间不够时,会发生栈溢出。
解决方法包括增加栈空间大小、减少递归深度等。
2. 队列空间浪费:当使用数组实现队列时,可能会出现队列空间不足的情况。