多媒體課件畢業(yè)設(shè)計(jì)論文

1、<p><b>　　畢業(yè)設(shè)計(jì)論文</b></p><p>　　設(shè)計(jì)（論文）題目：基于工作過(guò)程數(shù)據(jù)結(jié)構(gòu)多媒體課件設(shè)計(jì) </p><p>　　基于工作過(guò)程數(shù)據(jù)結(jié)構(gòu)多媒體課件設(shè)計(jì) </p><p>　　摘要: 伴隨高職教育以工作過(guò)程為導(dǎo)向的新一輪改革，多媒體技術(shù)以其易于再現(xiàn)和

2、模擬實(shí)際工作過(guò)程的優(yōu)勢(shì)，一定能在新一輪教學(xué)改革中發(fā)揮舉足輕重的作用。本文作為一個(gè)實(shí)例，表現(xiàn)了基于工作過(guò)程數(shù)據(jù)結(jié)構(gòu)多媒體課件設(shè)計(jì)，可新技術(shù)發(fā)展下可以實(shí)現(xiàn)的載體。CAI模式的應(yīng)用，克服了傳統(tǒng)教學(xué)方式上單一、片面的缺點(diǎn)。它的使用能有效地縮短學(xué)習(xí)時(shí)間、提高教學(xué)質(zhì)量和教學(xué)效率，實(shí)現(xiàn)最優(yōu)化的教學(xué)目標(biāo)。而把工作過(guò)程運(yùn)用在實(shí)踐中，也成了檢驗(yàn)教學(xué)應(yīng)用質(zhì)量的方式。 </p><p>　　關(guān)鍵詞:工作過(guò)程,課程改革,多媒體,課件設(shè)計(jì),

3、新技術(shù)</p><p>　　Multimedia courseware design based on the work process data structure</p><p><b>　　Abstract</b></p><p>　　With the vocational education new round of reform wo

4、rk process-oriented, multimedia technology for its advantages of easy to reproduce and simulate the actual working process, will be able to play in the new round of teaching reform in a pivotal role. This article as an e

5、xample, the performance of multimedia courseware design based on the data structure of the work process, the carrier can be achieved in the development of new technologies. CAI mode, to overcome the traditional teaching

6、methods </p><p>　　Keywords: work process, curriculum reform, multimedia, courseware design, new technology</p><p><b>　　目錄</b></p><p><b>　　摘要:II</b></p>

7、;<p>　　第一章 背景簡(jiǎn)介1</p><p>　　1.1 多媒體技術(shù)的定義1</p><p>　　第二章、數(shù)據(jù)結(jié)構(gòu)部分介紹2</p><p><b>　　2.1 二叉樹(shù)2</b></p><p>　　2.1.1 二叉樹(shù)的定義2</p><p>　　2.1.2 二叉樹(shù)的重

8、要性質(zhì)3</p><p>　　2.1.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5</p><p>　　2.1.4 二叉樹(shù)二叉鏈表生成算法6</p><p><b>　　2.2 隊(duì)列8</b></p><p>　　2.2.1 隊(duì)列的應(yīng)用實(shí)例及概念8</p><p>　　2.2.2 隊(duì)列的存儲(chǔ)方式10<

9、/p><p>　　2.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)10</p><p>　　2.2.4 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)12</p><p><b>　　2.3 排序16</b></p><p>　　2.3.1 排序的基本概念16</p><p>　　2.3.2 插入排序17</p><

10、p>　　2.3.3 直接插入排序17</p><p>　　2.3.4 冒泡排序19</p><p>　　第三章 相關(guān)軟件介紹21</p><p>　　2.1 Flash課件的特點(diǎn)21</p><p>　　2.1.1 Flash課件優(yōu)勢(shì):21</p><p>　　2.1.2 flash課件的效果:21&

11、lt;/p><p>　　2.2 Flash制作介紹.22</p><p>　　2.2.1 基本操作界面.22</p><p>　　2.2.2 Flash中的Shape與Motion的動(dòng)畫(huà)：23</p><p>　　2.2.3 庫(kù)面板23</p><p>　　第四章 多媒體課件的設(shè)計(jì)與開(kāi)發(fā)過(guò)程24</p>

12、;<p><b>　　4.1 選題25</b></p><p>　　4.1.1 確定項(xiàng)目范圍25</p><p>　　4.1.2 分析學(xué)習(xí)者分析26</p><p>　　4.2 明確項(xiàng)目限制條件26</p><p>　　4.2.1 制定評(píng)價(jià)表和項(xiàng)目標(biāo)準(zhǔn)26</p><p>

13、　　4.2.2 課件總體印象27</p><p>　　4.2.3 規(guī)范和慣例27</p><p>　　第五章 多媒體項(xiàng)目課件的規(guī)劃28</p><p>　　5.1 設(shè)計(jì)制作多媒體課件應(yīng)注意的幾個(gè)問(wèn)題28</p><p>　　5.1.1 課件的界面要精致美觀，盡量做到風(fēng)格統(tǒng)一，畫(huà)面簡(jiǎn)潔28</p><p>　　

14、5.1.2 要考慮到課件的實(shí)用性，不可華而不實(shí)29</p><p>　　5.2 源代碼項(xiàng)目目的30</p><p>　　5.3 項(xiàng)目要求31</p><p>　　5.4 項(xiàng)目對(duì)象32</p><p>　　5.5 課件制作方法及常見(jiàn)問(wèn)題的探討32</p><p>　　5.5.1 課件制作軟件的選擇及設(shè)計(jì)思想定位

15、32</p><p>　　5.5.2 制作教學(xué)課件應(yīng)注意的幾點(diǎn)事項(xiàng)33</p><p>　　5.5.3 首頁(yè)設(shè)計(jì)花哨新穎34</p><p>　　第六章 多媒體教學(xué)設(shè)計(jì)36</p><p>　　6.1 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)36</p><p>　　6.1.1 原型開(kāi)發(fā)36</p><p>　

16、　6.1.2 稿本編寫(xiě)37</p><p>　　6.1.3 媒體的選擇37</p><p>　　6.2選擇和收集資源38</p><p>　　6.2.1學(xué)科內(nèi)容資源38</p><p>　　6.2.2教學(xué)設(shè)計(jì)資源39</p><p>　　6.3 確定課件總體印象39</p><p>

17、　　6.3.1 初步構(gòu)思39</p><p>　　6.3.2 速原型法39</p><p>　　第七章 總結(jié)和展望40</p><p>　　7.1 存在問(wèn)題40</p><p>　　7.2 設(shè)計(jì)展望暨致謝40</p><p><b>　　第一章 背景簡(jiǎn)介</b></p>&

18、lt;p>　　1.1 多媒體技術(shù)的定義</p><p>　　多媒體技術(shù)是專(zhuān)指于電腦程序中處理圖形、圖像、影音、聲訊、動(dòng)畫(huà)等的電腦應(yīng)用技術(shù)。</p><p>　　在計(jì)算機(jī)系統(tǒng)中，組合兩種或兩種以上媒體的一種人機(jī)交互式信息交流和傳播媒體。使用的媒體包括文字、圖片、照片、聲音 (包含音樂(lè)、語(yǔ)音旁白、特殊音效)、動(dòng)畫(huà)和影片，以及程式所提供的互動(dòng)功能。</p><p>

19、　　第二章、數(shù)據(jù)結(jié)構(gòu)部分介紹</p><p><b>　　2.1 二叉樹(shù)</b></p><p>　　2.1.1 二叉樹(shù)的定義</p><p>　　二叉樹(shù)（Binary Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諛?shù)（n=0），或?yàn)榉强諛?shù)；對(duì)于非空樹(shù)有：</p><p>　?、庞幸粋€(gè)特定的稱(chēng)之為根的結(jié)點(diǎn)；</

20、p><p>　?、聘Y(jié)點(diǎn)以外的其余結(jié)點(diǎn)分別由兩棵互不相交的稱(chēng)之為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。</p><p>　　這個(gè)遞歸定義表明二叉樹(shù)或?yàn)榭?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)組成。由于左、右子樹(shù)也是二叉樹(shù)，則由二叉樹(shù)的定義，它們也可以為空。由此，二叉樹(shù)可以有五種基本形態(tài)，如圖1-1所示。</p><p><b>　　圖1-1&

