实验1-1 顺序表的基本操作

任务描述
定义SqList类型，实现顺序表的基本操作。基本操作的定义参照教材抽象数据类型ADT List的定义。
设顺序表的初始存储空间的容量LIST_INIT_SIZE是10，当顺序表的存储空间已满，扩容时的增量LISTINCREMENT是2。

相关知识
线性表的类型定义
线性表的逻辑结构
线性表的顺序存储结构
编程要求
根据提示，在右侧编辑器补充代码，实现线性表的基本操作。注意以下两点：
（1）void CreateList(SqList*)函数从键盘（测试集）读入线性表中数据元素个数n（n>=0），再依次读入n个数据元素。若读入的n是负值，则视为读入0；
（2）void ListTraverse(SqList)函数的输出格式是用一对花括号{  }将数据元素括起来，数据元素间隔一个空格。例如：对有8个整数的线性表(3, 2, 1, 5, 7, 6, 8, 9)，其输出格式是{ 3 2 1 5 7 6 8 9 }。

测试说明
平台会对你编写的代码进行测试：
关注void ListTraverse(SqList)函数的输出格式，见上述编程要求中的注意事项，花括号与数据元素也间隔一个空格。

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2
typedef int ElemType;
typedef struct 
{
    ElemType* elem;
    int length;
    int listsize;
} SqList;

Status InitList(SqList* L) 
{
    L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L->elem)
	{
		return OVERFLOW;  // 存储分配失败
	} 
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

void DestroyList(SqList* L) 
{
    if (L->elem) 
	{
        free(L->elem);
        L->elem = NULL;
    }
    L->length = 0;
    L->listsize = 0;
}

void ClearList(SqList* L) 
{
    L->length = 0;
}

Status ListEmpty(SqList L) 
{
    return L.length == 0 ? TRUE : FALSE;
}

int ListLength(SqList L) 
{
    return L.length;
}

Status GetElem(SqList L, int i, ElemType* e) 
{
    if (i < 1 || i > L.length)
	{
		return ERROR;	
	} 
    *e = L.elem[i - 1];
    return OK;
}

int LocateElem(SqList L, ElemType e) 
{
    int i;
    for (i = 0; i < L.length; i++) 
	{
        if (L.elem[i] == e) return i + 1;  // 返回位序，从1开始
    }
    return 0;  // 如果没找到，返回0
}

Status PriorElem(SqList L, ElemType cur, ElemType* pre) 
{
    int i;
    for (i = 0; i < L.length; i++) 
	{
        if (L.elem[i] == cur) 
		{
            if (i == 0) return ERROR;  // cur是第一个元素，没有前驱元素
            *pre = L.elem[i - 1];
            return OK;
        }
    }
    return ERROR;  // 没有找到cur
}

Status NextElem(SqList L, ElemType cur, ElemType* next) 
{
    int i;
    for (i = 0; i < L.length; i++) 
	{
        if (L.elem[i] == cur) 
		{
            if (i == L.length - 1)
			{
				return ERROR;  // cur是最后一个元素，没有后继元素	
			} 
            *next = L.elem[i + 1];
            return OK;
        }
    }
    return ERROR;  // 没有找到cur
}

Status ListInsert(SqList* L, int i, ElemType e) 
{
    int j;
    if (i < 1 || i > L->length + 1)
	{
		return ERROR; 
	}
    if (L->length >= L->listsize) 
	{  // 当前存储空间已满，增加存储空间
        ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase)
		{
			return OVERFLOW;  // 存储分配失败
		}
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }
    for (j = L->length - 1; j >= i - 1; j--) 
	{
        L->elem[j + 1] = L->elem[j];  // 插入位置及之后的元素后移
    }
    L->elem[i - 1] = e;
    L->length++;
    return OK;
}

Status ListDelete(SqList* L, int i, ElemType* e) 
{
    int j;
    if (i < 1 || i > L->length)
	{
		return ERROR;  // 删除位置不合法
	}
    *e = L->elem[i - 1];
    for (j = i; j < L->length; j++) 
	{
        L->elem[j - 1] = L->elem[j];  // 被删除元素之后的元素前移
    }
    L->length--;
    return OK;
}

