《RAPTOR流程圖算法設(shè)計(jì)教程》課件ch6

第6章

利用數(shù)組實(shí)現(xiàn)批量數(shù)據(jù)的處理學(xué)習(xí)目標(biāo)了解數(shù)組的概念和特點(diǎn)掌握數(shù)組定義和使用應(yīng)用數(shù)組處理批量數(shù)據(jù)目錄6.1數(shù)組的引入6.2一維數(shù)組及應(yīng)用6.3二維數(shù)組及應(yīng)用6.4字符數(shù)組及應(yīng)用6.5數(shù)組的其他應(yīng)用方式6.1數(shù)組的引入6.1.1數(shù)組的概念6.1.2數(shù)組的特點(diǎn)6.1.1數(shù)組的概念數(shù)組將若干個(gè)數(shù)據(jù)按順序存儲(chǔ)在一起形成的一組數(shù)據(jù)集合就稱為數(shù)組。數(shù)組名用一個(gè)統(tǒng)一的名字標(biāo)識(shí)這組數(shù)據(jù)，這個(gè)名字稱為數(shù)組名。6.1.1數(shù)組的概念數(shù)組元素構(gòu)成數(shù)組的每個(gè)數(shù)據(jù)項(xiàng)稱為數(shù)組元素。下標(biāo)變量數(shù)組中的每一個(gè)數(shù)組元素具有相同的名稱，用不同的下標(biāo)表示一組數(shù)據(jù)，我們把這種變量稱之為下標(biāo)變量。6.1.1數(shù)組的概念數(shù)組創(chuàng)建的一般形式為：

