C++程序設(shè)計(jì)基礎(chǔ)：第5章 集合與結(jié)構(gòu)

1、第第5 5章章 集合與結(jié)構(gòu)集合與結(jié)構(gòu) 5.1 5.1 位運(yùn)算位運(yùn)算5.2 5.2 集合集合5.3 5.3 結(jié)構(gòu)結(jié)構(gòu) 5.4 5.4 結(jié)構(gòu)數(shù)組結(jié)構(gòu)數(shù)組 5.5 5.5 鏈表鏈表 小結(jié)小結(jié) 5.1 5.1 位運(yùn)算位運(yùn)算 計(jì)算機(jī)的存儲器采用二進(jìn)制表示數(shù)據(jù)計(jì)算機(jī)的存儲器采用二進(jìn)制表示數(shù)據(jù) 計(jì)算機(jī)系統(tǒng)的存儲器用每計(jì)算機(jī)系統(tǒng)的存儲器用每8位為位為1字節(jié)編址字節(jié)編址 不同類型的數(shù)據(jù)由不同字節(jié)長度存儲不同類型的數(shù)據(jù)由不同字節(jié)長度存儲 每一個數(shù)位的取值，只有兩個可能值：每一個數(shù)位的取值，只有兩個可能值：0或者或者1 位運(yùn)算能夠直接處理數(shù)據(jù)中每一位的值位運(yùn)算能夠直接處理數(shù)據(jù)中每一位的值為方便起見，本節(jié)敘述中用一個

2、字節(jié)表示一個正整數(shù)為方便起見，本節(jié)敘述中用一個字節(jié)表示一個正整數(shù)5.1 5.1 位運(yùn)算位運(yùn)算位運(yùn)算符位運(yùn)算符& &按位與按位與&=&=按位與賦值按位與賦值| |按位或按位或|=|=按位或賦值按位或賦值 按位異或按位異或=按位異或賦值按位異或賦值左移左移=右移右移=右移賦值右移賦值 按按位取反位取反1. 1. 按位與運(yùn)算按位與運(yùn)算左右操作數(shù)對應(yīng)的每一位分別做邏輯與運(yùn)算左右操作數(shù)對應(yīng)的每一位分別做邏輯與運(yùn)算 10 0 0 0 0 1 0 1 0& 29& 0 0 0 1 1 1 0 1 8 0 0 0 0 1 0 0 0若有語句若有語句 cout10

3、&29=(10&29)endl;則顯示結(jié)果為則顯示結(jié)果為10&29=82. 2. 按位或運(yùn)算按位或運(yùn)算左右操作數(shù)對應(yīng)的每一位分別做邏輯或運(yùn)算左右操作數(shù)對應(yīng)的每一位分別做邏輯或運(yùn)算 10 0 0 0 0 1 0 1 0 | 29 | 0 0 0 1 1 1 0 1 31 0 0 0 1 1 1 1 1若有語句若有語句 cout10|29=(10|29)endl;則顯示結(jié)果為則顯示結(jié)果為10|29=313. 3. 按位異或運(yùn)算按位異或運(yùn)算當(dāng)左右操作數(shù)對應(yīng)位不相同，即當(dāng)且僅當(dāng)其中一個為當(dāng)左右操作數(shù)對應(yīng)位不相同，即當(dāng)且僅當(dāng)其中一個為1 1時(shí)，時(shí)，位操作的結(jié)果才為位操作的結(jié)果才為

4、1 1 10 0 0 0 0 1 0 1 0 29 0 0 0 1 1 1 0 1 23 0 0 0 1 0 1 1 1若有語句若有語句 cout10|29=(10|29)endl;則顯示結(jié)果為則顯示結(jié)果為1029=234. 4. 左移左移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向左移動，騰空數(shù)按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向左移動，騰空數(shù)位補(bǔ)位補(bǔ)0 0 102 000010102 40 00101000若有語句若有語句 cout102=(102)endl;則顯示結(jié)果為則顯示結(jié)果為102=40對于一個整數(shù)，每左移一位就相當(dāng)于乘以對于一個整數(shù)，每左移一位就相當(dāng)于乘以2（結(jié)果不溢出時(shí)）（結(jié)果不溢出時(shí)

