c第8講數(shù)組一維的使用

1、第八講 第七章 數(shù)組 一維數(shù)組的使用典型算法 排序 查找 插入 刪除 一維數(shù)組的基本概念數(shù)組及數(shù)組元素的概念數(shù)組:是具有一定順序的一組類型相同、下標(biāo)不同變量的 集合體。例如：表示A班（n個(gè)學(xué)生）C語(yǔ)言成績(jī)的一組數(shù)據(jù).數(shù)組a 2 下標(biāo)數(shù)組名數(shù)組元素(下標(biāo)變量 ) a0,a1,a2,a3,an-1數(shù)組元素：組成數(shù)組的變量稱為該數(shù)組的元素。數(shù)組及數(shù)組元素的概念基本概念數(shù)組是由同一名字和相同類型的一組連續(xù)內(nèi)存單元構(gòu)成的。為了引用數(shù)組中的特定位置或元素，我們需要指定數(shù)組的名稱，并指定數(shù)組中特定元素的位置編號(hào)，這個(gè)位置編號(hào)稱為數(shù)組下標(biāo)。 方括號(hào)中的數(shù)組元素下標(biāo)必須是整數(shù)或整數(shù)表達(dá)式。 數(shù)組下標(biāo)是從0開(kāi)始的

2、，“數(shù)組的第7個(gè)元素”的下標(biāo)是6，而“數(shù)組元素7”的下標(biāo)為7，實(shí)際上是指數(shù)組的第8個(gè)元素。 數(shù)組的基本概念例如：整型數(shù)組a10，包含十個(gè)變量，分別是:a0,a1,a2,a3a9 數(shù)組的維 一維數(shù)組：數(shù)組元素只有一個(gè)下標(biāo)組成的數(shù)組。二維數(shù)組：數(shù)組元素有兩個(gè)下標(biāo)組成的數(shù)組。 例如：數(shù)組 b34,實(shí)型,12個(gè)變量:b00,b01,b02,b03先定義，后使用 使用原則名字類型大小維數(shù)b10,b11,b12,b13b20,b21,b22,b23一維數(shù)組的使用 數(shù)組的定義類型說(shuō)明符 數(shù)組名常量 ;例如：int a10;整型數(shù)組名字為a十個(gè)變量a0a1a9 數(shù)組的初始化float b5=1,2,3,4,5

3、; 一維數(shù)組的存儲(chǔ)結(jié)構(gòu)a0a1.a9數(shù)組ab0b1.b4數(shù)組b1.02.05.0 數(shù)組的使用 (1) 數(shù)組元素在內(nèi)存中順序存放 (2) 數(shù)組元素的地址是連續(xù)的等價(jià)于：float b5=1;float b =1,2 ,3,4,5;b0b1b4數(shù)組b1.00.0.0.0一維數(shù)組的輸入和輸出例1 將十個(gè)數(shù)據(jù)輸入到數(shù)組中，并按下標(biāo)的逆序輸出。void main( ) int a10,i;for(i=0;iai);for(i=9;i=0;i - -)coutai; cout“nResult:”endl;printf(“nInput data:”);使用數(shù)組的關(guān)鍵在于控制下標(biāo)變化aii=09a0a1.a9

4、數(shù)組a將數(shù)據(jù)輸入到各個(gè)數(shù)組元素中一維數(shù)組的初始化同簡(jiǎn)單變量一樣，數(shù)組元素在說(shuō)明后就對(duì)其賦值，如果用輸入語(yǔ)句或賦值語(yǔ)句使數(shù)組中的元素得到值，會(huì)占用運(yùn)行時(shí)間，因此可以使數(shù)組在程序運(yùn)行之前初始化，即在編譯階段使之得到初值。 例 #include stdio.hmain() int i, a10; for (i = 0;i = 9;i+) scanf(%d,&ai);一維數(shù)組的初始化初始化方法：從數(shù)組的第一個(gè)元素開(kāi)始依次給出初始值表;表中各值之間用逗號(hào)分開(kāi)，并用一對(duì)大括號(hào)括起來(lái)。 在定義數(shù)組時(shí)對(duì)數(shù)組元素賦予初值 int a10=9,1,6,3,4,5, 2,7, 0, 8; 只給一部分元素賦初值 in

5、t a10=0,1,2,3,4; 欲使一個(gè)數(shù)組中全部元素初值為0，只能寫(xiě)成： int a10 = 0,0,0,0,0,0,0,0,0,0,; 不能寫(xiě)成：int a10 = 0*10;/error 在對(duì)全部數(shù)組元素賦初值時(shí)，可以不指定數(shù)組長(zhǎng)度 int a =0,1,2,3,4,5;數(shù)組排序基本概念排序是根據(jù)某個(gè)標(biāo)準(zhǔn)，按照指定的次序（升序或降序）組織一組數(shù)據(jù)的過(guò)程。 根據(jù)執(zhí)行效率，排序算法通常分為兩大類：順序排序，一般使用一對(duì)嵌套的循環(huán)結(jié)構(gòu)，對(duì)排序n個(gè)元素需要大約n2次比較；對(duì)數(shù)排序，對(duì)排序n個(gè)元素一般需要大約nlog2n次比較。本節(jié)將介紹3種排序技術(shù)：選擇排序法插入排序法冒泡排序法排序算法插入排

