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

第5章集合與結(jié)構(gòu)

5.1位運(yùn)算

5.2集合

5.3結(jié)構(gòu)

5.4結(jié)構(gòu)數(shù)組

5.5鏈表

小結(jié)

5.1位運(yùn)算

計(jì)算機(jī)的存儲(chǔ)器采用二進(jìn)制表示數(shù)據(jù)

計(jì)算機(jī)系統(tǒng)的存儲(chǔ)器用每8位為1字節(jié)編址

不同類型的數(shù)據(jù)由不同字節(jié)長(zhǎng)度存儲(chǔ)

每一個(gè)數(shù)位的取值，只有兩個(gè)可能值：0或者1

位運(yùn)算能夠直接處理數(shù)據(jù)中每一位的值為方便起見(jiàn)，本節(jié)敘述中用一個(gè)字節(jié)表示一個(gè)正整數(shù)5.1位運(yùn)算位運(yùn)算符& 按位與 &= 按位與賦值

| 按位或 |= 按位或賦值^ 按位異或 ^= 按位異或賦值<< 左移 <<= 左移賦值>> 右移 >>= 右移賦值~ 按位取反1.按位與運(yùn)算左右操作數(shù)對(duì)應(yīng)的每一位分別做邏輯與運(yùn)算10 00001010&29 &000111018 00001000若有語(yǔ)句

cout<<"10&29="<<(10&29)<<endl;則顯示結(jié)果為

10&29=82.按位或運(yùn)算左右操作數(shù)對(duì)應(yīng)的每一位分別做邏輯或運(yùn)算10 00001010|29 |0001110131 00011111若有語(yǔ)句

cout<<"10|29="<<(10|29)<<endl;則顯示結(jié)果為

10|29=313.按位異或運(yùn)算當(dāng)左右操作數(shù)對(duì)應(yīng)位不相同，即當(dāng)且僅當(dāng)其中一個(gè)為1時(shí)，位操作的結(jié)果才為110 00001010^29 ^0001110123 00010111若有語(yǔ)句

cout<<"10|29="<<(10|29)<<endl;則顯示結(jié)果為

10^29=234.左移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向左移動(dòng)，騰空數(shù)位補(bǔ)010<<2 00001010<<240 00101000若有語(yǔ)句

cout<<"10<<2="<<(10<<2)<<endl;則顯示結(jié)果為

10<<2=40對(duì)于一個(gè)整數(shù)，每左移一位就相當(dāng)于乘以2（結(jié)果不溢出時(shí)）4.左移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向左移動(dòng)，騰空數(shù)位補(bǔ)0若有語(yǔ)句

cout<<"-10<<2="<<(-10<<2)<<endl;則顯示結(jié)果為

-10<<2=-40做算術(shù)左移時(shí)，只要不溢出，不會(huì)移動(dòng)符號(hào)位對(duì)于一個(gè)整數(shù)，每左移一位就相當(dāng)于乘以2（結(jié)果不溢出時(shí)）5.右移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向右移動(dòng)12>>2 00001100>>23 00000011若有語(yǔ)句

cout<<"12>>2="<<(12>>2)<<endl;則顯示結(jié)果為

12>>2=3對(duì)于一個(gè)整數(shù)，每右移一位就相當(dāng)于整除以25.右移按右操作數(shù)指定位數(shù)，將左操作數(shù)按位向右移動(dòng)若有語(yǔ)句

cout<<“-12>>2="<<(-12>>2)<<endl;則顯示結(jié)果為

-12>>2=-3對(duì)于一個(gè)整數(shù)，每右移一位就相當(dāng)于整除以2做算術(shù)右移時(shí)，不會(huì)移動(dòng)符號(hào)位6.按位取反單目運(yùn)算。對(duì)操作數(shù)按位做邏輯非~10 ~00001010-11 11110101若有語(yǔ)句

cout<<"~10="<<(~10)<<endl;則顯示結(jié)果為