21、lt;/b></p><p><b>　　(a)空二叉樹(shù) </b></p><p>　　(b)只有一個(gè)根結(jié)點(diǎn)</p><p>　　(c)有根結(jié)點(diǎn)和左子樹(shù) </p><p>　　(d)有根結(jié)點(diǎn)和右子樹(shù) </p><p>　　(e) 有根結(jié)點(diǎn)和左，右子樹(shù)</p><p>

22、　　從以上分析得知二叉樹(shù)與普通樹(shù)比較，有以下特點(diǎn)：</p><p>　?、哦鏄?shù)可以為空樹(shù)。</p><p>　?、贫鏄?shù)的度不大于2(即每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù))。</p><p>　?、嵌鏄?shù)是有序樹(shù)，其左子樹(shù)和右子樹(shù)是嚴(yán)格區(qū)分且不能隨意顛倒的。</p><p>　　2.1.2 二叉樹(shù)的重要性質(zhì)</p><p>　

23、　性質(zhì)1 二叉樹(shù)第i（i≥1）層上至多有2i-1個(gè)結(jié)點(diǎn)。</p><p>　　根據(jù)二叉樹(shù)和結(jié)點(diǎn)層次的定義可知，根結(jié)點(diǎn)在第一層上，這層結(jié)點(diǎn)數(shù)至多為1個(gè)，即20個(gè)；顯然第二層上至多有2個(gè)結(jié)點(diǎn)，即21個(gè)；…假設(shè)第i-1層的結(jié)點(diǎn)至多有2i-2個(gè)，且每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，那么第i層上結(jié)點(diǎn)至多有2×2i-2=2i-1個(gè)。</p><p>　　性質(zhì)2 深度為k（k≥1）的二叉樹(shù)至多有2k

24、-1個(gè)結(jié)點(diǎn)。</p><p>　　由性質(zhì)1可知各層結(jié)點(diǎn)最多數(shù)目之和為20+21+22+…+2k-1；由二進(jìn)制換算關(guān)系可知：20+21+22+…+2k-1=2k-1，因此二叉樹(shù)中結(jié)點(diǎn)的最大數(shù)目為2k-1。</p><p>　　性質(zhì)3 在任意二叉樹(shù)中，若葉子結(jié)點(diǎn)（即度為零的結(jié)點(diǎn)）個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，那么n0=n2+1。</p><p

25、>　　證明：設(shè)n代表二叉樹(shù)結(jié)點(diǎn)總數(shù)，那么</p><p>　　n=n0+n1+n2 (1)</p><p>　　由于有n個(gè)結(jié)點(diǎn)的二叉樹(shù)總分支數(shù)為n-1條，于是得</p><p>　　n-1=0×n0+1×n1+2×n2 (2)&

26、lt;/p><p>　　將式(1)代入式(2)得</p><p><b>　　n0=n2+1</b></p><p>　　有兩種特殊形態(tài)的二叉樹(shù)，它們是滿(mǎn)二叉樹(shù)和完全二叉樹(shù)。</p><p>　　滿(mǎn)二叉樹(shù)：深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)為滿(mǎn)二叉樹(shù)，這種樹(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，如圖1-2(a)所示。對(duì)滿(mǎn)二

27、叉樹(shù)的結(jié)點(diǎn)可以從根結(jié)點(diǎn)開(kāi)始自上向下，自左至右順序編號(hào)，圖1-2(a)中每個(gè)結(jié)點(diǎn)斜上角的數(shù)字即是該結(jié)點(diǎn)的編號(hào)。</p><p>　　完全二叉樹(shù)：深度為k，含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)與相應(yīng)滿(mǎn)二叉樹(shù)結(jié)點(diǎn)順序號(hào)從0到n-1對(duì)應(yīng)時(shí)，則稱(chēng)此二叉樹(shù)為完全二叉樹(shù)，如圖1-2(b)所示。而圖1-2(c)則不是完全二叉樹(shù)。</p><p>　　圖7.7 滿(mǎn)二叉樹(shù)、完全二叉樹(shù)和非完全二叉樹(shù)&

28、lt;/p><p>　?。╝）滿(mǎn)二叉樹(shù)；（b）完全二叉樹(shù)；（c）非完全二叉樹(shù)</p><p>　　性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為 lbn +1（其中x表示不大于X的最大整數(shù)）。</p><p>　　性質(zhì)5 若對(duì)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)進(jìn)行順序編號(hào)（0≤i≤n-1，那么，對(duì)于編號(hào)為i(i≥0)的結(jié)點(diǎn)：</p><p>　　當(dāng)i=0時(shí)，該結(jié)

29、點(diǎn)為根，它無(wú)雙親結(jié)點(diǎn)；</p><p>　　當(dāng)i＞0時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為(i-1)/2；</p><p>　　若2i+1≤n-1, 則有編號(hào)為2i+1的左孩子，否則沒(méi)有左孩子；</p><p>　　若2i+2≤n-1，則有編號(hào)為2i+2的右孩子，否則沒(méi)有右孩子。</p><p>　　2.1.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)</p>&

30、lt;p>　　二叉樹(shù)常用的存儲(chǔ)結(jié)構(gòu)有兩種，順序存儲(chǔ)結(jié)構(gòu)（向量）和鏈表存儲(chǔ)結(jié)構(gòu)。</p><p>　　(1)順序存儲(chǔ)結(jié)構(gòu)（向量）可以作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。這種存儲(chǔ)結(jié)構(gòu)適用于完全二叉樹(shù)和滿(mǎn)二叉樹(shù)。假設(shè)用一維數(shù)組a存放圖1-3(a)的滿(mǎn)二叉樹(shù)?？梢园l(fā)現(xiàn)圖1-3(a)中結(jié)點(diǎn)的編號(hào)恰好與數(shù)組元素的下標(biāo)相對(duì)應(yīng)，見(jiàn)圖1-3。根據(jù)二叉樹(shù)性質(zhì)5，在a數(shù)組中可以方便地由某結(jié)點(diǎn)a[i]的下標(biāo)i找到它們的雙親結(jié)點(diǎn)a[(i-1)/2

31、]或左、右孩子結(jié)點(diǎn)a[2i+1]、a[2i+2]。在哈夫曼樹(shù)構(gòu)造算法中也用到順序存儲(chǔ)結(jié)構(gòu)。一般二叉樹(shù)較少采用順序存儲(chǔ)結(jié)構(gòu)。</p><p>　　圖1-3 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)</p><p>　　(1)鏈表存儲(chǔ)結(jié)構(gòu)通常用于二叉樹(shù)存儲(chǔ)。常見(jiàn)的有二叉鏈表和三叉鏈表。</p><p>　　二叉鏈表的每個(gè)結(jié)點(diǎn)都有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，一個(gè)指針指向左孩子，另一個(gè)指針指向右孩

32、子。結(jié)點(diǎn)結(jié)構(gòu)如圖1-4(a)所示，可以描述為：</p><p>　　typedef char DataType; /*結(jié)點(diǎn)屬性值的類(lèi)型*/</p><p>　　typedef struct Node </p><p><b>　　{</b></p><p>　　DataType data;

33、 /*數(shù)據(jù)域*/</p><p>　　struct Node *leftChild; /*左子樹(shù)指針*/</p><p>　　struct Node *rightChild; /*右子樹(shù)指針*/</p><p>　　}BiTreeNode; </p><p>　　圖1-4二叉樹(shù)鏈表存儲(chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)結(jié)構(gòu)<

