当前位置：文档之家 › 09-PPT006-第六章-查找

09-PPT006-第六章-查找

  • 格式：pdf
  • 大小：274.11 KB
  • 文档页数：47

下载文档原格式

  / 47

合集下载

数据结构部分(查找)课件

数据结构部分(查找)课件

n=0
n=1
n=2
空树
最大深度为 0 最大深度为 1 最大深度为 2
n=4
n=7
最大深度为 3
最大深度为 4
三、 B - 树
1．定义
2．查找过程
1．B-树的定义
B-树是一种 平衡 的 多路 查找 树：
root 50
15
71 84
38
20 26 43
56 62 78 89 96
在 m 阶的B-树上，每个非终端结点可能 含有：
low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。
分析折半查找的平均查找长度
先看一个具体的情况，假设：n=11
i 1 2 3 4 5 6 7 8 9 10 11 Ci 3 4 2 3 4 1 3 4 2 3 4
判定树
3
6 9
1
4
7
10
2
5
8
11
一般情况下，表长为 n 的折半查找 的判定树的深度和含有 n 个结点的完全 二叉树的深度相同。
何谓查找表 ？
查找表是由同一类型的数据元素( 或记录)构成的集合。
由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵 便的结构。
对查找表经常进行的操作:
• 1）查询某个“特定的”数据元素是否 在查找表中；
• 2）检索某个“特定的”数据元素的各 种属性；
• 3）在查找表中插入一个数据元素； • 4）从查找表中删去某个数据元素。
• 根据动态查找表的定义，“插入”操 作在查找不成功时才进行;
• 若二叉排序树为空树，则新插入的 结点为新的根结点；否则，新插入 的结点必为一个新的叶子结点，其 插入位置由查找过程得到。

006现代部分第六章 散文(一)

006现代部分第六章 散文(一)

2、“现代评论派”的散文
• 徐志摩的散文集：《落叶集》、《自剖
集》、《巴黎的鳞爪》、《秋》。 • 特色：想象丰富，结构繁复，语言铺张， 词藻华丽，感情强烈。
20年代散文的特点
（一）个性化。五四对“人”的观念的发
现在散文上的表现。独抒性灵、率真自 然的散文较多。 （二）散文表现内容扩大。“宇宙之大、 苍蝇之微，无可不谈”。但对社会、人 生问题的关注是其共同特点。
（1） 谈论知识，探索人生，语言机智而 有文彩。 （2）善于在小题目里开掘微言大义，引用 外国的经典、警句信手拈来，却又处处 切题。
（3）折射出作者的孤傲气：懒散的绅士风
度，不愿受约束的个性，享受人生的生
活主张。
• 从生活细节中发现某种哲理，又喜作反
语，表面看似是标新立异，实质上是一 种很成熟的愤世嫉俗。
2、瞿秋白(1899——1935)
• 《俄乡纪程》《赤都心史》 • 开中国报告文学之先声
• 四、郁达夫和“创造社”作家散文
五、“语丝”派和“现代评论”派的 散文
1、语丝社是以1924年11月创刊于北京的
《语丝》周刊而得名的，是现代文学史 上第一个以散文创作为主的文学刊物， 倡导思想和言论自由。 “语丝文体”
出清丽的文字，雅俗并出，很有风致。
三、冰心、朱自清和“文学研究 会”作家散文
1、冰心的散文集《往事》与《寄小读者》、 美文小品《笑》；冰心散文中的“爱的 哲学”；“冰心体”。
2、朱自清的散文集《背影》与《你我》； 朱自清散文的思想艺术特色 3、丰子恺、梁遇春、许地山、瞿秋白的散 文
一）朱自清的散文
• 不粉饰，不渲染，以平易的叙述寄
寓深情厚意。
• 《背影》
• 一篇回忆性的抒情 散文 • 以父亲的背影为线 索，在描写无微不 至的父爱的同时， 写出了独特的人生 感受。

006第六章TCC计时器

006第六章TCC计时器

第六章TCC計時器6-1、簡介ET44M210微控制器內提供了一個有預除器(Prescaler)的計時器(TCC)，一個自由振盪計時器(FRC)。

