线性表的顺序表示和实现-----两个集合的并集（无序，有序），线性表的就地逆置，两个线性表的比较大小，插入元素(O(1))， A 表中 删去既在 B 表中出现又在 C 表中出现的元素，

线性表的顺序表示和实现

①集合A=AUB，无序的；

②A,B两个顺序表递增有序，执行C=AUB,算法时间复杂度要求为 O(n+m)(A,B这两个顺序表只允许遍历一次)；

③//实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,...,an)逆置为(an,...,a1)；

④//设A=(a1,...,an)和B=(b1,...,bn)均为顺序表。试写一个比较 A，B 大小的算法,依次比较 A,B 元素的值,如果一样则继续比较,如果不一样则比较完成。；

⑤//设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以 保持该表的有序性；

⑥已知 A，B 和 C 为三个递增有序的顺序表，现要求对 A 表作如下操作：
删去那些既在 B 表中出现又在 C 表中出现的元素。
试对顺序表编写实现上述操作的算法，并分析你的算法的 时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 

头文件

#pragma once//防止头文件被重复引用
//动态不定长顺序表#define INIT_SIZE 10//顺序表的初始化大小typedef struct SqList
{int *elem;//指向动态内存创建的内存，用于存储数据int length;//存放有效数据个数int listsize;//存放顺序表的总大小
}Sqlist,* PSqList;//PSqList为结构体类型指针//初始化线性表
void InitSqlist(PSqList ps);//在ps的pos位置处插入数据val
bool Insert(PSqList ps,int pos,int val);//在ps中查找第一个key值,找到返回下标,失败返回-1
int Search(PSqList ps,int key);//删除ps中的第一个key值
bool DeleteVal(PSqList ps,int key);//删除ps中pos位置的值
bool DeletePosVal(PSqList ps,int pos);//获取ps中pos位置的值
int GetElel(PSqList ps,int pos);//将ps中pos位置的值设为newpos
bool SetElem(PSqList ps,int pos,int newval);//获取有效数据个数
int GetLentgh(PSqList ps);//判断ps是否为空
bool IsEmpty(PSqList ps);//输出ps
void Show(PSqList ps);//清空ps
void Clear(PSqList ps);//销毁ps
void Destory(PSqList ps);