34、;/p><p>　　(a)二叉鏈表中的結(jié)點(diǎn)結(jié)構(gòu)；(b)三叉鏈表中的結(jié)點(diǎn)結(jié)構(gòu)</p><p>　　三叉鏈表的結(jié)點(diǎn)比二叉鏈表多了一個(gè)指向雙親的指針域。結(jié)點(diǎn)結(jié)構(gòu)如圖1-4 (b)所示，可以描述為：</p><p>　　typedef struct Node3 </p><p><b>　　{</b></p><

35、p>　　DataType data; /*數(shù)據(jù)域*/</p><p>　　struct Node3 *leftChild; /*左子樹(shù)指針*/</p><p>　　struct Node3 *rightChild; /*右子樹(shù)指針*/</p><p>　　struct Node3 *parent;

36、 /*雙親的指針*/</p><p>　　}BiTreeNode3;</p><p>　　對(duì)于圖1-5(a)中二叉樹(shù)T，它的二叉鏈表如圖1-5（b），三叉鏈表如圖7.10（c）</p><p>　　圖1-5二叉樹(shù)的鏈表存儲(chǔ)結(jié)構(gòu)</p><p>　　2.1.4 二叉樹(shù)二叉鏈表生成算法</p><p>　　算法思路分析：此

37、方法主要利用二叉樹(shù)的性質(zhì)5。對(duì)任意二叉樹(shù)，先按滿(mǎn)二叉樹(shù)對(duì)其進(jìn)行編號(hào)，如圖1-6（a）所示。由于此樹(shù)并非完全二叉樹(shù)，所以編號(hào)并不連續(xù)。算法中使用一個(gè)輔助向量s用于存放指向樹(shù)結(jié)點(diǎn)的指針，如s[i]中存放編號(hào)為i的結(jié)點(diǎn)的指針，即為該結(jié)點(diǎn)的地址。此例原始數(shù)據(jù)序列如圖1-6（b）所示，把它存入a數(shù)組，a數(shù)組的類(lèi)型定義如下：</p><p>　　typedef struct</p><p>　　{ D

38、ataType data;</p><p>　　int number;</p><p><b>　　}DataNum;</b></p><p>　　當(dāng)結(jié)點(diǎn)編號(hào)i=0時(shí)，所產(chǎn)生的結(jié)點(diǎn)為根結(jié)點(diǎn)，同時(shí)將指向該結(jié)點(diǎn)的指針存入s[0]。</p><p>　　當(dāng)結(jié)點(diǎn)編號(hào)i＞0時(shí)，產(chǎn)生一個(gè)新的結(jié)點(diǎn)之后，也要將指向該結(jié)點(diǎn)的指針存入s[i

39、]。由性質(zhì)5可知：j=(i-1)/2為它的雙親結(jié)點(diǎn)編號(hào)。如果i為奇數(shù)，則它是雙親結(jié)點(diǎn)的左孩子，即讓s [j]-> leftChild=s[i]；如果i為偶數(shù)，則它是雙親結(jié)點(diǎn)的右孩子，即讓s[j]-> rightChild =s[i]。這樣就將a數(shù)組的結(jié)點(diǎn)逐一與其雙親結(jié)點(diǎn)相連，生成二叉樹(shù)。</p><p>　　圖1-6 二叉樹(shù)及數(shù)據(jù)表</p><p>　　二叉樹(shù)生成算法如下:&l

40、t;/p><p>　　BiTreeNode * creat(DataNum a[],int n)</p><p>　　{BiTreeNode *t,*q;</p><p>　　BiTreeNode *s[20];</p><p>　　/*動(dòng)態(tài)申請(qǐng)2*n+1個(gè)BiTreeNode類(lèi)型的數(shù)組空間*/</p><p>　　int

41、 i,j,k;</p><p>　　for(k=0;k<n;k++)</p><p>　　{q=(BiTreeNode *) malloc(sizeof(BiTreeNode)); /* 產(chǎn)生一個(gè)結(jié)點(diǎn) */</p><p>　　q->data=a[k].data;</p><p>　　q->leftChild=NULL;&

42、lt;/p><p>　　q->rightChild =NULL;</p><p>　　i=a[k].number;</p><p><b>　　s[i]=q;</b></p><p>　　if(i==0) t=q; /* t為局部變量，代表樹(shù)根結(jié)點(diǎn) */</p>&l

43、t;p>　　else{j=(i-1)/2; /* 雙親結(jié)點(diǎn)編號(hào) */</p><p>　　if(i%2==1) s[j]-> leftChild =q;</p><p>　　else s[j]-> rightChild =q;</p><p><b>　　}</b></p>&l

44、t;p><b>　　}</b></p><p>　　return(t);</p><p><b>　　}</b></p><p><b>　　2.2 隊(duì)列</b></p><p>　　2.2.1 隊(duì)列的應(yīng)用實(shí)例及概念</p><p>　　數(shù)據(jù)結(jié)構(gòu)中

45、所定義的隊(duì)列與日常生活中的排隊(duì)相當(dāng)類(lèi)似。在日常生活中，有許多是“先來(lái)先服務(wù)”的例子。例如，在銀行排隊(duì)等待取款的事件，或者在公共汽車(chē)站排隊(duì)等車(chē)事件等等。在這些排隊(duì)事件中，新來(lái)的成員總是加入在隊(duì)尾，而每次離開(kāi)的成員總是隊(duì)列頭上的成員，即入隊(duì)在隊(duì)尾進(jìn)行，而出隊(duì)在隊(duì)頭進(jìn)行。</p><p>　　隊(duì)列是限定只能在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線(xiàn)性表。在表中允許插入的一端叫做隊(duì)尾(Rear)，允許刪除的一端叫做隊(duì)

46、頭(Front)，向隊(duì)尾插入一個(gè)元素的操作叫做入隊(duì)操作，從隊(duì)頭取出一個(gè)元素的操作叫做出隊(duì)操作。隨著入隊(duì)、出隊(duì)操作的執(zhí)行，隊(duì)列的隊(duì)頭、隊(duì)尾也不斷地隨之改變。由于隊(duì)列的操作具有“先進(jìn)先出”的特點(diǎn)，因此隊(duì)列又稱(chēng)作先進(jìn)先出表(FIFO，即First In First Out)。</p><p>　　在圖2-1所表示的隊(duì)列中，a0是隊(duì)頭元素，an-1是隊(duì)尾元素。隊(duì)列中的元素以a0，a1， …，an-1的順序進(jìn)隊(duì)列。如果對(duì)

47、這個(gè)隊(duì)列執(zhí)行入隊(duì)操作，入隊(duì)元素為an，則該隊(duì)列的隊(duì)尾元素就變?yōu)閍n；如果對(duì)這個(gè)隊(duì)列執(zhí)行出隊(duì)操作，則隊(duì)列的隊(duì)頭元素a0從隊(duì)列中取出，當(dāng)前的隊(duì)頭元素就變?yōu)閍1。</p><p>　　圖2-1隊(duì)列結(jié)構(gòu)示意圖</p><p>　　一般，一個(gè)隊(duì)列是由n個(gè)元素組成的有限序列，可記作：</p><p>　　Q=(a0，a1，…ai，…，an-1) </p><

48、p>　　其中，每個(gè)ai都是隊(duì)列Q的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類(lèi)型，但必須屬于同一種數(shù)據(jù)對(duì)象。</p><p>　　從銀行排隊(duì)等待取款的實(shí)例中我們可以看到，隊(duì)列的操作與排隊(duì)、離隊(duì)的動(dòng)作非常相 似，入隊(duì)操作就相當(dāng)于來(lái)了一位新的顧客在隊(duì)尾排隊(duì)等候的事件，而出隊(duì)操作就相當(dāng)于取款后離隊(duì)的事件。除了入隊(duì)、出隊(duì)操作以外，隊(duì)列的操作通常還包括初始化、求當(dāng)前元素個(gè)數(shù)、判是否為空隊(duì)列、清空以及取隊(duì)頭元素等。我們可以通過(guò)對(duì)隊(duì)

