5_数据结构—查找和排序

软件技术基础

数据结构查找和排序

沙河校区主楼西301 沙河校区主楼西301 主楼西

颜红梅

hmyan@ 13981787311

软件技术基础

上节课复习线性表顺序表 结构体定义和表达 操作:初始化,赋值,插入, 操作:初始化,赋值,插入,删除 优缺点 链表 结构体表达 指针 操作:查找,插入, 操作:查找,插入,删除 优缺点

栈 队列

软件技术基础

数据结构1,基本概念 2,线性结构 3,非线性结构 4,查找与排序

软件技术基础

本节主要内容

查找算法顺序查找 二分查找

排序算法简单插入排序 简单选择排序 冒泡排序

软件技术基础

一,基本概念1,算法的概念 算法是对某一特定问题的解题步骤的描 是计算机指令的有限序列. 述,是计算机指令的有限序列. 数据结构的选择对算法的选择起决定作 用.

程序=算法+ 程序=算法+数据结构+…(运行环境相关) 运行环境相关)

软件技术基础

2,算法的特征可行性 确定性 有穷性 输入 输出:算法必须有确定的执行结果( 输出:算法必须有确定的执行结果(一个 或多个输出) 或多个输出)

软件技术基础

3,算法的评价: 算法的评价:正确性: 正确性:对于一切合法输入都能产生满足规格 要求的结果. 要求的结果. 易读性:算法要便于阅读,有助于人们对算法 易读性:算法要便于阅读, 的理解. 的理解. 健壮性:当输入非法数据时, 健壮性:当输入非法数据时,也能正常作出反 应和处理.要考虑出错的情况. 应和处理.要考虑出错的情况. 运行时间及占用空间:对相同规模的问题, 运行时间及占用空间:对相同规模的问题,运 行时间短,占用空间少. 行时间短,占用空间少.

软件技术基础

二,查找算法查找的效率将直接影响到数据处理的效率. 查找的效率将直接影响到数据处理的效率. 查找——就是在给定的数据集合中找出 就是在给定的数据集合中找出满足 查找——就是在给定的数据集合中找出满足 的结点/ 某种条件的结点 元素. 某种条件的结点/元素. 一般是依据结点/元素的关键字进行查找; 关键字进行查找 一般是依据结点/元素的关键字进行查找;关键字:元素的标志,检索的依据; 关键字:元素的标志,检索的依据; 一般情况下, 一般情况下,关键字是一个元素的唯一标识

查找表——是一组待查数据元素的集合. 查找表——是一组待查数据元素的集合. 是一组待查数据元素的集合

软件技术基础

查找的方法与数据结构的关系 查找的方法与数据结构的关系数据结构决定了检索的方法; 数据结构决定了检索的方法; 有时为提高检索效率,需要对数据结构 有时为提高检索效率, 采用特殊的实现方式; 采用特殊的实现方式;例:按成绩检索学生,检索一个学生成绩递 按成绩检索学生, 增的表格比杂乱的表格效率高. 增的表格比杂乱的表格效率高.

软件技术基础

平均查找长度ASLASL-Average Search Length 在查找过程中, 在查

找过程中 , 要对每个结点记录中的 关键字进行反复比较,以确定其位置. 关键字进行反复比较 , 以确定其位置 . 因此,与关键字进行比较的平均次数, 因此 , 与关键字进行比较的平均次数 , 就称为平均查找长度. 就称为平均查找长度. 是用来评价查找算法好坏的一个依据. 是用来评价查找算法好坏的一个依据. 评价查找算法好坏的一个依据

软件技术基础

基本查找算法顺序查找 二分查找 分块查找 树表查找 哈希查找

软件技术基础

1,顺序查找算法(1)算法思想: 算法思想:从第1个元素到最后1个元素,逐个比较. 从第1个元素到最后1个元素,逐个比较.

(2)特点: 特点:最简单,最普通的查找方法. 最简单,最普通的查找方法.

(3)操作步骤: 操作步骤:step1 从第1个元素开始查找; step1 从第1个元素开始查找;

逐个比较

step2 用待查关键字值与各结点(记录) step2 用待查关键字值与各结点(记录)的关键字值逐个进行比 若找到相等的结点,则查找成功;否则,查找失败. 较;若找到相等的结点,则查找成功;否则,查找失败.

(4)适用范围(查找表的存储结构): 适用范围(查找表的存储结构)既适用于顺序存储结构 也适用于链式存储结构

软件技术基础

