資源簡介

(共39張PPT)
3.3數(shù)據(jù)的查找
高中信息技術(shù)/教科版/選擇性必修1
目錄
1.創(chuàng)設(shè)情境，
導(dǎo)入新課
2.體驗探究，初始查找
3.討論探究，實現(xiàn)查找
4.自主探究，二分查找
5.遞歸實現(xiàn)二分查找
6.課堂小結(jié)
1.創(chuàng)設(shè)情境，導(dǎo)入新課
在網(wǎng)上商城眾多的商品數(shù)據(jù)中，如何快速地查找到所需商品的相關(guān)信息呢
本節(jié)圍繞“網(wǎng)上商城查找商品”項目展開學習，通過項目活動體驗計算機查找數(shù)據(jù)的過程，理解算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。本節(jié)主要包含“根據(jù)品牌查找商品”和“根據(jù)價格查找商品”兩個任務(wù)。
2.體驗探究，初始查找
任務(wù)一 根據(jù)品牌查找商品 活動1體驗順序查找過程
表3.3.1所示是某網(wǎng)上商城的簽字筆銷售數(shù)據(jù)，如何在表中查詢到品牌為“得利”的簽字筆銷售數(shù)據(jù)呢
品牌 銷量/盒 價格/元 評論數(shù)/條
博士 80 66 108
英雄 188 78 86
永輝 236 58 186
晨輝 200 46 190
得利 56 68 50
梅花 185 26 92
凌梅 68 32 65
巧虎 221 72 198
表3.3.1簽字筆銷售數(shù)據(jù)
從表格的第1行數(shù)據(jù)開始，先比較第1行數(shù)據(jù)中的品牌與“得利”是否相等，如果相等則說明查找成功;如果不相等則繼續(xù)與下一個數(shù)據(jù)進行比較，直到所有數(shù)據(jù)都比較完畢。
任務(wù)一 根據(jù)品牌查找商品 活動1體驗順序查找過程
第 1次比較:“博士”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較第 2次比較:“英雄”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較。請根據(jù)這個思路，繼續(xù)完成后面幾個數(shù)據(jù)的比對過程。
第3次比較: 。
第4次比較: 。
第5次比較: 。
從第1個數(shù)據(jù)開始，按順序逐一進行比較，經(jīng)過5次比較，找到品牌為“得利”的簽字筆銷售數(shù)據(jù)。
填一填
“永輝”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較
“晨輝”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較
“得利”與“得利”相等,結(jié)束比較
通過剛才的查找體驗，你能分別給查找和順序查找下個定義嗎？
查找(searching)就是在數(shù)據(jù)表中確定一個與給定值相等的數(shù)據(jù)若存在這樣的數(shù)據(jù)則表示查找成功，否則表示查找不成功。
順序查找(sequential search )是一種從頭開始逐個數(shù)據(jù)進行比較的查找方法。
從數(shù)據(jù)表中第1個數(shù)據(jù)開始，逐個與要查找的數(shù)據(jù)進行比較，如果與要查找的數(shù)據(jù)相等，則查找成功;
如果直至最后個數(shù)據(jù)，與要查找的數(shù)據(jù)都不相等，則查找不成功。
順序查找的過程
3.討論探究，實現(xiàn)查找
任務(wù)一 根據(jù)品牌查找商品 活動2建立數(shù)據(jù)結(jié)構(gòu)
創(chuàng)建一個線性表對象alist，存放表3.3.1所示的簽字筆銷售數(shù)據(jù)對象。請補全下面的代碼。
填一填
01. from linearList import LinearList #導(dǎo)人線性表
02.alist= #創(chuàng)建線性表對象
03.alist.appendItem(pen("博士",80,66,108))#添加簽字筆數(shù)據(jù)元素
04.alist.appendItem(pen("英雄",188,78,86))#添加簽字筆數(shù)據(jù)元素
05.alist.appendItem(pen("永輝",236,58,186))#添加簽字筆數(shù)據(jù)元素
LinearList ( )
任務(wù)一 任務(wù)一 根據(jù)品牌查找商品 活動2建立數(shù)據(jù)結(jié)構(gòu)
06. alist.appendItem(pen( ))#添加簽字筆數(shù)據(jù)元素
07. alist.appendItem(pen( ))#添加簽字筆數(shù)據(jù)元素
08. alist.appendItem(pen( ))#添加簽字筆數(shù)據(jù)元素
09. alist.appendItem(pen( ))#添加簽字筆數(shù)據(jù)元素
10. alist.appendItem(pen( ))#添加簽字筆數(shù)據(jù)元素
"晨輝",200,46,190
"得利",56,68,50
"梅花",185,26,92
"凌美",68,32,65
"巧虎",221,72,198
任務(wù)一 根據(jù)品牌查找商品 活動3順序查找算法的設(shè)計與實現(xiàn)
假設(shè)有n個簽字筆銷售數(shù)據(jù)，實現(xiàn)順序查找的算法描述如下。
(1) 從線性表中的第1個數(shù)據(jù)開始，依次進行操作 (2)
(2)將當前數(shù)據(jù)與要查找數(shù)據(jù)進行比較，如果相等，則查找成功，返回數(shù)據(jù)在表中的位置，查找結(jié)束。如果不相等，則繼續(xù)查找。
(3) 查找失敗。
請將上述順序查找的算法過程轉(zhuǎn)化為流程圖。
任務(wù)一 根據(jù)品牌查找商品 活動3順序查找算法的設(shè)計與實現(xiàn)
根據(jù)上述算法，定義sequentialSearch(alist,key,item)函數(shù)，參數(shù)alist表示存儲數(shù)據(jù)的線性表，key表示查找的關(guān)鍵詞，參數(shù)item表示要查找的數(shù)據(jù)。請補全下面的代碼。
11.#順序查找算法
12. def sequentialSearch(alist， key， item):
13.i=0 #初始化循環(huán)變量
14.while i15.#判斷第i個位置上的數(shù)據(jù)與查找的數(shù)據(jù)是否相等
16.if getattr( ,key)==item:
17.return #返回查找到的數(shù)據(jù)在表中的位置
18.else:
19.i=i+l #進行下一個數(shù)據(jù)比較
19.return -1 #返回查找失敗
alist.getItem(i)
i
任務(wù)一 根據(jù)品牌查找商品 活動3順序查找算法的設(shè)計與實現(xiàn)
以表3.3.1中的數(shù)據(jù)為例，利用順序查找法查找品牌為“得利”的簽字筆，并顯示查找到的簽字筆銷售數(shù)據(jù)。請補全下面的代碼。
21. result=sequentialSearch(alist， ， ) #調(diào)用順序查找函數(shù)
22.print(“順序查找的結(jié)果是:“)
23. if result==-1:
24.print("查找失敗")
25.else:
print(getattr(alist.getItem(result),'brand'), ,
, )#顯示查找結(jié)果
‘brand’
‘凌美’
alist.getItem(result),'sales'
alist.getItem(result),'price'
alist.getItem(result),'comments'
假設(shè)有n個數(shù)據(jù)，利用順序查找法，整個查找過程需要進行k(1kn)次數(shù)據(jù)比較，可以利用循環(huán)語句實現(xiàn)。
4.自主探究，二分查找
任務(wù)二 根據(jù)價格查找商品 活動1體驗二分查找過程
在表3.3.1中如何快速查找到價格是68的簽字筆銷售數(shù)據(jù)呢
品牌 銷量/盒 價格/元 評論數(shù)/條
博士 80 66 108
英雄 188 78 86
永輝 236 58 186
晨輝 200 46 190
得利 56 68 50
梅花 185 26 92
凌梅 68 32 65
巧虎 221 72 198
表3.3.1 按價格升序排列后的簽字筆銷售數(shù)據(jù)
把簽字筆銷售數(shù)據(jù)表按照價格進行升序排列，找到中間項 (位于表中間位置 ) 數(shù)據(jù)，如果查找項與中間項相等，則查找結(jié)束。如果查找項比中間項大，可以把數(shù)據(jù)表中較小的那部分 (包括中間項) 排除了，因為如果查找項在中，那它一定在較大的那一半中。接下來，可以在較大的一半中重這個過程。如果查找項比中間項小，可以把數(shù)據(jù)表中較大的那部分包括中間項) 排除了，因為如果查找項在表中，那它一定在較小的那一半中。接下來，在較小的一半中重復(fù)這個過程即可。
任務(wù)二 根據(jù)價格查找商品 活動1體驗二分查找過程
品牌 銷量/盒 價格/元 評論數(shù)/條
梅花 185 26 92
凌梅 68 32 65
晨輝 200 46 190
永輝 236 58 186
博士 80 66 108
得利 56 68 50
巧虎 221 72 198
英雄 188 78 86
表3.3.2 按價格升序排列后的簽字筆銷售數(shù)據(jù)
任務(wù)二 根據(jù)價格查找商品 活動1體驗二分查找過程
第1次查找:確定數(shù)據(jù)表的中間項是價格為58的簽字筆，如圖所示。將查找項與中間項進行比較，68>58，排除較小的那部分和中間項。
梅花26
凌梅32
晨輝46
永輝58
博士66
得利68
巧虎72
英雄78
中間項
第1次查找
任務(wù)二 根據(jù)價格查找商品 活動1體驗二分查找過程
第2次查找:在數(shù)據(jù)表較大的部分中繼續(xù)查找，確定數(shù)據(jù)表較大部分的中間項是68，如圖所示。將查找項與中間項進行比較，68=68，查找成功。
博士66
得利68
巧虎72
英雄78
中間項
第2次查找
請根據(jù)這個思路，寫出查找價格是46的簽字筆銷售數(shù)據(jù)的過程。
任務(wù)二 根據(jù)價格查找商品 活動1體驗二分查找過程
第1次查找:確定數(shù)據(jù)表的中間項是價格為 58 的簽字筆，將查找項與中間項進行比較，46<58，排除較大的那部分和中間項。
梅花26
凌梅32
晨輝46
永輝58
博士66
得利68
巧虎72
英雄78
中間項
第 2次查找:確定數(shù)據(jù)表的中間項是價格為 32 的簽字筆，將查找項與中間項進行比較，46>32，排除較小的那部分和中間項。
梅花26
凌梅32
晨輝46
中間項
第
1
次查找
第
2
次查找
第 3次查找:確定數(shù)據(jù)表的中間項是價格為46 的簽字筆，46=46，查找成功。
對于有序表的查找，從表的中間項開始比對，如果表的中間項匹配查找項，則查找結(jié)束。如果不匹配，就有兩種情況: 表的中間項比查找項大，那么查找項只可能出現(xiàn)在前半部分;表的中間項比查找項小，那么查找項只可能出現(xiàn)在后半部分。重復(fù)上述查找過程，每次都會將比對范圍縮小一半，直到查找結(jié)束。這種查找的方法，稱為二分查找。
二分查找概念
任務(wù)二 根據(jù)價格查找商品 活動2二分查找算法的設(shè)計與實現(xiàn)
假設(shè)有n種商品，實現(xiàn)二分查找的算法描述如下：
(1)確定查找范圍，每次查找如步驟 (2)和(3)，如果沒有完成則繼續(xù)操作。第1次查找的范圍是n個數(shù)據(jù)。
(2) 取得查找范圍的中間位置，將查找數(shù)據(jù)與中間位置的數(shù)據(jù)進行比對，如果二者相等則查找成功，返回數(shù)據(jù)在表中的位置。
(3) 如果查找數(shù)據(jù)小于中間位置的數(shù)據(jù)則縮小查找范圍至前半部分，如果大于中間位置的數(shù)據(jù)則縮小查找范圍至后半部分。
二分查找的算法步驟
任務(wù)二 根據(jù)價格查找商品 活動2二分查找算法的設(shè)計與實現(xiàn)
根據(jù)上述算法，定義binarySearch(alist,key,item)函數(shù)，參數(shù)alist表示按關(guān)鍵字key排序后的線性表，參數(shù)key表示查找的關(guān)鍵字，參數(shù)item表示要查找的數(shù)據(jù)。請補全下面的代碼。
填一填
11.#二分找算法
12. def binarySearch(alist， key， item)：
13.first=0 #標記查找范圍起始位置
14.last=alist.size()-1 #標記查找范圍終點位置
15.while first<=last:
16.mid=( )//2 #取得查找范圍的中間位置
first+last
任務(wù)二 根據(jù)價格查找商品 活動2二分查找算法的設(shè)計與實現(xiàn)
填一填
17.#判斷中間項是否等于查找項
18. if getattr(alist.getItem(mid),key)==item:
19.#返回查找到的商品在線性表中的位置
20. return mid
21. else:
22.#判斷查找項是否小于中間項
23.if item24.last=mid-1 #縮小查找范圍至前半部分
25.else:
26.first= .
27.return -1 #返回查找失敗
alist.getItem(mid),key
mid+1
任務(wù)二 根據(jù)價格查找商品 活動2二分查找算法的設(shè)計與實現(xiàn)
以表3.3.1中的數(shù)據(jù)為例，利用二分查找法查找價格為68的簽字筆銷售數(shù)據(jù)，并顯示查找到的簽字筆銷售數(shù)據(jù)。請補全下面的代碼。
28.bubbleSort(alist，'price') #調(diào)用冒泡排序函數(shù)
29.result=binarySearch(alist， ， #調(diào)用二分查找函數(shù)
30.print("二分查找法查找的結(jié)果是:“)
31.if result==-1:
32. print("查找失敗")
33.else:
34. print(getattr(alist.getItem(result),'brand'), ，
35. ， )
‘price’
68
getattr(alist.getItem(result),'price')
getattr(alist.getItem(result),'sales')
getattr(alist.getItem(result),'comments')
5.遞歸實現(xiàn)二分查找
任務(wù)二 根據(jù)價格查找商品 活動3利用遞歸法實現(xiàn)二分查找
利用遞歸法實現(xiàn)二分查找，定義recursionSearch(alist,key,item,first,last)函數(shù)，參數(shù)alist表示按關(guān)鍵字key排序后的線性表對象，參數(shù)key表示查找的關(guān)鍵字，參數(shù)item表示要查找的數(shù)據(jù)，參數(shù)first表示查找范圍的起始位置，參數(shù)last表示查找范圍的結(jié)束位置。利用Pvthon編寫的代碼如下，請補全下面的代碼。
01.#利用遞歸方法實現(xiàn)二分查找算法
02. def recursionSearch(alist,key,item,first,last):
03.if first<=last:
04.mid=(first+last)//2 #取得中間項位置
05.else:
06.return -1 #返回查找失敗
任務(wù)二 根據(jù)價格查找商品 活動3利用遞歸法實現(xiàn)二分查找
以表3.3.1中的數(shù)據(jù)為例，利用遞歸二分查找法查找商品價格為32的商品，并顯示該商品的相關(guān)信息。請補全下面的代碼。
18.bubbleSort(alist，'price') #調(diào)用冒泡排序函數(shù)
19.#調(diào)用遞歸二分查找函數(shù)
20.result=recursionSearch(alist， , , , )
21.print(“遞歸二分查找法查找的結(jié)果是:“)
22.if result==-1:
23.print("查找失敗")
24.else:
25.#顯示查找結(jié)果
26.print(getattr( ,‘brand')， ,
‘price’
32
alist.size( )
0
alist.getItem(result)
getattr(alist.getItem(result),‘sales'
任務(wù)二 根據(jù)價格查找商品 活動3利用遞歸法實現(xiàn)二分查找
07.#中間項與查找項比較
08.if getattr(alist.getItem(mid), key)==item:
09.return mid #返回查找到的商品在線性表中的位置
10.else:
11.#判斷查找項是否小于中間項
12.if item13.#遞歸調(diào)用
14.return recursionSearch(alist,key,item,first, )
15.else:
16.#遞歸調(diào)用
17.return recursionSearch(alist,key,item, ,last)
alist.getItem(mid)
mid-1
填一填
mid+1
當對一個有序表執(zhí)行二分查找時，首先確定中間項。如果查找項比中間項小，可以在原來表的前半部分執(zhí)行二分查找;如果查找項比中間項大，可以在后半部分執(zhí)行二分查找。分析二分查找算法的過程可以發(fā)現(xiàn)它是把一個問題分解成更小規(guī)模的問題，先用一些方法解決這些更小規(guī)模的問題，然后重組整個問題來得到結(jié)果。
6.課堂小結(jié)
本節(jié)我們學習了查找的基本概念、順序查找算法的基本思想和實現(xiàn)方法、二分查找算法的基本思想和實現(xiàn)方法、遞歸方法實現(xiàn)二分查找算法的基本思路。
請同學們認真完成教材中的拓展練習哦！
下節(jié)課見！

展開更多......

收起↑