6、序直接插入排序折半插入排序表插入排序希爾排序交換排序冒泡排序快速排序（不穩(wěn)定）選擇排序歸并排序基數(shù)排序插入排序 插入排序的基本思想是： 每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11）， 請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列?！?3】, 6, 3, 31, 9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3,

7、6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后順移。最簡(jiǎn)單的排序法！交換排序 兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序交換排序的基本思想是： 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按

8、“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲(chǔ)結(jié)構(gòu) 例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟54129867103a0a1a2a3a4

9、a5a6a7a8a9a0a1a j a j+1a8a9a1a2第一遍： j=08a1a1a7a0a2a j a j+1a8第二遍： j=07數(shù)據(jù)個(gè)數(shù)：n 遍數(shù)：i=0n-2 比較：j=0(n-2)-ifor (i=0;in-1;i+)for (j=0;jaj+1) t=aj;aj=aj+1;aj+1=t;冒泡排序（冒泡法）排序的基本思想是：倆倆相鄰數(shù)據(jù)比較交換。冒泡排序（冒泡法）例 用起泡法對(duì)10個(gè)數(shù)排序。#include stdio.h main() int a10=9,8,5,4,2,0,6,1,3,7; int i, j,temp,n = 10; for (i = 0; i =n-2;

10、i+) for (j = 0; j aj+1) temp = aj; aj = aj+1; aj+1 = temp; for (i = 0;i aj+1真for j=1 to n-2-i 假aj aj+1 互換for i=0 to n-2輸出:a數(shù)組元素比較排序（比較法）排序的基本思想是：倆倆相鄰數(shù)據(jù)比較交換。54129867103a0a1a2a3a4a5a6a7a8a9a0a1a9a i a i+1a9a8a9a1a2a9數(shù)據(jù)個(gè)數(shù)：n 遍數(shù)：i=0n-2 比較：j=i+1(n-1)for (i=0;in-1;i+)for (j=i+1;jaj) t=ai;ai=aj;aj=t;選擇排序（選擇

11、法）排序的基本思想是：找出數(shù)據(jù)中最小元素的位置再交換。54129867103a0a1a2a3a4a5a6a7a8a9a0a1a9a i a i+1a9a8a9a1a2a9數(shù)據(jù)個(gè)數(shù)：n 遍數(shù)：i=0n-2 比較：j=i+1(n-1)for (i=0;in-1;i+) w=i; for (j=i+1;jaj) w=j; if(w!=i) t=ai;ai=aw;aw=t; 選擇排序(選擇法）算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個(gè)數(shù)據(jù)同第一個(gè)數(shù)據(jù)交換位置；接下來(lái)找第二小的數(shù)據(jù)，再將其同第二個(gè)數(shù)據(jù)交換位置，以此類推。第1次，在數(shù)組a的n個(gè)數(shù)據(jù)中選出其小者（只標(biāo)記其所在位置），若它不在其位置（即

12、其下標(biāo)不等于1）則與第一個(gè)數(shù)據(jù)進(jìn)行交換（只需交換一次），經(jīng)過(guò)本次處理后，總可以使得數(shù)組a的第1個(gè)數(shù)據(jù)為第1小。第2次，在數(shù)組a的后n-1個(gè)數(shù)據(jù)（即出去已經(jīng)選擇的最小者的各數(shù)據(jù)）中，經(jīng)過(guò)類似的處理后，可以使得數(shù)組a的第2個(gè)數(shù)據(jù)為第2小。第i次，在數(shù)組a后的n-i+1個(gè)數(shù)據(jù)中，經(jīng)過(guò)類似選擇處理后，數(shù)組a的第i個(gè)數(shù)據(jù)為第i小。第n-1次，在數(shù)組后的2個(gè)數(shù)據(jù)中，經(jīng)過(guò)類似處理后，總可以使數(shù)組a的第n-1個(gè)數(shù)據(jù)為第n-1小。而這時(shí)候第n個(gè)數(shù)據(jù)是第n小。數(shù)組查找基本概念查找是在一組元素中尋找某個(gè)指定的目標(biāo)元素，或者確定該組元素中是否存在目標(biāo)元素的過(guò)程。 進(jìn)行查找的元素組有時(shí)稱為查找池（search pool

13、）。 本節(jié)將介紹兩種查找技術(shù)：線性查找（linear search）二分查找（binary search）查 找查找之前要求排序，不然無(wú)章可查順序查找按照排好序的順序進(jìn)行查找，比如對(duì)一個(gè)升序排列的數(shù)組中，找到第一個(gè)大于需要查找的數(shù)為止。折半查找（二分查找）查找算法：12345678910a0a1a2a3a4a5a6a7a8a9查 找例4 查找一個(gè)數(shù)是否在某數(shù)組中出現(xiàn)。 順序查找 設(shè)數(shù)組為a，待查找的數(shù)為x把x與數(shù)組a中的元素從頭到尾一 一進(jìn)行比較輸入n,a,x f：標(biāo)記1：查到0：沒(méi)查到 for i=0 to n-1x=ai真f=1假void main() int n,x,i,f,a50; s

14、canf(“%d,%d”,&n,&x); f=0; for(i=0;i=n-1;i+) if(x=ai) f=1; if(f) printf(“yes,%d”,i); else printf(“no”); for(i=0;iam,(m,t2)為新的查找范圍 t1=m3.若xam,(t1,m)為新的查找范圍 t2=mt1:查找范圍內(nèi)下標(biāo)最小值t2:查找范圍內(nèi)下標(biāo)最大值m:查找范圍內(nèi)下標(biāo)中值輸入n,a,x t1=0 t2=n-1 當(dāng)t1amt1=m假t2=m查找輸入n,a,x t=0 b=n-1 當(dāng)tamt=m+1假b=m-1void main()int a50,x,i,n,t1,t2,m,f;

15、cinn; for(i=0;iai; cinx; t1=0;t2=n-1;f=0; while(t1am)t1=m+1; else t2=m-1; if(f=1) cout“Yes,”m; else cout“No;例5 數(shù)組a有五個(gè)元素，其值分別為：1、2、3、4、5，循環(huán)移動(dòng)該數(shù)組的數(shù)，使其變成2、3、4、5、1。 m=a0for i=1,4ai-1=ai a4= m待移動(dòng)數(shù)據(jù)的下標(biāo)void main( ) int a5=1,2,3,4,5;m=a0;for (i=1;i=4;i+)ai-1=ai;a4=m;int i,m;for(i=0;inx); f=0; for(i=0;i=n-1;

16、i+) if(x=ai) f=1; break; for(i=0;iai; if(f) for(k=i+1;k=n-1;k+) ak-1=ak; n-; for(i=0;in;i+) couta0?操作真插入點(diǎn)是01xa1?真插入點(diǎn)是1ixai?真插入點(diǎn)是in-1xan-1?真插入點(diǎn)是n-1假插入點(diǎn)是n操作結(jié)果數(shù)組aa0a1a2a3a4a5a6a7a81085210-1-7數(shù)組a插入前插入后4108510-1-7-7224-1012有序插入例7 在一個(gè)降序排列的數(shù)列中插入一個(gè)數(shù)，使新數(shù)列保持原序。a7a81 向后移動(dòng)數(shù)據(jù)2 插入n-1i位置j：a6a7ajaj+1ai=xfor i=0 to

17、n-1xai真break假ai=xfor j=n-1 to i,-1aj+1=ajn+void main( ) int a20,i,j,x,n;scanf(“%d”,&x);for(i=0;iai) break;for(j=n-1;j=i;j- -)aj+1=aj;ai=x;n+;for(i=0;in;i+)printf(“%3d”,ai);for(i=0;iai真break假for j=n-1,i,-1aj+1=aj輸入數(shù)據(jù)輸出數(shù)據(jù)scanf(“%d”,&n);小結(jié)有序刪除：比如要?jiǎng)h除ad這個(gè)元素，則： for (j = d+1;j = L;j-) aj+1=aj;第三次實(shí)驗(yàn)作業(yè)（14周周三

18、提交）第七章（數(shù)組）實(shí)驗(yàn)： P147: ,2,4,5,6,(8,9,10,11,12)源程序文件命名方式： 例： 7-2.c 表示第七章第二題打包文件方式： 例： 程玉明-工程0901（三）.rar字符數(shù)組基本概念字符數(shù)組可用一個(gè)字符串常量來(lái)初始化，例如： char chStr = Hello;在字符串“Hello”中，除包含5個(gè)字符之外，還包含一個(gè)特殊的字符串結(jié)束字符，即NULL字符。所以，chStr數(shù)組實(shí)際包含了6個(gè)元素。C+使用0字符常量來(lái)表示NULL字符，所有字符串都必須使用這個(gè)字符結(jié)束的。排序的引例讀入amax=a讀入aamax真max=afor i=2 to n讀入n輸出假給數(shù)組t 賦值titw真for i=1 to n-1讀入n 假例2 從n個(gè)數(shù)中找出最大