TCC及FRC的時脈來源是IC內部的Clock或是外部RC振盪。

6-2、TCC如圖6-1所示為ET44M210的TCC功能方塊圖。

這是一個8位元附有預除器(Prescaler)的計時器。

TCC的時脈來源可以是來自IC內部的Clock也可以是來自外部RC振盪。

當TCC的時脈是來自IC內部的Clock時，TCC會在每個指令週期自動加1。

當TCC 的時脈是來自外部RC振盪時，TCC會在外部TCC接腳正緣觸發(Rising Edge) 或負緣觸發(Falling Edge) 時自動加1。

TCCS0是選擇TCC時脈使用IC內部的Clock或是來自外部RC振盪。

TCCE是選擇是否啟動TCC的功能。

TCCOF是表示TCC是否發生溢位中斷。

PS0~PS2是選擇以預除器的倍率，因為TCC有使用預除器，因此TCC加1的時間是由PS0~PS2所決定。

當TCC計時器內的值由FFh變成00h時，產生溢位中斷，中斷旗標暫存器中的TCC 溢位中斷旗標(TCCOF)會被設為1，程式會跳至中斷相量位址0x0028h去執行相關的中斷副程式以下是TCC Timer 計算的公式：TCC Timer=(0x100-TCC) * Prescaler* (1/Clock Source) 當TCC的時脈是來自外部RC振盪時，在ET44M210的ICE上，RC振盪的公式是Freq (KHz) * R (Meg Ohm) = 150 (常數)而由於ET44M210的ICE上，RC震盪電阻的預設值是300KΩ，因此外部RC的振盪頻率是500KHz。

I.TCC相關的暫存器預除器(Prescaler Counter )– PRC (0x0F)一個八位元的計數器。

Time Clock Counter – TCC (0x10)此暫存器存放TCC的值。

ppt课件查找

ppt课件查找

社交媒体查找
总结词
社交媒体上也有一些PPT课件资源，但需 要注意版权问题和内容质量。
VS
详细描写
在社交媒体上，如微信、微博等平台，有 一些个人或机构会分享他们的PPT课件资 源。这些资源的质量和内容可能各不相同 ，因此在下载使用时需要注意版权问题和 内容质量。同时，一些在线办公协作平台 ，如腾讯文档、文档等，也提供PPT模板 和在线制作功能，方便用户快速制作演示 文稿。
05
PPT课件查找工具 推举
PowerPoint内置查找功能
查找PPT模板
PowerPoint内置的查找功能可以帮助用户快速找到符合 需求的PPT模板，提高制作效率。
搜索PPT元素
用户可以在PPT中搜索特定的文字、图片、形状等元素， 方便对PPT进行编辑和修改。
查找PPT教程
PowerPoint也提供了丰富的教程和帮助文档，用户可以 通过查找功能快速找到相关教程，提高PPT制作水平。
Getty Images图库搜索
1 2
专业品质
Getty Images作为专业的图库网站，提供了大 量高品质的图片素材，满足用户在PPT中展示专 业内容的需求。
版权保护
Getty Images重视版权保护，提供的图片都有 版权保护信息，用户可以放心使用。
3
定降服务
Getty Images还提供定制拍摄和设计服务，用 户可以根据需求进行定制，提高PPT的专业性和 品质。
详细描写
使用搜索引擎时，可以通过关键词组合来缩小搜索范围，如“免费PPT课件”、 “高质量PPT课件”等。同时，查看搜索结果的来源和内容，选择信誉度高、评 判好的资源下载使用。
学术网站查找
总结词
学术网站通常提供较为严谨、专业的PPT课件资源，适用于学术研究和课堂教学。

金融学(006)第6章利率理论

金融学(006)第6章利率理论