數(shù)組名[下標(biāo)1，下標(biāo)2，……，下標(biāo)n]說明：數(shù)組名用于標(biāo)識(shí)該數(shù)組；方括號(hào)中的數(shù)值為下標(biāo)值，其值必須是正整數(shù)，不能是0或小數(shù)；下標(biāo)的個(gè)數(shù)表示數(shù)組的維數(shù)。數(shù)組元素用整個(gè)數(shù)組的名字和該元素在數(shù)組中的順序位置來表示。默認(rèn)的情況下，第1個(gè)數(shù)組元素的下標(biāo)值為16.1數(shù)組的引入6.1.1數(shù)組的概念6.1.2數(shù)組的特點(diǎn)6.1.2數(shù)組的特點(diǎn)數(shù)組是有序數(shù)據(jù)的集合；利用數(shù)組數(shù)據(jù)類型可以存放若干個(gè)數(shù)據(jù)；數(shù)組中的每個(gè)元素可以是相同數(shù)據(jù)類型，也可以是不同類型的數(shù)據(jù)（字符、字符串和數(shù)值等）；按照數(shù)組下標(biāo)變量的個(gè)數(shù)不同，數(shù)組可以分為一維數(shù)組、二維數(shù)組、多維數(shù)組。目錄6.1數(shù)組的引入6.2一維數(shù)組及應(yīng)用6.3二維數(shù)組及應(yīng)用6.4字符數(shù)組及應(yīng)用6.5數(shù)組的其他應(yīng)用方式6.2一維數(shù)組及應(yīng)用6.2.1一維數(shù)組的創(chuàng)建6.2.2一維數(shù)組的引用6.2.3一維數(shù)組的應(yīng)用6.2.1一維數(shù)組的創(chuàng)建一維數(shù)組的概念數(shù)組的維數(shù)可以用下標(biāo)的個(gè)數(shù)來表示，下標(biāo)個(gè)數(shù)為1時(shí)，稱為一維數(shù)組。一維數(shù)組的表示形式數(shù)組名[下標(biāo)]6.2.1一維數(shù)組的創(chuàng)建一維數(shù)組的創(chuàng)建利用賦值語句或輸入語句利用輸入語句創(chuàng)建數(shù)組時(shí)，所創(chuàng)建的數(shù)組大小為給定的最大元素下標(biāo)值，未賦值的數(shù)組元素將默認(rèn)為0，數(shù)組類型為輸入數(shù)據(jù)的類型，6.2一維數(shù)組及應(yīng)用6.2.1一維數(shù)組的創(chuàng)建6.2.2一維數(shù)組的引用6.2.3一維數(shù)組的應(yīng)用6.2.2一維數(shù)組的引用引用數(shù)組中的數(shù)組元素可以采用“數(shù)組名[下標(biāo)]”的形式如：values[1]表示引用數(shù)組values中的第1個(gè)數(shù)組元素的值。數(shù)組中的下標(biāo)變量可以為正整數(shù)，也可以使用表達(dá)式，如：values[5-3]、values[1+1]、values[i+1]（這里的i是變量）都表示引用數(shù)組中的數(shù)組元素。6.2一維數(shù)組及應(yīng)用6.2.1一維數(shù)組的創(chuàng)建6.2.2一維數(shù)組的引用6.2.3一維數(shù)組的應(yīng)用6.2.3一維數(shù)組的應(yīng)用排序問題所謂排序就是將一組數(shù)據(jù)的值按從小到大（或從大到?。┑捻樞蛑匦屡帕?。基本排序方法冒泡排序、插入排序、選擇排序、交換排序等冒泡排序【例6-3】從鍵盤上輸入某班10名學(xué)生的計(jì)算機(jī)課程考試成績(jī)，將該成績(jī)按照從高到低的順序排列并輸出。冒泡排序的基本思想：從數(shù)組的第1個(gè)元素開始，依次比較相鄰的兩個(gè)數(shù)組元素的大小，如果發(fā)現(xiàn)兩個(gè)數(shù)組元素的次序相反時(shí)就進(jìn)行交換，如此重復(fù)地進(jìn)行，直到比較沒有反序的數(shù)組元素為止。冒泡排序的排序過程：根據(jù)本題是從高到低排序，即從大到小排序，因此排序過程：①先將第1個(gè)數(shù)與第2個(gè)數(shù)比較，若array[1]<array[2]，則交換；然后比較第2個(gè)數(shù)與第3個(gè)數(shù)，以此類推，直到第n-1個(gè)數(shù)和第n個(gè)數(shù)比較為止，第一趟冒泡排序，結(jié)果使最小的數(shù)被安置在最后一個(gè)元素位置上。②對(duì)前n-1個(gè)數(shù)進(jìn)行第二趟冒泡排序，結(jié)果使次小的數(shù)被安置在第n-1個(gè)元素位置上。③重復(fù)上述過程，共經(jīng)過n-1趟冒泡排序后，排序結(jié)束。本題為了使程序結(jié)構(gòu)更加清晰，采用子過程方式（關(guān)于子過程概念在后續(xù)章節(jié)介紹）完成。主圖Main用于輸入數(shù)據(jù)、調(diào)用子過程和輸出排序好的數(shù)據(jù)；子過程sort用于對(duì)數(shù)據(jù)排序。6.2.3一維數(shù)組的應(yīng)用查找數(shù)據(jù)問題查找問題和排序問題有密切的聯(lián)系，很多查找問題都是依賴于要查找的數(shù)據(jù)集的有序程度。查找算法順序查找、二分查找、基數(shù)查找、哈希查找等順序查找【例6-4】從鍵盤上輸入某班10名學(xué)生的計(jì)算機(jī)課程考試成績(jī)，任意輸入一個(gè)成績(jī)，若找到該成績(jī)則輸出其位置，否則輸出“NoFound”提示信息。順序查找的基本思想：從一組無序或有序的數(shù)據(jù)的第1個(gè)元素開始，將要查找的數(shù)據(jù)與該組數(shù)據(jù)中的每一個(gè)元素進(jìn)行比較，如果要查找的數(shù)據(jù)與該組數(shù)據(jù)中的元素相等，則找到該數(shù)據(jù)，查找成功；如果要查找的數(shù)據(jù)要該組數(shù)據(jù)的所有元素都不相等，則表示該組數(shù)據(jù)沒有要查找的數(shù)據(jù)，查找失敗。

