C++ 第5章集合与结构

本文主要是介绍C++ 第5章集合与结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

5.1 位运算

运算符	说明
&	按位与
I	按位或
^	按位异或
<<	左移
>>	右移
~	按位取反
&=	按位与赋值
I=	按位或赋值
^=	接位异或赋值
<<=	按位左称赋值
>>=	按位右称赋值

5.2 集合

5.2.1 集合的基本运算
集合通常用大写字母标记，集合元素用小写字母标记。若A，B是全集E中的两个集合。x表示元素，则集合最主要的运算有:

运算	说明
并集 A∪B	由A和B中的全部元素组成
交集 A∩B	由A和B中的公共元素组成
差 A-B	由属于A但不属于B的元素组成
包含 A⊆B	A中的每个元素都在B中，称为A被B包含，或B包含A
补集 ~A	由全集中不在A的元素组成
属于x∈A	元素x在A中
空集Φ	集合中没有元素

集相关符号：
∪ 　并
　∩　交
　⊂ 　A属于B
　⊃ 　A包括B
　∈　 a∈A,a是A的元素
　⊆　 A⊆B,A不大于B
　⊇　 A⊇B,A不小于B
　Φ　空集
　R　实数
　N　自然数
　Z　整数
　Z+　正整数
　Z-　负整数

5.2.1 集合运算的实现
1.集合的数据表示
一个元符号整数有32位，可以表示32个元素的集合。二进制位串从低位到高位(从右向左)表示2^0~2^31,对应位序为0~31.
unsigned A;
要用A表示集合{1, 3, 6}，此时A二进制位串的情况是：
00000000 00000000 00000000 00100101

2.集合基本运算的实现
当用无符号整数表示集合的时候，位运算可以实现各种基本运算。
unsigned A,B; //表示两个集合
unsigned x; // 表示集合元素
用C++位运算实现集合运算

集合运算	对应位运算
并集 A∪B	A\|B
交集 A∩B	A&B
差A-B	A&(~(A&B))
包含 A⊆B	A\|B == B
补集~A	~A
属于x∈A	1<<(x-1)&A == 1<<(x-1)
空集Φ	A==0

用无符号整数和位运算实现集合的基本运算

//setH.h
#include <iostream>
using namespace std;void setPut( unsigned &S ); //输入集合S中的元素
void setDisplay( unsigned S); //输出集合S中的全部元素
unsigned putX( unsigned &S, unsigned x ); //元素x并入集合S中
unsigned Com( unsigned A, unsigned B); //求并集
unsigned setInt( unsigned A, unsigned B); //求交集
unsigned setDif( unsigned A, unsigned B); //求差集
bool Inc( unsigned A, unsigned B); //判蕴含
bool In( unsigned S, unsigned x); //判属于
bool Null( unsigned S); //判空//setOperate.cpp
#include "setH.h"
//输入集合S中的元素
void setPut( unsigned &S )
{unsigned x;cin >>x;while( x ){putX(S, x); cin >>x;}
}//输出集合S中的全部元素
void setDisplay( unsigned S)
{unsigned c;unsigned bitMask = 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";return;
}//元素x并入集合S中
unsigned putX( unsigned &S, unsigned x )
{unsigned bitMask = 1;bitMask <<= x-1;S|=bitMask;return S;
}//求并集
unsigned Com( unsigned A, unsigned B)
{return A|B;
}//求交集
unsigned setInt( unsigned A, unsigned B)
{return A&B;
}//求差集
unsigned setDif( unsigned A, unsigned B)
{return A&(~(A&B));
}//判蕴含,A⊆ B true, 
bool Inc( unsigned A, unsigned B)
{if( (A|B) == B) return true;return false;
}//判属于
bool In( unsigned S, unsigned x)
{unsigned bitMask = 1;bitMask <<= x-1;if( S&bitMask) return true;return false;
}//判空
bool Null( unsigned S)
{if(S) return false;return true;
}//test.cpp#include "setH.h"int main()
{unsigned A=0, B=0;unsigned x;cout <<"Input the elements of set A, 1~32, until input 0:\n";setPut(A);cout <<"Input the elements of set B, 1~32, until input 0:\n";setPut(B);cout<<"A = ";setDisplay(A);cout<<"B = ";setDisplay(B);cout <<"input x:";cin >> x;cout <<"Put "<<x<<" in A = ";setDisplay(putX(A, x));cout <<"A+B =";setDisplay(Com(A, B));cout <<"A*B =";setDisplay(setInt(A, B));cout <<"A-B =";setDisplay(setDif(A, B));if(Inc(A, B))cout<<"A <= B\n";elsecout <<"not A <= B\bn";cout<<"Input x:";cin >> x;if(In(A, x))cout <<x<<" in A\n";elsecout <<x<<"not in A\n";
}