5、）4. 4. 左移左移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向左移動，騰空數(shù)按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向左移動，騰空數(shù)位補(bǔ)位補(bǔ)0 0若有語句若有語句 cout-102=(-102)endl;則顯示結(jié)果為則顯示結(jié)果為-102 000011002 3 00000011若有語句若有語句 cout2=2)2=3對于一個整數(shù)，每右移一位就相當(dāng)于整除以對于一個整數(shù)，每右移一位就相當(dāng)于整除以25. 5. 右移右移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向右移動按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向右移動若有語句若有語句 cout2=2)2=-3對于一個整數(shù)，每右移一位就相當(dāng)于整除以對于一個整數(shù)，每右移一位就相當(dāng)

6、于整除以2做算術(shù)右移時(shí)，不會移動符號位做算術(shù)右移時(shí)，不會移動符號位6. 6. 按位取反按位取反單目運(yùn)算。對操作數(shù)按位做邏輯非單目運(yùn)算。對操作數(shù)按位做邏輯非 10 00001010 -11 11110101若有語句若有語句 cout10=(10)endl;則顯示結(jié)果為則顯示結(jié)果為10=-11負(fù)數(shù)在計(jì)算機(jī)中用補(bǔ)碼表示。負(fù)數(shù)在計(jì)算機(jī)中用補(bǔ)碼表示。11110101是是-11的補(bǔ)碼的補(bǔ)碼7. 7. 位運(yùn)算的復(fù)合賦值位運(yùn)算的復(fù)合賦值位運(yùn)算的位運(yùn)算的5 5個復(fù)合賦值與其他復(fù)合賦值的操作形式一致個復(fù)合賦值與其他復(fù)合賦值的操作形式一致例如，若有例如，若有int a, b ;則則a&=b等價(jià)于等價(jià)于a=a

7、&ba|=b等價(jià)于等價(jià)于 a=a|ba=b等價(jià)于等價(jià)于 a=aba=b等價(jià)于等價(jià)于a=a=b等價(jià)于等價(jià)于a=ab 當(dāng)一個整數(shù)的二進(jìn)制串中只有一個數(shù)位為當(dāng)一個整數(shù)的二進(jìn)制串中只有一個數(shù)位為1時(shí)，稱為時(shí)，稱為掩碼掩碼 程序中通常借助掩碼對數(shù)據(jù)按位進(jìn)行測試程序中通常借助掩碼對數(shù)據(jù)按位進(jìn)行測試掩碼掩碼0 01 10 00 00 00 00 00 0#includeusing namespace std;void bitDisplay(unsigned value);void main() unsigned x; coutx; bitDisplay(x);/調(diào)用函數(shù)，以二進(jìn)制形式輸出正整數(shù)調(diào)用函

8、數(shù)，以二進(jìn)制形式輸出正整數(shù)【例例5-15-1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;【例例5-15-1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)

9、的值。0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 11 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0valuebitMask0【例例5-15-1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位

10、if(c%8=0) cout ; coutendl;0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value0bitMask【例例5-15-1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位

11、 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value0bitMask【例例5-5-1 1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask

12、?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value0bitMask【例例5-5-1 1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+

13、) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value1bitMask【例例5-5-1 1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 cou

14、tvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value1bitMask【例例5-5-1 1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsigned c; unsigned bitMask=

15、131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value0bitMask【例例5-5-1 1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDisplay(unsigned value) unsig

16、ned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0value1bitMask【例例5-5-1 1】按二進(jìn)制位串形式輸出正整數(shù)的值。按二進(jìn)制位串形式輸出正整數(shù)的值。void bitDispl

17、ay(unsigned value) unsigned c; unsigned bitMask=131;/掩碼，最高位置掩碼，最高位置1 coutvalue=; for(c=1;c=32;c+) cout(value&bitMask?1:0);/輸出輸出value的最高位的最高位 value=1;/value左移左移1位位 if(c%8=0) cout ; coutendl;【例例5-25-2】位運(yùn)算測試位運(yùn)算測試#includeusing namespace std;void bitDisplay(unsigned value);int main() unsigned n1,n2;

18、n1=214; n2=5; coutn1=t; bitDisplay(n1); coutn2=t“; bitDisplay(n2); coutn1&n2=t; bitDisplay(n1&n2); coutn1|n2=t; bitDisplay(n1|n2); coutn1n2=t; bitDisplay(n1n2); coutn1n2=t; bitDisplay(n1n2); coutn1n2n2); coutn1=t“; bitDisplay(n1);#includeusing namespace std;void bitDisplay(unsigned value);in

