計(jì)算機(jī)二級(jí) 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)二級(jí)構(gòu)造型數(shù)據(jù)結(jié)構(gòu)第1頁(yè)，共20頁(yè)，2023年，2月20日，星期四1一維數(shù)組的定義一維數(shù)組的定義形式：類型名

數(shù)組名

[常量表達(dá)式]『說(shuō)明』類型名：數(shù)組元素的類型，它們可以是基本類型，如int、float等，也可以是構(gòu)造類型數(shù)組名：數(shù)組的名稱，命名規(guī)則與變量的名稱一樣。常量表達(dá)式：用方括號(hào)括起，表示數(shù)組元素的個(gè)數(shù)，即數(shù)組的長(zhǎng)度，它是一個(gè)正整數(shù)。其中可以包含常數(shù)和符號(hào)常量，但不能包含變量。第2頁(yè)，共20頁(yè)，2023年，2月20日，星期四2

（1）數(shù)組名后面必須是方括號(hào)。例如：inta（100）；是錯(cuò)誤的。（2）“[]”中的常量表達(dá)式中不能包含變量，即使是變量已被賦值。如下面的用法是錯(cuò)誤的：intm;m=10;inta[m];（3），可同時(shí)說(shuō)明類型相同的多個(gè)數(shù)組和多個(gè)變量。例如：inta,b,k1[10],k2[20];（4）常量表達(dá)式的值表示數(shù)組元素的個(gè)數(shù)。例如：inta[10];/*定義一個(gè)名為a的一維數(shù)組，數(shù)組中有10個(gè)數(shù)組元素*/floatb[‘A’],c[3*5];inta1[MAX],b1,c1;/*MAX為一符號(hào)常量*/一維數(shù)組的定義第3頁(yè)，共20頁(yè)，2023年，2月20日，星期四3

（5）一維數(shù)組在內(nèi)存中順序存放，占用連續(xù)空間

例如，有如下定義：inta[10]；系統(tǒng)為數(shù)組a開(kāi)辟了10個(gè)連續(xù)的存儲(chǔ)單元，定義了十個(gè)變量，這一批變量的名字分別為a[0]，a[1]，a[2]，a[3]，a[4]，a[5]，a[6]，a[7]，a[8]，a[9]。數(shù)組名代表的是整個(gè)存儲(chǔ)單元的首地址，可以說(shuō)a與數(shù)組元素a[0]的地址值相同。

a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]

（6）C語(yǔ)言不允許對(duì)數(shù)組的大小做作動(dòng)態(tài)定義，即數(shù)組的大小不依賴程序運(yùn)行過(guò)程中變量的值.例如：intd;d=5;inta[d];……是錯(cuò)誤的。一維數(shù)組的定義第4頁(yè)，共20頁(yè)，2023年，2月20日，星期四4一維數(shù)組元素的表示形式數(shù)組名[下標(biāo)]『說(shuō)明』數(shù)組必須先定義后使用不能一次引用整個(gè)數(shù)組。只能逐個(gè)引用數(shù)組元素，每個(gè)數(shù)組元素具有和相同類型單個(gè)變量一樣的屬性，可以對(duì)它進(jìn)行賦值和參與各種運(yùn)算。數(shù)組元素的下標(biāo)可以是整型常量或整型表達(dá)式，其值代表元素相對(duì)于數(shù)組起始地址的偏移量，所以從0開(kāi)始順序編號(hào)，取值范圍是0~（元素個(gè)數(shù)-1）。以下假設(shè)是16位機(jī)一維數(shù)組的引用第5頁(yè)，共20頁(yè)，2023年，2月20日，星期四5&a[i]a[i]a=1000→01002→101004→201006→301008→401010→501012→601014→70inta[8];a[0]=0;a[1]=10;a[2]=20;a[3]=30;a[4]=40;a[5]=50;a[6]=60;a[7]=70注意：a=&a[0]=1000一維數(shù)組的引用第6頁(yè)，共20頁(yè)，2023年，2月20日，星期四6『程序4.1』程序使a[0]~a[9]的值為0~9，然后按逆序輸出。main(){inti,a[10];for(i=0;i<=9;i++)/*對(duì)數(shù)組元素賦值*/a[i]=i;for(i=9;i>=0;i--)/*逆序逐個(gè)輸出數(shù)組元素*/printf(“%2d”,a[i]);}運(yùn)行結(jié)果為：9876543210一維數(shù)組的引用第7頁(yè)，共20頁(yè)，2023年，2月20日，星期四7靜態(tài)數(shù)組與動(dòng)態(tài)數(shù)組：staticinta[10];——靜態(tài)數(shù)組

