线性顺序表：

指的是用一组地址连续的存储单元依次存储线性表中的数据元素。就根数组一样的道理，只不过我们这里可以用结构体或类来定义一个动态的数组，使其存储空间可以随我们的需要而改变，不会造成空间的浪费。
所以我们这里有两种存储结构，各有优点：
1.动态分配顺序存储结构：

//线性表的动态分配顺序存储结构
typedef int ElemType;//顺序表的数据元素类型
typedef struct{
     ElemType  *elem;//存储空间的基地址
     int lenth;//当前的表长，即元素个数
     int listsize;//我们所分配的该表的存储空间
}SqList;

2.数组形式
其实在一般在做竞赛题时，我经常使用的还是数组形式的顺序表，会更方便。

typedef struct{
      ElemType  data[MAX];//存储数据元素的数组
      int length;//当前的元素个数
  }SqList;    

对应的一些基本函数实现就可以看出它们各自的优点：

先看动态分配存储结构的一些函数

1.创建并初始化一个顺序表
就是一个结构变量的初始化问题，
初始化时表中没有元素，故length=0;

//创建并初始化线性表
int InitList_Sq(SqList *L){
    (*L).elem=(int*)malloc(IN*sizeof(int));
    if(!(*L).elem)printf("error\n"); //空间分配失败
    (*L).length=0;     //表长为0
    (*L).listsize=MAX;       //初始存储容量
    return 0;
}

初始化了结构体变量，然后需要对其进行赋值，或者后面可能需要在原始的表中插入新的元素。在插入新的元素过程中，如果说存储空间已经满了，那么就需要重新分配存储空间，以达到扩容的目的。

//插入元素
int ListInsert_Sq(SqList *L,int i,int e){
    int *newbase;
    int *p,*q;
    if(i<1||i>(*L).length)return 0;    //i值不合法
    if((*L).length>=(*L).listsize){//存储空间已满，增加分配
        newbase=(int*)realloc((*L).elem,((*L).listsize+10)*sizeof(int));
        (*L).elem=newbase;//新基址
        (*L).listsize+=10;         //增加存储容量
    }
    q=&(*L).elem[i-1];//插入元素的位置
    p=&(*L).elem[(*L).length-1];
    for(;q<=p;p--){
    	*(p+1)=*p;
	}
    *q=e;              //插入
    (*L).length++;        //表长+1
    return 1;
}

3.删除元素

//删除元素
int ListDelete_Sq(SqList *L,int i,int *e){
    //删除表中第i个元素，并用e返回其值
    int j;
    int *p,*q;
    if(i<1||i>(*L).length)return 0;//i值不合法
    p=&(*L).elem[i-1];       //p为被删除的位置
    *e=*p;                   //赋值给e
    q=(*L).elem+(*L).length-1;//表尾部元素位置
    while(p<=q){           //元素后移
        *p=*(p+1);
        ++p;
    }
    (*L).length--;   //表长-1
    return 1;
}

对于顺序表的赋值构造过成有两种办法：
要么就是不断的调用插入函数；要么就是普通的遍历赋值

void CreateList_Sq(SqList *L,int n){
    printf("输入%d个元素：",n);
    int i=0;
    for(;i<n;i++){
        scanf("%d",&(*L).elem[i]);
    }
    printf("\n");
    (*L).length=n;
}

5.合并两个表
将两个表合并为一个表就是将不在表La中的元素，而在另一个表Lb中的元素插入表La中；
这里就需要判断表Lb中的某个元素是否在表La中,所以在对Lb遍历的函数内，得到一个Lb中的某个元素，再遍历表La,看此元素是否再La中。

int LocateElem(SqList L,int e,int k){
      int i;
      for(i=0;i<L.length;i++){
            if(*(L.elem)==e)return 1; 
     }
     return 0;
}
void union(SqList &La,SqList Lb){
     //将所有在表Lb中但不在La中的元素插入到La中
     int i;
     int e;
     for(i=0;i<Lb.length;i++){
          GetElem(Lb,i,e);//取表Lb中第i各数据元素赋值给e
          if(!LocateElem(La,e,k)){
               ListInsert(La,La.length+1,e);
          }
      }
  }        

1.将两个表合并成同一个表：
对于两个元素按值非递减顺序排列的线性表，合并的方式更为简单。

//取某位置的元素
void GetElem(SqList L,int i,int &e){
	e=*(L.elem+i);
} 
//合并两个线性表为一个线性表
void MargsList_Sq1(SqList La,SqList Lb,SqList *Lc){
    //已经知道线性表元素按值非递减顺序排列
    //归并La和Lb得到新的顺序表Lc的元素也是按值非递减排列的
    InitList_Sq(Lc);
    int i=1,j=1;int k=0;
    int ai,bj;
    while(i<=La.length&&j<=Lb.length){
    	//La和Lb均非空
		GetElem(La,i,ai);
		GetElem(Lb,j,bj);
		if(ai<bj){
			ListInsert_Sq(Lc,k,ai);i++;k++;
		} 
		else{
			ListInsert_Sq(Lc,k,bj);j++;k++;
		}
	}
	//La和Lb中有一个已经遍历完了
	while(i<=La.length){
		GetElem(La,i,ai);
		ListInsert_Sq(Lc,k,ai);
		i++;k++;
	} 
	while(j<=Lb.length){
		GetElem(Lb,j,bj);
		ListInsert_Sq(Lc,k,bj);
		j++;k++;
	} 
}

主函数：

//基本函数实现
int main(){
     SqList L;
    int e;
    int i,a;
    if(InitList_Sq(&L)==0)printf("初始化成功！！！\n");
    CreateList_Sq(&L,10);
    printf("输出所有元素：");
    ListTraverse_Sq(L);
    printf("输出表长:%d\n",L.length);
    printf("查找元素a");
    scanf("%d",&a);
    printf("元素%d在表中的位置是：%d\n",a,LocateElem_Sq(L,a));
    printf("在表中第4个位置出入%d\n",a+1);
    ListInsert_Sq(&L,4,a+1);

    printf("输出操作后的表：\n");
    ListTraverse_Sq(L);
    printf("删除表中第3个位置的元素：\n");
    ListDelete_Sq(&L,3,&e);
    printf("输出删除的表：\n");
    ListTraverse_Sq(L);
    return  0;
}    

  //两个表的合并
  int main( {
    SqList La,Lb,Lc;
    int e;
    int i,a;
    InitList_Sq(&La);
    InitList_Sq(&Lb);
    InitList_Sq(&Lc);
    CreateList_Sq(&La,5);
    CreateList_Sq(&Lb,5);
    printf("输出所有元素：");
    ListTraverse_Sq(La);
    ListTraverse_Sq(Lb);
    printf("输出表长:La=%d\tLb=%d\tLc=%d\n",La.length,Lb.length,Lc.length);
    MargsList_Sq(La,Lb,&Lc);
    printf("\n");
     printf("输出表长:La=%d\tLb=%d\tLc=%d\n",La.length,Lb.length,Lc.length);
    MargsList_Sq(La,Lb,&Lc);
    printf("输出表长:La=%d\tLb=%d\tLc=%d\n",La.length,Lb.length,Lc.length);
    printf("输出操作后的表：\n");
    ListTraverse_Sq(Lc); 
    return 0;
}

数组

要考试了，今天暂且写到这里，考试完了再补上