数据结构项目八课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构项目八课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 项目 课件
- 资源描述:
-
1、数据结构数据结构项目八共分为五个任务项目八共分为五个任务项目八项目八 排序排序任务一任务一 排序的相关概念排序的相关概念 任务二任务二 插入排序插入排序 任务三任务三 交换排序交换排序 任务四任务四 选择排序选择排序 任务五任务五 归并排序和基数排序归并排序和基数排序 任务一任务一 排序的相关概念排序的相关概念 1排序排序 2数据元素的存储结构数据元素的存储结构3算法的稳定性算法的稳定性 4算法的评价算法的评价 1排序排序 排序排序是指将一个数据元素的任意序列按关键字的递增或递减次序重新是指将一个数据元素的任意序列按关键字的递增或递减次序重新排列起来,使其成为一个按关键字有序排列的序列。排列起
2、来,使其成为一个按关键字有序排列的序列。内部排序内部排序是指将待排数据元素完全放置在内存中进行排序的方法。是指将待排数据元素完全放置在内存中进行排序的方法。外部排序外部排序是指因待排数据元素数量太大,排序过程中不仅需要使用内是指因待排数据元素数量太大,排序过程中不仅需要使用内存,还要借助外部存储器来完成的排序方法。存,还要借助外部存储器来完成的排序方法。2数据元素的存储结构数据元素的存储结构数据元素可有数据元素可有3种存储结构:种存储结构:顺序结构顺序结构、链式结构链式结构和和地址向量结构地址向量结构。排序过程中一定要排序过程中一定要移动数据元素移动数据元素排序过程中不用移动数据元排序过程中不
3、用移动数据元素,而只需要修改指针素,而只需要修改指针 指将数据元素顺序存储的同时,另设一个指示各个数据元素指将数据元素顺序存储的同时,另设一个指示各个数据元素位置的地址向量,这样在排序过程中不用移动数据元素,而位置的地址向量,这样在排序过程中不用移动数据元素,而只需修改地址向量中数据元素的只需修改地址向量中数据元素的“地址地址”即可即可 顺序结构的数据类型定义如下:顺序结构的数据类型定义如下:#define MAXSIZE 100/顺序表的最大长度顺序表的最大长度typedef struct KeyType key;/关键字项关键字项OtherType otheritem;/另外的数据项另外的
4、数据项RecordType;typedef structRecordType rMAXSIZE+1;/定义数据元素数组,定义数据元素数组,r0为哨兵单元为哨兵单元int length;/顺序表长度顺序表长度SeqList;3算法的稳定性算法的稳定性 如果待排序的数据元素序列中有两个数据元素的关键字的值相同,经如果待排序的数据元素序列中有两个数据元素的关键字的值相同,经过排序后,两个数据元素的过排序后,两个数据元素的相对次序保持不变相对次序保持不变,则称所用的排序方法,则称所用的排序方法是是稳定稳定的;反之,则称所用的排序方法是的;反之,则称所用的排序方法是不稳定不稳定的。的。关键字序列(关键字
5、序列(35,2,15,6,81,6*)结果序列为(结果序列为(2,6,6*,15,35,81)表示为)表示为稳定稳定的排序方法的排序方法 结果序列为(结果序列为(2,6*,6,15,35,81)表示为)表示为不稳定不稳定的排序方法的排序方法 4算法的评价算法的评价 可以从两个方面来评价某种排序算法的优劣:可以从两个方面来评价某种排序算法的优劣:通过排序过程中所需的内存辅助空间的多少来衡量。通过排序过程中所需的内存辅助空间的多少来衡量。通过排序过程中关键字的比较次数和数据元素的移动次数来反映。通过排序过程中关键字的比较次数和数据元素的移动次数来反映。空间复杂度空间复杂度:时间复杂度时间复杂度:任
6、务二任务二 插入排序插入排序 一、直接插入排序一、直接插入排序 二、折半插入排序二、折半插入排序 三、希尔排序三、希尔排序 1基本思想基本思想 2算法实现算法实现 一、直接插入排序一、直接插入排序 3算法分析算法分析 1基本思想基本思想 将待排数据元素插入到已排好序的有序表中,从而得到一个新的有序表。将待排数据元素插入到已排好序的有序表中,从而得到一个新的有序表。对于一个具有对于一个具有n个数据元素的序列,进行直接插入排序具体过程:个数据元素的序列,进行直接插入排序具体过程:将第将第1个数据元素看作一个已排好序的有序表。个数据元素看作一个已排好序的有序表。将第将第i(2in)个数据元素的关键字
7、)个数据元素的关键字Ki依次与其前面数据元素的关依次与其前面数据元素的关键字键字Ki1、Ki2、K1进行比较,将所有关键字大于进行比较,将所有关键字大于Ki的数据元素依的数据元素依次向后移动一个位置,直到某个数据元素的关键字次向后移动一个位置,直到某个数据元素的关键字Kj小于或者等于小于或者等于Ki时,时,将第将第i个数据元素插入到关键字为个数据元素插入到关键字为Kj的数据元素后面,即完成第的数据元素后面,即完成第i个数据个数据元素的插入。元素的插入。经过经过n1次插入操作后,所有数据元素构成一个按关键字值大小排次插入操作后,所有数据元素构成一个按关键字值大小排列的有序序列。列的有序序列。数据
8、元素序列数据元素序列35,66,2,15,6,81,6*,9进行直接插入排序的过程:进行直接插入排序的过程:2算法实现算法实现 void InsertSort(SeqList*L)/对顺序表对顺序表L作直接插入排序作直接插入排序int i,j;for(i=2;i Length;i+)/从第二个数据元素开始排序从第二个数据元素开始排序if(L-ri.key ri-1.key)/如果第如果第i个数据元素的关键字小于其前面数据元素的关键字,则将其个数据元素的关键字小于其前面数据元素的关键字,则将其插入到有序表中插入到有序表中L-r0=L-ri;/将待插入数据元素存入将待插入数据元素存入r0作为监视哨
9、作为监视哨/搜索插入位置,将有序表中大于待排关键字的数据元素后移搜索插入位置,将有序表中大于待排关键字的数据元素后移for(j=i-1;L-r0.key rj.key;j-)L-rj+1=L-rj;L-rj+1=L-r0;/将待排数据元素插入到第将待排数据元素插入到第j个数据元素之后个数据元素之后3算法分析算法分析(1)空间复杂度)空间复杂度 排序过程中仅使用了一个辅助单元排序过程中仅使用了一个辅助单元r0,算法的空间复杂度为,算法的空间复杂度为O(1)。(2)时间复杂度)时间复杂度 直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(n2)。(3)稳定性)稳定性 直接插入排序是一种直接插
10、入排序是一种稳定稳定的排序算法。的排序算法。二、折半插入排序二、折半插入排序 1算法实现算法实现 2算法分析算法分析 1算法实现算法实现 通过对有序表进行折半查找来确定插入位置,以减少关键字比较的次通过对有序表进行折半查找来确定插入位置,以减少关键字比较的次数。算法描述如下:数。算法描述如下:void BinSort(SeqList*L)/对顺序表对顺序表L作折半插入排序作折半插入排序int i,j;int low,high,mid;for(i=2;i length;i+)/从第从第2个元素开始排序个元素开始排序L-r0=L-ri;/将待插入数据元素存入将待插入数据元素存入r0作为监视哨作为监
11、视哨low=1;high=i-1;/设置初始查找区间设置初始查找区间while(low r0.key rmid.key)high=mid 1;/在前半部分查找在前半部分查找else low=mid+1;/在后半部分查找在后半部分查找for(j=i-1;j=low;j-)/将插入位置以后的数据元素后移将插入位置以后的数据元素后移L-rj+1=L-rj;L-rlow=L-r0;/插入数据元素插入数据元素 2算法分析算法分析(1)空间复杂度)空间复杂度(2)时间复杂度)时间复杂度(3)稳定性)稳定性 排序过程中仅使用了一个辅助单元排序过程中仅使用了一个辅助单元r0,算法的空间复杂度为,算法的空间复杂
12、度为O(1)。折半插入排序的时间复杂度为折半插入排序的时间复杂度为O(n2)。折半插入排序是一种折半插入排序是一种稳定稳定的排序算法。的排序算法。三、希尔排序三、希尔排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 将待排序数据元素划分成若干个子序列,其中每个子序列由相隔某个将待排序数据元素划分成若干个子序列,其中每个子序列由相隔某个“增量增量”的数据元素组成,然后对这些子序列分别进行直接插入排序,的数据元素组成,然后对这些子序列分别进行直接插入排序,通过缩小通过缩小“增量增量”对子序列进行调整。当整个序列基本有序时,对全对子序列进行调整。当整个序列基本有序
13、时,对全部数据元素进行一次直接插入排序。部数据元素进行一次直接插入排序。具体过程:具体过程:按选定增量按选定增量d1(d1n),将所有距离为),将所有距离为d1的数据元素划分为一个的数据元素划分为一个子序列,对各个子序列进行直接插入排序。子序列,对各个子序列进行直接插入排序。选定增量选定增量d2(d2d1),对所有数据元素重新进行划分并对各子序),对所有数据元素重新进行划分并对各子序列直接插入排序。列直接插入排序。重复以上操作,直到增量重复以上操作,直到增量di1,即将所有数据元素放在一个子序列中,即将所有数据元素放在一个子序列中进行一次直接插入排序,最后得到所有数据元素按关键字有序排列的序进
14、行一次直接插入排序,最后得到所有数据元素按关键字有序排列的序列。列。2算法实现算法实现 void ShellInsert(SeqList*L,int di)/对顺序表对顺序表L作一趟希尔排序,作一趟希尔排序,di为增量为增量int i,j;for(i=di+1;i Length;i+)if(L-ri.key ri-di.key)/将第将第i个数据元素插入有序子序列个数据元素插入有序子序列L-r0=L-ri;/将第将第i个数据元素存入个数据元素存入r0作为监视哨作为监视哨/查找插入位置,将子序列内插入位置后的数据元素后移查找插入位置,将子序列内插入位置后的数据元素后移for(j=i-di;j 0
15、&L-r0.key rj.key;j=j-di)L-rj+di=L-rj;L-rj+di=L-r0;/插入数据元素插入数据元素void ShellSort(SeqList*L,int d,int t)/按增量序列按增量序列d对顺序表对顺序表L作作t趟希尔排序趟希尔排序int k;for(k=0;k t;k+)ShellInsert(L,dk);/一趟增量为一趟增量为dk的希尔排序的希尔排序3算法分析算法分析(1)空间复杂度)空间复杂度(2)时间复杂度)时间复杂度(3)稳定性)稳定性 排序过程中仅使用了一个辅助单元,算法的空间复杂度为排序过程中仅使用了一个辅助单元,算法的空间复杂度为O(1)。希
16、尔排序是一种希尔排序是一种不稳定不稳定的排序算法。的排序算法。在在数据量较少数据量较少时,利用时,利用直接插入排序的效率较高直接插入排序的效率较高;当待排序的数据元;当待排序的数据元素素数目较大数目较大时,时,希尔排序方法希尔排序方法一般要比直接插入排序方法一般要比直接插入排序方法快快。任务三任务三 交换排序交换排序 一、冒泡排序一、冒泡排序 二、交换排序二、交换排序一、冒泡排序一、冒泡排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 从头扫描待排序的数据元素序列,依次比较相邻两个数据元素的关键字从头扫描待排序的数据元素序列,依次比较相邻两个数据元素的关键字
17、大小,如果逆序,则交换它们的位置,逐步将待排序列变成有序序列。大小,如果逆序,则交换它们的位置,逐步将待排序列变成有序序列。具体过程:具体过程:对待排序数据元素序列进行第一趟扫描,依次比较相邻两个数据元对待排序数据元素序列进行第一趟扫描,依次比较相邻两个数据元素的关键字大小,如果前面数据元素的关键字大于后面数据元素的关素的关键字大小,如果前面数据元素的关键字大于后面数据元素的关键字,就将它们交换,这样具有较大关键字的数据元素将不断后移,键字,就将它们交换,这样具有较大关键字的数据元素将不断后移,最后,具有最大关键字的数据元素移动到最后一个位置上;最后,具有最大关键字的数据元素移动到最后一个位置
18、上;第二趟扫描仅需对前第二趟扫描仅需对前n1个数据元素进行,重复以上操作,使具有个数据元素进行,重复以上操作,使具有次大关键字的数据元素移动到第次大关键字的数据元素移动到第n1个位置;个位置;依此类推,直到某一趟扫描过程中没有发生数据元素的交换,则可依此类推,直到某一趟扫描过程中没有发生数据元素的交换,则可结束冒泡排序。结束冒泡排序。对数据元素序列(对数据元素序列(35,66,2,15,6,81,6*,9)进行冒泡排序:)进行冒泡排序:2算法实现算法实现 void BubbleSort(SeqList*L)/对顺序表对顺序表L作冒泡排序作冒泡排序int i,j,change;change=TR
19、UE;/设置交换标志,初始值为设置交换标志,初始值为TRUEfor(i=1;i Length&change;i+)/进行冒泡排序,无交换时结束进行冒泡排序,无交换时结束change=FALSE;/设置交换标志为设置交换标志为FALSEfor(j=1;j Length-i;j+)/对未排好序的数据元素排序对未排好序的数据元素排序if(L-rj.key L-rj+1.key)/比较相邻两个数据元素的大小比较相邻两个数据元素的大小L-r0=L-rj;/要交换的数据元素暂时存入要交换的数据元素暂时存入r0中中L-rj=L-rj+1;L-rj+1=L-r0;change=TRUE;/设置交换标志为设置交
20、换标志为TRUE3算法分析算法分析(1)空间复杂度)空间复杂度(2)时间复杂度)时间复杂度(3)稳定性)稳定性 冒泡排序过程中仅使用了一个辅助单元,算法的空间复杂度为冒泡排序过程中仅使用了一个辅助单元,算法的空间复杂度为O(1)。冒泡排序的时间复杂度为冒泡排序的时间复杂度为O(n2)。冒泡排序是一种冒泡排序是一种稳定稳定的排序算法。的排序算法。二、快速排序二、快速排序 1基本思想基本思想 2算法实现算法实现 3算法分析算法分析 1基本思想基本思想 从待排数据元素序列中选取一个数据元素为基准,通过一趟扫描将待排序从待排数据元素序列中选取一个数据元素为基准,通过一趟扫描将待排序列分成两部分。其中一
21、部分数据元素的关键字都小于或等于基准数据元素列分成两部分。其中一部分数据元素的关键字都小于或等于基准数据元素的关键字,而另一部分数据元素的关键字都大于或等于基准数据元素的关的关键字,而另一部分数据元素的关键字都大于或等于基准数据元素的关键字。对各部分不断划分,直到整个序列按关键字有序排列为止。键字。对各部分不断划分,直到整个序列按关键字有序排列为止。具体过程如下:具体过程如下:选取待排序列中的第一个数据元素为基准,将其复制到选取待排序列中的第一个数据元素为基准,将其复制到r0中,并令该位置为中,并令该位置为空;设置两个指针空;设置两个指针low和和high,分别指向第一个数据元素和最后一个数据
22、元素,即,分别指向第一个数据元素和最后一个数据元素,即初始状态时初始状态时rlow为空。为空。从后向前扫描,若从后向前扫描,若rhigh的关键字大于或等于基准关键字,则的关键字大于或等于基准关键字,则high向前移动向前移动一个位置,直到一个位置,直到rhigh的关键字小于基准关键字时,将的关键字小于基准关键字时,将rhigh与与rlow交换。交换。从前向后扫描,若从前向后扫描,若rlow的关键字小于或等于基准关键字,则的关键字小于或等于基准关键字,则low向后移动一个向后移动一个位置,直到位置,直到rlow的关键字大于基准关键字时,将的关键字大于基准关键字时,将rlow与与rhigh交换。交
23、换。重复步骤重复步骤和和,直至,直至lowhigh时,令时,令rlowr0,以,以rlow为基准将待为基准将待排序列划分为前后两部分,第一次划分完成。排序列划分为前后两部分,第一次划分完成。按照以上方法,对各部分不断划分,直到各部分只有一个数据元素时,整个序按照以上方法,对各部分不断划分,直到各部分只有一个数据元素时,整个序列排序完成。列排序完成。对数据元素序列(对数据元素序列(35,66,2,15,6,81,6*,9)进行一趟快速排序)进行一趟快速排序的过程的过程:2算法实现算法实现 int Partition(SeqList*L,int low,int high)/以第一个数据元素为基准进
24、行一趟快排,返回排序后基准数据元素的位置以第一个数据元素为基准进行一趟快排,返回排序后基准数据元素的位置L-r0=L-rlow;/以序列中第一个数据元素为基准以序列中第一个数据元素为基准while(low high)/从序列两端交替向中间扫描从序列两端交替向中间扫描while(low rhigh.key=L-r0.key)/从后向前扫描从后向前扫描high-;/high指针前移指针前移L-rlow=L-rhigh;/将小于基准关键字的数据元素移到将小于基准关键字的数据元素移到low所指位置所指位置while(low rlow.key r0.key)/从前向后扫描从前向后扫描low+;/low指
25、针后移指针后移L-rhigh=L-rlow;/将大于基准关键字的数据元素移到将大于基准关键字的数据元素移到high所指位置所指位置L-rlow=L-r0;/将基准数据元素移到将基准数据元素移到low所指位置所指位置return low;/返回排序后基准数据元素的位置返回排序后基准数据元素的位置void QuickSort(SeqList*L,int low,int high)/对顺序表对顺序表L作快速排序作快速排序int p;if(low high)/表长度大于表长度大于1p=Partition(L,low,high);/对对L进行一趟快速排序,返回基准数据元素的位置进行一趟快速排序,返回基准
展开阅读全文