函数说明以及实现与顺序线性表的实现：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"SeqList.h"//引用本项目头文件//初始化线性表
void InitSqlist(PSqList ps)
{assert(ps != NULL);if(ps == NULL){printf("Init Error\n");return;}//-> 自带 *ps->elem = (int*)malloc(sizeof(int)*INIT_SIZE);//存放整型元素ps->length = 0;//初始化长度为0ps->listsize = INIT_SIZE;
}//扩容，将总容量扩大为原来的2倍
static void Inc(PSqList ps)
{assert(ps != NULL);if(ps == NULL){return;}ps->elem = (int*)realloc(ps->elem,sizeof(int)*INIT_SIZE*2);//realloc会把原来数据copy过来ps->listsize *= 2;
}//判断ps是否已满,内部函数,不对外
static bool IsFull(PSqList ps)
{assert(ps != NULL);if(ps == NULL){return false;}return ps->length == ps->listsize;//已满
}//在ps的pos位置处插入数据val
//插入的数据必须在顺序表的最左边,且连续
bool Insert(PSqList ps,int pos,int val)//O(n)
{assert(ps != NULL);assert(ps != NULL);if(ps == NULL  || pos < 0 || pos > ps->length){return false;}if(IsFull(ps)){Inc(ps);//如果满了，就扩容}for(int i = ps->length - 1;i >= pos;i--){ps->elem[i+1] = ps->elem[i];}ps->elem[pos] = val;ps->length++;return true;
}//在ps中查找第一个key值,找到返回下标,失败返回-1
int Search(PSqList ps,int key)
{assert(ps != NULL);if(ps == NULL){return false;}int flag = -1;for(int i=0;i < ps->length;i++){if(ps->elem[i] == key){flag = i;  //找到了break;}		}return flag;
}//删除ps中的第一个key值
bool DeleteVal(PSqList ps,int key)
{assert(ps != NULL);if(ps == NULL){return false;}int index = Search(ps,key);return DeletePosVal(ps,index);
}//删除ps中pos位置的值
bool DeletePosVal(PSqList ps,int pos)
{assert(ps != NULL);if(ps == NULL || pos > ps->length && pos < 0){return false;}for(int i = pos;i + 1 < ps->length;i++)//将后面的数据往前移{ps->elem[i]=ps->elem[i+1];}ps->length --;return true;
}//获取ps中pos位置的值
int GetElel(PSqList ps,int pos)
{assert(ps != NULL );if(ps == NULL && pos > ps->length && pos < 0 ){return -1;}return ps->elem[pos];
}//将ps中pos位置的值设为newpos
bool SetElem(PSqList ps,int pos,int newval)
{assert(ps != NULL );if(ps == NULL && pos > ps->length && pos < 0 ){return false;}ps->elem[pos] = newval;return true;
}//获取有效数据个数
int GetLentgh(PSqList ps)
{assert(ps != NULL );if(ps == NULL){return 0;}return ps->length;
}//判断ps是否为空
bool IsEmpty(PSqList ps)
{assert(ps != NULL );if(ps == NULL){return false;}return ps->length == 0;
}//输出ps
void Show(PSqList ps)
{assert(ps != NULL );if(ps == NULL && ps->length < 0){return ;}for(int i = 0;i < ps->length;i++){printf("%d ",ps->elem[i]);}printf("\n");
}//清除数据
void  Clear(PSqList ps)
{assert(ps != NULL );if(ps == NULL){return ;}ps->length = 0;
}//销毁ps,回收内存
void Destory(PSqList ps)
{assert(ps != NULL );if(ps == NULL){return ;}free(ps->elem);ps->elem = NULL;ps->length = 0;ps->listsize = 0;
}

主函数（所有函数都已经测试过）：

#include<stdio.h>
#include"SeqList.h"//集合A=AUB，无序的
void Union_unsort(PSqList pA,PSqList pB)
{int value_a = 0;int Lenght_A = GetLentgh(pA);int Lenght_B = GetLentgh(pB);for(int i = 0;i < Lenght_B;i++){value_a = GetElel(pB,i);if(-1 == Search(pA,value_a)){Insert(pA,Lenght_A,value_a);}}printf("\n");
}//A,B两个顺序表递增有序，执行C=AUB,算法时间复杂度要求为 O(n+m)(A,B这两个顺序表只允许遍历一次)
void Union_Merge_sort(PSqList pA,PSqList pB,PSqList pC)
{int value_a = 0,value_b = 0;int Lenght_A = GetLentgh(pA);int Lenght_B = GetLentgh(pB);int i = 0,j = 0,k = 0;while (i < Lenght_A && j < Lenght_B){value_a = GetElel(pA,i);value_b = GetElel(pB,j);if(value_a < value_b){Insert(pC,k,value_a);i++;}else  if(value_a == value_b){Insert(pC,k,value_a);i++;j++;}else{Insert(pC,k,value_b);j++;}k++;}//一个顺序表长度>另一个顺序表长度while (i < Lenght_A){value_a = GetElel(pA,i);Insert(pC,k,value_a);i++,k++;}while (j < Lenght_B){value_b = GetElel(pB,j);Insert(pC,k,value_b);j++,k++;}
}void Swap_Int(int *a,int *b)
{int tmp = 0;tmp = *a;*a = *b;*b = tmp;
}//实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,...,an)逆置为(an,...,a1)。 
void Inversion(PSqList pA)
{int tmp = 0;int length_A = GetLentgh(pA);for(int i = 0,j = length_A - 1;i < length_A / 2;i++,j--){Swap_Int(&pA->elem[i],&pA->elem[j]);}	
}int Min_Int(int a,int b)
{return a < b ? a : b;
}//设A=(a1,...,an)和B=(b1,...,bn)均为顺序表。试写一个比较 A，B 大小的算法,依次比较 A,B 元素的值,如果一样则继续比较,如果不一样则比较完成。 
int Compare(PSqList pA,PSqList pB)
{int Lenght_A=GetLentgh(pA);int Lenght_B=GetLentgh(pB);for(int i = 0;i < Min_Int(Lenght_A,Lenght_B);i++){if(GetElel(pA,i) != GetElel(pB,i)){		return GetElel(pA,i) - GetElel(pB,i);//不相等返回较大的顺序表}}return Lenght_A - Lenght_B;//==0表示相等，大于0A大，反之B大
}//设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 
int  Insert_Merge_SList(PSqList pA,int x)
{int i = 0;for(i = GetLentgh(pA) - 1;i >= 0;i--){if(x >= GetElel(pA,i)){break;}}return Insert(pA,i + 1,x);
}/*
已知 A，B 和 C 为三个递增有序的顺序表，现要求对 A 表作如下操作：
删去那些既在 B 表中出现又在 C 表中出现的元素。
试对顺序表编写实现上述操作的算法，并分析你的算法的 时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 
*/
void List_A_sub_BC(PSqList pA,PSqList pB,PSqList pC)//O(n)
{int value_a = 0,value_b = 0,value_c = 0;int i = 0,j = 0,k = 0;//分别为顺序表ABC的下标while (i < GetLentgh(pA) && j < GetLentgh(pB) && k < GetLentgh(pC)){value_a = GetElel(pA,i);value_b = GetElel(pB,j);value_c = GetElel(pC,k);if( value_a == value_b && value_a == value_c ){DeletePosVal(pA,i);}else if(value_b < value_a ){j++;}else if(value_c < value_a ){k++;}else{i++;}}printf("\n");
}int main()
{SqList pA,pB,pC;InitSqlist(&pA);InitSqlist(&pB);InitSqlist(&pC);Insert(&pA,0,1);Insert(&pA,1,2);Insert(&pA,2,3);Insert(&pA,3,5);Insert(&pA,4,7);Insert(&pA,5,9);Insert(&pA,6,10);Insert(&pA,7,11);Insert(&pA,8,19);Insert(&pA,9,29);Insert(&pB,0,1);Insert(&pB,1,3);Insert(&pB,2,4);Insert(&pB,3,6);Insert(&pB,4,8);Insert(&pC,0,1);Insert(&pC,1,3);Insert(&pC,2,5);Insert(&pC,3,6);Insert(&pC,4,8);Insert(&pC,5,9);printf("A集合:");Show(&pA);printf("B集合:");Show(&pB);printf("C集合:");Show(&pC);Destory(&pA);Destory(&pB);Destory(&pC);return 0;
}