49、列的操作及其實(shí)現(xiàn)方法的研究，來(lái)實(shí)現(xiàn)具體問(wèn)題中的有關(guān)操作。</p><p>　　綜上所述，隊(duì)列是一種數(shù)據(jù)類(lèi)型，其數(shù)據(jù)元素之間呈線(xiàn)性關(guān)系，其操作的特點(diǎn)是“先進(jìn)先出”，主要操作有入隊(duì)、出隊(duì)和取隊(duì)頭元素等。</p><p>　　隊(duì)列在程序設(shè)計(jì)中也經(jīng)常使用。一個(gè)最典型的例子就是操作系統(tǒng)中的作業(yè)排隊(duì)。在允許多道程序運(yùn)行的計(jì)算機(jī)系統(tǒng)中，作業(yè)輸入后通常處于后備狀態(tài)，由操作系統(tǒng)中的作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)入執(zhí)行

50、。作業(yè)調(diào)度程序可以采用不同的調(diào)度策略，其中最簡(jiǎn)單的調(diào)度策略就是“先來(lái)先服務(wù)”，也就是要使用一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)這種調(diào)度策略。同樣在做輸出時(shí)也要按請(qǐng)求輸出的先后次序排隊(duì)。作業(yè)輸出統(tǒng)一由操作系統(tǒng)中的輸出程序來(lái)執(zhí)行，每當(dāng)輸出程序傳輸完畢可以接收新的輸出任務(wù)時(shí)，隊(duì)頭的輸出作業(yè)從隊(duì)列中退出做輸出操作。凡是請(qǐng)求輸出的作業(yè)都是從隊(duì)尾進(jìn)入隊(duì)列的。</p><p>　　此外，在一些算法中也經(jīng)常使用隊(duì)列。例如，在圖的遍歷的非遞歸算法中，要

51、使用一個(gè)“層次隊(duì)列”來(lái)存放已訪(fǎng)問(wèn)的上層元素，由此來(lái)實(shí)現(xiàn)對(duì)下層元素的依次訪(fǎng)問(wèn)。在本章中將要介紹使用一個(gè)“循環(huán)隊(duì)列”的應(yīng)用實(shí)例。</p><p>　　我們先要考慮隊(duì)列的存儲(chǔ)方式，然后考慮有關(guān)的操作如何實(shí)現(xiàn)，在以下幾節(jié)中我們將圍繞這些問(wèn)題展開(kāi)討論。</p><p>　　2.2.2 隊(duì)列的存儲(chǔ)方式</p><p>　　與線(xiàn)性表類(lèi)似，隊(duì)列也有順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種存儲(chǔ)

52、方式。按順序存儲(chǔ)結(jié)構(gòu)建立起來(lái)的隊(duì)列稱(chēng)為順序隊(duì)列，按鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立起來(lái)的隊(duì)列稱(chēng)為鏈隊(duì)列。</p><p>　　2.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)</p><p>　　我們已經(jīng)知道，對(duì)于使用中數(shù)據(jù)元素的個(gè)數(shù)難以事先估計(jì)，而又進(jìn)出變動(dòng)較大的數(shù)據(jù)結(jié)構(gòu)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比采用順序存儲(chǔ)結(jié)構(gòu)更為有利。顯然，隊(duì)列也可以采用這種存儲(chǔ)方式。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列簡(jiǎn)稱(chēng)為鏈隊(duì)列，如圖2-2所示。</p>

53、<p>　　圖2-2鏈隊(duì)列示意圖</p><p>　　對(duì)于一個(gè)鏈隊(duì)列，顯然需要設(shè)置兩個(gè)指針，分別指向該隊(duì)列的隊(duì)頭和隊(duì)尾(分別稱(chēng)為頭指針和尾指針)，一般為了操作方便起見(jiàn)，我們也給鏈隊(duì)列增加一個(gè)頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)。由此，空的鏈隊(duì)列的判別條件為頭指針和尾指針均指向頭結(jié)點(diǎn)，如圖2-3(a)所示。</p><p>　　鏈隊(duì)列的操作即為單鏈表的插入和刪除的特殊情形，入隊(duì)操作相當(dāng)

54、于從鏈尾插入一個(gè)元素，出隊(duì)操作相當(dāng)于從鏈頭刪除一個(gè)元素。入隊(duì)出隊(duì)操作均可通過(guò)修改尾指針或頭指針來(lái)實(shí)現(xiàn)，圖2-3(b)～(d)展示了這兩種操作進(jìn)行時(shí)的指針變化情況。</p><p>　　圖2-3鏈隊(duì)列指針變化狀況</p><p>　　(a)空隊(duì)列；(b)a1入隊(duì)列；(c) a2入隊(duì)列；(d)a1出隊(duì)列</p><p>　　如前所述，鏈隊(duì)列可以由頭指針與尾指針唯一地確定

55、，因此在定義鏈隊(duì)列的類(lèi)型時(shí)，應(yīng)該包括一個(gè)頭指針與一個(gè)尾指針。為了表示鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)，我們先要定義存放隊(duì)列中數(shù)據(jù)元素的結(jié)點(diǎn)類(lèi)型及其指向這種結(jié)點(diǎn)的指針類(lèi)型，然后再定義由一個(gè)頭指針與一個(gè)尾指針組成的結(jié)構(gòu)類(lèi)型來(lái)表示一個(gè)鏈隊(duì)列。如圖2-4所示，假設(shè)結(jié)點(diǎn)類(lèi)型名為L(zhǎng)QNode，結(jié)點(diǎn)類(lèi)型中數(shù)據(jù)域名為data，指針域名為next，數(shù)據(jù)元素的類(lèi)型為DataType，鏈隊(duì)列的頭指針和尾指針?lè)謩e為front與rear，則鏈隊(duì)列類(lèi)型LQueue可定義如下：&l

56、t;/p><p>　　typedef struct qnode</p><p><b>　　{</b></p><p>　　DataType data;</p><p>　　struct qnode *next;</p><p>　　} LQNode; </p><p>　　t

57、ypedef struct</p><p><b>　　{</b></p><p>　　LQNode *front; /*隊(duì)頭指針*/</p><p>　　LQNode *rear; /*隊(duì)尾指針*/</p><p><b>　　} LQueue;</b></p><p>

58、　　圖2-4鏈隊(duì)列類(lèi)型結(jié)構(gòu)</p><p>　　在程序中使用的鏈隊(duì)列可以用一個(gè)LQueue型變量來(lái)表示，例如： </p><p>　　LQueue ql；</p><p>　　當(dāng)ql.front=ql.rear時(shí)，這個(gè)隊(duì)列就成為空隊(duì)列，否則，ql.front->next指向隊(duì)頭結(jié)點(diǎn)，而ql.rear指向隊(duì)尾結(jié)點(diǎn)。和鏈棧的情形相同，一般不會(huì)出現(xiàn)隊(duì)列滿(mǎn)的情形，除非

59、整個(gè)可用空間都被占滿(mǎn)，malloc()都無(wú)法執(zhí)行的情形下才會(huì)發(fā)生上溢。同樣空隊(duì)列的狀態(tài)在程序設(shè)計(jì)中也被用作實(shí)現(xiàn)控制轉(zhuǎn)移的條件。 </p><p>　　2.2.4 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)</p><p>　　盡管鏈隊(duì)列使用起來(lái)比較方便，但由于鏈表中的每個(gè)結(jié)點(diǎn)都設(shè)置一個(gè)指針域，因此，它的順序存儲(chǔ)方式要多占用一些存儲(chǔ)空間。有的情況下，仍需要使用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示隊(duì)列。</p><

60、p>　　隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)是指使用一組地址連續(xù)的存儲(chǔ)單元來(lái)依次存放隊(duì)列中的數(shù)據(jù)元素，除了用一個(gè)能容納最多元素個(gè)數(shù)的向量以外，還需要兩個(gè)指針?lè)謩e指向隊(duì)頭元素和隊(duì)尾元素。在C語(yǔ)言中，通?？墒褂靡粋€(gè)一維數(shù)組queue[MaxQueueSize]來(lái)存儲(chǔ)隊(duì)列中的數(shù)據(jù)元素，兩個(gè)整型指示器front與rear分別表示隊(duì)頭元素前一個(gè)和隊(duì)尾元素的位置。類(lèi)型定義如下：</p><p>　　MaxQueueSize=隊(duì)列中允許存