void CreateList(SqList* L) 
{
    int n, i;
	printf("要输入的元素个数:") ; 
    scanf("%d", &n);  // 读取元素数量
    if (n < 0) n = 0;
    for (i = 0; i < n; i++) 
	{
        if (L->length >= L->listsize) 
		{  // 当前存储空间已满，增加存储空间
            L->elem = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
            if (!L->elem) exit(1);  // 存储分配失败
            L->listsize += LISTINCREMENT;  // 增加存储容量
        }
		printf("元素 %d: ", i + 1); 
        scanf("%d", &L->elem[L->length++]);  // 读取元素
    }
}

void ListTraverse(SqList L) 
{
    int i;
    if (L.length > 0)
    {
    	printf("{ ");
        for (i = 0; i < L.length; i++) 
		{
            printf("%d", L.elem[i]);
            if (i < L.length - 1) 
			{
                printf(" ");
            }
        }
        printf(" }");
	}
	else
	{
		printf("{ }");
	}
}
int main() {
    SqList L;
    ElemType e;
    Status status;
    int i;
    ElemType new_value;
    int positions_to_insert[] = {-3, 0, 2, 6, 9, 12}; // 插入元素的位置示例
    ElemType test_elements[] = {3, 13, 1, 11, 7, 17, 8, 18}; // 用于定位元素位置的测试数组
	ElemType pre_e, next_e;
    // 初始化链表
    status = InitList(&L);
    if (status != OK) {
        printf("顺序表初始化失败\n");
        return 1;
    }
    
    // 创建链表
    CreateList(&L);

    // 遍历顺序表
    printf("顺序表内容： ");
    ListTraverse(L);
    printf("\n");

    // 检查顺序表是否为空
    if (ListEmpty(L)) {
        printf("顺序表为空\n");
    } else {
        printf("顺序表不为空\n");
    }

    // 获取顺序表长度
    printf("顺序表长度：%d\n", ListLength(L));
    
    // 插入元素
    printf("请输入要插入的元素：");
    scanf("%d", &new_value);
    for (i = 0; i < 6; i++) {
        status = ListInsert(&L, positions_to_insert[i], new_value);
        if (status == OK) {
            printf("在第%d个位置插入元素%d后，顺序表内容：", positions_to_insert[i], new_value);
            ListTraverse(L);
            printf("\n");
        } else {
            printf("插入元素失败，位置：%d\n", positions_to_insert[i]);
        }
    }

    // 删除元素
    status = ListDelete(&L, 3, &e);
    if (status == OK) {
        printf("删除第3个元素后，顺序表内容：");
        ListTraverse(L);
        printf("\n");
    } else {
        printf("删除元素失败\n");
    }
    
    // 获取第2个元素
    status = GetElem(L, 2, &e);
    if (status == OK) {
        printf("顺序表的第2个元素是：%d\n", e);
    } else {
        printf("获取元素失败\n");
    }

    // 获取元素的前驱和后继
    for (i = 1; i <= ListLength(L); i++) {
        ElemType cur_e;
        GetElem(L, i, &cur_e);
        if (PriorElem(L, cur_e, &pre_e) == OK) {
            printf("元素%d的前驱是：%d\n", cur_e, pre_e);
        } else {
            printf("元素%d没有前驱或找不到该元素\n", cur_e);
        }
        
        if (NextElem(L, cur_e, &next_e) == OK) {
            printf("元素%d的后继是：%d\n", cur_e, next_e);
        } else {
            printf("元素%d没有后继或找不到该元素\n", cur_e);
        }
    }

    // 定位元素的位置
    for (i = 0; i < 8; i++) {
        int pos = LocateElem(L, test_elements[i]);
        if (pos) {
            printf("元素%d在顺序表中的位置是：%d\n", test_elements[i], pos);
        } else {
            printf("元素%d不存在\n", test_elements[i]);
        }
    }
    
    // 销毁顺序表
    DestroyList(&L);
    if (L.elem == NULL) {
        printf("顺序表已销毁\n");
    }

    return 0;
}