（二）市场利率、官定利率、公定 利率
市场利率与官定、公定利率是依据利率是否按 市场资金供求关系自由变动的标准来划分的。 市场利率是指在金融市场上，由借贷资金的供 求关系决定，并由借贷双方自由议定的利率。 官定利率是指由一国政府的金融管理部门，大 多为中央银行确定的，由各金融机构严格执行的 利率。 公定利率是由非政府部门的民间金融组织，如 银行公会等所确定的利率。 官定利率和公定利率都程度不同地反映了非市 场的强制力量对利率形成的干预。
二、利率的表示与计算方法
（一）利率的表示方法
习惯上按照利息额计算的时间把利率划分为 年利率、月利率和日利率。年利率是以年为单 位计算的利息；月利率是以月为单位计算利息； 日利率，是以日为单位计算利息。 年利率：用﹪表示； 月利率：用‰表示； 日利率：用 0 000 表示。 三者之间的换算方法为：年利率/12=月利率， 月利率/30=日利率，年利率/360=日利率。 在民间计算利率时，也常用“厘”、“分” 表示。应加以区别。
流动性陷阱
三、可贷资金利率理论
可贷资金理论认为，可贷资金的需求除 了企业投资所需资金I之外，还有人们的手 持现金（窑藏现金）∆ MD；可贷资金的供 给除了储蓄S之外，还有手持现金（窑藏现 金）的启用和银行信用创造的增量货币 ∆MS。
如果以FS表示可贷资金的总供给，则 FS=S+∆MS；以FD表示对可贷资金的总需 求，则FD=I+∆MD。如图所示，如单纯考 虑I与S两因素，利率处在一特定水平；如 单纯考虑∆ MD和∆MS 两因素，则利率又 处在另一特定水平。而可贷资金的利率水 平是由可贷资金的总供给FS与总需求FD 决定的，即FS和FD相交的均衡点决定了 可贷资金供求均衡状态下的市场利率。
i I Y i C AD Y

6 查找

6 查找

CH6 查找⏹查找的基本概念⏹6.1 静态查找表◆ 6.1.1 顺序查找◆ 6.1.2 有序表的查找⏹6.2 动态查找表◆ 6.2.1 二叉排序树⏹6.3 哈希表吴国祥571056735@⏹1.查找表⏹2.查找◆关键字●主关键字●次关键字◆查找：根据某个给定的值，在表中确定一个其关键字等于给定值的记录或数据元素。

●查找成功●查找失败⏹3.查找表的分类◆静态查找表◆动态查找表⏹4.衡量查找算法效率的标准◆平均查找长度ASL (A verage S earch L ength)◆查找成功时的平均查找长度111ni ii ni i ASL p c p ====∑∑⏹5.本章数据元素类型与比较运算的符号约定◆数据类型定义typedef struct {KeyType key;……}ElemType◆6.查找的基本方法比较式查找法计算式查找法基于线性表的查找法（静态查找）基于树的查找法（动态查找）——HASH 查找法顺序查找法折半查找法二叉排序树6.1 静态查找表⏹静态查找表主要有：◆顺序表◆有序顺序表⏹针对静态查找表的查找算法主要有：◆顺序查找（线性查找）◆折半查找（二分查找）⏹1.顺序表上的顺序查找的基本思想◆从顺序表的一端开始，用给定数据元素的关键字逐个与顺序表中各数据元素的关键字比较，●若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；●否则查找失败，函数返回0。

