线性表的顺序表示和实现（参考严蔚敏版）

#include<stdio.h>        //输入输出头文件
#include<stdlib.h>            //malloc和free都在这个头文件里
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT    10//线性表存储空间的分配增量
#define TRUE        1
#define FALSE        0
#define OK            1
#define ERROR        0
#define INFEASIBLE    -1
#define OVERFLOW    -2
typedef int Status;//函数类型，其值是函数结果状态代码
typedef int ElemType;
#define maxList        10
ElemType* q;
ElemType* p;
ElemType* pa;
ElemType* pb;
ElemType* pc;
ElemType* pa_last;
ElemType* pb_last;
int i;
/******************元素类型*******************/
typedef struct {
    ElemType* elem;//存储空间基址，L.elem[5]为第六位的地址
    int length;        //当前长度
    int listsize;    //当前分配的存储容量（以sizeof（ElemType）为单位）
}SqList;

Status  InitList_Sq(SqList& L)
{
    //构建一个空的线性表L
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));//给L分配一个地址
    if (!L.elem)exit(OVERFLOW);        //exit函数是退出应用程序，并将应用程序的一个状态返回给OS
                                    //此句表示，如果分配失败，退出程序，返回值为OVERFLOW（-2）
    L.length = 0;                    //初始化长度为0
    L.listsize = LIST_INIT_SIZE;    //初始存储容量
    return OK;//返回1
}

/***********插入**************/
Status ListInsert_Sq(SqList& L, int i, ElemType e)
{
    ElemType* newbase;
    //在顺序表L中插入第i个位置之前插入新的元素e
    //i的合法性  0<i<ListLength.Sq(L)+1 //ListLength.Sq(表长)
    if (i<1 || i>L.length + 1)
        return ERROR;//i不合法

    /*当前存储空间已满，增加分配*/
    if (L.length >= L.listsize)
    {
        newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        /*先释放原来L.elem所指内存区域，并重新分配大小为(L.listsize+LISTINCREMENT)*sizeof(ElemType)
        同时将原有数据从头到尾拷贝到新分配的内存区域，并返回该内存区域的首地址。*/

        if (!newbase)exit(OVERFLOW);    //此句表示，如果分配失败，退出程序，返回值为OVERFLOW（-2）
        L.elem = newbase;                //新基址
        L.listsize += LISTINCREMENT;    //增加存储容量
    }
    q = &(L.elem[i - 1]);                    //q为插入位置
    for (p = &(L.elem[L.length - 1]); p >= q; --p)
        *(p + 1) = *p;                    //插入位置及向后的元素右移
    *q = e;            //插入e
    ++L.length;        //表长+1
    return OK;

}

/**************************删除第i个元素********************************/
Status ListDelete_Sq(SqList& L, int i, ElemType& e)
{
    //在顺序表中删除第i个元素，并用e返回其值
    //i的合法性，0<i<L.ListLength.Sq(L)
    if ((i < 1) || (i > L.length))
        return ERROR;
    p = &(L.elem[i - 1]);            //p取地址为被删除的i元素的位置
    e = *p;                        //被删除的元素值赋给e
    q = L.elem + L.length - 1;    //表尾元素的位置
    for (++p; p <= q; ++p)        //被删除元素之后的元素左移
        *(p - 1) = *p;
    --L.length;                    //表长 -1
    return OK;

}

/*************************在顺序表中查询是否存在和e相同的元素**********************/
int locateElem_Sq(SqList L, ElemType e)
{
    
    //若找到，则返回其在L中的位序，否则返回0
    i = 1;                //i的初值为第1个元素的位序
    p = L.elem;            //p的初值为第1个元素的存储位置
    while (i <= L.length && *p++!=e)
        i++;
    if (i <= L.length)
        return i;
    else
        return 0;
}

void PrintList_sq(SqList L)//输出顺序表中的元素
{
    int i;
    for (i = 0; i <L.length; i++)
        printf("%d ",L.elem[i]);
            printf("\n");
}

void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)
{
    //已知顺序表La和Lb的元素按值非递减排列
    //归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列
    pa = La.elem;
    pb = Lb.elem;
    Lc.listsize = Lc.length = La.length + Lb.length;//Lc的表长为La+Lb
    pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));//给pc分配空间
    if (!Lc.elem)
        exit(OVERFLOW);//存储分配失败
    pa_last = La.elem + La.length - 1;//最后一个元素的位置
    pb_last = Lb.elem + Lb.length - 1;
    while (pa <= pa_last && pb <= pb_last)//当pa和pb没有超出相应的表时
    {
        //归并
        //*pa指针存储值
        //&pa指针地址
        if (*pa <= *pb)            //当pa<=pb时，pc赋给pa并且两个指针+1 
            *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }
    //当表的长度不一样时，插入剩余的部分
    while (pa <= pa_last)
        *pc++ = *pa++;            //插入La的剩余元素
    while (pb <= pb_last)
        *pc++ = *pb++;            //插入Lb的剩余元素

}

int main()
{
    int options;
    SqList p;
    SqList q;
    int n;
    int e;
    int a[maxList];
    InitList_Sq(p);//初始化顺序表
    printf("请输入你要创建的元素个数：\n");
    scanf("%d", &n);//不能超过maxList

    for (int i = 1; i <= n; i++)
    {
        printf("请输入第%d个元素值\n", i);
        scanf("%d", &a[i]);
        ListInsert_Sq(p, i, a[i]);
    }
    PrintList_sq(p);
    int status1 = 1;
    while (status1)
    {
        printf("请输入你要进行的操作：1、插入；2、删除；3、查询；4、退出\n");
        scanf("%d", &options);
        switch (options)
        {
        case 1:
            //{
            printf("请输入你要存放的位置\n");
            scanf("%d", &i);
            printf("请输入你要插入的元素值\n");
            scanf("%d", &e);
            ListInsert_Sq(p, i, e);
            PrintList_sq(p);
            //}
            break;
        case 2:
            printf("请输入你要删除的位置\n");
            scanf("%d", &i);
            ListDelete_Sq(p, i, e);
            printf("删除%d成功\n", e);
            PrintList_sq(p);
            break;
        case 3:
            printf("请输入你要查询的值\n");
            scanf("%d", &e);
            i = locateElem_Sq(p, e);
            if (i != 0)
                printf("此值的位置为：%d\n", i);
            else
                printf("没有此值\n");
            PrintList_sq(p);
            break;
        case 4:
            exit(0);
        default:printf("\t错误\n"); exit(0);
            PrintList_sq(p); 
            break;
        }

    }
    printf("%d\n",p.length);
    return 0;
}