本例題是查找指定數(shù)據(jù)在數(shù)組中的位置，而數(shù)組中數(shù)據(jù)又是無序的，所以可以直接利用順序查找的方法。其算法的基本思想是：利用循環(huán)結(jié)構(gòu)順序掃描整個(gè)數(shù)組，依次將每個(gè)元素與要查找的值進(jìn)行比較，若找到，則停止循環(huán)，輸出其位置值并顯示“Found”提示信息；若所有元素都比較后仍未找到，則循環(huán)結(jié)束后，輸出“NoFound”提示信息。其算法表示如下：Step1：從鍵盤輸入10名學(xué)生成績(jī)，并存入一維數(shù)組score中；Step2：從鍵盤輸入要查找成績(jī)data的值；Step3：該成績(jī)值data與數(shù)組中每個(gè)數(shù)組元素score[i]進(jìn)行比較，若是找到，則輸出其所在位置，否則輸出“Nofound”提示信息。從上例可以看出，由于數(shù)組元素事先并沒有按照一個(gè)特定的順序排序，在查找過程中，有可能第一元素的元素值就與要查找的數(shù)據(jù)相等，也有可能在數(shù)組的最后一個(gè)元素位置找到它。如果已知數(shù)據(jù)中不存在待查找數(shù)據(jù)時(shí)，也需要對(duì)所有數(shù)據(jù)進(jìn)行比對(duì)，則查找次數(shù)將等于數(shù)據(jù)量的大小。二分查找【例6-6】從鍵盤上輸入某班10名學(xué)生的計(jì)算機(jī)課程考試成績(jī)，任意輸入一個(gè)成績(jī)，若找到該成績(jī)則輸出其位置，否則輸出“NOFound”提示信息。二分查找法的基本思想：首先假設(shè)這組數(shù)據(jù)是按升序排列，將數(shù)組中間位置元素與查找數(shù)值比較，如果兩者相等，則查找成功；否則利用中間位置將數(shù)組分成前、后兩個(gè)子數(shù)組，如果查找數(shù)小于中間位置元素，則進(jìn)一步二分查找前一子數(shù)組，否則進(jìn)一步二分查找后一子數(shù)組。重復(fù)以上過程，直到找到滿足條件的數(shù)據(jù)，使查找成功，或直到子數(shù)組不存在為止。二分查找過程：假設(shè)這組有序數(shù)據(jù)為a[10]，要查找的數(shù)據(jù)為63。low用來存儲(chǔ)數(shù)組a的最小下標(biāo)，high用來存儲(chǔ)數(shù)組的最大下標(biāo)，利用公式mid=floor((low+high)/2)求出數(shù)組的中間下標(biāo)。本例題是查找指定數(shù)據(jù)在數(shù)組中的位置，利用二分查找方法實(shí)現(xiàn)。其算法表示如下：Step1：從鍵盤輸入10名學(xué)生成績(jī)，并存入一維數(shù)組a中；Step2：對(duì)這組數(shù)據(jù)進(jìn)行升序排列；Step3：從鍵盤輸入要查找成績(jī)data的值；Step4：對(duì)low、mid、high變量初始賦值：Low1，midfloor((low+high)/2)，highn-1；Step5：比較data與a[mid]的值。當(dāng)data=a[mid]時(shí)，說明找到；當(dāng)data>a[mid]，則待查元素可能在a[mid+1]~a[high]之間，讓low=mid+1；當(dāng)data<a[mid]，則待查元素可能在a[low]~a[mid-1]之間，讓high=mid-1。Step6：重復(fù)執(zhí)行Step5，直到查找范圍縮小到零（沒有找到）或data等于a[mid]（查找成功）為止。目錄6.1數(shù)組的引入6.2一維數(shù)組及應(yīng)用6.3二維數(shù)組及應(yīng)用6.4字符數(shù)組及應(yīng)用6.5數(shù)組的其他應(yīng)用方式6.3二維數(shù)組及應(yīng)用6.3.1二維數(shù)組的創(chuàng)建6.3.2二維數(shù)組的引用6.2.3二維數(shù)組的應(yīng)用二維數(shù)組

