第25章、排序、棧和隊(duì)列(理論課)

使用C語言開發(fā)簡單應(yīng)用第二十五章排序、棧和隊(duì)列上一章內(nèi)容回顧文件文件類型指針文件的操作打開文件關(guān)閉文件讀寫文件文件的定位清除流出錯(cuò)的檢測2/23本章學(xué)習(xí)目標(biāo)理解冒泡排序理解選擇排序理解插入排序理解棧及其操作理解隊(duì)列及其操作3/23內(nèi)容進(jìn)度排序冒泡排序選擇排序插入排序棧隊(duì)列4/23排序相關(guān)概念數(shù)據(jù)列表（DataList）待排序數(shù)據(jù)對(duì)象的有限集合關(guān)鍵碼（Key）通常數(shù)據(jù)對(duì)象有多個(gè)數(shù)據(jù)成員/屬性，其中有一個(gè)屬性域用來區(qū)分各個(gè)數(shù)據(jù)信息/數(shù)據(jù)對(duì)象，該屬性域被稱為關(guān)鍵碼。排序根據(jù)關(guān)鍵碼遞增/遞減的順序，把數(shù)據(jù)對(duì)象依次排列起來，使一組任意排列的對(duì)象變成一組按照關(guān)鍵碼順序排列的對(duì)象。5/23冒泡排序基本思想：將被排序的記錄數(shù)組R[n]垂直排列，每個(gè)記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。初始：R[1..n]為無序區(qū)。第一趟掃描從無序區(qū)底部向上依次比較相鄰的兩個(gè)氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(R[n-1]，R[n-2])，(R[n-2]，R[n-3])，…，(R[1]，R[0])；對(duì)于每對(duì)氣泡(R[j]，R[j-1])，若R[j].key<R[j-1].key，則交換R[j]和R[j-1]的內(nèi)容。第一趟掃描完畢時(shí)，“最輕”的氣泡就飄浮到該區(qū)間的頂部，即關(guān)鍵字最小的記錄被放在最高位置R[0]上。第二趟掃描掃描R[1..n-1]。掃描完畢時(shí)，"次輕"的氣泡飄浮到R[1]的位置上……最后，經(jīng)過n-1趟掃描可得到有序區(qū)R[0..n-1]。6/23冒泡排序例1：對(duì)數(shù)組a[5]={3,8,2,9,5};進(jìn)行從小到大排序。其排序過程可以利用下面的表格來說明：7/23冒泡排序程序?qū)崿F(xiàn)見教材P273排序過程示意圖8/2321254925*16080123452125*i=149251649chang=10825*chang=1i=2i=30816chang=125*25214921251608i=4chang=1i=5chang=025*491608252125*4916082521內(nèi)容進(jìn)度排序冒泡排序選擇排序插入排序棧隊(duì)列9/23選擇排序基本思想：初始狀態(tài)：無序區(qū)為R[0..n-1]，有序區(qū)為空。第1趟排序在無序區(qū)R[0..n-1]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[0]交換，使R[0..0]和R[1..n-1]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。第i趟排序第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[0..i-2]和R[i-1..n-1](0≤i≤n-2)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[i-1]交換，使R[0..i-1]和R[i..n-1]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。這樣，n個(gè)記錄的文件可經(jīng)過n-1趟選擇排序得到有序結(jié)果。10/23選擇排序程序?qū)崿F(xiàn)：11/23voidSelectSort(inta[],intn){ inttemp=0,i=0,j=0,k=0; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; if(k!=i) { temp=a[i]; a[i]=a[k]; a[k]=temp; } }}12/23初始：[49386597761327]kj1349一趟：13[386597764927]2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：13273849

65[9776]六趟：132738496576[97]kkkkjjjjjjjjjj選擇排序內(nèi)容進(jìn)度排序冒泡排序選擇排序插入排序棧隊(duì)列13/23插入排序基本思想：假設(shè)待排序的記錄存放在數(shù)組R[n]中。初始時(shí)，R[0]自成1個(gè)有序區(qū)，無序區(qū)為R[1..n-1]。從i=1起直至i=n-1為止，依次將R[i]插入當(dāng)前的有序區(qū)R[0..i-1]中，生成含n個(gè)記錄的有序區(qū)。一趟插入排序方法：首先在當(dāng)前有序區(qū)R[0..i-1]中查找R[i]的正確插入位置k(0≤k≤i-2)；然后將R[k．．i-2]中的記錄均后移一個(gè)位置，騰出k位置上的空間插入R[i]。14/23插入排序例3：對(duì)數(shù)組a[5]={9,8,5,3,2};進(jìn)行從小到大的排序。其排序過程可以利用下面的表格來說明：15/23插入排序各趟排序結(jié)果：16/2321254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=2插入排序17/2321254925*1608012345temp012345temp21254925*1608i=4012345temp21254925*1608i=5i=325*160821254925*1608012345完成插入排序i=4時(shí)的排序過程：18/2316491616012345temp21254925*08012345temp21254925*160816i=4j=3i=4j=22525*161621254925*08012345temp012345temp214925*08012345temp21254925*160816162521i=4j=1i=4j=0i=4j=-116內(nèi)容進(jìn)度排序冒泡排序選擇排序插入排序棧隊(duì)列19/23棧概念一種限定存取位置的線性表只允許在線性表的一端進(jìn)行操作，稱為棧頂。不允許在線性表的另一端進(jìn)行插入和刪除等操作，稱為棧底。棧操作：進(jìn)棧出棧特點(diǎn)：后進(jìn)先出（LIFO）兩種典型存儲(chǔ)方式：順序方式：數(shù)組鏈接方式：鏈表程序?qū)崿F(xiàn)例4（見教材P278）20/23內(nèi)容進(jìn)度排序冒泡排序選擇排序插入排序棧隊(duì)列2