~10=-11負(fù)數(shù)在計(jì)算機(jī)中用補(bǔ)碼表示。11110101是-11的補(bǔ)碼7.位運(yùn)算的復(fù)合賦值位運(yùn)算的5個(gè)復(fù)合賦值與其他復(fù)合賦值的操作形式一致例如，若有 inta,b;則 a&=b 等價(jià)于 a=a&b a|=b 等價(jià)于 a=a|b a^=b 等價(jià)于 a=a^b a<<=b 等價(jià)于 a=a<<b a>>=b 等價(jià)于 a=a>>b

當(dāng)一個(gè)整數(shù)的二進(jìn)制串中只有一個(gè)數(shù)位為1時(shí)，稱為掩碼

程序中通常借助掩碼對(duì)數(shù)據(jù)按位進(jìn)行測(cè)試掩碼01000000#include<iostream>usingnamespacestd;voidbitDisplay(unsignedvalue);voidmain(){unsignedx;cout<<"Enteranunsignedinteger:";cin>>x;bitDisplay(x); //調(diào)用函數(shù)，以二進(jìn)制形式輸出正整數(shù)}【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。0000110110000000valuebitMask0【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}0001101010000000value0bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}0011010010000000value0bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}0110100010000000value0bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}1101000010000000value1bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}1010000010000000value1bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}0100000010000000value0bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}1000000010000000value1bitMask【例5-1】按二進(jìn)制位串形式輸出正整數(shù)的值。voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31; //掩碼，最高位置1cout<<value<<'=';for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0'); //輸出value的最高位

value<<=1; //value左移1位

if(c%8==0)cout<<'';}cout<<endl;}【例5-2】位運(yùn)算測(cè)試#include<iostream>usingnamespacestd;voidbitDisplay(unsignedvalue);intmain(){unsignedn1,n2;n1=214;n2=5;cout<<n1<<"=\t";bitDisplay(n1);cout<<n2<<"=\t“;bitDisplay(n2);cout<<n1<<'&'<<n2<<"=\t"; bitDisplay(n1&n2);cout<<n1<<'|'<<n2<<"=\t";bitDisplay(n1|n2);cout<<n1<<'^'<<n2<<"=\t";bitDisplay(n1^n2);cout<<n1<<"<<"<<n2<<"=\t";bitDisplay(n1<<n2);cout<<n1<<">>"<<n2<<"=\t";bitDisplay(n1>>n2);cout<<'~'<<n1<<"=\t“;bitDisplay(~n1);}#include<iostream>usingnamespacestd;voidbitDisplay(unsignedvalue);intmain(){unsignedn1,n2;n1=214;n2=5;cout<<n1<<"=\t";bitDisplay(n1);cout<<n2<<"=\t“;bitDisplay(n2);cout<<n1<<'&'<<n2<<"=\t"; bitDisplay(n1&n2);cout<<n1<<'|'<<n2<<"=\t";bitDisplay(n1|n2);cout<<n1<<'^'<<n2<<"=\t";bitDisplay(n1^n2);cout<<n1<<"<<"<<n2<<"=\t";bitDisplay(n1<<n2);cout<<n1<<">>"<<n2<<"=\t";bitDisplay(n1>>n2);cout<<'~'<<n1<<"=\t“;bitDisplay(~n1);}【例5-2】位運(yùn)算測(cè)試voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31;for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0');value<<=1;if(c%8==0)cout<<'';

}cout<<endl;}#include<iostream>usingnamespacestd;voidbitDisplay(unsignedvalue);intmain(){unsignedn1,n2;n1=214;n2=5;cout<<n1<<"=\t";bitDisplay(n1);cout<<n2<<"=\t“;bitDisplay(n2);cout<<n1<<'&'<<n2<<"=\t"; bitDisplay(n1&n2);cout<<n1<<'|'<<n2<<"=\t";bitDisplay(n1|n2);cout<<n1<<'^'<<n2<<"=\t";bitDisplay(n1^n2);cout<<n1<<"<<"<<n2<<"=\t";bitDisplay(n1<<n2);cout<<n1<<">>"<<n2<<"=\t";bitDisplay(n1>>n2);cout<<'~'<<n1<<"=\t“;bitDisplay(~n1);}【例5-2】位運(yùn)算測(cè)試voidbitDisplay(unsignedvalue){unsignedc;unsignedbitMask=1<<31;for(c=1;c<=32;c++){cout<<(value&bitMask?'1':'0');value<<=1;if(c%8==0)cout<<'';

}cout<<endl;}#include<iostream>usingnamespacestd;voidmain(){inta=123,b=456;cout<<"a="<<a<<"\tb="<<b<<endl;a=a^b;cout<<"a=a^b\t"<<a<<endl;a=a^b;cout<<"a=a^b\t"<<a<<endl;}【例5-3】數(shù)據(jù)恢復(fù)#include<iostream>usingnamespacestd;voidmain(){inta=123,b=456;cout<<"a="<<a<<"\tb="<<b<<endl;a=a^b;b=a^b;a=a^b;cout<<"a="<<a<<"\tb="<<b<<endl;}【例5-4】整變量交換集合是不能精確定義的基本數(shù)學(xué)概念。一般認(rèn)為，當(dāng)一些事物是可以按照某種性質(zhì)（屬性）分辨，這種事物構(gòu)成的整體就稱為集合。