61、放元素個(gè)數(shù)的最大值； </p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　DataType queue[MaxQueueSize];</p><p>　　int rear; /*隊(duì)尾指針*/</p><p>　　int

62、 front; /*隊(duì)頭指針*/</p><p>　　} SeqQueue; </p><p>　　這樣我們就可以定義一個(gè)SeqQueue型的隊(duì)列，SeqQueue Q。順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)形式如圖2-5所示。</p><p>　　圖2-5順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)</p><p>　　在圖2-6中，front指針指向剛出隊(duì)的那個(gè)元素

63、的位置，而rear指針指向隊(duì)尾元素的位置，因?yàn)樵趫?zhí)行入隊(duì)、出隊(duì)操作時(shí)，先修改指針，再取出或送入元素。圖2-6(a)～(d)展示了對(duì)這種順序隊(duì)列在執(zhí)行入隊(duì)、出隊(duì)操作時(shí)，頭尾指針變化情況。</p><p>　　圖2-6順序隊(duì)列中頭尾指針的變化</p><p>　　(a)空隊(duì)列；(b)A、B、C、D依次入隊(duì)；(c)A、B依次出隊(duì)；(d)E、F入隊(duì)，C出隊(duì)</p><p>

64、　　從圖2-6可以看出，對(duì)一般的順序隊(duì)列Q，我們可以用Q.front==Q.rear作為判別隊(duì)列是否為空的條件；用Q.rear≥MaxQueueSize-1作為判別隊(duì)列是否為滿(mǎn)的條件。</p><p>　　當(dāng)隊(duì)列非空時(shí)，可執(zhí)行如下的出隊(duì)操作：</p><p>　　Q.front=Q.front+l；</p><p>　　data=Q.queue [front]；&l

65、t;/p><p>　　當(dāng)隊(duì)列非滿(mǎn)時(shí)，可執(zhí)行如下的入隊(duì)操作：</p><p>　　Q.rear=Q.rear+1；</p><p>　　Q.queue [Q.rear]=data；</p><p>　　在這里值得考慮的是：當(dāng)Q.rear≥MaxQueueSize-1時(shí)，隊(duì)列是否真正為滿(mǎn)?假設(shè)當(dāng)前隊(duì)列是處在圖 4.6(d)的狀態(tài)，即MaxQueueS

66、ize-1=5，Q.rear=5，Q.front=2，顯然此時(shí)不能再做入隊(duì)列的操作，因?yàn)镼.rear≥MaxQueueSize-1，但隊(duì)列中實(shí)際上并未存滿(mǎn)元素，這種現(xiàn)象稱(chēng)為假溢出。當(dāng)然，在發(fā)生假溢出時(shí)可以將全部元素向下移動(dòng)直至頭指針為-1，但這樣處理效率不高。一個(gè)比較巧妙的辦法是將隊(duì)列設(shè)想成首尾相接的環(huán)，一端放滿(mǎn)時(shí)再?gòu)牧硪欢舜嫒?，只要尾指針不與頭指針相遇，該隊(duì)列即可使用下去。這就是我們所講的循環(huán)隊(duì)列。</p><p&

67、gt;　　圖2-7是一個(gè)循環(huán)隊(duì)列的示意圖。在這個(gè)示圖中，循環(huán)隊(duì)列的長(zhǎng)度MaxQueueSize=8，隊(duì)列中元素的序號(hào)在0～7之間變化，7號(hào)元素的后面又是0號(hào)元素。隊(duì)列中的元素按順時(shí)針的方向進(jìn)入隊(duì)列，Q.front指針指向剛出隊(duì)的那個(gè)元素的位置，即序號(hào)為l，當(dāng)前的隊(duì)頭元素在2號(hào)位，而Q.rear指針正好指向隊(duì)尾元素的位置，當(dāng)前的隊(duì)尾元素在4號(hào)位。</p><p>　　圖2-7循環(huán)隊(duì)列示意圖</p>&

68、lt;p>　　對(duì)于循環(huán)隊(duì)列，當(dāng)頭指針和尾指針相等時(shí)，隊(duì)列為空隊(duì)列，但當(dāng)隊(duì)列的元素都存滿(mǎn)時(shí)，尾指針也正好與頭指針相等。為了能區(qū)分這兩種不同的狀態(tài)，規(guī)定循環(huán)隊(duì)列少用一個(gè)元素空間，以尾指針加1等于頭指針為隊(duì)列滿(mǎn)的判別條件。圖2-8表示了循環(huán)隊(duì)列的各種狀態(tài)與頭尾指針的關(guān)系。</p><p>　　圖2-8循環(huán)隊(duì)列的頭尾指針</p><p>　　(a)空隊(duì)列；(b)隊(duì)列中有一個(gè)元素；(c)隊(duì)列滿(mǎn)

69、</p><p>　　另外對(duì)于循環(huán)隊(duì)列，無(wú)論是頭指針還是尾指針，在對(duì)其進(jìn)行加l處理時(shí)，都要考慮對(duì)結(jié)果取模。綜上所述：我們可以用Q.front==Q.rear作為判別隊(duì)列是否為空的條件；用(Q.rear+1)%MaxQueueSize=Q.front作為判別隊(duì)列是否為滿(mǎn)的條件。</p><p>　　當(dāng)隊(duì)列非空時(shí)，可執(zhí)行如下的出隊(duì)操作：</p><p>　　Q.fron

70、t=(Q.front+1)%MaxQueueSize；</p><p>　　data= Q.queue [Q.front]；</p><p>　　當(dāng)隊(duì)列非滿(mǎn)時(shí)，可執(zhí)行如下的入隊(duì)操作：</p><p>　　Q.rear=(Q.rear+1)%MaxQueueSize；</p><p>　　Q.queue [Q.rear]=data；</p

71、><p>　　如前所述，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，應(yīng)該包括一個(gè)存儲(chǔ)數(shù)據(jù)元素的一維數(shù)組，取其名為queue，其長(zhǎng)度可取為一個(gè)適當(dāng)?shù)淖畲笾礛axQueueSize，另外還應(yīng)包括兩個(gè)位置指示器front和rear，它們分別指向隊(duì)頭和隊(duì)尾的位置。使用C語(yǔ)言，我們可以定義以下的結(jié)構(gòu)類(lèi)型來(lái)表示順序隊(duì)列或循環(huán)隊(duì)列，設(shè)其類(lèi)型名用SeqCQueue表示：</p><p>　　MaxQueueSize=隊(duì)列中允許存

72、放元素個(gè)數(shù)的最大值； </p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　DataType queue[MaxQueueSize];</p><p>　　int rear; /*隊(duì)尾指針*/</p><p

73、>　　int front; /*隊(duì)頭指針*/</p><p>　　} SeqCQueue; </p><p>　　在定義了順序隊(duì)列的類(lèi)型SeqCQueue之后，我們就可以定義屬于這種類(lèi)型的隊(duì)列，例如：SeqCQueue Q1；</p><p>　　此后可在程序中引用順序隊(duì)列Q1的相應(yīng)成分，例如，Q1.queue[Q1．rea

74、r]表示隊(duì)尾元素等。</p><p><b>　　2.3 排序</b></p><p>　　2.3.1 排序的基本概念</p><p>　　排序(Sorting)是把一個(gè)無(wú)序的數(shù)據(jù)元素序列按某個(gè)關(guān)鍵字進(jìn)行有序（遞增或遞減）排列的過(guò)程。排序中經(jīng)常把數(shù)據(jù)元素稱(chēng)為記錄(Record)。把記錄中作為排序依據(jù)的某個(gè)數(shù)據(jù)項(xiàng)稱(chēng)為排序關(guān)鍵字，簡(jiǎn)稱(chēng)關(guān)鍵字（Key