19、t main() unsigned n1,n2; n1=214; n2=5; coutn1=t; bitDisplay(n1); coutn2=t“; bitDisplay(n2); coutn1&n2=t; bitDisplay(n1&n2); coutn1|n2=t; bitDisplay(n1|n2); coutn1n2=t; bitDisplay(n1n2); coutn1n2=t; bitDisplay(n1n2); coutn1n2n2); coutn1=t“; bitDisplay(n1);【例例5-25-2】位運(yùn)算測試位運(yùn)算測試void bitDisplay(

20、unsigned value ) unsigned c; unsigned bitMask=131; for( c=1; c=32; c+ ) cout ( value&bitMask ? 1 : 0 ) ; value = 1; if( c%8 = 0 ) cout ; cout endl ;#includeusing namespace std;void bitDisplay(unsigned value);int main() unsigned n1,n2; n1=214; n2=5; coutn1=t; bitDisplay(n1); coutn2=t“; bitDisplay

21、(n2); coutn1&n2=t; bitDisplay(n1&n2); coutn1|n2=t; bitDisplay(n1|n2); coutn1n2=t; bitDisplay(n1n2); coutn1n2=t; bitDisplay(n1n2); coutn1n2n2); coutn1=t“; bitDisplay(n1);void bitDisplay( unsigned value ) unsigned c; unsigned bitMask=131; for( c=1; c=32; c+ ) cout ( value&bitMask ? 1 : 0 )

22、 ; value = 1; if( c%8 = 0 ) cout ; cout endl ;【例例5-25-2】位運(yùn)算測試位運(yùn)算測試#includeusing namespace std;void main() int a=123, b=456; couta=atb=bendl; a=ab; couta=abtaendl; a=ab; couta=abtaendl;【例例5-35-3】數(shù)據(jù)恢復(fù)數(shù)據(jù)恢復(fù) 10 = 1 10 = 1 01 = 1 11 = 0 11 = 0 01 = 1 00 = 0 00 = 0#includeusing namespace std;void main() in

23、t a=123, b=456; couta=atb=bendl; a=ab; b=ab; a=ab; couta=atb=bendl;【例例5-45-4】整變量交換整變量交換#includeusing namespace std;int main() double a=123.456, b=456.789; int*ap,*bp; ap = (int*)(&a); bp = (int*)(&b); couta=atb=bendl; *ap=(*ap)*(bp); *bp=(*ap)(*bp); *ap=(*ap)(*bp); ap+; bp+; *ap=(*ap)*(bp);

24、*bp=(*ap)(*bp); *ap=(*ap)(*bp); couta=atb=bendl;【例例5-55-5】浮點(diǎn)變量交換浮點(diǎn)變量交換 集合是不能精確定義的基本數(shù)學(xué)概念。一般認(rèn)為，當(dāng)集合是不能精確定義的基本數(shù)學(xué)概念。一般認(rèn)為，當(dāng)一些事物是可以按照某種性質(zhì)（屬性）分辨，這種事物構(gòu)一些事物是可以按照某種性質(zhì)（屬性）分辨，這種事物構(gòu)成的整體就稱為集合。成的整體就稱為集合。 根據(jù)集合的屬性，可以斷定某個特定的事物是否屬于根據(jù)集合的屬性，可以斷定某個特定的事物是否屬于這個集合。如果屬于，就稱它為這個集合的元素。這個集合。如果屬于，就稱它為這個集合的元素。5.2 5.2 集合集合集合的基本運(yùn)算集合的

25、基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成E AB集合的基本運(yùn)算集合的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成

26、 交集交集 A AB B由由A A和和B B中的公共的組成中的公共的組成集合的基本運(yùn)算集合的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成 交集交集 A AB B由由A A和和B B中的公共的組成中的公共的組成 差差A(yù)-BA-B由屬于由屬于A A但不屬于但不屬于B B的元素組成的元素組成集合的基本運(yùn)算集合的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母

27、標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成 交集交集 A AB B由由A A和和B B中的公共的組成中的公共的組成 差差A(yù)-BA-B由屬于由屬于A A但不屬于但不屬于B B的元素組成的元素組成 包含包含 A BA BA A中的每個元素都在中的每個元素都在B B中，中，稱為稱為A A被被B B包含，或包含，或B B包含包含A A集合的基本運(yùn)算集合的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合