⏹2.顺序表的机内存储结构typedef struct{ElemType *elem;int length;}SSTable;x a 1a 2a 3……a n-2a n-1a n int Search_Seq(SSTable ST,KeyType key){ ST.elem[0].key=key;for (i=ST.length;ST.elem[i].key!=key);--i);return i;}顺序查找过程⏹3.顺序查找操作的性能分析（设n ＝ST.length ）◆（1）查找成功时的平均查找长度●x i 查找成功的比较次数为n －i ＋1（1≤i ≤n ）●等概率情况下查找成功的平均查找长度：1111(1)2n nsucc i i i i n ASL p c n i n ==+=⨯=-+=∑∑6.1.2 有序表的查找⏹有序顺序表上的查找算法◆（1）顺序查找法●有序顺序表上顺序查找算法类同顺序表上的顺序查找算法◆（2）二分查找法（又称折半查找法）●前提条件：•1）表中的记录按关键字有序（设递增有序）•2）查找表采用顺序存储结构●查找过程折半查找过程示例1) 查找关键字等于21的记录1234567891011513192137566475808892ST.elem[mid].key>21 513192137566475808892 ST.elem[mid].key<21513192137566475808892 ST.elem[mid].key=21(查找成功）2) 查找关键字等于85的记录1234567891011 513192137566475808892ST.elem[mid].key<85 513192137566475808892ST.elem[mid].key<85 513192137566475808892ST.elem[mid].key>85 513192137566475808892失败算法描述int Search_Bin(SSTable ST,KeyType key){low=1;high=ST.length;while (low<=high){mid=(low+high)/2;if (key= = ST.elem[mid].key) return mid;else if (key<ST.elem[mid].key) high=mid-1;else low=mid+1;}return 0;}⏹折半查找过程可以描述为一棵二叉树◆折半查找的判定树如：（a 1, a 2, a 3,a 4, a 5, a 6, a 7, a 8, a 9,a 10, a 11）a 9a 6a 3a 1a 4a 7a10a 2a 5a 8a 11~a 1a 3-a 4a 6-a 7a 9-a 10a 1-a 2a 2-a 3a 4-a 5a 5-a 6a 7-a 8a 8-a 9a 10-a 11a 11-⏹折半查找算法的性能分析◆可以看出：●n 个结点的判定树的深度和n 个结点的完全二叉树的深度相同，即2log 1n +⎢⎥⎣⎦◆查找成功：●查找成功的过程：•走了一条从根结点到与该记录对应结点的路径。

查找PPT课件


high
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowmid high
找70 例 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low
mid
123456 7
5 13 19 21 37 56 64
练习
设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
AsS u c 1 1 L ci1 1 4 C 4i 1 1 (4 1 2 * 2 3 * 4 4 * 7 ) 1 44 5 Au S ns L u 1 1 ci1 c 5 0 5 C i ' 1 1(5 * 3 1 4 * 1 4 1 5)5 9
5 13 19 21 37 56 64 75 80 88 92
判定树： 3
6 9
1
4 7 10
2
5 8 11
判定树的构造方法
⑴ 当n=0时，折半查找判定树为空；
⑵ 当n＞0时，折半查找判定树的根结点是
有序表中序号为mid=(n+1)/2的记录，根 结点的左子树是与有序表r[1] ~ r[mid-1] 相对应的折半查找判定树，根结点的右子树 是与r[mid+1] ~ r[n]相对应的折半查找判 定树。
high=13
例：查找值为22的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