根據(jù)集合的屬性，可以斷定某個(gè)特定的事物是否屬于這個(gè)集合。如果屬于，就稱它為這個(gè)集合的元素。5.2集合集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B

由A和B中的全部元素組成E

AB集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B

由A和B中的公共的組成集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B 由A和B中的公共的組成

差

A-B

由屬于A但不屬于B的元素組成集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B 由A和B中的公共的組成

差

A-B 由屬于A但不屬于B的元素組成

包含

AB A中的每個(gè)元素都在B中，

稱為A被B包含，或B包含A集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B 由A和B中的公共的組成

差

A-B 由屬于A但不屬于B的元素組成

包含

AB A中的每個(gè)元素都在B中，

稱為A被B包含，或B包含A

補(bǔ)集

～A由全集中不在A的元素組成集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B 由A和B中的公共的組成

差

A-B 由屬于A但不屬于B的元素組成

包含

AB A中的每個(gè)元素都在B中，

稱為A被B包含，或B包含A

補(bǔ)集

～A由全集中不在A的元素組成

屬于

x∈A

元素x在A中集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B 由A和B中的公共的組成

差

A-B 由屬于A但不屬于B的元素組成

包含

AB A中的每個(gè)元素都在B中，

稱為A被B包含，或B包含A

補(bǔ)集

～A由全集中不在A的元素組成

屬于

x∈A 元素x在A中

空集

集合中沒(méi)有元素E

集合的基本運(yùn)算集合通常用大寫(xiě)字母標(biāo)記，集合元素用小寫(xiě)字母標(biāo)記

若A、B是全集E中的兩個(gè)集合，

x表示元素

集合主要運(yùn)算有：

并集

A∪B 由A和B中的全部元素組成

交集

A∩B 由A和B中的公共的組成

差

A-B 由屬于A但不屬于B的元素組成

包含

AB A中的每個(gè)元素都在B中，

稱為A被B包含，或B包含A

補(bǔ)集

～A由全集中不在A的元素組成

屬于

x∈A 元素x在A中

空集

集合中沒(méi)有元素集合運(yùn)算的實(shí)現(xiàn)

數(shù)據(jù)表示

用無(wú)符號(hào)整數(shù)表示全集為32個(gè)元素整數(shù)集合：

{1,2,3,4,......,31,32}

集合變量

unsignedA;

第i-1位值等于1，表示元素i在集合中第i-1位值等于0，表示元素i不在集合中

位序從低位高位

從0i-1集合運(yùn)算的實(shí)現(xiàn)

數(shù)據(jù)表示 unsignedA;集合

二進(jìn)制位串值

十進(jìn)制值{1,3,6} 00100101 37{1,2,5,7} 01010011 101{2,3,5,7,8} 11010110 214集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素并集

A∪B

A|B

A={1,2,5}

A

B={2,5,7}B

A∪B={1,2,5,7}A|B=000100110101001001010011集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)交集

A∩B A&B

A={1,2,5}A

B={2,5,7}B