28、通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成 交集交集 A AB B由由A A和和B B中的公共的組成中的公共的組成 差差A(yù)-BA-B由屬于由屬于A A但不屬于但不屬于B B的元素組成的元素組成 包含包含 A BA BA A中的每個元素都在中的每個元素都在B B中，中，稱為稱為A A被被B B包含，或包含，或B B包含包含A A 補(bǔ)集補(bǔ)集 A A 由全集中不在由全集中不在A A的元素組成的元素組成集合的基本運(yùn)算集合

29、的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成 交集交集 A AB B由由A A和和B B中的公共的組成中的公共的組成 差差A(yù)-BA-B由屬于由屬于A A但不屬于但不屬于B B的元素組成的元素組成 包含包含 A BA BA A中的每個元素都在中的每個元素都在B B中，中，稱為稱為A A被被B B包含，或包含，或B B包含包含A A 補(bǔ)集補(bǔ)集 A A 由全集

30、中不在由全集中不在A A的元素組成的元素組成 屬于屬于 x xA A元素元素x x在在A A中中集合的基本運(yùn)算集合的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成 交集交集 A AB B由由A A和和B B中的公共的組成中的公共的組成 差差A(yù)-BA-B由屬于由屬于A A但不屬于但不屬于B B的元素組成的元素組成 包含包含 A BA BA A中的每個元素都在中

31、的每個元素都在B B中，中，稱為稱為A A被被B B包含，或包含，或B B包含包含A A 補(bǔ)集補(bǔ)集 A A 由全集中不在由全集中不在A A的元素組成的元素組成 屬于屬于 x xA A元素元素x x在在A A中中 空集空集 集合中沒有元素集合中沒有元素E 集合的基本運(yùn)算集合的基本運(yùn)算 集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記集合通常用大寫字母標(biāo)記，集合元素用小寫字母標(biāo)記 若若A、B是全集是全集E中的兩個集合，中的兩個集合， x表示元素表示元素 集合主要運(yùn)算有：集合主要運(yùn)算有： 并集并集 A AB B由由A A和和B B中的全部元素組成中的全部元素組成 交集交集 A AB B由由A A和和B

32、 B中的公共的組成中的公共的組成 差差A(yù)-BA-B由屬于由屬于A A但不屬于但不屬于B B的元素組成的元素組成 包含包含 A BA BA A中的每個元素都在中的每個元素都在B B中，中，稱為稱為A A被被B B包含，或包含，或B B包含包含A A 補(bǔ)集補(bǔ)集 A A 由全集中不在由全集中不在A A的元素組成的元素組成 屬于屬于 x xA A元素元素x x在在A A中中 空集空集 集合中沒有元素集合中沒有元素集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 數(shù)據(jù)表示數(shù)據(jù)表示 用無符號整數(shù)表示全集為用無符號整數(shù)表示全集為32個元素整數(shù)集合：個元素整數(shù)集合： 1,2,3,4,., 31,32 集合變量集合變量unsign

33、ed A; 第第 i-1 位值等于位值等于1，表示元素，表示元素 i 在集合中在集合中 第第 i-1 位值等于位值等于0，表示元素，表示元素 i 不在集合不在集合中中 位序從低位位序從低位 高位高位 從從0 i-1集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 數(shù)據(jù)表示數(shù)據(jù)表示 unsigned A;集合集合二進(jìn)制位串值二進(jìn)制位串值十進(jìn)制值十進(jìn)制值 1, 3, 6 00100101 371, 2, 5, 7 01010011 101 2, 3, 5, 7, 8 11010110 214集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)unsigned A, B;/表示表示2個集合變量個集合變量unsigne

34、d x;/表示集合元素表示集合元素并集并集A AB BA|BA = 1, 2, 5 AB = 2, 5, 7 BAB= 1, 2, 5, 7 A|B = 0 0 0 1 0 0 1 10 1 0 1 0 0 1 00 1 0 1 0 0 1 1集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)交集交集ABA&BA = 1, 2, 5 AB = 2, 5, 7 BAB = 1, 2, 5, 7 A&B = 0 0 0 1 0 0 1 10 1 0 1 0 0 1 00 0 0 1 0 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;

35、/表示集合元素表示集合元素集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)差差A(yù)-BA-BA&(A&B)A = 1, 2, 5 A B = 2, 5, 7 B A- -B = 1 A&B 0 0 0 1 0 0 1 10 1 0 1 0 0 1 00 0 0 1 0 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)差差A(yù)-BA-BA&(A&B)A = 1, 2, 5 A B = 2, 5, 7 B A- -B = 1 A&am

