线性表是数据结构中最基本和简单的一个，它是n的相同类型数据的有序序列，我们也可以用c语言中的数组来理解线性表。
一、线性表声明
我们定义一个线性表的结构体，内部有三个元素：其中elem是一个指针，指向线性表的头，length记录线性表元素个数，listsize记录线性表的总长度。
//
// Created by 111 on 2024/11/15.
//
#ifndef TEST1_LINELIST_H
#define TEST1_LINELIST_H
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 30 //初始化线性表大小
#define LIST_INCREMENT 10 //线性表长度不够时，每次动态增加的长度
typedef struct
{
int *elem; //指向线性表的头
int length; //线性表元素个数
int listsize; //线性表总长度
}LineList;
int initLineList(LineList *);
int lineListInsert(LineList *,int,int);
int lineListDelete(LineList *,int);
int printLineList(LineList *);
int freeLineList(LineList *);
int lineListLocateElem(LineList *,int elem);
#endif //TEST1_LINELIST_H
二、线性表初始化
我们通过初始化函数，进行线性表的空间申请，一开始我们申请可以存有30个元素的线性表，具体函数如下：
int initLineList(LineList *L)
{
L->elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int)); //动态申请堆空间，初始化30个元素
if(!L->elem)
{
printf("LineList allocate failed!"); //申请失败，提示错误，推出程序
exit(ERROR);
}
L->length = 0; //记录元素个数
L->listsize = LIST_INIT_SIZE; //记录线性表总大小
return OK;
}三、插入元素
插入元素我们通过指定位置进行插入，如果插入位置超过元素最大位置+1，则抛错；如果中间位置进行元素插入，我们则需要将后面的元素进行后移。
int lineListInsert(LineList *L,int i,int newelem)
{
int *tmpaddr; //用来存放扩展后的线性表地址
int *tmpdata; //用来存放临时元素的地址
int *q;
if(i<1||i>L->length+1) //如果超过位置，则报错
return ERROR;
if(L->length>=L->listsize)
{
tmpaddr = (int *)realloc(L->elem,(L->listsize+LIST_INCREMENT)*sizeof(int));//元素个数超过线性表最大大小，则进行动态扩展
if(!tmpaddr)
{
printf("linesize reallocate failed!\n");
exit(ERROR);
}
L->elem = tmpaddr;//线性表新地址
L->listsize += LIST_INCREMENT;//线性表总大小该表
}
tmpdata =(L->elem+i-1);
for(q = (L->elem+L->length-1);q>=tmpdata;--q) //从线性表最后一个元素开始，进行元素后移
*(q+1) = *q; //插入元素
*tmpdata = newelem;
++L->length;
return OK;
}四、删除元素
删除一个元素后，我们需要将后续的元素进行前移动，确保线性表的连续：
int lineListDelete(LineList *L,int index)
{
if(index<1||(index>L->length)) //错误的位置，返回ERROR
{
return ERROR;
}
int *tmpdel = L->elem+index; //临时存放删除元素的后一个元素
int *mp = L->elem + L->length -1; //指向最后一个元素
for(tmpdel;tmpdel<=mp;++tmpdel){ //从删除位置开始，进行元素前移
*(tmpdel-1)= *tmpdel;
}
--L->length;
return OK;
}五、元素定位
返回第一个匹配元素的位置，如果都不匹配，则返回0.
int lineListLocateElem(LineList *L,int elem)
{
int i=1;
int *p = L->elem;
while(i<=L->length&&(*p++)!=elem)
++i;
if(i<=L->length)
return i;
else
return 0;
}六、打印线性表
int printLineList(LineList *L)
{
int *p = L->elem;
for(int i =0 ;i<L->length;i++)
{
printf("the %d element is %d\n",(i+1),*(L->elem+i));
}
return OK;
}七、释放空间
int freeLineList(LineList *L)
{
free(L->elem);
return OK;
}
八、测试
我们在main函数中进行测试的编写，验证上述函数的功能。
int main() {
LineList l;
initLineList(&l);
lineListInsert(&l,1, 10);
lineListInsert(&l,2, 18);
lineListInsert(&l,2,20);
printLineList(&l);
lineListDelete(&l,2);
printf("after the linelist deleted.....\n");
printLineList(&l);
freeLineList(&l);
return 0;
}
