6組織同類型數(shù)據(jù)ppt課件

1、C言語程序的數(shù)據(jù)構(gòu)造根底第2篇數(shù)據(jù)構(gòu)造 + 算法 = 程序C言語提供的數(shù)據(jù)耐久化技術(shù)，用來把數(shù)據(jù)存儲(chǔ)在外部存儲(chǔ)器上一種基于變量地址的派生數(shù)據(jù)類型一種描畫一類對(duì)象屬性的構(gòu)外型數(shù)據(jù)類型一種用來組織同類型數(shù)據(jù)的構(gòu)外型數(shù)據(jù)類型數(shù)組構(gòu)造體指針文件這一篇主要引見C言語提供的4種構(gòu)外型數(shù)據(jù)類型：順序地組織同類型數(shù)據(jù)數(shù)組類型數(shù)組是一種用于組織同類型數(shù)據(jù)的構(gòu)外型數(shù)據(jù)類型，其特征是類型一樣、順序存儲(chǔ)、隨機(jī)訪問、空間延續(xù)。第5單元5.1 數(shù)組根底數(shù)組定義、數(shù)組初始化、數(shù)組元素援用5.1.1 撲克牌的表示與數(shù)組定義1. 用數(shù)組存儲(chǔ)撲克牌101113，分別表示紅桃A紅桃K；201213，分別表示方塊A方塊K；30131

2、3，分別表示梅花A梅花K；401413，分別表示黑桃A黑桃K；501、502，分別表示大王、小王。這樣，54張撲克牌可以用一個(gè)int類型數(shù)組card表示和存儲(chǔ)，而每個(gè)元素以其在數(shù)組中下標(biāo)subscript或索引index區(qū)分，如card0、card1、card2、card53 分別表示54張撲克牌。2. 數(shù)組的定義數(shù)組定義的普通格式是數(shù)組用一個(gè)名字存儲(chǔ)多個(gè)同類型數(shù)據(jù)。運(yùn)用數(shù)組前，必需先進(jìn)展定義。存儲(chǔ)撲克的數(shù)組card可以用如下聲明定義。int card54; 數(shù)組類型 數(shù)組名 數(shù)組長(zhǎng)度 ;這個(gè)聲明語句定義了一個(gè)名字為card的數(shù)組；它有54個(gè)元素下標(biāo)變量，稱數(shù)組大小為54；并且每個(gè)元素都是in

3、t類型，稱這是一個(gè)int類型的數(shù)組。3. 數(shù)組初始化數(shù)組card的初始化語句為int card 54= 101,102,103,104,105,106,107,108,109,110,111,112,113,201,202,203,204,205,206,207,208,209,210,211,212,213,301,302,303,304,305,306,307,308,309,310,311,312,313,401,402,403,404,405,406,407,408,409,410,411,412,413,501,502;注1：C言語允許對(duì)數(shù)組中左面的部分元素初始化。例如，可以寫成in

4、t card 54= 101,102 ;注2：對(duì)于將全部元素都初始化時(shí)，在聲明語句中可以省略數(shù)組長(zhǎng)度。例如int card = 101,102,103,104,105,106,107,108,109,110,111,112,113,201,202,203,204,205,206,207,208,209,210,211,212,213,301,302,303,304,305,306,307,308,309,310,311,312,313,401,402,403,404,405,406,407,408,409,410,411,412,413,501,502 ;這樣，只需前兩個(gè)元素被初始化，后面元素

5、的值還是不確定的只對(duì)部分元素初始化時(shí)，不可以省略數(shù)組大小。4. 數(shù)組的特點(diǎn)各元素具有一樣類型。這個(gè)類型稱為數(shù)組基類型。元素之間具有順序性邏輯上的順序性和物理存儲(chǔ)上的順序性，并用下標(biāo)表示這種順序關(guān)系。(1)(2)一個(gè)數(shù)組的一切元素占有一片延續(xù)的內(nèi)存空間。(3)數(shù)組的元素可以用下標(biāo)隨機(jī)訪問。留意：下標(biāo)從0開場(chǎng)(4)5.1.2 撲克牌查找：數(shù)組元素援用與數(shù)組名參數(shù)1. 數(shù)組元素的援用數(shù)組名加上括在方括號(hào)中的下標(biāo)。例如card0、card1、card2、card3、的語法意義，就相當(dāng)于一組變量，稱為下標(biāo)變量。用下標(biāo)變量可以隨機(jī)地訪問數(shù)組中的任何一個(gè)元素，對(duì)其賦值或援用其值。代碼5.1 用賦值方法給定每