36、p;B (A&B) 0 0 0 1 0 0 1 10 1 0 1 0 0 1 00 0 0 1 0 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素1 1 1 0 1 1 0 1集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)差差A(yù)-BA-BA&(A&B)A = 1, 2, 5 A B = 2, 5, 7 B A- -B = 1 A&B (A&B) A&(A&B) 0 0 0 1 0 0 1 10 1 0 1 0 0 1 00 0 0 1 0 0 1 0unsig

37、ned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素1 1 1 0 1 1 0 10 0 0 0 0 0 0 1集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)0 0 0 0 0 0 1 10 1 0 1 0 0 1 10 1 0 1 0 0 1 1unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素包含包含A BA BA|B=BA = 1, 2 A B = 1, 2, 5, 7 B A B 為真為真 A|B 集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)包含包含A BA BA|

38、B=BA = 1, 2 A B = 1, 2, 5, 7 B A B 為真為真 A|B A|B=B 等于等于 true0 0 0 0 0 0 1 10 1 0 1 0 0 1 10 1 0 1 0 0 1 1unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素A = 2, 4, 5, 7 A x = 3 1(x-1) 集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)0 1 0 1 1 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素屬于屬于x xA A1(x-1)

39、&A = 1(x-1)0 0 0 0 0 1 0 0A = 2, 4, 5, 7 A x = 3 1(x-1) 1(x-1)&A集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)0 1 0 1 1 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素屬于屬于x xA A1(x-1)&A = 1(x-1)0 0 0 0 0 1 0 00 0 0 0 0 0 0 0A = 2, 4, 5, 7 A x = 3 1(x-1) 1(x-1)&A 1(x-1)&A = 1(x-1) 等于等于 f

40、alse集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)0 1 0 1 1 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素屬于屬于x xA A1(x-1)&A = 1(x-1)0 0 0 0 0 1 0 00 0 0 0 0 0 0 0A = 2, 4, 5, 7 A A=0 等于等于 false集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)0 1 0 1 1 0 1 0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素空集空集A=A=0集合運(yùn)

41、算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn) 基本運(yùn)算實(shí)現(xiàn)基本運(yùn)算實(shí)現(xiàn)并集并集ABA|B交集交集ABA&B差差A(yù)-BA&(A&B)包含包含A BA|B=B補(bǔ)集補(bǔ)集AA屬于屬于xA1(x-1)&A = 1(x-1)空集空集A=A=0unsigned A, B;/表示表示2個集合變量個集合變量unsigned x;/表示集合元素表示集合元素/用無符號整數(shù)用無符號整數(shù) 表示表示132的的 整數(shù)集合整數(shù)集合/setH.h#includeusing namespace std;unsigned putX( unsigned &S, unsigned x ); /元素元素x并入集合并入集

42、合Svoid setPut( unsigned &S ); /輸入集合輸入集合S的元素的元素void setDisplay( unsigned S ); /輸出集合輸出集合S中的全部元素中的全部元素unsigned Com( unsigned A, unsigned B ); /求并集求并集A Bunsigned setInt( unsigned A, unsigned B ); /求交集求交集ABunsigned setDiff( unsigned A, unsigned B); /求差集求差集A-Bbool Inc(unsigned A, unsigned B); /判蘊(yùn)含判蘊(yùn)含b

43、ool In(unsigned S, unsigned x); /判屬于判屬于xSbool Null( unsigned S ); /判空集判空集【例例5-65-6】集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn)/steOperate.cpp#includesetH.h“void setPut(unsigned & S) /輸入集合元素輸入集合元素 unsigned x; cinx; while( x ) putX( S, x ); cinx; void setDisplay(unsigned S) /輸出集合輸出集合S中的全部元素中的全部元素 unsigned c; unsigned bitMask=

44、1; if( Null( S ) ) cout n“; return ; cout ; for( c=1; c=32; c+ ) if( S&bitMask ) coutc, “; bitMask=1; coutbb n; 【例例5-65-6】集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn)unsigned putX(unsigned &S, unsigned x) /元素元素x并入集合并入集合S unsigned bitMask=1; bitMask = x-1; S |= bitMask; return S;unsigned Com( unsigned A,unsigned B ) /求并集求

