例题讲解数据结构算法.pptx

例题讲解,基本概念,什么是数据？什么是数据元素？什么是数据结构？数据结构的要素是什么？数据逻辑结构的分类。数据存储结构的分类。数据类型与抽象数据类型。算法的概念及五个要素。算法的性能分析：时间复杂度和空间复杂度。Clog2nnnlog2nn2n32n3nn!nn,顺序存储表示数据元素之间的逻辑关系是由（）表示的，链接存储表示数据元素之间的逻辑关系是由（）表示的。A指针B逻辑顺序C存储位置D问题的上下文下面关于抽象数据类型的描述，不正确的是（）。A数据封装B使用与实现分离C信息隐藏D用例驱动算法的时间复杂度与（）有关。A问题规模B计算机硬件的运行速度C源程序的长度D编译后执行程序的质量某算法的时间复杂度是O(n2)，表明该算法（）。A问题规模是n2B问题规模与n2成正比C执行时间等于n2D执行时间与n2成正比以下关于数据结构的说法中，错误的是（）。A数据结构相同，对应的存储结构也相同B数据结构涉及数据的逻辑结构、存储结构及操作三个方面C数据结构操作的实现与存储结构有关D定义逻辑结构时可不考虑存储结构试举一个例子，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。答：例如，线性表中的插入与删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n);而在链式存储方式下，插入与删除时间复杂度都是O(1)。,数组元素循环右移K位时空权衡,设计一个算法，将数组A0.n-1中的元素循环右移K位。要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。算法一：采用K次循环进行右移。算法二：采用K个辅助空间的右移K位。算法三：右移K位的海豚算法。算法四：利用三组置逆，完成右移K位。,有实现同一功能的两个算法A1和A2，其中A1的渐近时间复杂度T1(n)=O(2n)，A2的渐近时间复杂度是T2(n)=O(n2)。仅就时间复杂度，具体分析这两个算法哪个好？分析：比较算法好坏需要比较两个函数。,线性表定义线性表的特点线性表的操作,例seq,例seq1：设有一个线性表(e1,e2,e3,en)存放在一个一维数组A的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容转换为(en,e3,e2,e1)。例seq2：假定数组An中有多个零元素，试写出一个函数，将A中所有的非零元素依次移到数组A的前端Ai(0=i=n-1)。例seq3：试编写一个函数，将一个有n个非零元素的整数一维数组An拆分为两个一维数组，使得A中大于零的元素存放在B中，小于零的元素存放在C中。例seq4：已知在一维数组Am+n中依次存放着两个顺序表(a1,a2,am)和(b1,b2,bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,bn)放在(a1,a2,am)的前面。例seq5：试编写一个函数，以不多于3*n/2的平均比较次数，在一个有n个整数的顺序表A中找出具有最大值和最小值的整数。,Seq综合,基于线性表的顺序存储表示（顺序表）实现以下函数。（1）从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。（2）从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。（3）向顺序表中第i个位置插入一个新的元素。如果i不合理则显示出错信息并退出运行。（4）从顺序表中删除具有给定值x的所有元素。（5）从顺序表中删除其值在给定值s与t之间（要求s小于或等于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。（6）从有序顺序表中删除其值在给定值s与t之间（要求s小于或等于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。（7）将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。（8）从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不相同。,Link例题,例Link1：针对带表头结点的单链表编写以下函数。（1）定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。（2）求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。（3）统计函数number：统计单链表中具有给定值x的所有元素。（4）建立函数create：根据一维数组an建立一个单链表，使单链表中各元素的次序与an中各元素的次序相同，要求该程序的时间复杂度为O(n)。（5）整理函数tidyup：在非递减有序的单链表中删除值相同的多余的结点。例Link2：设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他存储空间。表中允许有得利的数据。,