5_数据结构―查找和排序.docx

5段据结构一查找和排序软件技术基础数据结构查找和排序沙河校区主楼西301沙河校区主楼西301主楼西颜红梅hmyan®_软件技术基础上节课复习线性表顺序表结构体定义和表达操作:初始化,赋值,插入,操作初始化,赋值,插入删除优缺点链表结构体表达指针操作渣找,插入,操作渣找,插入,删除优缺点栈队列软件技术基础数据结构1,基本概念2,线性结构3,非线性结构4,查找与排序软件技术基础本节主要内容查找算法顺序查找二分查找排序算法简单插入排序简单选择排序冒泡排序软件技术基础一,基本概念L算法的概念算法是对某一特定问题的解题步骤的描是计算机指令的有限序列.述,是计算机指令的有限序列.数据结构的选择对算法的选择起决定作用.程序二算法+程序=算法+数据结构（运行环境相关）运行环境相关）软件技术基础2,算法的特征可行性确定性有穷性输入输出:算法必须有确定的执行结果（输出:算法必须有确定的执行结果（一个或者多个输出）或者多个输出）软件技术基础3,算法的评价：算法的评价:正确性：正确性:对于一切合法输入都能产生满足规格要求的结果.要求的结果.易读性:算法要便于阅读,有助于人们对算法易读性:算法要便于阅读，的理解.的理解.茁壮性:当输入非法数据时，茁壮性:当输入非法数据时，也能正常作出反应和处理.要考虑出错的情况.应和处理.要考虑出错的情况,运行时间及占用空间:对相同规模的问题,运行时间及占用空间对相同规模的问题运行时间短,占用空间少.行时间短,占用空间少.软件技术基础二,查找算法查找的效率将直接影响到数据处理的效率.查找的效率将直接影响到数据处理的效率.查找就是在给定的数据集合中找出就是在给定的数据集合中找出满足查找一就是在给定的数据集合中找出满足的结点/某种条件的结点元素.某种条件的结点/元素.普通是依据结点/元素的关键字进行查找；关键字进行查找普通是依据结点/元素的关键字进行查找;关键字:元素的标志，检索的依据；关键字:元素的标志，检索的依据；普通情况下，普通情况下,关键字是一个元素的惟一标识查找表一是一组待查数据元素的集合.查找表是一组待查数据元素的集合.是一组待查数据元素的集合软件技术基础查找的方法与数据结构的关系查找的方法与数据结构的关系数据结构决定了检索的方法；数据结构决定了检索的方法；有时为提高检索效率,需要对数据结构有时为提高检索效率,采用特殊的实现方式;采用特殊的实现方式例:按成绩检索学生,检索一个学生成绩递按成绩检索学生，增的表格比杂乱的表格效率高.增的表格比杂乱的表格效率高.软件技术基础平均查找长度ASLASL-AverageSearchLength在查找过程中，在查找过程中，要对每一个结点记录中的关键字进行反复比较，以确定其位置.关键字进行反复比较，以确定其位置.因此,与关键字进行比较的平均次数，因此，与关键字进行比较的平均次数，就称为平均查找长度.就称为平均查找长度.是用来评价查找算法好坏的一个依据.是用来评价查找算法好坏的一个依据.评价查找算法好坏的一个依据软件技术基础基本查找算法顺序查找二分查找分块查找树表查找哈希查找软件技术基础1.顺序查找算法算法思想：算法思想:从第1个元素到最后1个元素逐个比较,从第1个元素到最后1个元素,逐个比较.特点：特点:最简单,最普通的查找方法.最简单,最普通的查找方法.操作步骤:操作步骤:StePl从第1个元素开始查找;Stepl从第1个元素开始查找；逐个比较step2用待查关键字值与各结点（记录）step2用待查关键字值与各结点（记录）的关键字值逐个进行比若找到相等的结点,则查找成功;否则渣找失败较;若找到相等的结点，则查找成功；否则,查找失败.（4）合用范围（查找表的存储结构）:合用范围（查找表的存储结构）既合用于顺序存储结构也合用于链式存储结构软件技术基础1.顺序查找算法(以顺序表为例)顺序查找算法(以顺序表为例)顺序表IiSt的结构类型说明：顺序表IiSt的结构类型说明：IiSt的结构类型说明typedefstructIistJypeelemtypedataMAX;itlength;list;list;elemtype为元素的数据类型如float1struct;为元素的数据类型,，；MAX为元素允许的最大个数.为元素允许的最大个数.Length为当前线性表的表长为当前线性表的表长软件技术基础seq_search(A,key)A待查表n元素个数key要找的值软件技术基础itseq_search(list*s,it,itmykey)seq_search(inti=0;while(isi.key!=mykey)si./*查找key的循环*/查找key的循环i+;i÷+;if(in)return(i);/*查找成功*/(i);/*查找成功elsereturn(-1);/*查找失败*/*查找失败While循环中，有两个判断条件,改进循环中,有两个判断条件,循环中一下,可以减少一半.一下,可以减少一半.软件技术基础itseq_search(list*s,it,itmykey)seq_search(iti=0;s.s.key=mykey;/*设置监视标志表/mykey;设置监视标志*/while(si.key!=mykey)si./*查找key的循环*/查找key的循环i+÷i+÷if(i)return(i);/*查找成功*/(i);/*查找成功else/*查找失败return查找失败/顺序查找算法中,执行频率最高的是语句，顺序查找算法中执行频率最高的是WhiIe语句执行频率最高的是语句改进后,可以节省近一半的时间可以节省近一半的时间,改进后可以节省近一半的时间.软件技术基础例:查找顺序表中关键值为_的元素查找顺序表中关键值为的元素#includestdio.htypedefstructlistcharname;itkey;list;list;itseq_search(o)略voidmai()itkey,Ioc=O;listset;set.key=1013;set.ame=uYao"set.key=1012;set.name="McGrady"set.key=1014;set.ame="Alston"pritf("lputkey:");scaf(',%d",key);loc=seq-search(set,3,key);if(loc0)printf("loc=%d,loc);pritf("ame=%spritf("ame=%s*"1setloc.ame);软件技术基础顺序查找算法的效率查找成功时的平均查找次数为：查找成功时的平均查找次数为:ASL=(l+2+3+4+O÷)=(n+l)2查找不成功时的比较次数为:查找不成功时的比较次数为:n÷l则顺序查找的平均查找长度为：则顺序查找的平均查找长度为：ASL=(n+l)2+n+l)2=(n+l)34时间复杂度:()时间复杂度Q(n)软件技术基础顺序查找算法优点:优点C对结点的逻辑次序(不必有序)和存储结构（顺对结点的逻辑次序（不必有序）和存储结构（对结点的逻辑次序链表均可）无要求;序,链表均可）无要求;C当序列中的记录按访问概率”基本有序”或者N当序列中的记录按访问概率”基本有序”当序列中的记录按访问概率值较小时,是较好的算法;值较小时,是较好的算法；缺点:平均查找长度（ASL）缺点：平均查找长度（ASL）较长对于有序的数据表,能否减少比较次数,对于有序的数据表,能否减少比较次数以提高效率？效率？软件技术基础2,二分查找算法先决条件:查找表中的数据元素必须有序.先决条件渣找表中的数据元素必须有序,先决条件（顺序存储结构的顺序表中的所有数据元素按关键字有序）关键字有序）思想:（2）思想：有序序列的中点设置为比较对象设置为比较对象将有序序列的中点设置为比较对象，如果要找的元素值小于该中点元素,找的元素值小于该中点元素，则将待查序列缩小为左半部份,否则为右半部份.缩小为左半部份,否则为右半部份.即通过一次比较，将查找区间缩小一半.通过一次比较,将查找区间缩小一半.软件技术基础（3）特点：特点：二分查找是一种高效的查找方法.二分查找是一种高效的查找方法,高效的查找方法它可以明显减少比较次数，它可以明显减少比较次数，提高查找效率,找效率.但是二分查找的先决条件但是二分查找的先决条件是查找先决条件是查找表中的数据元素必须有序.表中的数据元素必须有序.