45、并集AB return A|B;unsigned setInt( unsigned A, unsigned B ) /求交集求交集AB return A&B;unsigned setDiff( unsigned A,unsigned B) /求差集求差集A-B return A&( ( A&B ) );【例例5-65-6】集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn)bool Inc(unsigned A,unsigned B) /判蘊(yùn)含判蘊(yùn)含 if( ( A | B ) = B ) return true; return false;bool In(unsigned S,unsigne

46、d x)/判屬于判屬于xS unsigned bitMask=1; bitMask = x-1; if( S & bitMask ) return true; return false;bool Null(unsigned S) /判空集判空集 if( S ) return true; return false;【例例5-65-6】集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn)/test.cpp#include setH.hint main() unsigned A=0, B=0; unsigned x; coutInput the elements of set A, 1-32, until inpu

47、t 0 :n; setPut( A ); coutInput the elements of set B, 1-32, until input 0 :n; setPut( B ); coutA = ; setDisplay( A ); coutB = ; setDisplay( B ); coutx; coutPut x in A = ; setDisplay( putX( A,x ) );【例例5-65-6】集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn)coutA+B = ; setDisplay( Com( A, B ) ); coutA*B = ; setDisplay( setInt( A, B ) )

48、; coutA-B = ; setDisplay( setDiff( A, B ) ); if( Inc( A, B ) ) cout A = Bn; else cout not A = Bn; cout x; if( In( A, x ) ) cout x in An; else cout x not in An;/test.cpp#include setH.hint main() unsigned A=0, B=0; unsigned x; coutInput the elements of set A, 1-32, until input 0 :n; setPut( A ); coutI

49、nput the elements of set B, 1-32, until input 0 :n; setPut( B ); coutA = ; setDisplay( A ); coutB = ; setDisplay( B ); coutx; coutPut x in A = ; setDisplay( putX( A,x ) );【例例5-65-6】集合運(yùn)算的實(shí)現(xiàn)集合運(yùn)算的實(shí)現(xiàn)coutA+B = ; setDisplay( Com( A, B ) ); coutA*B = ; setDisplay( setInt( A, B ) ); coutA-B = ; setDisplay(

50、setDiff( A, B ) ); if( Inc( A, B ) ) cout A = Bn; else cout not A = Bn; cout x; if( In( A, x ) ) cout x in An; else cout x not in An; 用長度用長度為為N，元素為無符號整數(shù)的數(shù)組表示集合，可以元素為無符號整數(shù)的數(shù)組表示集合，可以表示表示1, , 32*N整數(shù)集合整數(shù)集合 每個數(shù)組元素表示每個數(shù)組元素表示32個元素個元素段，長度段，長度N為為4的數(shù)組：的數(shù)組：S S3S2S1S0 當(dāng)當(dāng)x S，有，有:S(x-1)/32 的第的第 (x-1)%32 位位 等于等于 1

51、 例如：例如：85S S(85-1)/32 S2(85-1)%3220 得得 S2 00000000 00010000 00000000 00000000 1【例例5-75-7】 1,32 1,32* *N N 整數(shù)集合運(yùn)算的實(shí)現(xiàn)整數(shù)集合運(yùn)算的實(shí)現(xiàn)【例例5-75-7】 1,321,32* *N N 整數(shù)集合運(yùn)算的實(shí)現(xiàn)整數(shù)集合運(yùn)算的實(shí)現(xiàn)/setH.h#includeusing namespace std; const unsigned N=4;/數(shù)組長度數(shù)組長度typedef unsigned setTypeN;/用數(shù)組存放長度的集合用數(shù)組存放長度的集合void setPut( setType

52、S ); /輸入集合輸入集合S的元素的元素void setDisplay( const setType S ); /輸出集合輸出集合S中的全部元素中的全部元素void putX( setType S, unsigned x ); /元素元素x并入集合并入集合Svoid Com( setType C, const setType A, const setType B ); /求并集求并集C=ABvoid setInt(setType C,const setType A,const setType B ); /求交集求交集C=ABvoid setDiff(setType C,const setTy

53、pe A,const setType B); /求差集求差集C=A-Bbool Inc( const setType A, const setType B ); /判蘊(yùn)含判蘊(yùn)含bool In( const setType S, unsigned x ); /判屬于判屬于xSbool Null( const setType S ); /判空集，空集返回判空集，空集返回true/steOperate.cpp#includesetH.h void setPut( setType S) /輸入集合元素輸入集合元素 unsigned x ; cin x ; while( x ) putX( S, x )