A∩B={1,2,5,7}A&B=000100110101001000010010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)差

A-B A&(~(A&B))

A={1,2,5}

A

B={2,5,7}

B

A-B={1}A&B

000100110101001000010010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)差

A-B A&(~(A&B))

A={1,2,5}

A

B={2,5,7}

B

A-B={1}A&B

~(A&B)

000100110101001000010010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素11101101集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)差

A-B A&(~(A&B))

A={1,2,5}

A

B={2,5,7}

B

A-B={1}A&B

~(A&B)A&(~(A&B))

000100110101001000010010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素1110110100000001集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)000000110101001101010011unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素包含

AB A|B==B

A={1,2}

A

B={1,2,5,7}

B

A

B為真

A|B

集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)包含

AB A|B==B

A={1,2}

A

B={1,2,5,7}

B

A

B為真

A|B

A|B==B等于

true000000110101001101010011unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素A={2,4,5,7}

A

x=3

1<<(x-1)

集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)01011010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素屬于

x∈A

1<<(x-1)&A==1<<(x-1)

00000100A={2,4,5,7}

A

x=3

1<<(x-1)

1<<(x-1)&A集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)01011010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素屬于

x∈A

1<<(x-1)&A==1<<(x-1)

0000010000000000A={2,4,5,7}

A

x=3

1<<(x-1)

1<<(x-1)&A1<<(x-1)&A==1<<(x-1)等于

false集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)01011010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素屬于

x∈A

1<<(x-1)&A==1<<(x-1)

0000010000000000A={2,4,5,7}

A

A==0等于

false集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)01011010unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素空集

A==

A==0

集合運(yùn)算的實(shí)現(xiàn)

基本運(yùn)算實(shí)現(xiàn)并集

A∪B A|B

交集

A∩B A&B差

A-B A&(~A&B)包含

AB A|B==B補(bǔ)集

～A ~A屬于

x∈A 1<<(x-1)&A==1<<(x-1) 空集

A== A==0unsignedA,B; //表示2個(gè)集合變量unsignedx; //表示集合元素//用無(wú)符號(hào)整數(shù)表示｛1…32｝的整數(shù)集合//setH.h#include<iostream>usingnamespacestd;unsignedputX(unsigned&S,unsignedx);//元素x并入集合SvoidsetPut(unsigned&S); //輸入集合S的元素voidsetDisplay(unsignedS); //輸出集合S中的全部元素unsignedCom(unsignedA,unsignedB);//求并集A∪BunsignedsetInt(unsignedA,unsignedB);//求交集A∩Bunsigned