6、張撲克牌的值，輸出各張撲克牌的值并搜索一張牌。#include int main (void)int card54 ,i, j, k, x, flag = -1;/* 數(shù)組元素賦值 */for( i = 0; i 4; i +)/* 在反復(fù)構(gòu)造中給前52個(gè)元素賦值 */for(j = 0; j 13; j +)cardi * 13 + j = 100 * (i + 1) + j + 1;card52 = 501;/* 給最后兩張撲克牌賦值 */card53 = 502;/* 輸出各張牌的值 */for( i = 0; i = 53; i +) printf(card%d= %d, ,i,car

7、di );/* 搜索一張撲克牌 */printf(n輸入要查找的牌：);scanf(“%d,&x);for (k = 0; k 54; k +)/* 搜索為x的牌*/if(cardk = x)flag = k;break;if(flag = -1)printf(n找不到要找的牌！);elseprintf(n這張牌是第%d張牌。,k);return 0;2. 用函數(shù)實(shí)現(xiàn)數(shù)組操作功能與數(shù)組名參數(shù)代碼5.3 撲克牌搜索函數(shù)。int searchCard(int pk54 ,int x) int k; for (k = 0; k 54; k +) /* 搜索為x的牌*/ if (pkk = x) re

8、turn k; return -1;代碼5.4 函數(shù)searchCard()的測(cè)試主函數(shù)。#include int searchCard(int pk ,int x);int main (void)int x,f;int card54 = 101,102,103,104,105,106,107,108,109,110,111,112,113,201,202,203,204,205,206,207,208,209,210,211,212,213,301,302,303,304,305,306,307,308,309,310,311,312,313,401,402,403,404,405,406,

9、407,408,409,410,411,412,413,501,502 ;printf(n輸入要查找的牌: );scanf(%d,&x);f = searchCard(card,x); if (f = -1)printf(n找不到要找的牌！n);else printf(n要找的是第%d張牌！n, f);return 0;在C言語中數(shù)組名有兩種含義：一是用來標(biāo)識(shí)數(shù)組；二是代表數(shù)組的首地址。因此，數(shù)組名作為函數(shù)參數(shù)，在函數(shù)被調(diào)用時(shí)所傳送的不是數(shù)組的內(nèi)容，而是數(shù)組在內(nèi)存中的起始地址。 運(yùn)用數(shù)組名作為函數(shù)參數(shù)，需求用一對(duì)方括號(hào)明確地指明它是一個(gè)數(shù)組，并且要指出其數(shù)組類型。除非特殊情況，普通數(shù)組的大小可

10、以不傳輸。由于在調(diào)用時(shí)，會(huì)用實(shí)踐數(shù)組參數(shù)的大小來初始化方式數(shù)組參數(shù)的大小。3. 函數(shù)的測(cè)試要測(cè)試函數(shù)，需求為之設(shè)計(jì)一個(gè)驅(qū)動(dòng)函數(shù)。在C言語中，普通用主函數(shù)作為驅(qū)動(dòng)函數(shù)。驅(qū)動(dòng)函數(shù)要為被測(cè)試函數(shù)預(yù)備所需求的實(shí)踐參數(shù)。對(duì)于函數(shù)searchCard()，需求有一個(gè)為之提供可操作的數(shù)組。5.1.3 撲克洗牌的隨機(jī)模擬1. 一次洗牌模擬算法在053之間產(chǎn)生一個(gè)隨機(jī)數(shù)rdm，將card0與card rdm交換；在153之間產(chǎn)生一個(gè)隨機(jī)數(shù)rdm，將card 1與card rdm交換；在253之間產(chǎn)生一個(gè)隨機(jī)數(shù)rdm，將card 2與card rdm交換；在i53之間產(chǎn)生一個(gè)隨機(jī)數(shù)rdm，將cardi與card

