成绩排名与查询

《成绩排名与查询》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2教学目标1、知识目标1）了解排序的基本概念；2）了解查找的基本概念；3）掌握基本的排序算法；4）掌握基本的查询算法；5）掌握分析不同排序算法的优劣的方法6）掌握分析不同查询算法的优劣的方法2、能力目标1）具有选择恰当的排序算法解决实际问题的能力；2）具有选择恰当的查询算法解决实际问题的能力。3、素质目标养成善于思考解决实际问题的良好习惯。一、任务描述排名与查询是我们在日常生活中经常碰到的一类任务，成绩排名与查询也是学校中不可或缺的一项重要工作，选择恰当的排序与查询算法是提高工作效率的一个重要途径。要完成这项任务，首先要选择一个合适的排序与查询算法，因此，选择什么样的排序与查询算

2、法等一系列的问题就成为了我们完成这项任务的关键。为此，我们先来学习下面的相关知识。3二、相关知识1、查找的基本概念查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可

3、能会发生变化。对动态查找表进行的查找操作称为动态查找。4关键字是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定

4、值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。5查找表的存储结构查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。62．顺序查找2.1顺序查找的基本思想顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，

5、也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。2.2顺序表的顺序查找下面是顺序表的类型定义：#defineMAX_NUM100//用于定义表的长度typedefstructelemtype{keytypekey;anytypeotheritem;}Se_List[MAX_NUM],Se_Item;7假设在查找表中，数据元素个数为n（n

6、下面我们给出顺序查找的完整算法。intseq_search(Se_Lista，keytypek){//在顺序表中查找关键字值等于k的记录，//若查找成功，返回该记录的位置下标序号，否则返回0i=1;while(i<=n&&a[i].key!=k)i++;if(i<=n)retruni;elsereturn0;}改进算法：intseq_search2(Se_Lista，keytypek){//设置了监视哨的顺序表查找，查找关键字值等于指定值k的记录，//若查找成功，返回记录存放位置的下标值，否则返回0i=n;a[0].key=k;while(a[i].key!=k)i--;retu

7、rn(i);}82.3链表的顺序查找链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。链表的类型定义如下所示：typedefstructnode{keytypekey;//结点的关键字类型anytypeotheritem;//结点的其他成分structnode*next;//指向链表结点的指针}Link_Node,*Link;将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺寻查找就是在有头结点的链