线性表-顺序存储结构

/** 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表内的数据元素
 *
 *  数据长度    -> 存放线性表的存储空间的长度，不可变
 *  线性表的长度 -> 线性表中数据元素的个数，随着线性表的插入和删除操作，可变
 *
 *  优点：1.无须为元素之间的逻辑关系而增加额外的存储空间
 *       2.可以快速的读取表中任一位置的元素
 *
 *  缺点：1.插入和删除操作需要移动大量元素
 *       2.当线性表长度变化较大时， 难以确定存储空间的k容量
 *       3.造成存储空间的‘碎片’，浪费了内存
 */

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

#define MAXSIZE 20
typedef int  ElemType;

typedef struct {
    ElemType *data;
    int length;
    int maxSize;
} SqlList;


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;

/** 初始化*/
int InitList(SqlList *L) {
    L->data = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    if (L->data == NULL) {
        return -1;
    }
    L->length = 0;
    L->maxSize = MAXSIZE;
    return 0;
}


/** 指定位置插入*/
Status ListInsert(SqlList *L, int i, ElemType e) {
    int k;
    if (L->length >= L->maxSize) {
        return ERROR;
    }
    if (i <1 || i > L->length+1) {
        return ERROR;
    }
    if (i <= L->length) {
        for (k = L->length-1; k>=i-1; k--) {
            L->data[k+1] = L->data[k];
        }
    }
    L->data[i-1] = e;
    L->length++;
    return OK;
}

/** 尾插法*/
void insert_last_list(SqlList *list, ElemType e) {
    if (list->length >= list->maxSize) {
        return;
    }
    list->data[list->length] = e;
    list->length++;
}


/** 头插法*/
Status insert_header(SqlList *list, ElemType e) {
    if (list->length >= list->maxSize) {
        printf("溢出了");
        return ERROR;
    }
    for (int i = (list->length); i >=0 ; i--) {
        list->data[i+1] = list->data[i];
    }
    list->data[0] = e;
    list->length++;
    return OK;
}

/** 删除指定元素，并且返回被删除的元素*/
Status List_Delete(SqlList *L,int i, ElemType *e) {
    int k;
    if (L->length == 0) {
        return ERROR;
    }
    
    if (i < 1 || i > L->length) {
        return ERROR;
    }
    *e = L->data[i-1];
    for (k = i-1; k < L->length; k++) {
            L->data[k] = L->data[k+1];
    }
    L->length--;
    return OK;
}

/** 当内存空间不够时，再次开辟空间*/
void again_malloc(SqlList *list) {
    ElemType *p = realloc(list->data, 2 * list->maxSize);
    if (!p) {
        printf("存储空间用完");
        return;
    }
    list->data = p;
}

/** 遍历输出当前顺序表*/
void iteratorData(SqlList *list) {
    for (int i =0; i < list->length; i++) {
        printf("current %d is %d",i,list->data[i]);
    }
}

/** 清空*/
void clear_list(SqlList *list) {
    if (list->data > 0) {
        list->length = 0;
    }
}

void destropy_list(SqlList *list) {
    
    if (list->data != NULL) {
        free(list->data);
        list->length = 0;
    }
}

#pragma mark - 调用
void k_printfData(void) {
    
    int a[10] = {2,4,6,8,10,12,14,16,18,20};
    SqlList q1;
    InitList(&q1);
    
    //顺序插入数据
    for (int i = 0; i < sizeof(a)/sizeof(int); i++) {
        insert_last_list(&q1, a[i]);
    }
    //遍历数据
    iteratorData(&q1);
    
    //在指定位置插入数据
    int result = ListInsert(&q1, 3, 9);
    if (result == OK) {
        printf("插入成功了\n");
    } else {
        printf("插入失败\n");
    }
    iteratorData(&q1);
    
    //在头部插入数据
    insert_header(&q1, 25);
    
    //删除指定元素
    ElemType deleteEle;
    List_Delete(&q1, 5, &deleteEle);
    printf("被删除的元素是 %d\n",deleteEle);
    
    iteratorData(&q1);
}