inta[10];——?jiǎng)討B(tài)數(shù)組關(guān)鍵字static是“靜態(tài)存儲(chǔ)”，其定義的數(shù)組稱為靜態(tài)數(shù)組，省略關(guān)鍵字static所定義的數(shù)組則是動(dòng)態(tài)數(shù)組。定義靜態(tài)數(shù)組時(shí)，如果不賦初值，所有元素初值為0。定義動(dòng)態(tài)數(shù)組時(shí)，如果不賦初值，數(shù)組元素的值不確定，如inta[10]

的每個(gè)元素的值可以是-32768～32767之間的一個(gè)整數(shù)一維數(shù)組的初始化第8頁(yè)，共20頁(yè)，2023年，2月20日，星期四8一維數(shù)組初始化的一般形式：static

數(shù)據(jù)類型數(shù)組名[常量表達(dá)式]＝{初值表}對(duì)所有數(shù)組元素賦初值：inta[5]={1,2,3,4,5};——a:12345staticintb[3]={3,4,5};——b:345對(duì)部分?jǐn)?shù)組元素賦初值inta[5]={1,2,4};——a:12400staticb[3]={0,3};——b:030按順序賦值，不能跳過(guò)前面的元素給后面的元素賦值初值個(gè)數(shù)少于元素個(gè)數(shù)，自動(dòng)給后面的元素補(bǔ)0；初值個(gè)數(shù)多于元素個(gè)數(shù)，出錯(cuò)！初始化不指定數(shù)組長(zhǎng)度，元素個(gè)數(shù)等于所賦初值的個(gè)數(shù)inta[]={1,2};——a:12即等同于inta[2]={1,2}