11、rdm交換；這個(gè)過程可以描畫為：120irdm53已洗好部分未洗好部分下標(biāo)內(nèi)容tempfor( i = 0; i 54; + i)在i到53之間產(chǎn)生隨機(jī)數(shù)rdm;將cardi與cardrdm交換;代碼5.5 一次洗牌模擬函數(shù)。#include #include void shuffle(int card)int i,rdm, temp;srand(time(00);/* 用時(shí)間函數(shù)作為偽隨機(jī)數(shù)序列種子*/for(i = 0; i 54;+ i)rdm = rand() % (54 - i) + i;/* 生成一個(gè)i,53之間的隨機(jī)數(shù)*/temp = cardi;/* 交換兩個(gè)數(shù)組元素的值*/c

12、ardi = cardrdm;cardrdm = temp;代碼5.6 多次洗牌模擬函數(shù)。#include #include void shuffle(int card)int times = 1;/* 洗牌次數(shù)*/int i, j,rdm,temp;srand(time(00); /* 用時(shí)間函數(shù)作為偽隨機(jī)數(shù)序列種子 */printf(n請(qǐng)輸入洗牌次數(shù)：);scanf(%d,×);for(j = 0;j times;+ j)/* 反復(fù)n次*/for(i = 0; i 54;+ i)rdm = rand() % (54 - i) + i; /* 生成一個(gè)i,53之間的隨機(jī)數(shù)*/tem

13、p = cardi;cardi = cardrdm;cardrdm = temp; 5.1.4 撲克牌整理：數(shù)組元素排序1. 冒泡排序算法每當(dāng)一場(chǎng)撲克游戲終了后，人們總要把玩后被搞得亂序的牌進(jìn)展整理，即按照一定的順序陳列好。對(duì)于本例來說，就是把card數(shù)組中的元素進(jìn)展排序。排序sorting也稱分類，是指將一列數(shù)據(jù)按一定的規(guī)那么陳列。排序方法很多，例如，有交換法、選擇法、希爾法、插入法等，不同的方法效率不同。本節(jié)僅引見一種在算法上具有代表性的交換排序算法冒泡排序。7539157391537915379153719351793157913579開場(chǎng)第1輪n-1次比較第2輪n-2次比較終了 第n-

14、1輪2. 撲克牌整序函數(shù)代碼代碼5.7 運(yùn)用冒泡排序法的撲克整理排序函數(shù)。void cardSort(int card) /* 撲克整理方法 */int temp,i,j;for(j = 0; j 53 - 1; j +)/* 總輪數(shù) */for(i = 0; i cardi + 1)temp = cardi;cardi = cardi + 1;cardi + 1 = temp;3. 撲克牌輸出函數(shù)代碼補(bǔ)充代碼： 撲克輸出函數(shù)。void printCards(int card,int cardNum) int i; for( i = 0; i cardNum; i +) printf(card

15、%d= %d, ,i,cardi); 4. 整牌函數(shù)的測(cè)試#include #include #include /* time()要求的頭文件*/void shuffle(int card);/* 洗牌函數(shù)原型 */void cardSort(int card);/* 整牌函數(shù)原型 */void printCards(int card,int cardNum);/* 輸出各張撲克牌 */int main (void)int card = 101,102,103,104,105,106,107,108,109,110,111,112,113,201,202,203,204,205,206,207

16、,208,209,210,211,212,213,301,302,303,304,305,306,307,308,309,310,311,312,313,401,402,403,404,405,406,407,408,409,410,411,412,413,501,502 ;printf(“n撲克牌的初始序列：n);printCards(card,54);shuffle(card);printf(“n洗牌后的撲克牌序列：n);printCards(card,54);cardSort(card);printf(“n整牌后的撲克牌序列：n);printCards(card,54);return 0