high
91 ) 91 )
low
mid
14,
high=mid-1 high mid
37, 46, 55, 68, 79, 91 )
low=mid+1
( 08, 14, 23,
low
( 08, ( 08, 14, 14, 23, 23, 37, 37,
mid
46, 46, 55, 68, 79, 79,

二叉排序树插入
二叉排序树是一种动态树表。特点是树的结构 不是一次生成，而是在查找过程中，当树中不 存在关键字等于给定值的结点时再进行插入。 新插入的结点一定是一个新添加的叶子结点， 并且是查找不成功时查找路径上访问的最后一 个结点的左孩子或右孩子结点。
二叉排序树的插入(续)
从空树出发，经过一系列的查找插入操作之后， 可生成一棵二叉排序树。 设插入的关键字序列为{45, 12, 53, 3, 37, 50, 98, 1, 8, 43, 60}，则生成的二叉排序树如下 中序遍历二叉排序树可得到 45 一个关键字的有序序列。 插入时，不必移动结点。 12 53
哈希表


理想情况是不经过任何比较，一次存取便能得 到所查记录，需在记录的存储位置和它的关键 字之间建立一个确定的对应关系。 从关键字集合到地址集合的对应关系f称为哈 希函数或散列函数（Hashed Function） 。按 这个思想建立的表称为哈希表(hashed table) 。 f(K)的值称为哈希地址或散列地址。 哈希查找(Hashed search)为在哈希表上进行查 找的过程，也称为散列法。
严格说来，查找算法的平均查找长度应是查找 成功时的平均查找长度与查找不成功时的平均 查找长度之和。 顺序查找的优点是算法简单、适应面广，且不 要求表中数据有序。缺点是平均查找长度较大， 特别是当 n 较大时，查找效率较低，不宜采用。
2、有序表的查找(二分查找)



二分查找（Birary search）也称为折半查找，它的 查找速度比顺序查找快，但它要求数据在线性表中 按查找的关键字域有序排列。 设n个数据存放于数组r中，且已经过排序，按由小 到大递增的顺序排列。 采用二分查找，首先用要查找的给定值k与表正中 间元素的关键值相比较，此元素的下 标 m = (1 + n ) / 2 。
二叉排序树举例
45 12 3 1 8 37 43 53 50 60 98

二叉排序树查找
将原始数据表示成二叉排序树，树的每个结点对应 一个记录，则可利用此二叉排序树进行类似于二分 查找思想的数据查找，这也是一个逐步缩小查找范 围的过程。这种查找方法称为树型查找。 基本思想：查找过程从根结点开始，首先将它的关 键字与给定值k进行比较，如果相等，则查找成功， 输出有关的信息；如果不等，若根结点关键字大于 给定值k，向左子树继续查找，否则向右子树继续 查找。 向子树查找又是树型查找，先以子树的根结点数据 与k进行比较，如果不相等又转向它的左或右子树 继续查找。
二叉排序树的删除图示
f p P c PL C PR CL QL SL Q S F p P PR CL QL SL PR f F c C Q S f F

二叉排序树查找分析
在二叉排序树上进行查找，若查找成功，则是从根结 点出发走了一条从根结点到所查找结点的路径；若查 找不成功，则是从根结点出发走了一条从根结点到某 个终端叶子结点的路径。与二分查找类似，和关键字 比较的次数不超过二叉排序树的深度。
二、动态查找表
特点：表结构本身是在查找过程中动态 生成的。 动态查找表的基本操作： InitDSTable; DestroyDSTable; SearchDSTable; TraverseDSTable； InsertDSTable; DeletdDSTable;

二叉排序树

定义：二叉排序树（Binary Sort Tree）是具有 下列性质的二叉树： (1) 若它的左子树不空，则左子树上所有结点 的值均小于它的根结点的值； (2) 若它的右子树不空，则右子树上所有结点 的值均大于它的根结点的值； (3) 它的左、右子树也分别为二叉排序树。
high
91 )
low
55,
mid
68,
high
91 )
low mid
high

比较结果有三种可能：
⑴ 如果r[m].key>k，说明如果存在欲查找的元素， 该元素一定在数组的前半部分，查找范围缩小了 一半，修改查找范围的上界high=m-1，继续对数 组的前半部分进行二分查找； ⑵ 如果r[m].key<k，说明如果存在欲查找的元素， 该元素一定在数组的后半部分，查找范围缩小了 一半，修改查找范围的的下界low=m+1，继续对 数组的后半部分进行二分查找； ⑶ 如果r[m].key=k，查找成功，m所指的记录就 是查找到的数据。
重复上述过程，查找范围每次缩小 1/2 ，当范围不 断缩小，出现查找范围的下界大于上界时，则查找 失败，确定关键字为key的记录不存在。 二分查找是一种效率较高的算法，最好的情况是第 一次比较即找到所查元素，即使一次比较没有找到， 也把进一步查找的范围缩小一半。与此类似，每比 较一次均使查找范围减半，对于较大的 n 显然较顺 序查找速度快得多。
查找表操作及分类


操作：(1)查询某个“特定的”数据元素是否在 查找表中；(2)查询某个“特定的”数据元素的 各种属性；(3)在查找表中插入一个数据元素； (4)从查找表中删除某个数据元素。 分类：若对查找表只作(1)和(2)两种操作，则 称此类查找表为静态查找表。若在查找过程中 同时插入查找表中不存在的数据元素，或者从 查找表中删除已存在的某个数据元素，则称此 类查找表为动态查找表。
一、 静态查找表

静态查找表是数据元素的线性表，可以是基于 数组的顺序存储或以线性链表存储。 静态查找表的基本操作： Create(&ST, n); Destroy(&ST); Search(ST,key); Traverse(ST,Visit())

1、顺序表的查找


顺序查找(Sequential search)也称为线性查找，是 采用线性表作为数据的存储结构，对数据在表中 存放的先后次序没有任何要求。 顺序查找是最简单的查找方法 基本思想：查找从线性表的一端开始，顺序将各 单元的关键字与给定值k进行比较，直至找到与k 相等的关键字，则查找成功，返回该单元的位置 序号；如果进行到表的另一端，仍未找到与k相等 的关键字，则查找不成功，返回0作为查找失败的 信息。
三、哈希表


集合结构--查找表是一种非常灵便的数据结构，关 系松散，给查找带来不便。为此，需在数据元素 之间人为地加上一些关系，以便按某种规则进行 查找，即以另一种数据结构来表示查找表。 在线性表、树表中，记录在结构中的相对位置是 随机的，查找时需进行一系列的比较，查找的效 率依赖于查找过程中所进行的比较次数。

二叉排序树的删除
• 若*p的左子树PL和右子树PR 均不空。可按中序 遍历保持有序进行调整。 即：在删去*p之前，中序遍历该二叉树得到的序 列，在删去*p之后，仍应保持其它元素的相对位 置不变， 方法：是令*p的左子树为*f的左子树，而*p的右 子树为*s的右子树； 即：是令*p的左子树PL为*f相应的子树，右子 树PR为PL中序遍历的最后一个结点 *s的右子树。
第六章 查找
静态查找表 动态查找表 哈希表

查找的基本概念
查找又称为查询或检索，是在一批记 录中依照某个域的指定域值，找出相应的 记录的操作。 在计算机中，被查找的数据对象是由 同一类型的记录构成的集合，可称之为查 找表（search table）。 在实际应用问题中，每个记录一般包 含有多个数据域，查找是根据其中某一个 指定的域进行的，这个作为查找依据的域 称为关键字（key）。
查找23和79的过程如下图：
( 08, ( 08, 14, 14, 23, 23, 37, 37,
mid=(low+high)/2不进位取整
46, 46, 55, 55, 68, 68, 79, 79, 91 ) 91 )
low
( 08, ( 08, 14, 23, 23, 37, 37,
mid
46, 46, 55, 55, 68, 68, 79, 79,
线性表与索引表：
索引表
24 58 68 82 1 5 10 13 4 9 12 16
线性表
9 22 23 24 35 42 44 58 48 60 68 67 78 77 82 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

分块查找性能分析
分块查找的平均查找长度为 ASL=Lb+Lw 其中Lb为查找索引表确定所在块的平均查找 长度， Lw为在块中查找元素的平均查找长度。 若将长度为n的表均匀地分成b块，每块含有s个 记录，即b=n/s; 又假定表中每个记录的查找概 率相等，则每块查找的概率为1/b,块中每个记录 的查找概率为1/s. 顺序查找确定所在块，平均查找长度为 ASL=Lb+Lw=(b+1)/2+(s+1)/2=((n/s+s)+1)/2 与n和s有关。
• 设有关键字为1，3，7，12，15的五个记录，定义一 个散列函数为： h(k)=(k mod m)+1 式中k为关键字，mod表示除法取余数的运算，m为 一项规定的整数。 • 假设在此我们取m=7，则按这五个关键字计算出的函 数值为： h(1)=2, h(3)=4, h(7)=1, h(12)=6, h(15)=2
分块查找的算法分两步进行，首先确定所查找的结 点属于哪一块，即在索引表中查找其所在的块，然 后在块内查找待查的数据。由于索引表是递增有序 的，可采用二分查找，而块内元素是无序的，只能 采用顺序查找。如果块内元素个数较少，则不会对 执行速度有太大的影响。 例如线性表中关键字为： 9, 22, 23, 24, 35, 42, 44, 58, 48, 60,67, 68, 78, 80, 77, 82 其索引如图所示。