总所周知，C语言的数组是不可增加长度的，这就导致很多时候不能采取随机存储结构数组。这时很多人想到了链表，我们可以申请空间存放数据然后插入表中，确实可行，但是随机存储结构的优点可以在“O(1)”的时间内存就不存在了，得到的是一个可以很方便插入删除的链表。
但这时问题就来了，如果我并不需要频繁的做插入删除操作呢？链表的缺点是需要一个指针指向下一个节点，这浪费了很多的空间。
上图是顺序存储结构示意图，可以很容易得到，存放n个数据需要n*存放数据的数据类型的长度。比如int为一个字长，如果你是三十二位操作系统就是4个字节，六十四位就是8个字节。
上图可以很直观的看出，存放n个数据时它需要的空间是远远多于顺序存储结构的，相当于需要2倍的顺序存储结构需要的空间。
回归正题，可不可以实现动态的数组呢？答案是可以的。
#define init_list_length 26
#define num 10
struct arrayList{
char *element;
int length;
int maxLength;
};
typedef struct arrayList *List;
typedef struct arrayList Node;
需要一个结构体结构体，结构体中三个元素的作用分别是element相当于指向数组头节点的指针，数组的当前有效长度，和当前最大长度。详细说明一下什么是指向头节点的指针，对于c语言申请一个int类型的数组需要这样的语句int a[5];a就是指向头节点的指针，有些同学这时会有些疑问，不是数组吗怎么又变成指针了？你们可以尝试一下下面的代码。
int a[2]={2,3};
int *b;
b = a;
printf("%dn",*b);
printf("%dn",*(b+1));
运行结果是2，3(ps这里没考虑换行)。
解决了一个问题，但是还有一个问题，它怎么变成动态的了。话不多说关门，放代码。
void dilation(List list){//扩容
list->maxLength+=num;
realloc(list->element,list->maxLength);
}
每当你要插入或输入一个新的元素时，当前元素长度就加一了，length==maxLength就代表着已经到顶了，这时就要用上这个realloc语句。先将maxLength+=一个事先定义好的常数值，然后重新申请空间。realloc语句的好处是，会把原来的数据按序填入到新申请的数据空间中，这样就可以在保留原数据的基础上，进行了扩容的操作。
虽然这里没有实现JAVA中ArrayList的可以自由控制存储类型，但是要实现也不会太过复杂，根据不同的数据类型申请不同大小的空间就是了。JAVA中ArrayList见下图。
public static void main(String[] args) throws InvocationTargetException, IllegalAccessException {
ArrayList arrayList = new ArrayList<>();
ArrayList arrayList1 = new ArrayList<>();
}
交并补差的实现：
1.需求分析
- 集合的元素限定为小写字母字符(‘a’..’z’)，集合输入的形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符和非法字符。
- 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
- 程序执行的命令应包括：① 构造集合1；② 构造集合2；③ 求并集；④求补集；⑤求差集：⑥求交集。
- 测试数据为任意键盘上的输入。
例如feubvaufo2foHKUNEUWF52631应该滤去所有大写字母、数字和重复的元素，剩下feubvao。能正确的求出选择的操作如交并补差并正确的输出。
2. 程序结构流程图:
3.调用分析：
主函数调用menu菜单，菜单中判断输入是否合法，不合法会提示重新输入直到合法，检测输入的数字执行对应的操作。
选择有一到七七个整数。
输入一和二时会调用输入函数，可以往集合中输入元素，调用插入函数，每次输入一个元素判断合法性然后插入到顺序表的最后一位，插入函数调用扩容函数，若长度等于最大长度时，会新申请空间。二选项与一相同。如下图3.1、3.2。
当你输入三时，调用求并集的函数，传入三个集合，分别时集合一集合二集合三，通过对集合一和集合二求并集得到集合三，调用了定位函数，即使用遍历来判断集合中是否存在的函数。然后在调用插入函数，把重复元素剔除后插入表三。调用输出表中元素的函数，依次输出表中的元素。然后释放表三中的元素，做一次重新申请的操作。如下图3.3。
四到七调用的函数整体与三相同，不过多赘述。
图3.1
图3.2
图3.3
交并补差差别很大，但是对于代码来说，其实差别不大。比如交集和并集，前者是要新的集合保留求交集的集合的共同元素，并集是把俩个集合中的重复元素删除然后变成一个新的集合（ps集合的元素唯一性）。
而对于补集就是把全集中的求补集的集合（比如说A）中的元素删去得到了集合A的补集。差集也差不多，把A集合中的属于B集合的元素删去，或把B集合中属于A集合的元素删去。
讲来讲去，都是找重复、删除之类的操作，所以考虑到重用性，我们完全可以把这些写成函数，然后直接调用就完事了。
找重复元素的代码：
Status LocateEle(List list,Element element){//判断表中是否有重复元素
for(int i=0;ilength;i++){
if(list->element[i]==element){
return Ok;
}
}
return Error;
}
list是传入一个集合，element是传入一个自定义类型的元素（typedef char Element）。Ok与Error是宏定义#define，相当于JAVA中Boolean类型的True和False。找到了就返回Ok，没找到则返回Error。
删除的代码其实逻辑上是删除，代码操作上来说可以变成不插入这个元素。因为会创建一个新的集合来存放，不符合条件的直接不存放入这个集合就行了。
需要注意每次操作完，需要清空A和B经过操作得到的集合。对应的函数是freeC()，意为释放C集合。
void freeC(List c){
c->length = 0;
c->element = (Element *) malloc(sizeof (Element)*c->maxLength);
}
总代码：
#include "stdio.h"
#include "stdlib.h"
#define init_list_length 26
#define num 10
#define Ok 1
#define Error 0;
struct arrayList{
char *element;
int length;
int maxLength;
};
typedef int Status;
typedef struct arrayList *List;
typedef struct arrayList Node;
typedef char Element;
Status LocateEle(List list,Element element);//定位
void insertEle(List list,int n,Element element);//插入,n插入位置,ele插入元素
void dilation(List list);//扩容
void printArrayList(List list);//打印
void initArrayList(List list);//初始化
void freeArr(List list,List list1);//终止程序
void unionArr(List list,List list1,List list2);//并集
void complementArr(List list,List list2);//补集
void intersectionArr(List list,List list1,List list2);//交集
void differenceArr(List list,List list1,List list2);//差集
void inputEle(List list);//输入
void DeleteEle(List list,Element element);//删除指定元素
void DeleteEle1(List list,int n);//删除下标为n的元素
void DeleteEle(List list,Element element){//删除元素
for(int i=0;ilength;i++){
if(list->element[i]==element){
for(int j=i;jlength-1;j++){//全部前移一位
list->element[j] = list->element[j+1];
list->length--;//表长减一
}
break;
}
}
}
void freeC(List c){
c->length = 0;
c->element = (Element *) malloc(sizeof (Element)*c->maxLength);
}
void DestroyArr(List list){
if(list->length==0){
free(list->element);
}
}
void dilation(List list){//扩容
list->maxLength+=num;
realloc(list->element,list->length);
}
Status LocateEle(List list,Element element){//判断表中是否有重复元素
for(int i=0;ilength;i++){
if(list->element[i]==element){
return Ok;
}
}
return Error;
}
void insertEle(List list,int n,Element element){//插入的位置n,插入的元素element
if(n>list->length){//插入位置应该小于或等于当前长度，当插入位置等于当前长度时，即插入最后一个位置
}else if(n==list->length){//当插入最后一个的时候，长度加一
if(list->length==list->maxLength){
dilation(list);
}
list->element[n] = element;
list->length++;
}else{
list->element[n] = element;
}
}
void inputEle(List list){
Element c='0';
printf("请输入集合中的元素n");
for(int i=0;c!='n';){
c = getchar();
if(c>='a'&&c<='z'&&!LocateEle(list,c)){//LocateEle有该元素返回Ok无元素返回Error
insertEle(list,i,c);
i++;
}
}
}
void initArrayList(List list){//初始化
list->length = 0;
list->maxLength = init_list_length;
list->element = (Element *) malloc(sizeof (Element)*init_list_length);
}
void unionArr(List list,List list1,List list2){//求并集
printf("集合一：");
printArrayList(list);
printf("集合二：");
printArrayList(list1);
for(int i=0,j=0,k=0;j!=list1->length||i!=list->length;){
if(i!=list->length&&!LocateEle(list2,list->element[i])){//如果并集的中没有这个元素就插入这个元素
insertEle(list2,k++,list->element[i]);
}
if(j!=list1->length&&!LocateEle(list2,list1->element[j])){
insertEle(list2,k++,list1->element[j]);
}
if(i!=list->length){
i++;
}
if(j!=list1->length){
j++;
}
}
printf("集合一和集合二的并集是：");
printArrayList(list2);
freeC(list2);
}
void complementArr(List list,List list1){//求补集
char a='a';
for(int i=0,k=0;ilength;i++){
if(!LocateEle(list1,list->element[i])){
insertEle(list2,k++,list->element[i]);
}
}
printf("集合一：");
printArrayList(list);
printf("集合二：");
printArrayList(list1);
printf("集合一对集合二的差：");
printArrayList(list2);
freeC(list2);
}
void intersectionArr(List list,List list1,List list2){//求交集
for(int i=0,k=0;ilength;i++){
if(LocateEle(list1,list->element[i])){
insertEle(list2,k++,list->element[i]);
}
}
printf("集合一：");
printArrayList(list);
printf("集合二：");
printArrayList(list1);
printf("集合一和集合二的交集：");
printArrayList(list2);
freeC(list2);
}
void freeArr(List list,List list1){//?????
printf("欢迎再次使用。n");
free(list);
free(list1);
exit(0);
}
void printArrayList(List list){
for(int i=0;ilength;i++){
printf("%c ",list->element[i]);
}
printf("n");
}
int menu(){
char a,b[200];
printf("------输入对应编号选择操作------n");
printf("------1.初始化集合一------n");
printf("------2.初始化集合二------n");
printf("------3.求并集-----------n");
printf("------4.求补集-----------n");
printf("------5.求差集-----------n");
printf("------6.求交集-----------n");
printf("------7.退出-------------n");
while(1){
printf("请输入操作编号n");
scanf("%c",&a);
gets(b);
if(b[0]!=' '){
a = '8';
}
if(a>'0'&&a<='7') break;
printf("error!n");
}
return (int )(a-'0');
}
int main(){
int n,i=0;
List a,b,c;
a = (List) malloc(sizeof (Node));
b = (List) malloc(sizeof (Node));
c = (List) malloc(sizeof (Node));
initArrayList(a);
initArrayList(b);
initArrayList(c);
while(i<100){
n = menu();
switch (n) {
case 1:
inputEle(a);
printf("集合一：");
printArrayList(a);
break;
case 2:
inputEle(b);
printf("集合二：");
printArrayList(b);
break;
case 3:
unionArr(a,b,c);
break;
case 4:
complementArr(a,c);
complementArr(b,c);
break;
case 5:
differenceArr(a,b,c);
differenceArr(b,a,c);
break;
case 6:
intersectionArr(a,b,c);
break;
case 7:
freeArr(a,b);
break;
}
i++;
}
return 0;
}
