#include <stdio.h>
#include <stdlib.h> //malloc函数会用到此头文件
#define MAX 30;//顺序表元素个数最大为30
//函数声明
void initlist(Sqlist* L); //初始化顺序表
void createlist(Sqlist* L); //创建顺序表
void printlist(Sqlist* L); //打印顺序表
void insertlist(Sqlist* L, int pos, Elemtype e); //插入操作
void deletlist(Sqlist* L, int pos, Elemtype e); //删除操作
typedef int Elemtype; //将Elemtype定义为int类型
//顺序表的定义
typedef struct{
Elemtype* elem; //顺序表的元素
int length; //顺序表的长度
}Sqlist; //将Sqlist定义为结构体类型，里面定义了顺序表元素和顺序表的长度两个成员
//初始化顺序表
void initlist(Sqlist* L)
{
L->elem = (Elemtype*)malloc(sizeof(Elemtype)*MAX);//sizeof(Elemtype)算每个元素大小再*MAX就是整个顺序表的大小，(Elemtype *)表示开辟空间来存什么类型的数
L->length = 0; //将顺序表的长度设为0，因为是空表
}
//总结初始化顺序表：
//1.给顺序表分配空间
//2.将表长设为0
//用户输入数据创建顺序表
void createlist(Sqlist* L)
{
int i,n;
printf("请输入存放的元素个数：");
scanf("%d",&n);
printf("请输入一组数字存到顺序表中：");
for(i = 0;i < n; i++)
{
scanf("%d",&L->elem[i]); //将输入直接存放到顺序表中
L->length++; //每放一个元素，表长+1
}
}
//总结创建顺序表：
//1.用户输入顺序表的元素个数
//2.用户依次输入顺序表的元素，存入顺序表中
//3.表长+1
//打印顺序表
void printlist(Sqlist* L)
{
int i;
for(i = 0; i < L->length; i++)
{
printf("%d ",L->elem[i]);
}
}
//按值查找
void searchlist(Sqlist* L, Elemtype e)
{
int i;
for(i = 0; i < L->length; i++)
{
if(L->elem[i] == e)
{
printf("找到了，下标是%d", i);
}
}
}//插入元素
void insertlist(Sqlist* L, int pos, Elemtype e)//在第pos位置插入元素e，pos是元素的下标
{
int len = L->length; //将表长(也就是元素个数)用变量len表示，方便后续书写
int i;
if((pos>=0) && (pos < len)) //判断插入位置是否合法，必须插入存放着有元素的下标的位置
{
if(len < MAX) //判断顺序表元素个数是否已满最大值，已经满了就不能插入元素了
{
for(i = len-1; i >= pos; i--)
{
L->elem[i+1] = L->elem[i] //将前一个元素放入后一个下标位置中
}
L->elem[pos] = e; //将要插入的元素插入第pos位置
L->length++; //增加元素后，表长+1
}
}
}
//总结插入元素：
//1.判断插入位置是否合法
//2.判断表是否已占满
//3.从最后一个元素开始，每次将一个元素向后移动一个位置(其本质是复制元素的值)
//4.将新元素插入指定位置
//5.表长+1//删除元素
void deletlist(Sqlist* L, int pos, Elemtype e)
{
int len = L->length;
int i;
if((pos >= 0) && (pos < len))
{
for(i = pos+1; i < len; i++)
{
//将后一个元素放入前一个下标位置中
L->elem[i-1] = L->elem[i]; //这句第一次写的时候错了，记住是第i个赋值给i-1个
}
L->length--; //删除元素后，表长-1
}
}
//总结删除元素：
//1.判断删除位置是否合法
//2.从删除指定元素的位置+1开始，将后面的元素每次向前移动一个位置(其本质是复制元素的值)
//3.表长-1//销毁顺序表
void destorylist(Sqlist* L)
{
if(L->elem) //顺序表中存在元素才能销毁
{
free(L->elem); //将空间释放
L->elem = NULL; //释放后一定要置为空指针
}
L->length = 0; //表长设为0
}新表中可以有重复的数字
依次取出表A中的一个元素和表B的一个元素比较，哪个元素值小，则将这个元素放到表C的表尾
//将A、B表合并为新表C
void Union(Sqlist A, Sqlist B, Sqlist& C)
{
//新表C的表长就是A表+B表的表长
C.length = A.length + B.length;
//给表C分配内存空间
C.elem = (int*)malloc(C.length);
//pa、pb、pc分别指向对应的表的第一个元素
int* pa = A.elem;
int* pb = B.elem;
int* pc = C.elem;
//lasta、lastb分别指向对应的表的最后一个元素
int* lasta = A.elem + (A.length - 1);
int* lastb = B.elem + (B.length - 1);
//判断是否到了表尾，到了表尾退出循环
while (pa <= lasta && pb <= lastb)
{
//A表的元素小于B表的元素，就将A表的元素插入新表里
if (*pa < *pb)
{
//将A表的元素赋值给新表
*pc = *pa;
//pa指向下一个元素
pa++;
//pc指向下一个元素
pc++;
//增加元素后，C表长+1
C.length++;
}
else
{
//将B表的元素赋值给新表
*pc = *pb;
//pb指向下一个元素
pb++;
//pc指向下一个元素
pc++;
//增加元素后，C表长+1
C.length++;
}
}
//A表到了表尾，就将B表剩余元素给C表
if (pa = lasta)
{
while (pb <= lastb)
{
//将B表的元素赋值给新表
*pc = *pb;
//pb指向下一个元素
pb++;
//pc指向下一个元素
pc++;
//增加元素后，C表长+1
C.length++;
}
}
//B表到了表尾，就将A表剩余元素给C表
else
{
while (pa <= lasta)
{
//将A表的元素赋值给新表
*pc = *pa;
//pa指向下一个元素
pa++;
//pc指向下一个元素
pc++;
//增加元素后，C表长+1
C.length++;
}
}
}