第9頁(yè)，共20頁(yè)，2023年，2月20日，星期四9一維數(shù)組引用舉例：使用冒泡法對(duì)數(shù)據(jù)進(jìn)行排序冒泡法思想：通過(guò)相鄰兩個(gè)數(shù)之間的比較和交換，使數(shù)值較小的數(shù)逐漸從底部移向頂部，數(shù)值較大的數(shù)逐漸從頂部移向底部。就像水底的氣泡一樣逐漸向上冒，故而得名。冒泡排序的過(guò)程設(shè)有A[1]～A[n]組成的n個(gè)數(shù)據(jù)，要從小到大排序：首先將相鄰的A[1]與A[2]進(jìn)行比較，如果A[1]的值大于A[2]的值，則交換兩者的位置，使較小的上浮，較大的下沉；接著比較A[2]與A[3]，同樣使小的上浮，大的下沉。依此類推，直到比較完A[n-1]和A[n]后，A[n]為具有最大數(shù)值的元素，稱第一趟排序結(jié)束。然后在A[1]~A[n-1]區(qū)間內(nèi)，進(jìn)行第二趟排序，使剩余元素中數(shù)值最大的元素下沉到A[n-1]；重復(fù)進(jìn)行n-1趟后，整個(gè)排序過(guò)程結(jié)束。第10頁(yè)，共20頁(yè)，2023年，2月20日，星期四10『程序4.2』用冒泡法對(duì)10個(gè)整數(shù)排序（由小到大）main(){inti,j,t,a[10];printf("input10numbers:\n");for(i=0;i<10;i++)/*輸入數(shù)組元素?cái)?shù)據(jù)，使用a[1]～a[10]*/scanf(“%d”,&a[i]);printf(“\n”);for(i=0;i<=8;i++)/*外循環(huán)：控制比較趟數(shù)*/for(j=0;j<=8-i;j++)/*內(nèi)循環(huán)：進(jìn)行每趟比較*/if(a[j]>a[j+1])/*如果a[j]大于a[j-1],交換兩者的位置*/{t=a[j];a[j]=a[j+1];a[j+1]=t;}printf(“Thesortednumbers:\n”);for(i=0;i<10;i++)/*輸出排序后數(shù)據(jù)*/printf(“%3d”,a[i]);}重要例題第11頁(yè)，共20頁(yè)，2023年，2月20日，星期四11一維數(shù)組引用舉例：使用選擇法對(duì)數(shù)據(jù)進(jìn)行排序選擇法思想：設(shè)有A[1]～A[n]組成的n個(gè)數(shù)據(jù)，從小到大排序：首先在A[1]和A[n]范圍內(nèi)，選擇最小的數(shù)與A[1]交換，然后在A[2]~A[n]區(qū)間內(nèi)，再選出最小的數(shù)與A[2]交換，重復(fù)進(jìn)行n-1趟后，整個(gè)排序過(guò)程結(jié)束。從A[i]~A[n]中選出最小的值并與A[i]交換可以采用下面的方法：引入變量j和k，j初值為i+1，k初值為i，反復(fù)比較A[k]和A[j]的值，若A[k]>A[j]，則將j的值賦給k，每進(jìn)行一次比較后，j加1。當(dāng)j=n，同時(shí)k≠i時(shí)，交換A[i]和A[k]。第12頁(yè)，共20頁(yè)，2023年，2月20日，星期四12『程序4.2』用排序法對(duì)10個(gè)整數(shù)排序（由小到大）main(){inti,j,k,t,a[11];printf("input10numbers:\n");for(i=1;i<=10;i++)/*輸入數(shù)組元素?cái)?shù)據(jù)，使用a[1]～a[10]*/scanf(“%d”,&a[i]);printf(“\n”);for(i=1;i<=9;i++)/*外循環(huán)：控制比較趟數(shù)*/{k=i;for(j=i+1;j<=10;j++)/*內(nèi)循環(huán)：選擇最小的值*/if(a[k]>a[j])k=j;if(k!=i)/*如果k不等于i，交換兩者的位置*/{t=a[i];a[i]=a[k];a[k]=t;}}printf(“Thesortednumbers:\n”);for(i=1;i<11;i++)/*輸出排序后數(shù)據(jù)*/printf(“%3d”,a[i]);}重要例題第13頁(yè)，共20頁(yè)，2023年，2月20日，星期四13二維數(shù)組的定義形式：類型名數(shù)組名[常量表達(dá)式1][常量表達(dá)式2]『說(shuō)明』類型名、數(shù)組名和一維數(shù)組類似。常量表達(dá)式1表示行數(shù)，常量表達(dá)式2表示列數(shù)，都為整型常量值或整型常量表達(dá)式，不能包含變量。數(shù)組元素的個(gè)數(shù)為：常量表達(dá)式1×常量表達(dá)式2。可以把二維數(shù)組看作特殊的一維數(shù)組，此一維數(shù)組的每個(gè)元素又是一個(gè)一維數(shù)組。二維數(shù)組的定義第14頁(yè)，共20頁(yè)，2023年，2月20日，星期四14『例』floatb[2][3];數(shù)組元素的類型為單精度實(shí)型數(shù)組元素共2×3＝6個(gè)，分為2行3列數(shù)組元素在內(nèi)存中連續(xù)存儲(chǔ)，按行存放，即地址從低到高：b[0][0]b[0][1]b[0][2]b[1][0]b[1][1]b[1][2]可理解為兩個(gè)一維數(shù)組：二維數(shù)組可以很容易擴(kuò)展到多維數(shù)組，如3維inta[2][3][2]第15頁(yè)，共20頁(yè)，2023年，2月20日，星期四15二維數(shù)組元素的表示形式數(shù)組名[下標(biāo)1][下標(biāo)2]『說(shuō)明』同一維數(shù)組一樣，二維數(shù)組必須先定義后使用；不能一次引用整個(gè)數(shù)組只能逐個(gè)引用數(shù)組元素。下標(biāo)可以是整型常量或整型表達(dá)式，要注意保證數(shù)組下標(biāo)不越界。如定義數(shù)組b[M][N]（M和N都是整型常量），則下標(biāo)的取值范圍分別是：下標(biāo)1：0～M-1下標(biāo)2：0～N-1二維數(shù)組的引用第16頁(yè)，共20頁(yè)，2023年，2月20日，星期四16對(duì)全部元素賦初值分行賦值inta[2][3]={{1,2,3},{4,5,6}};每一行用一個(gè)花括號(hào)括起，逗號(hào)作為間隔符。按順序賦值inta[2][3]={1,2,3,4,5,6};與一維數(shù)組相同，因?yàn)槎S數(shù)組存儲(chǔ)是連續(xù)的。省略一維長(zhǎng)度inta[][3]={{1,2,3},{4,5,6}};inta[][3]={1,2,3,4,5,6};二維數(shù)組的初始化第17頁(yè)，共20頁(yè)，2023年，2月20日，星期四17對(duì)部分元素賦初值分行賦值inta[3][3]={{1,3},{4,5,6}};后面沒(méi)賦初值的元素，系統(tǒng)自動(dòng)賦予初值0。按順序賦值inta[2][3]={1,2,3,4};與一維數(shù)組相同，因?yàn)槎S數(shù)組存儲(chǔ)是連續(xù)的。省略一維長(zhǎng)度inta[][3]={{1,2,3},{4,5,6},{}};→inta[3][3]=……inta[][3]={1,2,3,4,5,6,7};→inta[3][3]=……行數(shù)為3inta[][3]={1,2}→inta[1][3]=……行數(shù)為1第18頁(yè)，共20頁(yè)，2023年，2月20日，星期四18二