資源簡介

(共48張PPT)
信息技術(shù)
字符串、列表、棧
數(shù)組、鏈表
樹、二叉樹
排序、查找、迭代、遞歸
處理不同類型數(shù)據(jù)的方式
ONTENT
目 錄
C
第一章 數(shù)據(jù)與數(shù)據(jù)的組織
數(shù)據(jù)與信息
數(shù)據(jù)
數(shù)據(jù)的組織
數(shù)據(jù)結(jié)構(gòu)的概念
常見的數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)的作用
數(shù)據(jù)的表現(xiàn)形式
數(shù)據(jù)的價(jià)值與意義
內(nèi)容總覽
數(shù)字本身無意義，沒有量的含義，數(shù)字只有在具體的情境中才具有實(shí)際的意義。
數(shù)據(jù)的表現(xiàn)形式：數(shù)字、數(shù)值、文字、圖形、圖像、音頻、視頻等
1.數(shù)字
1.1 數(shù)據(jù)
2.數(shù)值
由數(shù)字符號組成的、具有量的意義、可以進(jìn)行算數(shù)運(yùn)算的數(shù)據(jù)。
在數(shù)字化時(shí)代，數(shù)據(jù)更多的指計(jì)算機(jī)進(jìn)行符號表示的總稱。
在編程中，確定具體的量的意義，由設(shè)定數(shù)據(jù)類型能實(shí)現(xiàn)。
3.其他表現(xiàn)形式
VR
AR(增強(qiáng)現(xiàn)實(shí))：將虛擬技術(shù)與現(xiàn)實(shí)世界巧妙融合的技術(shù)，兩種信息互相補(bǔ)充，從而實(shí)現(xiàn)對真實(shí)世界的 “增強(qiáng)”。
“實(shí)景紅包”：用戶在發(fā)、收紅包時(shí)，需要同時(shí)滿足地理位置和實(shí)景紅包掃描兩個(gè)條件，相比既有的紅包形式，增強(qiáng)了互動性和趣味性。
數(shù)據(jù)的價(jià)值和意義
肢體計(jì)數(shù)、石子和貝殼計(jì)數(shù)、結(jié)繩記事、籌碼計(jì)數(shù)、計(jì)算機(jī)編碼，幫人們實(shí)現(xiàn)了信息交流和意義建構(gòu)。
密碼編譯，計(jì)算機(jī)巨人（Colossus）,ENIAC電子計(jì)算機(jī)
1.數(shù)據(jù)促進(jìn)了人類社會的發(fā)展
制藥廠根據(jù)藥品的銷售庫存數(shù)規(guī)劃下一年各種藥品的生產(chǎn)量，以確保滿足患者需求又不產(chǎn)生過多庫存。
根據(jù)當(dāng)前學(xué)校學(xué)生人數(shù)和未來人口增長趨勢，教育管理部門判斷是否需要增設(shè)新學(xué)校。
2.大數(shù)據(jù)推動人類進(jìn)入嶄新時(shí)代
“4V”特征：
數(shù)量（volume）: 數(shù)據(jù)體量大；
高速（velocity）: 數(shù)據(jù)產(chǎn)生快，數(shù)據(jù)處理速度快；
多樣（variety） : 數(shù)據(jù)類型多；
價(jià)值（value） : 價(jià)值密度低。
醫(yī)療
分析病人特征數(shù)據(jù)和療效數(shù)據(jù)，找到針對特定病人的最佳治療途徑，以減少過度治療、避免治療不足。
傳輸疫苗途中的溫度檢測與控制；
智能掛號，提高醫(yī)院運(yùn)作效率；
中草藥園的氣象站以及自動化控制設(shè)施；
電子處方，遠(yuǎn)程會診
根據(jù)手機(jī)信號在真實(shí)地理空間上的覆蓋情況，完整、客觀地還原出手機(jī)用戶的現(xiàn)實(shí)活動軌跡，從而挖掘得到人口生活空間分布與工作空間分布等特征信息，為城市規(guī)劃提供可靠的參考信息。
大數(shù)據(jù)推動人類進(jìn)入一個(gè)嶄新的時(shí)代