1,顺序查找算法(以顺序表为例) 顺序查找算法(以顺序表为例) 顺序表list的结构类型说明: 顺序表list的结构类型说明: list的结构类型说明typedef struct list_type { elemtype data[ MAX]; int length; } list; list;elemtype 为元素的数据类型 如 float,struct; 为元素的数据类型, , ; MAX 为元素允许的最大个数. 为元素允许的最大个数. Length为当前线性表的表长 为当前线性表的表长

软件技术基础

seq_search(A, n, key) A 待查表 n 元素个数 key 要找的值

软件技术基础

int seq_search(list *s, int n , int mykey ) seq_search( { int i = 0; while ( i < n && s[i].key != mykey ) s[i]. /* 查找key的循环 */ 查找key的循环 i++; i++; if ( i < n ) return (i); /*查找成功 */ (i); /*查找成功 else return (-1); /*查找失败 */ /*查找失败 }While循环中,有两个判断条件,改进 循环中,有两个判断条件, 循环中 一下,可以减少一半. 一下,可以减少一半.

软件技术基础

int seq_search(list *s, int n , int mykey ) seq_search( { int i = 0; s[n]. s[n].key = mykey; /* 设置监视标志*/ mykey; 设置监视标志*/ while ( s[i].key != mykey ) s[i]. /* 查找key的循环 */ 查找key的循环 i++; i++; if ( i < n ) return (i); /*查找成功 */ (i); /*查找成功 else /*查找失败 return (-1); /*查找失败 */ }顺序查找算法中,执行频率最高的是 语句, 顺序查找算法中 执行频率最高的是while语句 执行频率最高的是 语句 改进后,可以节省近一半的时间 可以节省近一半的时间. 改进后 可以节省近一半的时间.

软件技术基础

例:查找顺序表中关键值为XX的元素 查找顺序表中关键值为 的元素#include <stdio.h> typedef struct list { char name

[10]; int key; } list; list; int seq_search(…) {略} void main() { int key, loc=0; list set[5]; set[0].key = 1013; set[0].name = "Yao"; set[1].key = 1012; set[1].name = "McGrady"; set[2].key = 1014; set[2].name = "Alston"; printf("Input key:"); scanf("%d",&key); loc=seq_search(set,3,key); if (loc >0) { printf("loc=%d, ",loc); printf("name=%s\ printf("name=%s\n", set[loc].name); } }

软件技术基础

顺序查找算法的效率查找成功时的平均查找次数为: 查找成功时的平均查找次数为: ASL=(1+2+3+4+……+n)/n=(n+1)/2 查找不成功时的比较次数为: 查找不成功时的比较次数为: n+1 则顺序查找的平均查找长度为: 则顺序查找的平均查找长度为: ASL==((n+1)/2+n+1)/2=(n+1)3/4

时间复杂度: ( ) 时间复杂度:O(n)

软件技术基础

顺序查找算法优点: 优点: –对结点的逻辑次序(不必有序)和存储结构(顺 对结点的逻辑次序(不必有序)和存储结构( 对结点的逻辑次序 链表均可)无要求; 序,链表均可)无要求; –当序列中的记录按访问概率"基本有序"或N 当序列中的记录按访问概率"基本有序" 当序列中的记录按访问概率 值较小时,是较好的算法; 值较小时,是较好的算法; 缺点:平均查找长度(ASL) 缺点:平均查找长度(ASL)较长 对于有序的数据表,能否减少比较次数, 对于有序的数据表,能否减少比较次数,以提高 效率? 效率?

软件技术基础

2,二分查找算法(1)先决条件:查找表中的数据元素必须有序. (1)先决条件:查找表中的数据元素必须有序. 先决条件 (顺序存储结构的顺序表中的所有数据元素按 关键字有序) 关键字有序) 思想: (2)思想: 有序序列的中点设置为比较对象 设置为比较对象, 将有序序列的中点设置为比较对象,如果要 找的元素值小于该中点元素, 找的元素值小于该中点元素 , 则将待查序列 缩小为左半部分,否则为右半部分. 缩小为左半部分,否则为右半部分. 即通过一次比较,将查找区间缩小一半. 通过一次比较,将查找区间缩小一半.

软件技术基础

(3)特点: 特点: 二分查找是一种高效 的查找方法. 二分查找是一种 高效 的查找方法 . 高效的查找方法 它可以明显减少比较次数, 它可以明显减少比较次数 , 提高查 找效率. 找效率. 但是, 二分查找的先决条件 但是 , 二分查找的 先决条件 是查找 先决条件是查找 表中的数据元素必须有序. 表中的数据元素必须有序.

本文来源：https://www.bwwdw.com/article/3u14.html