当前位置：首页 > news >正文

快速利用c语言实现线性表（lineList）

news 2025/7/4 23:48:47

线性表是数据结构中最基本和简单的一个，它是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;elsereturn 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;
}