用数组和位运算实现集合的基本运算

5.3 结构

5.3.1 定义结构
定义结构类型的说明形式为：
struct 标识符
{
类型成员1；
类型成员2；
…
类型成员n；
};
如
struct Employee
{
char name[10];
long code;
double salary;
char *address;
char phone[20];
};

struct Date
{
int month;
int day;
int year;
};

5.3.2 访问结构
结构变量名.成员

*（指针）.成员
或
指针->成员

5.3.3 结构参数
5.3.4 结构数组

5.5 链表

1.动态链表存储
new 和 delete操作可以随时生成、撤销数据元素。
单向链表的数据元素是一个结构：
struct Node
{
datatype data;
Node *next;
};
next是指向自身结构类型的指针；
data成员的类型datatype可以是任意C++允许的数据类型，但不能是自身的结构类型。
strcut Node
{
char name[20];
double salary;
Node *next;
};

2.建立和遍历链表
struct Node
{
int data;
Node *next;
};
Node *head, *p;
建立链表的过程可以描述为:
生成头结点；
while(未结束)
{
生成新结点；
把新结点插入链表；
}
//建立单向链表:

struct Node
{int data;Node *next;
};
void CreateList(Node * &head) //引用参数是表头指针
{Node *s, *p;s = new Node;cin>>s->data;while(s->data != 0){if(head == NULL)head = s;elsep->next = s;p = s;s = new Node;cin >>s->data;}p->next = NULL;delete s;return;
}//遍历链表
void ShowList(Node *head)
{cout <<"now the items of node are:\n";while(head){cout<<head->data<<'\t';head = head->next;}cout<<endl;
}int main()
{Node *head = NULL;CreateList(head);ShowList(head);
}

3.插入结点
链表便于实现插入和删除结点的动态操作，关键是正确修改结点的指针。

#include <iostream>
using namespace std;struct List
{int data;List *next;
};//把数据插入有序链表
void insert(List * &head, int num)
{List *s, *p, *q;s = new List;s->data = num;s->next = NULL;if(head == NULL) //若表为空，则建立一个结点的链表{head = s;return;}if(head->data > s->data) //被插入数据最小，插入表头{s->next = head;head = s;return;}for(q=head, p=head->next; p; q=p, p=p->next) //搜索插入{if(p->data > s->data){s->next = p;q->next = s;return;}}q->next = s; //被插入数据最大，插入表尾return;
}//输出链表数据
void ShowList(const List *head)
{cout<<"now the items of list are:\n";while(head){cout<<head->data<<'\t';head=head->next;}cout <<endl;
}int main()
{int k;List *head = NULL;cin >>k;while(k!=0){insert(head, k);cin>>k;}ShowList(head);
}

4.删除结点
删除结点也要根据结点的位置作不同处理，还要注意释放被删结点

void del(List *&head, int key)
{List *p;if(!head) //被删结点为空{cout<<"List null!\n";return;}if(head->data == key){p = head;head = head->nxet;delete p;p = NULL;cout <<key<<"the head of list have been deleted.\n";return;}   for(List *pg = head; pg->next; pg=pg->next) //查找并删除结点{if(pg->next->data == key){p = pg->next;pg->next = p->next;delete p;p = NULL;cout<<key<<"have been deleted.\n";return;}   cout<<"there is not key:"<<key<<endl; //链表中不存在key的值return;}   
}