17、;5.1.5 撲克發(fā)牌：二維數(shù)組運(yùn)用1. 問題描畫與算法框架發(fā)牌deal就是把洗好的牌，按照商定張數(shù)逐一發(fā)送到玩家hand手中。hand1hand2hand3hand4531314121617157861011919201821120453ij代碼5.8 發(fā)牌算法的C言語描畫。int i = 0, j;for( j = 0; j cardNumber; + j) /* cardNumber為每人發(fā)牌數(shù)目*/ hand1j = cardi; cardi = 0;+ i; /* cardi = 0 意味牌曾經(jīng)被取走*/ hand2j = cardi; cardi = 0;+ i; /* +i為下一

18、張牌下標(biāo) */ hand3j = cardi; cardi = 0;+ i; hand4j = cardi; cardi = 0;+ i;2. 用二維數(shù)組表示玩家手中的牌即一維用于表示玩家，另一維用于表示玩家手中的牌。例如，二維數(shù)組hand采用聲明語句int hand 4 12 ;聲明后，就表示開辟了一個(gè)4 12個(gè)int類型存儲(chǔ)空間，4表示4個(gè)玩家，12表示每人手中有12張牌。每個(gè)下標(biāo)變量分別表示某個(gè)人手中的某張牌。例如，hand25表示第3個(gè)玩家手中的第6張牌。1援用二維數(shù)組元素，要運(yùn)用兩個(gè)下標(biāo)，并且它們都用從0開場(chǎng)的整型常量或整型表達(dá)式表示。2二維數(shù)組初始化:例如：int a32 = 1,

19、2,3,4,5,6;例如：int a32 = 1,2,3,4,5,6;(1)(2)例如：int a 2 = 1,2,3,4,5,6;(3)例如：int a32 = 1,3,5;可以將行第1維的長(zhǎng)度省略，但第2維的大小不可以省略(4)還可以對(duì)部分元素初始化，但這時(shí)不可缺省第1維的大小。 3. 運(yùn)用二維數(shù)組的發(fā)牌方法運(yùn)用二維數(shù)組int hand后，用第1維表示玩家；用第2維表示給每位玩家的發(fā)牌數(shù)，各人手中的牌分別是：hand00、hand01、hand02、hand011;第1人手中的牌為hand10、hand11、hand12、hand111;第2人手中的牌為hand20、hand21、hand

20、22、hand211;第3人手中的牌為hand30、hand31、hand32、hand311;第4人手中的牌為對(duì)于更普通的情況，需求先確定玩家數(shù)handNumber和每人發(fā)牌數(shù)cardNumber代碼5.9 運(yùn)用二維數(shù)組的發(fā)牌函數(shù)。#define cardNumber 12 /* cardNumber為每人發(fā)牌數(shù)目 */#define handNumber 4 /* handNumber為玩家數(shù)目 */void deal( int card ,int handcardNumber )int i = 0, j, k;for(j = 0;j cardNumber;+ j)for(k = 0; k

21、 handNumber; + k)handkj = cardi; cardi = 0;+ i;代碼5.10 不傳送二維數(shù)組的發(fā)牌函數(shù)。#define cardNumber 12 /* cardNumber為每人發(fā)牌數(shù)目 */#define handNumber 4 /* handNumber為玩家數(shù)目*/void deal( int card ) int i = 0, j, k; int handhandNumbercardNumber; for(j = 0;j cardNumber;+ j) for(k = 0; k handNumber; + k) handkj = cardi; card

22、i = 0;+ i; for(k = 0;k handNumber;+ k) printf (n第%d人手中的牌為:,k + 1); for(j = 0; j cardNumber; + j) printf (%d ,handkj); 4. 發(fā)牌函數(shù)的測(cè)試運(yùn)用代碼5.9中的發(fā)牌函數(shù)，調(diào)用函數(shù)需求為其傳輸如下數(shù)據(jù)： 每人發(fā)牌數(shù)目cardNumber。 玩家數(shù)目handNumber。 存儲(chǔ)撲克牌的數(shù)組首地址。 存儲(chǔ)玩家手中牌的二維數(shù)組首地址。同時(shí)，調(diào)用函數(shù)還需求對(duì)撲克牌數(shù)組進(jìn)展了初始化。#include #define cardNumber 12#define handNumber 4void d

23、eal(int card,int handcardNumber);void printCards(int card,int cardNum); /* 輸出各張撲克牌*/int main (void) int i; int card54 = 101,102,103,104,105,106,107,108,109,110,111,112,113,201,202,203,204,205,206,207,208,209,210,211,212,213,301,302,303,304,305,306,307,308,309,310,311,312,313,401,402,403,404,405,406,

