#include<stdio.h>
#include<stdlib.h>
//-------- 线性表的动态分配顺序存储结构 -----------
int LIST_INIT_SIZE=100; //顺序表存储空间初始尺寸
int LISTINCREMENT=10; //顺序表存储空间分配增量
typedef int ElemType; //顺序表元素的数据类型为整数
//存储结构定义：顺序表
typedef struct {
ElemType *elem; //存储线性表元素的数组
int length; //表长度
int listsize; //存储容量
int incrementsize; //扩展增量
} SqList;
//-------- 线性表的基本运算 -----------------------------
//辅助函数：显示顺序表元素
void print_Sq (SqList L) {
for(int i=0; i<L.length; i++) printf("%5d", L.elem[i]);
printf("\n");
}
//运算1：初始化空顺序表L
void InitList_Sq(SqList *L, int initsize, int incresize) {// 算法2.4
L->elem = (ElemType *)malloc(initsize*sizeof(ElemType)); //分配数组空间
L->length=0; //表长度初值为0
L->listsize=initsize; //表空间初始尺寸
L-> incrementsize = incresize;
}
//运算2：销毁顺序表L// 算法2.8
void DestroyList_Sq(SqList *L) {
free(L->elem); //释放表的数组存储空间
L->elem=NULL; //清空指向数组的指针及表示表长度、数组尺寸的指示变量
L->length=0;
L->listsize=0;
}
//运算3：在顺序表L中第i个位置前插入新元素e
void ListInsert_Sq (SqList *L, int i, ElemType e) {
if(i < 1 || i > L->length+1)
return ERROR;// i值不合法
//动态扩展空间，每次空间不足，空间长度增加 LISTINCREMENT
if(L->length == L->listsize)
{
ElemType * increspace = (ElemType *)realloc(L->elem,(L->listsize + LISTINCREMENT) * sizeof(ElemType));
if(! increspace)
exit(OVERFLOW);
L->elem = increspace;
L->listsize += LISTINCREMENT;
}
for(int j=L->length-1;j>i-1;j--)
{
L->elem[j+1]=L->elem[j];
}
L->elem[i-1]=e;
L->length++;
return OK;
}
//运算4：在顺序表L中删除第i个元素，用输出变量e返回其值
void ListDelete_Sq (SqList *L, int i, ElemType* e) { //算法2.7
*e=L->elem[i-1];
printf("删除的第%d的元素为：%d\n",i,*e);
for(int j=i-1;j<L->length;j++)
{
L->elem[j]=L->elem[j+1];
}
L->length--;
}
//运算5：在顺序表L中找到第i个值与e相等的元素，返回其位序，否则返回0
int LocateElem_Sq (SqList L, ElemType e) { //算法2.5
for(int i=0;i<L.length;i++)
{
if(L.elem[i]==e)
return i+1;
}
return 0;
}