【数据结构 C语言】1.1.1顺序表（动态分配）

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

#define InitSize 5 // 初始化大小
#define AddSpace 5 // 容量不足时的自动增量大小

typedef int ElemType;

typedef struct
{
    int *elem;
    int length; // 当前长度
    int Maxsize; // 最大长度
}SqList_dynamic;


/*初始化线性表*/
int InitSqlist(SqList_dynamic *L)
{
    L->elem = (ElemType *) malloc(InitSize * sizeof(ElemType));
    L->length = 0;
    L->Maxsize = InitSize;

    return true;
}


/*销毁线性表*/
int DestroyList(SqList_dynamic *L)
{
    free(L->elem);
    L->length = 0;
    L->Maxsize = 0;

    return true;
}


/*尾插法*/
int TailInsert(SqList_dynamic *L, ElemType e)
{
    if(L->length == L->Maxsize)
    {
        ElemType *newSpace;
        newSpace = (ElemType *) realloc(L->elem, (L->Maxsize + AddSpace) * sizeof(ElemType));
        L->Maxsize += AddSpace;
    }

    ElemType *tail = &L->elem[L->length];
    *tail = e;
    L->length++;

    return 0;
}


/*头插法*/
int HeadInsert(SqList_dynamic *L, int e)
{
    if(L->length == L->Maxsize)
    {
        ElemType *newSpace = (ElemType *) realloc(L->elem, (L->Maxsize + AddSpace) * sizeof(ElemType));
        L->Maxsize += AddSpace;
    }

    ElemType *p = &L->elem[0];
    ElemType *q = &L->elem[L->length - 1];
    for(; q >= p; q--)
    {
        *(q + 1) = *q;
    }
    *p = e;
    L->length++;

    return true;
}


/*按位置插入*/
int Insert(SqList_dynamic *L, ElemType index, ElemType e)
{
    if(index > L->length)
    {
        printf("索引%d错误，未插入元素%d\n", index, e);

        return -1;
    }
        

    if(L->length == L->Maxsize)
    {
        ElemType *new;
        new = (ElemType *) realloc(L->elem, (AddSpace + L->Maxsize) * sizeof(ElemType));
        L->Maxsize += AddSpace;
    }

    ElemType *p = &L->elem[index - 1];
    ElemType *q = &L->elem[L->length - 1];
    for(; q >= p; q--)
    {
        *(q + 1) = *q;
    }
    *p = e;
    L->length++;

    return true;
}


/*展示线性表的元素*/
int ShowList(SqList_dynamic *L)
{
    if(L->length == 0)
        return -1;
    int i;
    for(i = 0; i < L->length; i++)
        printf("%d\t", L->elem[i]);
    printf("\n");   

    return 0;
}


/*返回表长*/
int getLength(SqList_dynamic *L)
{
    return L->length;
}


/*返回表容量*/
int getMaxsize(SqList_dynamic *L)
{
    return L->Maxsize;
}


/*程序主函数*/
int main()
{
    SqList_dynamic list1;

    InitSqlist(&list1);
    if(&list1){
        printf("list1初始化成功！\n");
    }

    int item = 11;
    while(item < 122)
    {
        TailInsert(&list1, item);
        printf("当前表长：%d， 最大容量：%d\n", getLength(&list1), getMaxsize(&list1));
        item += 11;
    }

    ShowList(&list1);
    /*------------------------*/
    printf("----------------------------\n");
    SqList_dynamic list2;

    InitSqlist(&list2);
    if(&list2)
    {
        printf("list2初始化成功！\n");
    }

    TailInsert(&list2, 888);
    TailInsert(&list2, 999);
    HeadInsert(&list2, 555);
    HeadInsert(&list2, 444);
    Insert(&list2, 3, 666);
    Insert(&list2, 4, 777);
    printf("当前表长：%d, 容量：%d\n", getLength(&list2), getMaxsize(&list2));
    Insert(&list2, 8, 1000);
    
    ShowList(&list2);

    getchar();
    return 0;
}