75、）。排序時(shí)選取哪一個(gè)數(shù)據(jù)項(xiàng)作為關(guān)鍵字，應(yīng)根據(jù)具體情況而定。</p><p>　　排序的方式根據(jù)待排記錄數(shù)量不同可以分為兩類(lèi)：</p><p>　?、旁谂判蜻^(guò)程中，只使用計(jì)算機(jī)的內(nèi)存儲(chǔ)器存放待排序的記錄，稱(chēng)為內(nèi)部排序。內(nèi)部排序用于排序的記錄個(gè)數(shù)較少時(shí)，全部排序可放在內(nèi)存中完成，不涉及外存儲(chǔ)器，因此，排序速度快。</p><p>　?、飘?dāng)排序的記錄數(shù)很大時(shí)，全部記錄不能

76、同時(shí)存放在內(nèi)存中，需要借助外存儲(chǔ)器，也就是說(shuō)排序過(guò)程中不僅要使用內(nèi)存，還要使用外存，記錄要在內(nèi)、外存之間移動(dòng)，這種排序成為外部排序。外部排序運(yùn)行速度較慢。</p><p>　　本章只討論內(nèi)部排序,不涉及外部排序。</p><p>　　內(nèi)部排序的方法很多，但不論哪種排序過(guò)程，通常都要進(jìn)行兩種基本操作：</p><p>　?、疟容^兩個(gè)記錄關(guān)鍵字的大小。</p>

77、;<p>　?、聘鶕?jù)比較結(jié)果，將記錄從一個(gè)位置移到另一個(gè)位置。所以，在分析排序算法的時(shí)間復(fù)雜度時(shí)，主要分析關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。</p><p>　　特別需要說(shuō)明的是：本章介紹的排序算法都是采用順序存儲(chǔ)結(jié)構(gòu)，即用數(shù)組存儲(chǔ)，且按關(guān)鍵字遞增排序，函數(shù)中記錄類(lèi)型及數(shù)組結(jié)構(gòu)定義如下：</p><p>　　# define MaxSize 100 /*MaxSize線(xiàn)性表

78、可能達(dá)到的最大長(zhǎng)度*/</p><p>　　typedef struct RecordNode</p><p>　　{keyType key;</p><p>　　DataType data;</p><p>　　}RecordNode;</p><p>　　RecordNode r[MaxSize];</p&g

79、t;<p>　　這里的keyType和DataType可以是任何相應(yīng)的數(shù)據(jù)類(lèi)型，如int，float及char等。</p><p>　　2.3.2 插入排序</p><p>　　插入排序的基本思想是：按關(guān)鍵字的大小將一個(gè)記錄插入到一個(gè)有序的記錄序列中，使得插入后的記錄序列仍然有序。要尋找適當(dāng)?shù)牟迦胛恢?，可以采用順序查找，也可以采用折半查找，相?yīng)地，插入排序有直接插入排序和折半

80、插入排序。另外，還有一種插入排序法—希爾排序。</p><p>　　2.3.3 直接插入排序</p><p>　　直接插入排序（Straight Insertion Sort）是最簡(jiǎn)單的排序方法之一。其基本思想是：在有序區(qū)中進(jìn)行順序查找，以確定插入的位置，然后移動(dòng)記錄騰出空間，以便插入關(guān)鍵字相應(yīng)的記錄。</p><p>　　圖3-1設(shè)有6個(gè)待排序的記錄，它們排序的關(guān)

81、鍵字序列為{20，6，15，7，3，6}。在順序查找中，為了防止循環(huán)變量越界，在有序區(qū)前段增設(shè)了一個(gè)“崗哨”temp，暫存當(dāng)前待插入的記錄，具體的排序過(guò)程如圖3-1所示。</p><p>　　圖3-1直接插入排序示例</p><p>　　從例圖3-1看出：①直接插入排序是從第二個(gè)紀(jì)錄開(kāi)始的，對(duì)記錄數(shù)為6的序列，需要進(jìn)行5趟排序才能完成。② 6和6的相對(duì)位置沒(méi)有變化，因此，直接插入排序是穩(wěn)定