導(dǎo)航如何預(yù)估時(shí)間
車載導(dǎo)航？
手機(jī)導(dǎo)航？
車載導(dǎo)航的信息不全面，更新的速度又很慢，一般會買個(gè)手機(jī)支架用手機(jī)導(dǎo)航，要么就把手機(jī)導(dǎo)航投到大屏上。
只要你設(shè)定了目的地，導(dǎo)航就會計(jì)算出預(yù)計(jì)抵達(dá)的時(shí)間，即使中途會有一點(diǎn)堵車，軟件也會不斷調(diào)整達(dá)到時(shí)間。
手機(jī)導(dǎo)航實(shí)際上在我們的城市道路中，會看到很多攝像頭，這些攝像頭不只是記錄車輛的違章情況，還會檢測道路上的車流量。由于手機(jī)接收信號很及時(shí)，這些車流量的數(shù)據(jù)就會進(jìn)入到導(dǎo)航平臺，就相當(dāng)于是數(shù)據(jù)共享。因此導(dǎo)航可以接收到實(shí)時(shí)的最新道路情況，有發(fā)生擁堵的地方會提示車主繞行。（擁堵情況與行駛路線的顏色）
1.2 數(shù)據(jù)的組織
1.2.1數(shù)據(jù)元素的概念
1.數(shù)據(jù)元素
數(shù)據(jù)元素是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、節(jié)點(diǎn)、頂點(diǎn)、記錄等。一個(gè)元素有若干個(gè)數(shù)據(jù)項(xiàng)組成（也稱為字段、域）組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小數(shù)據(jù)表示單位。
某天A股物聯(lián)網(wǎng)部分股價(jià)表現(xiàn)一覽
代碼 名稱 最新價(jià)格（元/股)| 動態(tài)市盈 流通股本(萬股)
300155 安居寶 15.62 48.55 5775.62
000988 華工科技 7.78 35.61 89111.65
002104 恒寶股份 9,92 40.83 34032.05
300168 萬達(dá)信息 18.4 88.06 17006.35
000997 新大陸 9.7 52.81 50870.62
300078 中瑞思創(chuàng) 11.83 26.47 6269.87
002121 科陸電子 7.68 26.96 26762.09
600718 東軟集團(tuán) 9.09 30.9 122227.59
002161 遠(yuǎn)望谷 7.96 41.15 52082.6
002073 軟控股份 9.8 38.66 61659.73
數(shù)據(jù)元素（記錄）
5個(gè)數(shù)據(jù)項(xiàng)
數(shù)據(jù)元素的第一個(gè)數(shù)據(jù)項(xiàng)的值
2.數(shù)據(jù)類型
具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個(gè)數(shù)據(jù)集合上的一組操作。
數(shù)據(jù)類型可以分為基本數(shù)據(jù)類型（也稱為原子數(shù)據(jù)類型）和結(jié)構(gòu)數(shù)據(jù)類型。
基本數(shù)據(jù)類型由計(jì)算機(jī)編程環(huán)境提供，編程者可以在編程時(shí)直接用系統(tǒng)提供的標(biāo)識符進(jìn)行定義，如Python編程語言中的整型、實(shí)型、布爾型等。
結(jié)構(gòu)數(shù)據(jù)類型是在程序設(shè)計(jì)時(shí)利用基本數(shù)據(jù)類型構(gòu)造出的、復(fù)合的新類型，這種新類型由用戶根據(jù)實(shí)際需要定義，能較好地描述數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)組成以及數(shù)據(jù)元素之間的邏輯關(guān)系，方便用戶根據(jù)數(shù)據(jù)之間邏輯關(guān)系的特點(diǎn)進(jìn)行數(shù)據(jù)處理，如很多編程語言中提供的記錄類型、集合等。
3.數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。
包括以下三個(gè)方面內(nèi)容：
數(shù)據(jù)元素之間的邏輯關(guān)系【邏輯結(jié)構(gòu)】；
數(shù)據(jù)元素及其在計(jì)算機(jī)中內(nèi)存表示【存儲結(jié)構(gòu) or 物理結(jié)構(gòu) 】；
數(shù)據(jù)的運(yùn)算（對數(shù)據(jù)施加的操作）。
本書中無特殊說明一般指此
舉例：對一批身高數(shù)據(jù)升序操作
在計(jì)算機(jī)中，既能表示各位置身高數(shù)據(jù)，又能體現(xiàn)位置之間的線性關(guān)系的數(shù)組來組織數(shù)據(jù)。數(shù)組就是一種數(shù)據(jù)結(jié)構(gòu)。
1.2.2 常見的數(shù)據(jù)結(jié)構(gòu)
數(shù)組、鏈表、隊(duì)列、棧、樹和圖等
1.數(shù)組（排隊(duì)）
語言描述：
“第1個(gè)是李彤” “第2個(gè)是張強(qiáng)” “第3個(gè)胡杰” “第4個(gè)是杜剛”
數(shù)據(jù)序列：
a[1]=“李彤” a[2]=“張強(qiáng)”
a[3]=“胡杰” a[4]=“杜剛”
a[1]、a[2] 、a[3]、 a[4]組成了數(shù)組a；
說明這是一批類型相同的數(shù)據(jù)
下標(biāo)1、2、3、4表示數(shù)據(jù)元素所處的位置順序。
總結(jié)： 快速通過下標(biāo)精準(zhǔn)訪問序列中的某個(gè)元素（第100個(gè)元素：a[99]，第1個(gè)元素：a[0]）
通過下標(biāo)依次順序遍歷序列中的每個(gè)數(shù)據(jù)元素
遍 歷
遍歷指的是根據(jù)數(shù)據(jù)之間的邏輯結(jié)構(gòu),遵循一定的順序依次對所有數(shù)據(jù)元素做一次且僅做一次訪問。訪問某個(gè)數(shù)據(jù)元素時(shí),需要進(jìn)行的操作依賴于具體實(shí)際問題。例如，當(dāng)需要計(jì)算滿足條件的元素之和時(shí),訪問每個(gè)元素時(shí)首先判斷元素是否符合條件,若滿足則將其累加。
2.鏈表
只需知道相鄰人員之間的前后順序關(guān)系，而對每個(gè)人的位置信息并不作要求。
軍訓(xùn)時(shí)，重新整隊(duì)的時(shí)候，只需要記住排在自己前面的人是誰，而對集合地點(diǎn)不做要求。
一旦集合，本來分散的人員可以根據(jù)鏈表關(guān)系，快速按照原順序排成隊(duì)伍。
雖然整隊(duì)前后每個(gè)人員的站位發(fā)生變化，但相互之間的順序關(guān)系是不變的。
整隊(duì)后
吳堅(jiān)
王林
黃剛
李豐
常用表現(xiàn)形式：
單向鏈表、雙向鏈表、循環(huán)鏈表
頭結(jié)點(diǎn)head（指針）：
為了記錄、識別各個(gè)鏈表，在鏈表頭部設(shè)立一個(gè)頭結(jié)點(diǎn)；
遍歷時(shí)，可從head指向的頭節(jié)點(diǎn)開始依次逐個(gè)遍歷鏈表的每個(gè)節(jié)點(diǎn)
鏈表指針可以指向前面，也可以指向后面。
吳堅(jiān)
王林
黃剛
李豐 ^
head
空指針
圖1.2.6 單項(xiàng)鏈表
指 針
在計(jì)算機(jī)科學(xué)中，指針(Pointer)是用來指示一個(gè)數(shù)據(jù)存儲地址（內(nèi)存或者寄存器）的變量。如圖1.2.6所示的head，該變量存儲的是頭節(jié)點(diǎn)所在的內(nèi)存地址，或者說存儲的地址指向了頭節(jié)點(diǎn),所以形象地稱為“指針"。
為了滿足鏈表在兩個(gè)方向都能進(jìn)行遍歷，會在單項(xiàng)鏈表增加一個(gè)前驅(qū)節(jié)點(diǎn)的鏈接，轉(zhuǎn)換為雙向鏈表。
若在鏈表首尾之間增加鏈接，就形成了循環(huán)鏈表。
吳堅(jiān)
王林
黃剛
李豐
吳堅(jiān)
王林
黃剛
李豐 ^
head
吳堅(jiān)
head
王林
黃剛
李豐 ^
吳堅(jiān)
head
王林
黃剛
李豐
前驅(qū)節(jié)點(diǎn)
雙向鏈表
循環(huán)鏈表
單向鏈表（指針向前）
單向鏈表（指針向后）
作業(yè)本 （雙色版）
10.22 作業(yè)：
《1.2 初識數(shù)據(jù)結(jié)構(gòu)》周一早上交
3.隊(duì)列
乘客排隊(duì)，先到的總是從隊(duì)伍的頭部出去上車，而后到的必須在隊(duì)伍的尾部加入。
為確保有序，規(guī)定不能從中間的位置插隊(duì)。
入隊(duì)
出隊(duì)
先進(jìn)先出
不能插隊(duì)
銀行叫號系統(tǒng)：
基于隊(duì)列的FIFO（First In First Out），解決CPU和主存儲器（RAM)數(shù)據(jù)存取之間的速度差問題，會在CPU中安裝速度遠(yuǎn)快于RAM的高速緩存(Cache )。
網(wǎng)絡(luò)平臺瞬間收到很多服務(wù)請求，系統(tǒng)會按照服務(wù)請求到達(dá)的先后順序，用隊(duì)列來依次保存各個(gè)請求，然后按照入隊(duì)順序逐個(gè)出隊(duì)并處理。
入隊(duì)
出隊(duì)
4.棧
只有一端是開放的，所有操作只能在開放的一端進(jìn)行。
彈匣[典型棧結(jié)構(gòu)]
只能在連接槍體的一端進(jìn)行子彈壓裝、彈出操作;
子彈被裝入彈匣稱為“入棧”，子彈被彈出彈匣稱為“出棧”。
子彈進(jìn)出彈匣的過程具有下列特點(diǎn):
①整個(gè)裝置只有一端開放（最上端)，而且進(jìn)、出只能在這一端進(jìn)行。
②彈匣中的子彈成一縱隊(duì)排列。
③任何子彈進(jìn)出彈匣的規(guī)律是“先進(jìn)后出、后進(jìn)先出”，即最先裝入彈匣的子彈最后 才能被彈出，而最后裝入彈匣的子彈則最先被彈出。
計(jì)算機(jī)科學(xué)家就發(fā)明了“棧”這種數(shù)據(jù)結(jié)構(gòu)，用來支持符合此種數(shù)據(jù)操作規(guī)律的數(shù)據(jù)。
如網(wǎng)頁瀏覽器對用戶瀏覽網(wǎng)頁的管理，內(nèi)部就采用了棧進(jìn)行網(wǎng)頁數(shù)據(jù)的組織。
當(dāng)用戶由一個(gè)網(wǎng)頁跳轉(zhuǎn)到另一個(gè)網(wǎng)頁瀏覽時(shí)，系統(tǒng)會將原先的網(wǎng)頁數(shù)據(jù)進(jìn)行入棧操作，而當(dāng)用戶單擊瀏覽器的“后退”按鈕時(shí)，系統(tǒng)又會將棧中最上方的網(wǎng)頁數(shù)據(jù)出棧，用戶即可看到剛才最后瀏覽過的網(wǎng)頁內(nèi)容。
“先進(jìn)后出”
“后進(jìn)先出”
問題與討論
在文字處理軟件Word中進(jìn)行“撤消”操作(按CtrH+Z鍵，或者單擊撤消操作快捷按鈕“ ”)。 根據(jù)“撤消”操作所產(chǎn)生的結(jié)果，說明Word中符號輸入及撤消操作中，內(nèi)部所依托的數(shù)據(jù)結(jié)構(gòu)是哪種數(shù)據(jù)結(jié)構(gòu) 為什么
舉例：
5.樹
無論是隊(duì)列還是棧,其中的數(shù)據(jù)元素之間都呈現(xiàn)出一種線性關(guān)系，即除首尾兩端的元素外，其他數(shù)據(jù)元素的前面和后面都只有一個(gè)相鄰的元素，所有元素都成“一條線”排列。
但現(xiàn)實(shí)世界中有些數(shù)據(jù)之間的關(guān)系并非是線性關(guān)系，如生物學(xué)中的動物分類圖、中國圖書館分類法、行政部門組織結(jié)構(gòu)圖等。
這些數(shù)據(jù)元素之間的關(guān)系都呈現(xiàn)出一個(gè)共同的特點(diǎn)，即一個(gè)元素前面(或上面)只有一個(gè)元素，而后面(或下面)卻有多個(gè)（0個(gè)或多個(gè))元素相鄰，所有數(shù)據(jù)元素之間的關(guān)系特征就像一棵倒放的樹，所以稱之為樹結(jié)構(gòu)。
樹結(jié)構(gòu)
線性表
線性表是由零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列,數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系,即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素以外，中間任何一個(gè)數(shù)據(jù)元素的前面和后面都只有一個(gè)數(shù)據(jù)元素與它相鄰。線性表是一種基本的、常見的數(shù)據(jù)結(jié)構(gòu),可以根據(jù)需要向線性表增加元素，或者刪除表中的元素。數(shù)組、隊(duì)列、棧、鏈表都是線性表的特殊形式。
例 2
數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)
數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的存儲及數(shù)據(jù)元素之間關(guān)系的存儲
數(shù)據(jù)的運(yùn)算是指對數(shù)據(jù)施加的操作，包括刪除、查找、插入數(shù)據(jù)等
數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)時(shí)不需要考慮編程的實(shí)現(xiàn)和數(shù)據(jù)處理的效率
例 1
以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的描述，不正確的是 ( )
用一帶蓋的玻璃筒來放取乒乓球，放、取球只能在帶蓋的一端進(jìn)行(另一端為封閉狀態(tài))，且桶的直徑只允許一個(gè)乒乓球進(jìn)出。若放入球的編號序列為1、2、3、4，則取出球的編號序列不可能的是 （ ）
1、2、3、4
2、3、4、1
4、2、3、1
3、2、1、4
D
C
1.2.3 數(shù)據(jù)結(jié)構(gòu)的作用
每個(gè)實(shí)際問題中的數(shù)據(jù)之間存在著一定的關(guān)系，用計(jì)算機(jī)程序解決問題時(shí)，需要將數(shù)據(jù)之間的這些關(guān)系映射到程序的數(shù)據(jù)表示中，這樣才能有效地用計(jì)算機(jī)程序解決問題。
對于同一個(gè)問題的解決，當(dāng)依據(jù)不同的數(shù)據(jù)結(jié)構(gòu)來設(shè)計(jì)算法時(shí)，算法的處理效率、程序的實(shí)現(xiàn)效率也是不同的。
1.設(shè)計(jì)算法解決問題離不開數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)統(tǒng)計(jì)前，需要先收集數(shù)據(jù)并將數(shù)據(jù)按照既有的邏輯關(guān)系進(jìn)行結(jié)構(gòu)化組織，可以用一張表格來組織數(shù)據(jù)并表示數(shù)據(jù)之間的邏輯關(guān)系，如表1.2.1所示。
趣味運(yùn)動會
姓名 班級 滾鐵圈 打彈子 拍紙板 竹蜻蜓 跳繩 踢鍵子
陳濤 9 3 2
楊瓊 3 5 1
金凱 2 4 5
吳敏 1 6 1 3
朱剛強(qiáng) 6 5 1 7
…. …… …… …… …. …… …… ……
根據(jù)本問題中數(shù)據(jù)之間的線性關(guān)系特點(diǎn)，可基于數(shù)組來設(shè)計(jì)算法并解決問題。
如果不針對數(shù)據(jù)之間的關(guān)系特點(diǎn)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，而是直接用一個(gè)個(gè)簡單變量來存儲所有學(xué)生姓名和各項(xiàng)得分，在此基礎(chǔ)上設(shè)計(jì)算法及編寫程序的工作量將變得非常巨大，用計(jì)算機(jī)處理這些數(shù)據(jù)就變得毫無意義。
列方向：
性質(zhì)和類型都相同
每一列用一個(gè)一維數(shù)組存儲
2.不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
xm[i] bj[i] d1[i] d2[i] d3[i] d[4i] d5[i] d6[i] sum[i]
陳濤 9 3 0 2 0 0 0
楊瓊 3 0 0 0 0 5 1
金凱 2 0 4 5 0 0 0
吳敏 1 6 1 0 3 0 0
朱剛強(qiáng) 6 5 0 1 0 7 0
…. …… …… …… …. …… …… ……
姓名 班級 滾鐵圈 打彈子 拍紙板 竹蜻蜓 跳繩 踢鍵子
一維數(shù)組
某個(gè)選手各個(gè)項(xiàng)目總得分sum
每位選手總分保存到sum[i]中，然后將sum[i]的值累加到bjdf[bj[i]]中，每個(gè)班級總分保存在數(shù)組bjdf中。
bjdf[bj[i]]=bjdf[bj[i]]+sum[i]
二維數(shù)組
xm[i] a[i,1] a[i,2] a[i,3] a[i,4] a[i,5] a[i,6] a[i,7] a[i,8]
陳濤 9 3 0 2 0 0 0
楊瓊 3 0 0 0 0 5 1
金凱 2 0 4 5 0 0 0
吳敏 1 6 1 0 3 0 0
朱剛強(qiáng) 6 5 0 1 0 7 0
…. …… …… …… …. …… …… ……
第i位選手的班級
第i位選手在6個(gè)項(xiàng)目上的得分
第i位選手的總得分
為了統(tǒng)計(jì)每位學(xué)生和各班的總得分，基于二維數(shù)組的總體算法同樣可通過遍歷每位選手的相關(guān)數(shù)據(jù)進(jìn)行，但在用計(jì)算機(jī)程序語言描述算法（編寫程序）時(shí)，相比于一維數(shù)組，二維數(shù)組在程序?qū)崿F(xiàn)上效率要高于前者，特別在每位選手統(tǒng)計(jì)部分。如果數(shù)據(jù)項(xiàng)數(shù)量增加，那么兩者相差會更大。
作業(yè)本 （雙色版）
10.26 作業(yè)：
《1.2 初識數(shù)據(jù)結(jié)構(gòu)》周三早上交
數(shù)據(jù)合并
1.生產(chǎn)廠家對各地產(chǎn)品銷量的數(shù)據(jù)進(jìn)行歸納整合（按各產(chǎn)品銷量進(jìn)行從大到小排序）降序！
各個(gè)地區(qū)的數(shù)據(jù)合并問題可以簡化為2個(gè)地區(qū)的數(shù)據(jù)合并問題，當(dāng)2個(gè)地區(qū)的數(shù)據(jù)合并完成后，剩余各地區(qū)的數(shù)據(jù)合并就可以按照同樣方式完成。因此，接下來著重分析2個(gè)地區(qū)的數(shù)據(jù)合并問題。
第一步 抽象與建模
設(shè)第1個(gè)地區(qū)共有n個(gè)產(chǎn)品銷量數(shù)據(jù)，第2個(gè)地區(qū)共有m個(gè)產(chǎn)品銷量數(shù)據(jù)。為了簡化描述，突出核心部分的分析，考慮將問題抽象為n個(gè)有序整數(shù)和m個(gè)有序整數(shù)的合并問題，具體的問題模型如下:
已知一個(gè)降序排列的非負(fù)整數(shù)數(shù)列A: ，以及一個(gè)降序排列的非負(fù)整數(shù)數(shù)列B: ，將兩個(gè)數(shù)列合并形成一個(gè)新的有序數(shù)列C，使新數(shù)列仍按降序排列，即≥ ≥ ≥ …≥ ≥ ≥… (其中∈A或者∈B)。請完成解決該問題的數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)。
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
第二步 設(shè)計(jì)、描述算法
1. 基于數(shù)組的算法設(shè)計(jì)與描述
（1）將數(shù)組a中所有元素存儲到數(shù)組c的前n個(gè)位置中；
1 2 3 4 5
19 16 12 8 5
a
19
16
12
8
5
1 2 3 4 5
19 16 12 8 5
b
20
15
14
10
4
1 2 3 4 5 6 7 8 9 10
c
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
第二步 設(shè)計(jì)、描述算法
1. 基于數(shù)組的算法設(shè)計(jì)與描述
（2）將數(shù)組c右邊的m個(gè)元素賦值為–1（c(n+1)直到c(n+m)）；
1 2 3 4 5
19 16 12 8 5
a
19
16
12
8
5
1 2 3 4 5
19 16 12 8 5
b
20
15
14
10
4
c
-1
-1
-1
-1
-1
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
第二步 設(shè)計(jì)、描述算法
1. 基于數(shù)組的算法設(shè)計(jì)與描述
（3）變量p賦值為0，將表示數(shù)組c中有效元素總個(gè)數(shù)的變量tot賦值為n ；
1 2 3 4 5
19 16 12 8 5
a
19
16
12
8
5
1 2 3 4 5
19 16 12 8 5
b
20
15
14
10
4
c
-1
-1
-1
-1
-1
0
i
p
tot
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
（4）將數(shù)組b中元素b(i)逐個(gè)插入到數(shù)組c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
-1
-1
-1
0
i
p
tot
①p值增加1；
②如果c(p)＞b(i)，那么使p值增加1；
③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時(shí)tot值增加1；
④ 如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個(gè)位置，然后將b(i)存儲到c(p)中，同時(shí)tot值增加1。
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
（4）將數(shù)組b中元素b(i)逐個(gè)插入到數(shù)組c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
-1
-1
0
i
p
tot
①p值增加1；
②如果c(p)＞b(i)，那么使p值增加1；
③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時(shí)tot值增加1；
④ 如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個(gè)位置，然后將b(i)存儲到c(p)中，同時(shí)tot值增加1。
p
p
②如果c(p)＞b(i)，那么使p值增加1；
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
（4）將數(shù)組b中元素b(i)逐個(gè)插入到數(shù)組c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
-1
0
i
tot
①p值增加1；
②如果c(p)＞b(i)，那么使p值增加1；
③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時(shí)tot值增加1；
④ 如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個(gè)位置，然后將b(i)存儲到c(p)中，同時(shí)tot值增加1。
p
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
（4）將數(shù)組b中元素b(i)逐個(gè)插入到數(shù)組c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
0
i
tot
①p值增加1；
②如果c(p)＞b(i)，那么使p值增加1；
③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時(shí)tot值增加1；
④ 如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個(gè)位置，然后將b(i)存儲到c(p)中，同時(shí)tot值增加1。
p
p
1 2 3 4 5 6 7 8 9 10
不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同
（4）將數(shù)組b中元素b(i)逐個(gè)插入到數(shù)組c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
0
i
tot
①p值增加1；
②如果c(p)＞b(i)，那么使p值增加1；
③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時(shí)tot值增加1；
④ 如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個(gè)位置，然后將b(i)存儲到c(p)中，同時(shí)tot值增加1。
p
p
p
2.基于鏈表的算法設(shè)計(jì)與描述
用鏈表a存儲數(shù)列A，且從頭節(jié)點(diǎn)開始鏈表中每個(gè)元素成降序排列。用同樣的方法將數(shù)列B存儲到鏈表b中。兩個(gè)鏈表的初始狀態(tài)如圖1.2.19所示，其中指針p、q分別指向每個(gè)鏈表的當(dāng)前節(jié)點(diǎn)，指針p1指向鏈表a當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，指針q1指向鏈表b當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。
19
16
12
5 ^
8
head_a
指針p1
指針p
鏈表a:
20
15
14
4 ^
10
鏈表b:
head_b
指針q1
指針q
兩個(gè)數(shù)列的合并=兩個(gè)鏈表的合并
題目要求，將鏈表b中q指針?biāo)腹?jié)點(diǎn)插人到鏈表a中
只需將q所指元素與p所指元素比較;
如果p所指元素大于q所指元素，那么使p指針后移到下一個(gè)節(jié)點(diǎn)(同時(shí)指針p1也移到下一個(gè)節(jié)點(diǎn))，直到p所指元素小于或等于q所指元素。
此時(shí)，不必像數(shù)組中那樣移動數(shù)列C中的元素，而只需調(diào)整指針的指向，即可將q所指元素插人到鏈表a中p所指元素之前。
19
16
12
5 ^
8
head_a
指針p1
指針p
鏈表a:
20
15
14
4 ^
10
鏈表b:
head_b
指針q1
指針q
19
16
12
5 ^
8
head_a
指針p1
指針p
鏈表a:
20
15
14
4 ^
10
鏈表b:
head_b
指針q1
指針q
當(dāng)將鏈表b中第一個(gè)元素20插入鏈表a時(shí):
只需將鏈表a中p1所指節(jié)點(diǎn)的后繼指針指向q所指元素;
鏈表b中q1所指節(jié)點(diǎn)的后繼指針指向q所指節(jié)點(diǎn)的后繼節(jié)點(diǎn)(元素15所在節(jié)點(diǎn));
q所指節(jié)點(diǎn)的后繼指針指向p所指節(jié)點(diǎn);
最后將指針q指向q1所指節(jié)點(diǎn)的后繼節(jié)點(diǎn)。
19
16
12
5 ^
8
head_a
指針p1
指針p
20
15
14
4 ^
10
head_b
指針q1
指針q
當(dāng)將鏈表b中第一個(gè)元素20插入鏈表a時(shí):
只需將鏈表a中p1所指節(jié)點(diǎn)的后繼指針指向q所指元素;
鏈表b中q1所指節(jié)點(diǎn)的后繼指針指向q所指節(jié)點(diǎn)的后繼節(jié)點(diǎn)(元素15所在節(jié)點(diǎn));
q所指節(jié)點(diǎn)的后繼指針指向p所指節(jié)點(diǎn);
最后將指針q指向q1所指節(jié)點(diǎn)的后繼節(jié)點(diǎn)。
從用上述兩種數(shù)據(jù)結(jié)構(gòu)分別來解決同一個(gè)問題的過程可知，不同的數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致算法的不同，而且解決問題的效率也不同。
例如，用數(shù)組實(shí)現(xiàn)時(shí)需要將插入位置后面的所有元素逐個(gè)右移一位，當(dāng)數(shù)列B中元素全部大于數(shù)列A中第一個(gè)元素時(shí)，將數(shù)列B中m個(gè)元素全部插入到數(shù)列A共需要移動n×m次;
當(dāng)兩個(gè)數(shù)列的元素大小比較均勻時(shí)，如A數(shù)列元素為20，18，16，12，6，而B數(shù)列元素為21，19，17，15，8時(shí)，共需要移動的次數(shù)也達(dá)到n+(n-1)+…+2+1= 次。
用鏈表實(shí)現(xiàn)時(shí)，向鏈表a中插入一個(gè)節(jié)點(diǎn)，最多需要5次指針操作，所以最多需要5m次指針操作，要比基于數(shù)組的處理低一個(gè)數(shù)量級。
鏈表 VS 數(shù)組
在插入元素中，
鏈表：動態(tài)存儲、無需移動位置，只需找到頭結(jié)點(diǎn)head
數(shù)組：靜態(tài)存儲、需要移動位置
1.2作業(yè)：
《創(chuàng)新設(shè)計(jì)》作業(yè)本 課時(shí)2
教學(xué)案 P6-P7

展開更多......

收起↑