/** 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表内的数据元素
*
* 数据长度 -> 存放线性表的存储空间的长度，不可变
* 线性表的长度 -> 线性表中数据元素的个数，随着线性表的插入和删除操作，可变
*
* 优点：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);
}
