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

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

article 2024/11/16 19:27:39

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