資源簡介

(共30張PPT)
第10課 遍歷列表
——一維列表——
問題：
輸入50個學(xué)生的某門課程的成績，打印出低于平均分的學(xué)生序號與成績。
導(dǎo)入新課
一維列表的定義
當(dāng)列表中每個元素只帶有一個下標時，我們稱這樣的列表為一維列表。
列表的定義格式如下：
類型標識符 列表名[常量表達式]
說明：
　　①列表名的命名規(guī)則與變量名的命名規(guī)則一致。
　　②常量表達式表示列表元素的個數(shù)。可以是常量和符號常量，但不能是變量。
　　例如：
　　int a[10]; //列表a定義是合法的
int b[n]; //列表b定義是非法的
一維列表的定義
int a[10]
其中，a是一維列表的列表名，該列表有10個元素，依次表示為：a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]。需要注意的是：a[10]不屬于該列表的空間范圍。當(dāng)在說明部分定義了一個列表變量之后,C++編譯程序為所定義的列表在內(nèi)存空間開辟一串連續(xù)的存儲單元，每個列表第一個元素的下標都是0，因此第一個元素為第0個列表元素。例如：上例中的a列表在內(nèi)存的存儲如表所示：
一維列表的引用
通過給出的列表名稱和這個元素在列表中的位置編號(即下標)，程序可以引用這個列表中的任何一個元素。
一維列表元素的引用格式：
列表名[下標]
例如：若i、j都是int型變量，則
a[5]
a[i+j]
a[i++]
都是合法的元素。
一維列表的引用
說明：
(1)下標可以是任意值為整型的表達式，該表達式里可以包含變量和函數(shù)調(diào)用。引用時，下標值應(yīng)在列表定義的下標值范圍內(nèi)。
(2)列表的精妙在于下標可以是變量，通過對下標變量值的靈活控制，達到靈活處理列表元素的目的。
(3)C++語言只能逐個引用列表元素，而不能一次引用整個列表。
　　(4)列表元素可以像同類型的普通變量那樣使用，對其進行賦值和運算的操作，和普通變量完全相同。
例如： c[10]=34;實現(xiàn)了給c[10]賦值為34。
一維列表的初始化
列表的初始化可以在定義時一并完成。
格式：類型標識符 列表名[常量表達式]={值1，值2，…}
例如：
　　int a[5]={1,2,3,4,5}
說明：
　　(1)在初值列表中可以寫出全部列表元素的值，也可以寫出部分。
　　例如：int x[10]={0,1,2,3,4};
　　該方法僅對列表的前5個元素依次進行初始化，其余值為0。
　　(2)對列表元素全部初始化為0，可以簡寫為：{}。
　　例如：int a[5]={}; 將列表a的5個元素都初始化為0。
一維列表的初始化
一維列表的初始化
【說明】
程序1、程序2和程序3的區(qū)別在于列表定義在int main()之外與之內(nèi)，程序1中列表定義放在int main()之外，其初始值是0值。程序2中列表定義放在int main()之內(nèi)，其初始值是隨機的。程序2中列表定義放在int main()之內(nèi)，只給a[0]、a[1]賦初值，但后面的a[2]～a[4]元素自動賦0值。
列表的越界
C++語言規(guī)定，使用列表時，要注意：
(1)、列表元素的下標值為正整數(shù)。
(2)、在定義元素個數(shù)的下標范圍內(nèi)使用。
然而，當(dāng)在程序中把下標寫成負數(shù)、大于列表元素的個數(shù)時，程序編譯的時候是不會出錯的。例如：
int a[10];
a[-3]=5;
a[20]=15;
a[10]=20;
int k=a[30]
這些語句的語法是正確的，能夠通過程序的編譯。然而，它們要訪問的列表元素并不在列表的存儲空間的，這種現(xiàn)象叫列表越界。例如下面程序
列表的越界
#include
using namespace std;
int main()
{
int a[5];
for (int i=0;i<=10;i++)
{
a[i]=i;
cout<}
return 0;
}
一維列表的應(yīng)用
例5.1 輸入n個數(shù),要求程序按輸入時的逆序把這n個數(shù)打印出來，已知整數(shù)不超過100個。也就是說，按輸入相反順序打印這n個數(shù)。
一維列表的應(yīng)用
例5.2 將a列表中第一個元素移到列表末尾,其余數(shù)據(jù)依次往前平移一個位置。
【分析】為完成題目所要求的操作，其算法應(yīng)該包括以下幾個主要步驟：
　　①把第一個元素的值取出放在一個臨時單元 temp中；
　　②通過 a[2]→a[1], a[3]→a[2], a[4]→a[3]，……， a[n]→a[n-1],實現(xiàn)其余元素前移
　 ③將 temp值送入a[n]。
一維列表的應(yīng)用
參考程序：
一維列表的應(yīng)用
例5.3 賓館里有一百個房間，從1-100編了號。第一個服務(wù)員把所有的房間門都打開了，第二個服務(wù)員把所有編號是2的倍數(shù)的房間“相反處理”，第三個服務(wù)員把所有編號是3的倍數(shù)的房間作“相反處理”…，以后每個服務(wù)員都是如此。當(dāng)?shù)?00個服務(wù)員來過后，哪幾扇門是打開的。（所謂“相反處理”是：原來開著的門關(guān)上，原來關(guān)上的門打開。）
一維列表的應(yīng)用
參考程序：
一維列表的應(yīng)用
例5.4 約瑟夫問題：N個人圍成一圈，從第一個人開始報數(shù)，數(shù)到M的人出圈；再由下一個人開始報數(shù)，數(shù)到M的人出圈；…輸出依次出圈的人的編號。N，M由鍵盤輸入。
一維列表的應(yīng)用
參考程序：
一維列表的應(yīng)用
例5.5 輸入n個整數(shù),存放在列表a[1]至a[n]中，輸出最大數(shù)所在位置(n<=10000)。
輸入樣例：
5
67 43 90 78 32
輸出樣例：
3
一維列表的應(yīng)用
參考程序：
一維列表的應(yīng)用
例5.6 編程輸入十個正整數(shù)，然后自動按從大到小的順序輸出。（冒泡排序）
【問題分析】
①用循環(huán)把十個數(shù)輸入到A列表中；
②從a[1]到a[10]，相鄰的兩個數(shù)兩兩相比較，即：
a[1]與a[2]比，a[2]與a[3]比，……a[9]與a[10]比。
只需知道兩個數(shù)中的前面那元素的標號，就能進行與后一個序號元素（相鄰數(shù)）比較，可寫成通用形式a[i]與a[i+1]比較，那么，比較的次數(shù)又可用1～( n-i )循環(huán)進行控制(即循環(huán)次數(shù)與兩兩相比較時前面那個元素序號有關(guān)) ；
③在每次的比較中，若較大的數(shù)在后面，就把前后兩個對換，把較大的數(shù)調(diào)到前面，否則不需調(diào)換位置。
一維列表的應(yīng)用
下面例舉5個數(shù)來說明兩兩相比較和交換位置的具體情形：
5 6 4 3 7 5和6比較，交換位置，排成下行的順序；
6 5 4 3 7 5和4比較，不交換，維持同樣的順序；
6 5 4 3 7 4和3比較，不交換，順序不變
6 5 4 3 7 3和7比較，交換位置，排成下行的順序；
6 5 4 7 3 經(jīng)過（1～（n-1））次比較后，將3調(diào)到了末尾。
經(jīng)過第一輪的1～ (N-1)次比較，就能把十個數(shù)中的最小數(shù)調(diào)到最末尾位置，第二輪比較1～ (N-2)次進行同樣處理，又把這一輪所比較的“最小數(shù)”調(diào)到所比較范圍的“最末尾”位置；……；每進行一輪兩兩比較后，其下一輪的比較范圍就減少一個。最后一輪僅有一次比較。在比較過程中，每次都有一個“最小數(shù)”往下“掉”，用這種方法排列順序，常被稱之為“冒泡法”排序。
一維列表的應(yīng)用
參考程序：
（冒泡排序）
一維列表的應(yīng)用
選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進去都是 O(n ) 的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。
1. 算法步驟
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。
重復(fù)第二步，直到所有元素均排序完畢。
一維列表的應(yīng)用
參考程序：
（選擇排序）
一維列表的應(yīng)用
冒泡排序
一維列表的應(yīng)用
選擇排序
一維列表的應(yīng)用
例5.6 輸入N 個正整數(shù)，保證每個數(shù)在10000以內(nèi)，輸出一共有多少個不同的數(shù)。
一維列表的應(yīng)用
例5.6 輸入N 個正整數(shù)，保證每個數(shù)在10000以內(nèi)，將這N個數(shù)按從小到大的順序輸出。
一維列表的應(yīng)用
計數(shù)排序

展開更多......

收起↑