54、 ; cin x ; void setDisplay( const setType S ) /輸出集合輸出集合S中的全部元素中的全部元素 unsigned c , i ; unsigned bitMask ; if( Null( S ) ) cout n“; return ; cout ; for( i=0; iN; i+ )/處理每個數(shù)組元素處理每個數(shù)組元素 bitMask = 1 ;/掩碼，掩碼，32位位 for( c=1; c=32; c+ )/按位處理按位處理 if( Si & bitMask ) cout i*32+c “, ” ; /輸出元素輸出元素 bitMask = 1

55、 ; cout x ; while( x ) putX( S, x ) ; cin x ; void setDisplay( const setType S ) /輸出集合輸出集合S中的全部元素中的全部元素 unsigned c , i ; unsigned bitMask ; if( Null( S ) ) cout n“; return ; cout ; for( i=0; iN; i+ )/處理每個數(shù)組元素處理每個數(shù)組元素 bitMask = 1 ;/掩碼，掩碼，32位位 for( c=1; c=32; c+ )/按位處理按位處理 if( Si & bitMask ) cout

56、i*32+c , ; /輸出元素輸出元素 bitMask = 1 ; cout bb n ;/刷除最后的逗號刷除最后的逗號按段測試按段測試元素值元素值/元素元素x并入集合并入集合Svoid putX( setType S, unsigned x ) unsigned bitMask = 1 ; bitMask = ( (x-1)%32 ) ; S(x-1)/32 |= bitMask ; /求并集求并集C=ABvoid Com( setType C, const setType A, const setType B ) for( int i=0; iN; i+ ) Ci = Ai | Bi ;

57、 /求交集求交集C=AB void setInt( setType C, const setType A, const setType B ) for( int i=0; iN; i+ ) Ci = Ai & Bi ;/求差集求差集C=A-B void setDiff( setType C, const setType A, const setType B ) for( int i=0; iN; i+ ) Ci = Ai & ( ( Ai & Bi ) ) ;元素在段中位置元素在段中位置元素段元素段bool Inc( const setType A, const set

58、Type B ) /判蘊(yùn)含判蘊(yùn)含 bool t = true ; for( int i=0; iN; i+) if( ( Ai | Bi ) != Bi ) t = false ; return t ; bool In( const setType S, unsigned x ) /判屬于判屬于xS unsigned bitMask = 1 ; bitMask = ( (x-1)%32 ) ; if ( S(x-1)/32 & bitMask ) return true; return false; bool Null( const setType S ) /判空集判空集 bool t

59、 = true ; for( int i=0; iN; i+) if( Si ) t = false ; return t ;/test.cpp#includesetH.hint main() setType A = 0 , B = 0 , C = 0 ; unsigned x; cout Input the elements of set A, 1-32*N , until input 0 :n ; setPut( A ); cout Input the elements of set B, 1-32*N , until input 0 :n ; setPut( B ); cout A =

60、; setDisplay( A ) ; cout B = ; setDisplay( B ); cout x ; putX( A, x); cout Put x in A = ; setDisplay( A ); cout C = A+B = ; Com( C, A, B ); setDisplay( C ); cout C = A*B = ; setInt( C, A, B ); setDisplay( C ); cout C = A-B = ; setDiff( C, A, B ); setDisplay( C ); if( Inc( A, B ) ) cout A = Bn ; else cout not A = Bn ; cout x ; if( In( A, x ) ) cout x in An ; else cout x not in An ; 結(jié)構(gòu)由數(shù)目固定的成員構(gòu)成結(jié)構(gòu)由數(shù)目固定的成員構(gòu)成 各成員可以具有不同的數(shù)據(jù)類型各成員可以具有不同的數(shù)據(jù)類型 一個結(jié)構(gòu)變量在內(nèi)存占有一片連續(xù)的存儲空間一個結(jié)構(gòu)變量在內(nèi)存占有一片連續(xù)的存儲空間5.3 5.3 結(jié)構(gòu)結(jié)構(gòu)結(jié)構(gòu)類型定義形式為：結(jié)構(gòu)類型定義形式為：struct 標(biāo)識符標(biāo)識符 類型類型 成員成員1 ; 類型類型 成員成員2 ; 類型類型 成