setDiff(unsignedA,unsignedB);//求差集A-BboolInc(unsignedA,unsignedB); //判蘊(yùn)含boolIn(unsignedS,unsignedx); //判屬于x∈SboolNull(unsignedS); //判空集【例5-5】集合運(yùn)算的實(shí)現(xiàn)//steOperate.cpp#include"setH.h“voidsetPut(unsigned&S) //輸入集合元素{unsignedx;cin>>x;while(x){putX(S,x);cin>>x;

}}voidsetDisplay(unsignedS) //輸出集合S中的全部元素{unsignedc;unsignedbitMask=1;if(Null(S)){cout<<"{}\n“;return;

}cout<<"{";for(c=1;c<=32;c++){if(S&bitMask)cout<<c<<",“;bitMask<<=1;

}cout<<"\b\b}\n";}【例5-5】集合運(yùn)算的實(shí)現(xiàn)unsignedputX(unsigned&S,unsignedx)//元素x并入集合S{unsignedbitMask=1;bitMask<<=x-1;S|=bitMask;returnS;}unsignedCom(unsignedA,unsignedB)//求并集A∪B{returnA|B;}unsignedsetInt(unsignedA,unsignedB) //求交集A∩B{returnA&B;}unsignedsetDiff(unsignedA,unsignedB)//求差集A-B{returnA&(~(A&B));}【例5-5】集合運(yùn)算的實(shí)現(xiàn)boolInc(unsignedA,unsignedB)//判蘊(yùn)含{if((A|B)==B)returntrue;returnfalse;}boolIn(unsignedS,unsignedx) //判屬于x∈S{unsignedbitMask=1;bitMask<<=x-1;if(S&bitMask)returntrue;returnfalse;}boolNull(unsignedS) //判空集{if(S)returntrue;returnfalse;}【例5-5】集合運(yùn)算的實(shí)現(xiàn)//test.cpp#include"setH.h"intmain(){unsignedA=0,B=0;unsignedx;cout<<"InputtheelementsofsetA,1-32,untilinput0:\n";setPut(A);cout<<"InputtheelementsofsetB,1-32,untilinput0:\n";setPut(B);cout<<"A=";setDisplay(A);cout<<"B=";setDisplay(B);cout<<"Inputx:";cin>>x;cout<<"Put"<<x<<"inA=";setDisplay(putX(A,x));【例5-5】集合運(yùn)算的實(shí)現(xiàn)cout<<"A+B=";setDisplay(Com(A,B));cout<<"A*B=";setDisplay(setInt(A,B));cout<<"A-B=";setDisplay(setDiff(A,B));if(Inc(A,B)) cout<<"A<=B\n";elsecout<<"notA<=B\n";cout<<"Inputx:";cin>>x;if(In(A,x)) cout<<x<<"inA\n";elsecout<<x<<"notinA\n";}//test.cpp#include"setH.h"intmain(){unsignedA=0,B=0;unsignedx;cout<<"InputtheelementsofsetA,1-32,untilinput0:\n";setPut(A);cout<<"InputtheelementsofsetB,1-32,untilinput0:\n";setPut(B);cout<<"A=";setDisplay(A);cout<<"B=";setDisplay(B);cout<<"Inputx:";cin>>x;cout<<"Put"<<x<<"inA=";setDisplay(putX(A,x));【例5-5】集合運(yùn)算的實(shí)現(xiàn)cout<<"A+B=";setDisplay(Com(A,B));cout<<"A*B=";setDisplay(setInt(A,B));cout<<"A-B=";setDisplay(setDiff(A,B));if(Inc(A,B)) cout<<"A<=B\n";elsecout<<"notA<=B\n";cout<<"Inputx:";cin>>x;if(In(A,x)) cout<<x<<"inA\n";elsecout<<x<<"notinA\n";}

用長(zhǎng)度為N，元素為無(wú)符號(hào)整數(shù)的數(shù)組表示集合，可以表示｛1,…,32*N｝整數(shù)集合

每個(gè)數(shù)組元素表示32個(gè)元素段，長(zhǎng)度N為4的數(shù)組：

SS[3]S[2]S[1]S[0]

當(dāng)x

∈S，有:

S[(x-1)/32]的第

(x-1)%32位等于1

例如： 85∈SS[(85-1)/32]S[2] (85-1)%3220

得S[2]00000000000100000000000000000000

1【例5-6】｛

1,…,32*N｝整數(shù)集合運(yùn)算的實(shí)現(xiàn)【例5-6】｛

1,…,32*N｝整數(shù)集合運(yùn)算的實(shí)現(xiàn)//setH.h#include<iostream>usingnamespacestd;

constunsignedN=4; //數(shù)組長(zhǎng)度typedefunsignedsetType[N]; //用數(shù)組存放長(zhǎng)度的集合voidsetPut(setTypeS); //輸入集合S的元素voidsetDisplay(constsetTypeS); //輸出集合S中的全部元素voidputX(setTypeS,unsignedx); //元素x并入集合SvoidCom(setTypeC,constsetTypeA,constsetTypeB); //求并集C=A∪BvoidsetInt(setTypeC,constsetTypeA,constsetTypeB); //求交集C=A∩BvoidsetDiff(setTypeC,constsetTypeA,constsetTypeB); //求差集C=A-BboolInc(constsetTypeA,constsetTypeB); //判蘊(yùn)含boolIn(constsetTypeS,unsignedx); //判屬于x∈SboolNull(constsetTypeS); //判空集，空集返回true//steOperate.cpp#include"setH.h"

