JZTXT

数据结构记录-链表

发布时间 2023-11-04 13:29:11作者: LX2020

1、单链表

1、单链表的组成

最基本的单链表组成如下：

typedef struct Link
{
    char elem; /*数据域*/
    struct Link *next; /*指针域*/
}link;/*节点名，每个阶段都是一个Link结构体*/

为什么这样的就是链表呢，需要从这个结构体内部组成来看，struct Link next; 定义了一个指针变量 next，它的类型是 struct Link，即指向 struct Link 结构体的指针，所以它可以执行一个这样的结构体，所以可以指向下一个结构体，只要我们每次都指一下就会这样一直循环不断下去，这样就形成一个链表。

2、单链表实现

创建一个最简单的单链表如下所示：

link *initLink() 
{
    /*创建无头结点*/
    // link *p = NULL;
    // link *temp = (link*)malloc(sizeof(link));

    // temp->elem = 1;
    // temp->next = NULL;

    // p = temp;

    // for(int i = 2; i<5; i++)
    // {
    //     link *a = (link*)malloc(sizeof(link));
    //     a->elem = i;
    //     a->next = NULL;

    //     temp->next = a;
    //     temp = temp->next; /*这样循环创建后驱*/
    // }

    /*创建有头结点*/

    link *p = (link*)malloc(sizeof(link));
    link *temp = p; /*声明一个指针指向头结点*/

    for(int i = 1; i<5; i++)
    {
        link *a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;

        temp->next = a;
        temp = temp->next; /*这样循环创建后驱*/
    }

    return p;
}

最关键的代码在这：
temp->next = a;
temp = temp->next；
从循环来看，第一次循环，数据域赋值为1，temp的第一个next指向这个新申请的a，之后temp更新到a这里，之后继续创建数据域为2的，在执行相同操作，这样一直到4结束。

但是这样链表的第一个元素，数据域是空的，因为没有地方给他赋值，图示上是这样的
image

3、单链表的基本操作

插入元素

插入如下图所示，就是先移动到他前面一个节点，之后修改next指针的指向。
image

/*
插入元素：
1、将新节点的next指针指向插入位置后的节点
2、将插入位置前节点的next指针指向插入节点

[param] elem 新数据
[param] add 插入位置
*/
link *insertElem(link *p, int elem, int add)
{
    link *temp = p;

    for(int i = 1; i<add; i++) /*将temp指针指向要插入的前一个节点*/
    {
        temp = temp->next;
        if(temp == NULL)
        {
            printf("插入位置无效\n");
            return p;
        }
    }

    link *c = (link*)malloc(sizeof(link));
    c->elem = elem;
    c->next = temp->next; /*创建一个新节点，将c的next指向temp的next，再把temp的next指向c*/
    temp->next = c;
    return p;
}

删除元素

和插入类似，找到，之后指向下一个的下一个。

/*
删除元素：
1、将节点从链表中摘除
2、手动释放节点

[param] elem 要删除元素的值
*/
link *delElem(link *p, int add)
{
    link *temp = p;
    for(int i=1;i<add;i++) /*移动到要删除的上一个节点*/
    {
        temp = temp->next;
        if(temp->next == NULL)
        {
            printf("删除位置无效\n");
            return p;
        }
    }
    link *del = temp->next;
    temp->next = temp->next->next; /*指向下一个节点是下一个的下一个*/
    free(del);
    return p;
}

寻找元素

int selectElem(link *p, int elem)
{
    link *t = p;

    int i=1;
    while (t->next)
    {
        t=t->next;
        if(t->elem == elem)
            return i;
        i++;
    }
    return -1;
}

link *amendElem(link *p, int add, int newElem)
{
    link *temp = p;
    temp = temp->next;
    for(int i=1; i<add;i++)
    {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}

修改元素

link *amendElem(link *p, int add, int newElem)
{
    link *temp = p;
    temp = temp->next;
    for(int i=1; i<add;i++)
    {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}