24、407,408,409,410,411,412,413,501,502 ; printf(n撲克牌的初始序列：); printCards(card,54); printf(n發(fā)牌情況：); deal(card); printf(n發(fā)牌后的底牌：); printCards(card,54); return 0; #include #define cardNumber 12#define handNumber 4void deal(int card,int handcardNumber);void printCards(int card,int cardNum); /* 輸出各張撲克牌*/int

25、main (void)int handhandNumbercardNumber;int i;int card54 = 101,102,103,104,105,106,107,108,109,110,111,112,113,201,202,203,204,205,206,207,208,209,210,211,212,213,301,302,303,304,305,306,307,308,309,310,311,312,313,401,402,403,404,405,406,407,408,409,410,411,412,413,501,502 ;printf(撲克牌的初始序列：);printC

26、ards(card,54);deal(card, hand);printf(發(fā)牌情況：);for(i = 0; i handNumber; i +)printf(玩家%d手中的牌為：,i);printCards(handi, cardNumber);printf(n); printf(發(fā)牌后的底牌：); printCards(card,54);return 0;5.2 字符串C言語的字符串是基于字符數(shù)組的5.2.1 字符串與字符數(shù)組1. 字符串的概念在C言語中，把用一對(duì)雙撇號(hào)括起來的零個(gè)或多個(gè)字符序列稱為字符串常數(shù)。如“hello、 “Programming in C等。字符串中的字符數(shù)稱為該

27、字符串的長(zhǎng)度。如上述字符串的長(zhǎng)度分別為5和16。2. 字符串中的特殊字符1本義字符的書寫。字符串以雙撇號(hào)為定界符，但雙撇號(hào)并不屬于字符串。要在字符串中插入撇號(hào)，應(yīng)借助本義字符。例如，要處置字符串I say:Goodbye!時(shí)，可以把它寫為I say:Goodbye!2格式字符串中的格式字符。格式化輸入輸出函數(shù)的格式參數(shù)都是一個(gè)字符串也稱格式字符串，其中的格式字符如c、d、f等都要以%開頭書寫。一切的本義字符，在字符串中都要以反斜杠開頭書寫。3. 字符串的存儲(chǔ)與字符數(shù)組在C言語中，字符串用字符數(shù)組存儲(chǔ)，并且在字符串的末尾加一個(gè)字符串終了標(biāo)志本義字符“0。如字符串“hello在內(nèi)存中存儲(chǔ)為留意字符

28、常數(shù)與字符串常數(shù)的區(qū)別，例如：A 是一個(gè)字符常數(shù)，用65存儲(chǔ)；而“ A是一個(gè)字符串常數(shù)，用6 50存儲(chǔ)。 表示一個(gè)空格，用32存儲(chǔ)；而“表示一個(gè)空字符串，用 0 存儲(chǔ)。hello04. 字符數(shù)組的定義及初始化字符數(shù)組是以字符為元素的數(shù)組，它的定義與初始化方法與一維數(shù)組一樣。例如：char str1=C, h, i, n, a;char str212= C, , p, r, o, g, r, a, m, i, n, g;字符串是特殊的字符數(shù)組，以字符串終了標(biāo)志0為最后一個(gè)元素。5. 字符串的定義和初始化可以有如下幾種方式:char str16= C, h, i, n, a, 0; /*基于字符的

29、初始化*/char str16= “China; /* 字符串方式的初始化*/char str16= “China; /* 字符串方式的初始化*/char str1=C, h, i, n, a, 0; /* 基于字符的初始化 */char str1=“China; /* 字符串方式的初始化 */char str1=“China; /* 字符串方式的初始化 */運(yùn)用字符串方式的初始化方式，C編譯器將自動(dòng)加上一個(gè)0標(biāo)志。因此給定的字符數(shù)組的大小要比實(shí)踐存儲(chǔ)的字符串中的有效字符數(shù)多1。6.為字符串常量添加下標(biāo)C+言語也允許用下標(biāo)來援用字符串常量中的一個(gè)字符，例如char ch;ch=“I am a