voidsetPut(setTypeS) //輸入集合元素{unsignedx;cin>>x;while(x){putX(S,x); cin>>x;}}voidsetDisplay(constsetTypeS) //輸出集合S中的全部元素{unsignedc,i;unsignedbitMask;if(Null(S)){cout<<"{}\n“;return;}cout<<"{";for(i=0;i<N;i++) //處理每個(gè)數(shù)組元素{bitMask=1; //掩碼，32位for(c=1;c<=32;c++) //按位處理{if(S[i]&bitMask)cout<<i*32+c<<“,”;//輸出元素bitMask<<=1;}}cout<<"\b\b}\n"; //刷除最后的逗號(hào)}//steOperate.cpp#include"setH.h"

voidsetPut(setTypeS) //輸入集合元素{unsignedx;cin>>x;while(x){putX(S,x); cin>>x;}}voidsetDisplay(constsetTypeS) //輸出集合S中的全部元素{unsignedc,i;unsignedbitMask;if(Null(S)){cout<<"{}\n“;return;}cout<<"{";for(i=0;i<N;i++) //處理每個(gè)數(shù)組元素{bitMask=1; //掩碼，32位for(c=1;c<=32;c++) //按位處理{if(S[i]&bitMask)cout<<i*32+c<<",";//輸出元素bitMask<<=1;}}cout<<"\b\b}\n"; //刷除最后的逗號(hào)}按段測(cè)試元素值//元素x并入集合SvoidputX(setTypeS,unsignedx) {unsignedbitMask=1;bitMask<<=((x-1)%32);S[(x-1)/32]|=bitMask;}

//求并集C=A∪BvoidCom(setTypeC,constsetTypeA,constsetTypeB) {for(inti=0;i<N;i++)C[i]=A[i]|B[i];}

//求交集C=A∩B

voidsetInt(setTypeC,constsetTypeA,constsetTypeB) {for(inti=0;i<N;i++)C[i]=A[i]&B[i];}//求差集C=A-B

voidsetDiff(setTypeC,constsetTypeA,constsetTypeB) {for(inti=0;i<N;i++)C[i]=A[i]&(~(A[i]&B[i]));}元素在段中位置元素段boolInc(constsetTypeA,constsetTypeB) //判蘊(yùn)含{boolt=true;for(inti=0;i<N;i++){if((A[i]|B[i])!=B[i])t=false;}returnt;}

boolIn(constsetTypeS,unsignedx) //判屬于x∈S{unsignedbitMask=1;bitMask<<=((x-1)%32);if(S[(x-1)/32]&bitMask)returntrue;returnfalse;}

boolNull(constsetTypeS) //判空集{boolt=true;for(inti=0;i<N;i++){if(S[i])t=false;}returnt;}//test.cpp#include"setH.h"intmain(){setTypeA={0},B={0},C={0};unsignedx;cout<<"InputtheelementsofsetA,1-"<<32*N<<",untilinput0:\n";setPut(A);cout<<"InputtheelementsofsetB,1-"<<32*N<<",untilinput0:\n";setPut(B);cout<<"A=";setDisplay(A);cout<<"B=";setDisplay(B);cout<<"Inputx:";cin>>x;putX(A,x);cout<<"Put"<<x<<"inA=";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<=B\n";elsecout<<"notA<=B\n";cout<<"Inputx:";cin>>x;if(In(A,x)) cout<<x<<"inA\n";elsecout<<x<<"notinA\n";}

結(jié)構(gòu)由數(shù)目固定的成員構(gòu)成各成員可以具有不同的數(shù)據(jù)類型一個(gè)結(jié)構(gòu)變量在內(nèi)存占有一片連續(xù)的存儲(chǔ)空間5.3結(jié)構(gòu)結(jié)構(gòu)類型定義形式為：

struct

標(biāo)識(shí)符

{類型成員1;

類型成員2; …

類型成員n; };5.3.1定義結(jié)構(gòu)例：structemployee

{charname[10];longcode;doublesalary;charaddress[50];charphone[20];};類型名5.3.1定義結(jié)構(gòu)例：structemployee

{charname[10];longcode;doublesalary;charaddress[50];charphone[20];};