82、的排序方法。</p><p>　　直接插入排序程序如下。</p><p>　　void InsertSort(RecordNode a[], int n)</p><p>　　/*用直接插入法對(duì)a[0]--a[n-1]排序*/</p><p><b>　　{</b></p><p><b&g

83、t;　　int i, j;</b></p><p>　　RecordNode temp;</p><p>　　for(i = 0; i < n-1; i++)</p><p>　　{temp = a[i+1];</p><p><b>　　j = i;</b></p><p>　

84、　while(j > -1 && temp.key < a[j].key)</p><p>　　{a[j+1] = a[j];</p><p><b>　　j--;</b></p><p><b>　　}</b></p><p>　　a[j+1] = temp;</

85、p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　算法分析：直接插入排序的比較次數(shù)取決于原記錄序列的有序程度。如果原始記錄的關(guān)鍵字正好為遞增順序時(shí)，比較次數(shù)最少為n-1次；如果為遞減順序時(shí)，比較次數(shù)最多，為(n-1)(n+2)/2次，因此，直接插入排序的時(shí)間復(fù)雜度為O( n2 )。

86、</p><p>　　有興趣的同學(xué)，可以用下面函數(shù)，驗(yàn)證插入排序?？匆豢唇Y(jié)果是否有序。</p><p>　　#define MaxSize 100</p><p>　　#include <stdio.h></p><p>　　typedef int KeyType;</p><p>　　typedef st

87、ruct</p><p>　　{char name[10];</p><p>　　float score;</p><p>　　}DataType;</p><p>　　typedef struct</p><p>　　{KeyType key;</p><p>　　DataType data;

88、</p><p>　　}RecordNode;</p><p>　　void main(void)</p><p><b>　　{</b></p><p>　　RecordNode test[3]={{8,"wang hong",87},{3,"wang hai",97},{1,&

89、quot;li ping",85}};</p><p>　　int i, n = 3;</p><p>　　insertSort(test,n);</p><p>　　for(i=0; i<n; i++)</p><p>　　printf("%d|%s|%f\n", test[i].key,test[i].

90、data.name,test[i].data.score);</p><p><b>　　}</b></p><p>　　2.3.4 冒泡排序</p><p>　　冒泡排序(Bubble Sort)是一種簡(jiǎn)單常用的排序方法。其排序思想是：通過(guò)相鄰記錄關(guān)鍵字間的比較和交換，使關(guān)鍵字最小的記錄像氣泡一樣逐漸上浮。比較可以采用不同的方法，本算法是從最

91、下面的記錄開(kāi)始，對(duì)兩個(gè)相鄰的關(guān)鍵字進(jìn)行比較并且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上，使得經(jīng)過(guò)一次冒泡后，關(guān)鍵字最小的記錄到達(dá)最上端，接著，再在剩下的記錄中找關(guān)鍵字最小的記錄，把它換到第二個(gè)位置上。依次類(lèi)推，一直到所有記錄都有序?yàn)橹?。一般，記錄?shù)為n，需要做n-1次冒泡。</p><p>　　圖3-2設(shè)待排記錄的關(guān)鍵字分別為{37，19，90，64，13，49，20，40}，進(jìn)行冒泡排序的具體過(guò)程如圖9.3所

92、示。</p><p>　　圖3-2冒泡排序示例</p><p>　　從排序的過(guò)程看，記錄數(shù)為8，需要作7次冒泡，但實(shí)際進(jìn)行到第五次冒泡是，整個(gè)記錄已經(jīng)有序了，因此，不需要再進(jìn)行6、7次冒泡了，也就是說(shuō)，在某次比較過(guò)程中，如果設(shè)有交換記錄，則排序可提前結(jié)束。這點(diǎn)在算法中給予考慮，可節(jié)省排序時(shí)間，為此在算法中設(shè)置一個(gè)變量flag來(lái)監(jiān)視排序情況，flag=1時(shí)表示有記錄交換，flag=0時(shí)無(wú)記錄

93、交換。</p><p><b>　　冒泡排序程序如下。</b></p><p>　　BubbleSort (RecordNode r[],int n)</p><p>　　{int i,j,flag;</p><p>　　RecordNode x;</p><p><b>　　flag=

94、1;</b></p><p>　　for(i=0;i<n-1&&flag==1;i++)</p><p><b>　　{flag=0;</b></p><p>　　for(j=n-1;j>=i+1;j--)</p><p>　　if(r[j].key<r[j-1].key)&

95、lt;/p><p><b>　　{flag=1;</b></p><p>　　x=r[j]; /*x用于中轉(zhuǎn)*/</p><p>　　r[j]=r[j-1];</p><p><b>　　r[j-1]=x;</b></p><p><b>　　}</

96、b></p><p><b>　　}</b></p><p>　　算法分析：冒泡排序是一種穩(wěn)定的排序方法，算法的執(zhí)行時(shí)間與原始記錄的有序程度有很大關(guān)系，如果原始記錄已經(jīng)是有序排列時(shí)，比較次數(shù)為n-1次,交換次數(shù)為0；如果原始記錄是“逆序”排列時(shí)，則總的比較次數(shù)為n（n-1）/2，交換次數(shù)為3n（n-1）/2。所以，算法的平均時(shí)間復(fù)雜度為0（n2）。</p&

97、gt;<p>　　第三章 相關(guān)軟件介紹</p><p>　　2.1 Flash課件的特點(diǎn)</p><p>　　Flash 由macromedia公司推出的交互式矢量圖和Web 動(dòng)畫(huà)的標(biāo)準(zhǔn)。網(wǎng)頁(yè)設(shè)計(jì)者使用 Flash 創(chuàng)作出既漂亮又可改變尺寸的導(dǎo)航界面以及其他奇特的效果。Flash是美國(guó)Macromedia公司所設(shè)計(jì)的一種二維動(dòng)畫(huà)軟件。通常包括Macromedia Flash，

98、用于設(shè)計(jì)和編輯Flash文檔，以及Flash Player，用于播放Flash影片。 </p><p>　　現(xiàn)在，F(xiàn)lash已經(jīng)被Adobe購(gòu)買(mǎi)，最新版本：Adobe Flash Professional CS6 </p><p>　　2.1.1 Flash課件優(yōu)勢(shì):</p><p>　　Flash課件能夠以交互方式將文本（text）、圖像（image）、圖形（gr

99、aphics）、音頻（audio）、動(dòng)畫(huà)（animation）、視頻（video）等多種信息，經(jīng)單獨(dú)或合成的形態(tài)表現(xiàn)出來(lái);用 flash做課件動(dòng)感更好、文件更小、傳輸更快、不易出錯(cuò)，windows自帶flash播放插件，可嵌入網(wǎng)頁(yè)</p><p>　　1、flash對(duì)圖片、聲音的壓縮率很高，可以多次插入多種格式聲音，容納多種格式多張圖片，而最終生成的swf文件并不太大.</p><p>　

100、　3、flash文件swf打包成可執(zhí)行文件（exe文件）后可獨(dú)立運(yùn)行，不需要任何軟件平臺(tái)的支持，因此使用方便，操作性極強(qiáng)。</p><p>　　4、flash導(dǎo)入mpg、avi等視頻文件可單獨(dú)做成swf文件供swf主文件分別調(diào)用，不增加主文件體積，一個(gè)課件容量豐富也可以播放流暢。 </p><p>　　2.1.2 flash課件的效果:</p><p>　　第一、利

101、用Flash制作的動(dòng)畫(huà)是矢量，不論你把它放大多少倍，都不會(huì)失真，保證了畫(huà)面的亮麗、清晰。播放時(shí)，你可隨時(shí)在Flash畫(huà)面上點(diǎn)右鍵，選"ZoomIn"放大畫(huà)面，細(xì)看畫(huà)面上的每一個(gè)細(xì)節(jié)，可見(jiàn)Flash畫(huà)面可制作的很細(xì)致。 </p><p>　　第二、利用Flash生成的動(dòng)畫(huà)播放文件（*.swf）都非常小巧;</p><p>　　第三、Flash對(duì)聲音的設(shè)置處理也很獨(dú)到，讀入

102、*．wav聲音在生成的Flash動(dòng)畫(huà)播放文件時(shí)，你會(huì)發(fā)現(xiàn)文件被壓縮到了原文件的十分之一大小，原來(lái)Flash播放文件中的聲音文件可設(shè)定為mp3格式。</p><p>　　2.2 Flash制作介紹.</p><p>　　2.2.1 基本操作界面.</p><p>　　基本操作界面有：舞臺(tái)、時(shí)間軸、幀和關(guān)鍵幀、層、工具欄、網(wǎng)格、輔助線(xiàn)和標(biāo)尺、面板和“屬性“檢查器<

103、/p><p><b>　　舞臺(tái)：</b></p><p>　　Flash創(chuàng)作環(huán)境中的舞臺(tái)相當(dāng)于flash文檔顯示是的矩形空間，可以再工作是放大和縮小的視圖（ctrl+alt+shift+鼠標(biāo)滾輪）、在屬性面板中定義舞臺(tái)的大小。</p><p><b>　　時(shí)間軸：</b></p><p>　　時(shí)間軸的主

104、要組件式層、幀和播放頭；文檔中的曾咧在時(shí)間左側(cè)的列中；每個(gè)層包含的幀顯示在層右邊的一行中；時(shí)間軸頂部的時(shí)間軸標(biāo)題指示幀編號(hào)；播放頭指示在舞臺(tái)當(dāng)前顯示的幀。</p><p><b>　　幀和關(guān)鍵幀：</b></p><p>　　關(guān)鍵幀是指在動(dòng)畫(huà)中定義的更改所在的幀，包含修改文檔的幀動(dòng)作的幀；Flash可以再關(guān)鍵幀之間補(bǔ)間或填充幀，從而生成流暢的動(dòng)畫(huà)；可以通過(guò)在時(shí)間軸中拖

105、動(dòng)關(guān)鍵幀來(lái)更改補(bǔ)間動(dòng)畫(huà)的長(zhǎng)度。</p><p><b>　　層：</b></p><p>　　像photoshop中的才呢過(guò)一樣一層層地疊在一起，可以幫助我們組織文檔中插圖，可以在層上繪制和編輯對(duì)象，而不會(huì)影響其他層上的對(duì)象；對(duì)層可以隱藏、鎖定和重新排列，還可以創(chuàng)建文件夾來(lái)組織和管理層！</p><p><b>　　輔助線(xiàn)和標(biāo)尺：&l

106、t;/b></p><p>　　Flash具有標(biāo)尺和輔助線(xiàn)，可以幫助用戶(hù)精確地勾畫(huà)和安排對(duì)象，可以在文檔中放置輔助線(xiàn)，然后讓對(duì)象與這些輔助線(xiàn)對(duì)齊，也可以打開(kāi)對(duì)象，然后讓對(duì)象與網(wǎng)格對(duì)齊。</p><p><b>　　工具欄：</b></p><p>　　工作區(qū)頂部的主工具欄顯示包含命令（用于控制flash功能）的菜單；主工具欄正下方的編輯欄

107、用于編輯場(chǎng)景和元件以及用于更改舞臺(tái)的縮放比率的控件和信息。</p><p>　　2.2.2 Flash中的Shape與Motion的動(dòng)畫(huà)：</p><p>　　Motion用于元件和文字的變化。</p><p>　　shape只適用與直接畫(huà)的矢量圖的變化</p><p>　　翻譯過(guò)來(lái)分別是"動(dòng)作","形狀&quo

108、t;</p><p>　　動(dòng)作動(dòng)畫(huà)是操縱的對(duì)象是一個(gè)整體,也就是不可改變形狀的整體,</p><p>　　與此相反,形狀動(dòng)畫(huà)的對(duì)象是填充,可以任意改變形狀和大小.</p><p>　　他們的區(qū)別在做補(bǔ)間動(dòng)畫(huà)時(shí)區(qū)別很明顯的.</p><p>　　基本上是能用動(dòng)作補(bǔ)間的,形狀補(bǔ)間都能完成,但這不是絕對(duì)的,制作過(guò)程中要注意選擇對(duì)象的屬性,是形狀還是

109、整體對(duì)象</p><p><b>　　2.2.3 庫(kù)面板</b></p><p>　　庫(kù)面板：庫(kù)面板是flash影片中所有可以重復(fù)使用的元素的儲(chǔ)存?zhèn)}庫(kù)，各種元件都放在庫(kù)面板中，在使用時(shí)從該面板中調(diào)用即可。</p><p>　　第四章 多媒體課件的設(shè)計(jì)與開(kāi)發(fā)過(guò)程</p><p>　　多媒體課件即利用文字、圖形、圖像、動(dòng)畫(huà)、