二維數(shù)組是指具有兩個(gè)下標(biāo)的數(shù)組，其中第一下標(biāo)表示行，第二下標(biāo)表示列。二維數(shù)組的表示形式數(shù)組名[下標(biāo)1，下標(biāo)2]6.3.1二維數(shù)組的創(chuàng)建6.3.1二維數(shù)組的創(chuàng)建二維數(shù)組的創(chuàng)建二維數(shù)組的創(chuàng)建同一維數(shù)組的創(chuàng)建相同，可以通過賦值語句或輸入語句對(duì)一個(gè)或多個(gè)二維數(shù)組元素賦值而被創(chuàng)建，所創(chuàng)建的數(shù)組大小為兩個(gè)維度中最大的最大下標(biāo)值確定，未賦值的數(shù)組元素將默認(rèn)為0。6.3.2二維數(shù)組的引用二維數(shù)組的引用使用“數(shù)組名[下標(biāo)1,下標(biāo)2]”的形式引用數(shù)組中的各個(gè)元素，如array[3,4]表示二維數(shù)組中的第3行第4列的數(shù)組元素。6.3.3二維數(shù)組的應(yīng)用【例6-8】求例6-7的二維數(shù)組元素的累加和問題分析：本例屬于二維數(shù)組的基本應(yīng)用問題。求二維數(shù)組的累加和問題與求一維數(shù)組的累加和問題類似。先要設(shè)置累加和的初值sum=0，讀入每個(gè)二維數(shù)組元素后執(zhí)行累加和運(yùn)算，即sum=sum+values[i,j]。同樣采用雙重循環(huán)結(jié)構(gòu)方式實(shí)現(xiàn)。【例6-9】設(shè)有一個(gè)3×4矩陣，找出矩陣中的最大值，并輸出其所在的行號(hào)和列號(hào)。問題分析：本例也屬于二維數(shù)組的基本應(yīng)用問題。解決該題可以先將矩陣的第1個(gè)元素賦值給最大值變量maxvalue，用maxvalue的值按從行到列的順序與矩陣其他元素進(jìn)行比較，若當(dāng)前比較的矩陣元素比maxvalue中的值大，則對(duì)maxvalue賦值為當(dāng)前的矩陣元素，并記下該矩陣元素的行號(hào)和列號(hào)。目錄6.1數(shù)組的引入6.2一維數(shù)組及應(yīng)用6.3二維數(shù)組及應(yīng)用6.4字符數(shù)組及應(yīng)用6.5數(shù)組的其他應(yīng)用方式6.4字符數(shù)組字符數(shù)組數(shù)組元素類型都是字符稱為字符數(shù)組?！纠?-11】編寫程序，輸入一行字符串，將該字符串逆序輸出。如：字符串“ABCDEF”，逆序輸出為：“FEDCBA”。問題分析：要想對(duì)輸入一行字符串進(jìn)行逆序輸出，可以利用兩個(gè)變量i和j分別表示該字符數(shù)組首部元素和末尾元素，讓變量i從1依次加1變化，變量j從數(shù)組尾部開始，依次減1變化，當(dāng)i>j時(shí)結(jié)束元素互換。其算法表示如下：Step1：從鍵盤輸入一行字符，并存放于數(shù)組str中；Step2：對(duì)變量i初始賦值為1，變量j初始賦值為該字符串個(gè)數(shù)；Step3：當(dāng)i>j時(shí)，程序跳轉(zhuǎn)執(zhí)行Step4，結(jié)束元素互換，否則對(duì)字符數(shù)組中首尾對(duì)稱位置的元素互換；Step4：逆序輸出字符串。【例6-12】編寫程序，輸入一行含有英文字母的字符串，將該字符串所有字符轉(zhuǎn)換為大寫形式。如：字符串“IloveRaptor.”轉(zhuǎn)換為“ILOVERAPTOR.”目錄6.1數(shù)組的引入6.2一維數(shù)組及應(yīng)用6.3二維數(shù)組及應(yīng)用6.4字符數(shù)組及應(yīng)用6.5數(shù)組的其他應(yīng)用方式6.5數(shù)組的其他應(yīng)用方式RAPTOR數(shù)組與其他語言程序相比，非常靈活，不強(qiáng)制同一個(gè)數(shù)組的不同元素必須具有相同的數(shù)據(jù)類型，利用這個(gè)特點(diǎn)，可以將二維數(shù)組設(shè)計(jì)成為類似像EXCEL設(shè)計(jì)的二維表數(shù)據(jù)記錄形式?！纠?-14】學(xué)生類型假設(shè)有5名學(xué)生信息，包括姓名和3門課程的成績(jī)，求每個(gè)學(xué)生課程成績(jī)總分，并顯示每個(gè)學(xué)生信息。問題分析：程序中每個(gè)學(xué)生信息都需要從鍵盤輸入，為了減少輸入工作量，僅選用5個(gè)學(xué)生作為對(duì)象。由于每個(gè)學(xué)生信息的數(shù)據(jù)類型不同，選擇二維數(shù)組student存放學(xué)生的相關(guān)信息。數(shù)組中第1下標(biāo)表示學(xué)生，第2個(gè)下標(biāo)表示該學(xué)生的信息，例如：student[2,3]表示第2個(gè)學(xué)生的第2門課程的成績(jī)。學(xué)生的總分可以用3門課的成績(jī)相加求得。【例6-15】學(xué)生總分成績(jī)排名假設(shè)有5名學(xué)生信息，包括姓名和3門課程的成績(jī)，求每個(gè)學(xué)生課程成績(jī)總分，并按照總分成績(jī)由高到低排名。問題分析：本題是在例6-14基礎(chǔ)上對(duì)學(xué)生總分進(jìn)行排序。排序方法可以采用常用