可以用不同方法定義一個(gè)結(jié)構(gòu)變量(1)聲明類型之后聲明變量employeeworker1,worker2,*Emp

;5.3.1定義結(jié)構(gòu)例：structemployee

{charname[10];longcode;doublesalary;charaddress[50];charphone[20];};

可以用不同方法定義一個(gè)結(jié)構(gòu)變量(1)聲明類型之后聲明變量worker1,worker2,*Emp

;(2)聲明類型的同時(shí)聲明變量5.3.1定義結(jié)構(gòu)例：structemployee

{charname[10];longcode;doublesalary;charaddress[50];charphone[20];};

可以用不同方法定義一個(gè)結(jié)構(gòu)變量(1)聲明類型之后聲明變量worker1,worker2,*Emp

;(2)聲明類型的同時(shí)聲明變量(3)直接聲明結(jié)構(gòu)類型變量注意此時(shí)沒(méi)有了結(jié)構(gòu)類型標(biāo)識(shí)符5.3.1定義結(jié)構(gòu)例：structemployee

{charname[10];longcode;doublesalary;charaddress[50];charphone[20];};employeeworker1,worker2, *Emp=&worker1;

說(shuō)明(1)結(jié)構(gòu)變量占有一片連續(xù)內(nèi)存空間，具有結(jié)構(gòu)類型的特征WangLi9910834561200.5guangzhou87111111worker1Emp5.3.1定義結(jié)構(gòu)

說(shuō)明(2)一個(gè)結(jié)構(gòu)類型的成員

可以是另一個(gè)已定義的結(jié)構(gòu)類型structdate{intmonth;intday;intyear;};structemployee{charname[10];

date

birthday

;longcode;doublesalary;charaddress[50];charphone[11];}worker1,worker2;例如:

為職工結(jié)構(gòu)添加出生日期信息類型和變量聲明為:personson

;5.3.1定義結(jié)構(gòu)

說(shuō)明(2)一個(gè)結(jié)構(gòu)類型的成員

可以是另一個(gè)已定義的結(jié)構(gòu)類型structperson{charname[10];longcode;doublesalary;charaddress[50];charphone[11];

}worker1,worker2;錯(cuò)誤不能實(shí)現(xiàn)的無(wú)窮遞歸結(jié)構(gòu)5.3.1定義結(jié)構(gòu)

說(shuō)明(3)聲明結(jié)構(gòu)類型變量可以同時(shí)初始化structemployee{charname[10];longcode;doublesalary;charaddress[50];charphone[11];}worker={"WangLi",991083456,1200.5,"guangzhou","87111111"

};（1）訪問(wèn)結(jié)構(gòu)變量的成員

結(jié)構(gòu)變量

.成員點(diǎn)運(yùn)算符//例5-7#include<iostream>usingnamespacestd;structweather //聲明結(jié)構(gòu)類型{doubletemp;doublewind;};intmain(){weathertoday; //聲明結(jié)構(gòu)類型變量

today.temp=10.5; //對(duì)結(jié)構(gòu)變量成員賦值

today.wind=3.1;cout<<“Temp=”<<today.temp<<endl; //按成員輸出

cout<<“Wind=”<<today.wind<<endl;}訪問(wèn)結(jié)構(gòu)變量成員5.1.2訪問(wèn)結(jié)構(gòu)5.3.2訪問(wèn)結(jié)構(gòu)（2）用指針訪問(wèn)結(jié)構(gòu)變量的成員

結(jié)構(gòu)指針

->成員

(*結(jié)構(gòu)指針

)

.成員//例5-8#include<iostream>usingnamespacestd;#include<cstring>structperson{charname[20];unsignedlongid;doublesalary;};intmain(){personpr1;

person*pp;

//定義結(jié)構(gòu)指針

pp=&pr1;

//取結(jié)構(gòu)變量地址

strcpy(pp->name,“DavidMarat”); //對(duì)結(jié)構(gòu)成員賦值

pp->id=987654321;