110、視頻、音頻、數(shù)字電影等多種媒體創(chuàng)作的交互式教學(xué)軟件。多媒體課件能夠同時(shí)將多種媒體呈現(xiàn)在屏幕上，在教學(xué)中可以圖、文、聲并茂，生動(dòng)形象地把教學(xué)內(nèi)容展示出來(lái)，能激發(fā)學(xué)生的多種感觀，使學(xué)習(xí)者容易理解、且記憶深刻。特別是多媒體課件中的超媒體結(jié)構(gòu)符合聯(lián)想思維和建構(gòu)性知識(shí)結(jié)構(gòu)，因此，利用多媒體課件進(jìn)行教學(xué)可以提高教學(xué)的效果，激發(fā)學(xué)生的學(xué)習(xí)興趣，同時(shí)還能培養(yǎng)教師和學(xué)生應(yīng)用計(jì)算機(jī)的水平和能力。</p><p>　　多媒體課件的制作

111、流程</p><p>　　要想制作出好的多媒體課件，必須把握好多媒體課件制作中的幾個(gè)重要環(huán)節(jié)。多媒體課件制作的環(huán)節(jié)及過(guò)程是：開(kāi)始→選題→學(xué)習(xí)者分析→課件結(jié)構(gòu)設(shè)計(jì)→稿本編寫(xiě)→素材搜集→課件集成→評(píng)價(jià)和修改→測(cè)試和應(yīng)用→總結(jié)演示，如下圖所示。</p><p><b>　　4.1 選題</b></p><p>　　多媒體課件制作過(guò)程比較繁瑣，運(yùn)用多媒

112、體課件進(jìn)行教學(xué)，教師投入的工作量比較大，在制作之前，教師要充分做好選題論證工作，盡量避免不必要的投入。因此，必須要高度重視選題工作，要選擇那些學(xué)生難以理解、教師不易講解清楚的重點(diǎn)和難點(diǎn)問(wèn)題，特別是要選擇那些能充分發(fā)揮圖像和動(dòng)畫(huà)效果的、不宜用語(yǔ)言和板書(shū)表達(dá)的內(nèi)容，對(duì)于那些課堂上較易講解的內(nèi)容就完全沒(méi)必要采用多媒體課件的方式。</p><p>　　制作多媒體課件應(yīng)根據(jù)教學(xué)大綱的要求，首先明確教學(xué)目的，要求突出重點(diǎn)、突

113、破難點(diǎn)。例如：設(shè)計(jì)課件的目的是激發(fā)學(xué)生學(xué)習(xí)興趣，調(diào)動(dòng)其學(xué)習(xí)積極性，還是解決某一重點(diǎn)，難點(diǎn)問(wèn)題；是為了幫助理解、加深印象、促進(jìn)記憶，還是為了使學(xué)生正確運(yùn)用已學(xué)過(guò)的知識(shí)；是擴(kuò)大知識(shí)面，豐富教學(xué)內(nèi)容、啟發(fā)想象力，還是培養(yǎng)某方面的技能技巧等等。</p><p>　　確定好教學(xué)目標(biāo)后， 才能有的放矢，做出符合教學(xué)需要的課件，真正起到輔助教學(xué)的作用。</p><p>　　多媒體課件內(nèi)容的選取則要以教材

114、為藍(lán)本，從實(shí)現(xiàn)教學(xué)目標(biāo)、完成教學(xué)任務(wù)的需要出發(fā)，但又不能為課本所束縛，要充分增加課件的含金量。一個(gè)優(yōu)秀的課件不能只是教材的幻燈片演示，而應(yīng)該增加它的生動(dòng)直觀的作用，因此教材內(nèi)容的選取很關(guān)鍵。</p><p>　　我們小組的課題是基于工作過(guò)程數(shù)據(jù)結(jié)構(gòu)多媒體課件設(shè)計(jì)，我所涉及的科目是利用flash做一個(gè)冒泡排序和利用Authorware軟件開(kāi)發(fā)一個(gè)課件，這個(gè)課件里面應(yīng)該有圖像、音樂(lè)、視頻的那個(gè)相關(guān)信息。</p&

115、gt;<p>　　我們小組所選的題目是基于工作過(guò)程數(shù)據(jù)結(jié)構(gòu)多媒體課件的設(shè)計(jì)</p><p>　　4.1.1 確定項(xiàng)目范圍</p><p>　　確定項(xiàng)目范圍，包括明確教學(xué)內(nèi)容范圍、課件產(chǎn)生的預(yù)期結(jié)果或課件目的、學(xué)習(xí)者、學(xué)習(xí)者的能力水平。其中最重要的是內(nèi)容范圍。</p><p>　　利用flash做一個(gè)冒泡排序和利用Authorware軟件開(kāi)發(fā)一個(gè)課件，這

116、個(gè)課件里面應(yīng)該有圖像、音樂(lè)、視頻的那個(gè)相關(guān)信息；本課件所包括的教學(xué)內(nèi)容是數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)！學(xué)習(xí)者需要熟練flash軟件、Authorware軟件等等。</p><p>　　4.1.2 分析學(xué)習(xí)者分析</p><p>　　分析學(xué)習(xí)者是教學(xué)設(shè)計(jì)的要素?！W(xué)習(xí)者分析是多媒體課件設(shè)計(jì)的關(guān)鍵，課件的內(nèi)容設(shè)計(jì)應(yīng)當(dāng)圍繞學(xué)習(xí)者進(jìn)行，這也是一種用戶(hù)至上的設(shè)計(jì)思想。分析學(xué)習(xí)者的目的是了解學(xué)習(xí)者的學(xué)習(xí)準(zhǔn)備（學(xué)

117、習(xí)準(zhǔn)備是指學(xué)習(xí)者從事新的學(xué)習(xí)時(shí)，他原有的知識(shí)水平或原有的心理發(fā)展水平對(duì)新的學(xué)習(xí)的適應(yīng)性）情況及其學(xué)習(xí)風(fēng)格，這樣，對(duì)教育者來(lái)說(shuō)可以做到因材施教，對(duì)學(xué)生來(lái)說(shuō)成為一個(gè)有準(zhǔn)備的學(xué)習(xí)者。學(xué)習(xí)者分析主要包括三方面的內(nèi)容：起始能力分析、一般特征分析和認(rèn)知風(fēng)格分析?？梢愿鶕?jù)課件開(kāi)發(fā)描述說(shuō)明中定義的課件服務(wù)對(duì)象，對(duì)學(xué)習(xí)者的需求要有一個(gè)總體范圍的估計(jì)。可以調(diào)查和預(yù)測(cè)學(xué)習(xí)者的學(xué)習(xí)動(dòng)機(jī)、操作風(fēng)格、注意度等，只有認(rèn)真分析學(xué)習(xí)者特征，才能設(shè)計(jì)出符合學(xué)習(xí)者需求的多媒

118、體課件。</p><p>　　在使用Flash軟件的時(shí)候特別要注意幀的設(shè)計(jì)和使用，使用Authorware軟件是要熟練交互按鈕的使用。</p><p>　　4.2 明確項(xiàng)目限制條件</p><p>　　制作人員應(yīng)該清楚課件設(shè)計(jì)與開(kāi)發(fā)的工作條件和限制因素，包括計(jì)算機(jī)軟件、硬件、網(wǎng)絡(luò)、音頻和視頻設(shè)備、預(yù)算、時(shí)間、項(xiàng)目組的責(zé)任、用戶(hù)的責(zé)任、使用資源的版權(quán)、用戶(hù)的特別要求等