30、student.8printf(“%c,ch);將輸出字符t。這在某些情況下會(huì)比較方便。5.2.2 字符串輸入輸出在定義了一個(gè)字符串后，可以采用兩類庫函數(shù)進(jìn)展輸入/輸出操作。運(yùn)用這兩類庫函數(shù)，必需在程序中運(yùn)用文件包含語句#include 。輸入函數(shù)輸出函數(shù)格式化輸入輸出庫函數(shù)scanf()printf()非格式化輸入輸出庫函數(shù)gets()puts()1. 運(yùn)用%s格式的格式化輸入函數(shù)scanf()在scanf()/printf()函數(shù)中運(yùn)用%s格式，可以實(shí)現(xiàn)字符數(shù)組內(nèi)容的一次性輸入/輸出。假設(shè)字符串變量名為str，那么可以運(yùn)用下面的語句進(jìn)展整體的鍵盤輸入：scanf(%s,str);留意1 ：

31、在scanf( )函數(shù)中，假設(shè)數(shù)據(jù)參考處運(yùn)用的是數(shù)組名，那么數(shù)組名前不可以加取地址符&。由于數(shù)組名本身就是一個(gè)地址。留意2：運(yùn)用%s格式的scanf()函數(shù)進(jìn)展字符串的鍵盤輸入時(shí)，遇到一個(gè)空白類字符空格、制表符，Enter等就表示一個(gè)字符串的終了，系統(tǒng)會(huì)就此給它加上一個(gè)字符串終了標(biāo)志0。例如對(duì)于語句：scanf(%s,str);假設(shè)從鍵盤上鍵入 Computer & C那么在變量str中保管的是Computer0留意3：假設(shè)用曾經(jīng)定義的長(zhǎng)度較大字符數(shù)組存儲(chǔ)字符串，那么數(shù)組中的空余元素將用0填充。例如char str19, str29, str39;scanf(%s %s %s , str1,s

32、tr2, str3);假設(shè)從鍵盤上鍵入 Computer & C那么這三個(gè)數(shù)組中的存儲(chǔ)情況為：str1str2str3Computer0&00000000C000000002. 運(yùn)用%s格式的格式化輸出函數(shù)printf()運(yùn)用下面的語句可以進(jìn)展字符串的整體輸出printf(%s,str);留意：輸出的內(nèi)容中不包括字符串終了標(biāo)志0。3. 運(yùn)用字符串處置函數(shù)gets()和puts()實(shí)現(xiàn)非格式化輸入輸出puts()函數(shù)用來輸出一個(gè)字符串，它的作用與printf(“%s,字符串)一樣。但用puts()函數(shù)一次只能輸出一個(gè)字符串，不能企圖用puts (str1,str2)的方式一次輸出兩個(gè)字符串。ge

33、ts()函數(shù)是一個(gè)用來輸入一個(gè)字符串的函數(shù)。代碼5.11 #include #define N 13int main (void) char strN;printf(請(qǐng)輸入一個(gè)字符串：n);gets (str);puts (str);puts (str);return 0;(1)用gets()可以讀入包括空格字符的字符串。(2)用puts()輸出時(shí)，將“0字符轉(zhuǎn)換成換行符，因此用puts()時(shí)一次輸出一行，不用另加換行符。(3) gets()和puts()函數(shù)都是具有前往值的函數(shù)，它們執(zhí)行勝利時(shí)將前往字符數(shù)組首元素的地址。請(qǐng)輸入一個(gè)字符串：Computer & CComputer & CCom

34、puter & C代碼5.12 #include #define N 13int main () char strN;printf(請(qǐng)輸入一個(gè)字符串：n);printf(gets的前往值為：%dn,gets (str);printf(puts的前往值為：%dn,puts (str); return 0;5.2.3 字符串的其他操作1. 字符串操作庫函數(shù)字符串不能直接用系統(tǒng)定義的操作符進(jìn)展賦值、比較等操作。下表是其中運(yùn)用較多的幾個(gè)字符串操作庫函數(shù)。函數(shù)的一般形式功能說明返回值strlen(字符串)求字符串長(zhǎng)度有效字符個(gè)數(shù)strcpy(字符串1,字符串2)將字符串2復(fù)制到字符串1中字符串1的起始地址strcmp(字符串1,字符串2)比較兩個(gè)字符串字符串1=字符串2，返回0;字符串1字符串2，返回正整數(shù);字符串1字符串2，返回負(fù)整數(shù)strchr(字