pp->salary=335.0;cout<<pp->name<<‘\t’<<pp->id<<‘\t’<<pp->salary<<endl;}person*pp;pp=&pr1;pp->namepp->idpp->salary5.1.2訪問(wèn)結(jié)構(gòu)5.3.2訪問(wèn)結(jié)構(gòu)（2）用指針訪問(wèn)結(jié)構(gòu)變量的成員

結(jié)構(gòu)指針

->成員

(*結(jié)構(gòu)指針

)

.成員//例5-8#include<iostream>usingnamespacestd;#include<cstring>structperson{charname[20];unsignedlongid;doublesalary;};intmain(){personpr1;person*pp; //定義結(jié)構(gòu)指針

pp=&pr1; //取結(jié)構(gòu)變量地址

strcpy(pp->name,“DavidMarat”); //對(duì)結(jié)構(gòu)成員賦值

pp->id=987654321;

pp->salary=335.0;cout<<pp->name<<‘\t’<<pp->id<<‘\t’<<pp->salary<<endl;}(*pp).name(*pp).id

(*pp).salary5.1.2訪問(wèn)結(jié)構(gòu)5.3.2訪問(wèn)結(jié)構(gòu)//例5-9#include<iostream>usingnamespacestd;structweather {doubletemp;doublewind;}yesterday;intmain(){weathertoday; yesterday.temp=10.5; yesterday.wind=3.1;

today=yesterday; //結(jié)構(gòu)變量整體賦值

cout<<“Temp=”<<today.temp<<endl;cout<<“Wind=”<<today.wind<<endl;}（3）類型相同的結(jié)構(gòu)變量可以整體賦值5.1.2訪問(wèn)結(jié)構(gòu)5.3.2訪問(wèn)結(jié)構(gòu)（3）類型相同的結(jié)構(gòu)變量可以整體賦值例如：

structweather1

{doubletemp;doublewind;}yesterday; structweather2

{doubletemp;doublewind;}today;“類型相同的變量”是指用同一類型標(biāo)識(shí)符說(shuō)明的變量yesterday和today盡管成員相同，但不是同類型變量不可以整體賦值5.1.2訪問(wèn)結(jié)構(gòu)5.3.2訪問(wèn)結(jié)構(gòu)5.2結(jié)構(gòu)數(shù)組例如

structS_type {inta;doublex;}; S_typeS_ary[10];S_ary是一個(gè)有10個(gè)元素的數(shù)組，元素類型是S_type。數(shù)組的每一個(gè)元素包含兩個(gè)數(shù)據(jù)成員。

S_ary[0].aS_ary[0].x S_ary[1].aS_ary[1].x …… S_ary[9].aS_ary[9].x5.2結(jié)構(gòu)數(shù)組5.4結(jié)構(gòu)數(shù)組

數(shù)組的元素類型為結(jié)構(gòu)類型時(shí)，稱為結(jié)構(gòu)數(shù)組。#include<iostream>usingnamespacestd;structperson //結(jié)構(gòu)定義{charname[10];unsignedintid;doublesalary;};personallone[6]; //結(jié)構(gòu)數(shù)組聲明intmain(){inti;persontemp; //結(jié)構(gòu)變量聲明

for(i=0;i<6;i++) //輸入數(shù)據(jù)

{cout<<i<<":name:";cgets(allone[i].name);cout<<"id:";cin>>allone[i].id;cout<<"salary:";cin>>allone[i].salary;cout<<endl;};cout<<"Sort:\n";for(i=1;i<6;i++) //以成員salary作關(guān)鍵字排序{for(intj=0;j<=5-i;j++){if(allone[j].salary>allone[j+1].salary)//結(jié)構(gòu)變量的整體交換

{temp=allone[j];allone[j]=allone[j+1];allone[j+1]=temp;}}}for(i=0;i<6;i++) //輸出排序后數(shù)據(jù)

cout<<allone[i].name<<'\t'<<allone[i].id<<'\t'<<allone[i].salary<<endl;}例5-10對(duì)結(jié)構(gòu)數(shù)組以某一成員作關(guān)鍵字排序5.2結(jié)構(gòu)數(shù)組#include<iostream>usingnamespacestd;structperson //結(jié)構(gòu)定義{charname[10];unsignedintid;doublesalary;};personallone[6];