11&12计算机科学导论第十一&十二章-数据结构&抽象数据类型

1第11&12章数据结构和抽象数据类型(DataStructure&AbstractDataType)2定义数据结构，了解其分类抽象数据类型的定义熟练掌握栈和队列的原理及应用广义表的定义及操作树与森林的转换二叉树及其应用二叉排序树的应用哈夫曼树与哈夫曼编码图及其应用最短路及最小生成树哈希表及处理冲突的方法教学目标通过本章的学习，同学们应该能够:31.引言Introduction程序=算法+数据结构程序：为计算机处理问题编制的指令集合算法：处理问题的策略数据结构：问题的数学模型数据结构就是研究数据的组织方式及相应的抽象操作。数据结构是计算机中存储、组织数据的方式。1.1数据结构的研究对象4数据结构大致体系51.2基本概念（1）数据能被输入计算机且能被计算机处理的一切对象。是信息的载体，是客观事物的符号表示。（2）数据元素现实世界中某独立实体的数据描述。是数据结构的基本单位，一般由若干个数据项组成。（3）数据项具有独立意义的最小数据单位，是对数据元素属性的描述。有时称为域或字段。（4）数据对象具有相同特征的数据元素的集合61.3数据结构的分类（逻辑）（1）集合（2）线性结构（3）树型结构（4）图状结构71.3数据结构的分类（存储）（1）顺序存储结构用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。（2）链式存储结构用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。81.4抽象数据类型（ADT）（1）数据类型（DataType）一组值的集合以及定义于这个值集上的一组操作的总称。（2）抽象（Abstract）抽出问题本质的特征而忽略非本质的细节（3）抽象数据类型（AbstractDataType，ADT）一个数据结构以及定义在该结构上的一组操作的总称92.线性表LinearTable2.1线性表的定义线性表是若干个具有相同数据类型的数据元素的有限序列。线性表的长度指数据元素的个数长度为0的线性表称为空表，记作L=()非空线性表记作L=(𝒂𝟏,𝒂𝟐,…,𝒂𝒊,…,𝒂𝒏)，其中𝒂𝒊下标i代表该元素在线性表中的位置102.2线性表的顺序存储结构顺序表：用一段连续的存储单元依次存储线性表中的数据元素。顺序表是一种随机存取的存储结构，在顺序表上进行查找和存取操作，时间复杂度为O(1)，即常数级复杂度。常见顺序表：数组112.2线性表的链式存储结构单链表：用一组任意的存储单元依次存储线性表中的数据元素。单链表是一种顺序存取的存储结构，在单链表上进行查找和存取操作，时间复杂度为O(n)。122.3单链表单链表由若干个结点构成：单链表的结点结构定义：data：数据（值）域，存储数据元素next：指针域，存储该结点后继结点的地址132.3单链表头结点：该结点是特殊结点，值域为空。一个空的单链表只有一个头结点，且头结点的指针域为NULL。引入头结点的目的是为了减少链表特殊情况而导致空指针引用错误，也为了方便实现任意位置插入。头指针：指向头结点的指针尾指针：指向单链表最后一个元素的指针142.3单链表ADT的定义：152.3单链表单链表的尾部插入操作（push_back）尾部插入，即正向建立链表，我们在定义链表的时候引入了尾部指针，这个指针的作用就是用来快速插入尾部元素。此指针需要保证始终指向链表最末端的元素。插入时，我们先需要申请一个Node结点，假设指向该新节点的指针为p，要插入的元素为elem，则现需要初始化该结点p-data=elem。由于此结点是插入到尾部，所以它插入以后就变成了最后一个元素，故需要将指针域置空，即p-next=NULL。如图所示：162.3单链表单链表的尾部插入操作（push_back）接下来，需要将p指针指向的元素添加到tail指向的元素之后：然后tail指针要始终保证指向最后一个元素，所以还需要将tail指向p所指的结点，即执行tail=p：172.3单链表单链表的尾部插入操作（push_back）182.3单链表单链表的头部插入操作（push_front）头部插入，即逆序建链表，逆序建链表不需要tail指针的辅助，只需要利用好head指针和头结点即可，第一步与尾部插入的步骤一样，先生成一个新结点，与尾插一致，区别在第二步，由于新结点需要插入到链表头部，也就是头结点与元素0之间，所以我们需要先将p的指针域指向元素0，保证p所指结点与除头结点外所有结点相连，如图：192.3单链表单链表的头部插入操作（push_front）然后，再把头结点的指针域指向p，使得包括头结点在内所有结点组成线性链：注意，这里顺序不能乱。如果我们先把头结点指针域指向了p，那么头结点与元素0之间的“链子”就会断开，我们就无法再找到元素0了：202.3单链表单链表的头部插入操作（push_front）另外，头部插入有种特殊情况，假设插入前链表为空且引入了尾指针，那么在插入完成后需要将尾指针指向p的指向，其他情况不需要移动尾指针：212.3单链表单链表的头部插入操作（push_front）222.3单链表单链表的任意位置插入（insert）首先先找出任意位置插入的两种特殊情况，假设链表的长度为n，则在位置0插入和在位置n插入属于两种特殊情况。在位置0插入相当于在链表头插入，即push_front，在位置n插入相当于链表尾插入（注意，并不是在n-1插入，想想为什么），相当于push_back。其他情况均属于通常情况。假设我们已有一个含有n元素的单链表，现在要在位置i（非0非n）插入一个新元素p，如图所示：232.3单链表单链表的任意位置插入（insert）在位置i插入，则新元素取代原i元素的位置，原i元素及后面所有元素均链接在新元素之后：然后我们把ptr看做是head，将p插入ptr和元素i之间，与头部插入类似，先p-next=ptr-next;将p的指针域指向元素i242.3单链表单链表的任意位置插入（insert）然后再将ptr的指针域指向p，即ptr-next=p，完成新元素的插入：252.3单链表删除任意位置的元素（del）由于单链表是顺序存取结构，只能通过前置元素找到后继元素，反之则不行。所以我们要删除某个元素，就要事先知晓待删除元素的前置元素。假设待删除元素为元素i，则需要将元素i-1的指针域指向元素i+1，也就是“跳过”元素i，这样元素i就“脱离”了链表的链子，然后再释放它的内存即可：262.3单链表删除任意位置的元素（del）由于i元素是我们要删除的元素，如果此时修改ptr的指针域使链表“跨过”元素i，那么元素i将无法找到，也就不能释放其内存，所以我们需要用一个指针指向它，假设为p，p即待删元素的指针，即p=ptr-next，然后再修改ptr的指针域为元素i的下一元素，也就是ptr-next=p-next，修改过后如图所示：观察上图，实际此时链表中已经没有了i元素，但是需要将i元素从内存中释放。同样，删除也有一种特殊情况，存在尾指针时，如果删除的元素为最后一个元素（n-1元素），则需要修改尾指针指向。272.3单链表删除任意位置的元素（del）282.4顺序表与单链表的比较顺序表：顺序表采用顺序存储结构，即使用一段连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过存储位置来实现，顺序表是随机存取的。单链表：单链表采用链式存储结构，用一组任意的存储单元存放线性表的数据元素，用指针来反映数据元素之间的逻辑关系，单链表是顺序存取的。292.4顺序表与单链表的比较线性表选用场景：（1）若线性表需要频繁查找却很少进行插入或删除操作时，应该采用顺序表作为存储结构；若线性表需要频繁进行增删操作，则应该选用链式存储结构。（2）若线性表中元素个数较多、未知或不固定时，应该采用单链表存储；如果元素个数较少或已知元素最大数量时，应该采用顺序表结构。303.栈和队列StackandQueue3.1栈栈是限定仅在表头进行插入和删除操作的线性表。栈也是一种线性表，不过它的运算和操作受限，不同于链表，栈的元素更改仅限于在其一端进行操作。也就是说，栈只能操作当前的首元素，其他元素不可见也不可访问更不可更改。我们假想栈是一个顶端开口底部封闭的“容器”：31可见，栈有先进后出（FILO）或后进先出（LIFO）的特点。栈的基本运算有以下几种：(1)入栈：Push将数据元素加入栈中（栈顶端）(2)出栈：Pop将顶端数据元素从栈中删除(3)取栈顶：Top获取栈顶数据元素的值(4)获取大小：Size获取栈内元素的数量(5)栈是否空：Empty判断栈是否为空栈（元素数量0）32与链表类似，我们首先定义出栈元素结点的结构，同样含有一个值域和一个指针域栈的结点33我们可以把栈想象成一条链表，只不过这条链表只能从头部插入元素，只能从头部获取元素，也只能从头部删除元素，这个头部，就是我们栈的栈顶。栈的ADT定义34Example1栈具有先进后出FILO（后进先出LIFO）性质，已知栈的输入序列为123，则输出序列有哪几种？123，132，213，231，321扩展：当输入序列为12…n时，经过栈可得的输出序列数量由尤·卡塔南数决定：𝟐𝒏!(n+1)(𝒏!)𝟐Example2若abcdef依次进栈，允许进栈、出栈交替进行，但是不允许连续三次出栈，则不可能得到的出栈序列是？A.dcebfaB.cbdaefC.bcaefdD.afedcb答案：D353.2栈的应用进制转换是栈的一个很典型的应用，我们通常说的使用栈解决进制转换问题是指的十进制转换成N进制，通常使用除基取余法，也叫辗转相除法，图示为2017转为八进制的过程。红色为每步计算的余数，最后余数倒置即为结果。应用1：进制转换36假设这样一个题目：输入两个数X和N，空格间隔，X代表一个十进制正整数，N表示要转换的进制（2=N=16），超过10进制的基数用大写ABCDEF表示。求X的N进制表示。这里我们需要注意的是，超过十进制的基数，也就是说，如果N大于10，那么栈内极有可能有大于等于10的数存在，这时候我们不能原样输出，而是要转换成字母或数码符号。应用1：进制转换37我们日常算术中使用的表达式是中缀式，通常是符号位于操作数中间，这种表达方式需要考虑算符的优先级问题，所以引入括号来强行更改算术优先级。这种中缀式适合人脑计算，比较符合人类的运算习惯，但是对计算机却很不友好，解析难度较大，所以引入了前缀式和后缀式，这两种表达式均没有括号，且无优先级限制，只需要按照书写顺序进行计算即可，不同于中缀式，后缀式只需要使用一个栈进行相关操作即可，而中缀式需要两个栈，一个存符号，一个存操作数。下面分析一个表达式转换问题。我们要做的是将一个中缀表达式转换成后缀表达式（前缀我们暂不考虑，与后缀大同小异），中缀表达式里包含+-*/和括号。应用2：表达式转换38①首先构造一个符号栈，此栈的特点是要求遵循栈内元素自底向上优先级严格递增原则，也就是说，上面的元素优先级必须大于下面的元素优先级（前缀式是大于等于，这点区别一定要记清楚）。②从左向右扫描表达式（前缀式从右向左），逐步判断：a)如果遇到运算数，则直接输出b)如果是运算符，则比较优先级，如果当前运算符优先级大于栈顶运算符优先级（栈空或栈顶为括号时，直接入栈），则将运算符入栈；否则弹出并输出栈顶运算符，直至满足当前运算符大于栈顶运算符优先级（或者栈变空、栈顶为括号）为止，然后再将当前运算符入栈。c)如果是括号，则特殊处理。左括号的话，直接入栈；右括号的话，则不断弹出并输出栈顶符号，直到栈顶符号是左括号，然后弹出栈顶左括号（不输出，因为后缀式没有括号），并忽略当前右括号，继续扫描。d)由以上步骤可知，括号具有特殊的优先级，左括号在栈外的时候，是最高的优先级，在栈内有最低优先级。③重复上述步骤，直到表达式扫描结束，此时若栈内有剩余符号，则将符号依次出栈并输出。应用2：表达式转换39例如：将a*b+(c-d/e)*f转换成后缀表达式，分解步骤如下：应用2：表达式转换Exa