LinkedList 单向链表C语言算法(递归)

单向链表

相比较直接用数组存储数据,链表的优势主要在于可拓展性,即数组的长度是固定的,而链表却可以根据需要拓展长度;

但相比较数组,链表在读取时需要进行元素的遍历,时效性较差,不可直接打开某个存储位置的内容。

实现功能

初始化单链表

添加元素

插入元素

更新元素

删除元素

清空表

查找元素数量

获取指定索引的元素内容

查找元素所在的索引位置

导出指针数组

打印顺序表所有元素

代码

GitHub:https://github.com/MagicDevilZhang/myDataStructProject/blob/master/LinkedList.cpp

CSDN:https://blog.csdn.net/MagicDevilZhang/article/details/83869462

以下代码多以递归法实现,纯手工编写,欢迎指出错误和优化方法。

/**
 * @ProjectName:LinkedList 单链表算法实现
 * @Author: MagicDevil.Top (MagicDevil.Zhang@gmail.com)
 * @Description: 实现功能:初始化单链表、添加元素、插入元素、更新元素、删除元素、清空表、查找元素数量、获取指定索引的元素内容、查找元素所在的索引位置、导出指针数组、打印顺序表所有元素
 */
#include <stdio.h>
#include <windows.h>

#define SUCCESS 1
#define ERROR -1

#define ElemType int
#define StatusType int

//自定义单链表类型
typedef struct LNode
{
    ElemType data;      //单链表存储
    struct LNode *next; //下个链表节点的指针
} LNode, *LinkedList;

//1.初始化单链表
StatusType InitLinkedList(LinkedList &L)
{
    L = (LinkedList)malloc(sizeof(LNode)); //为节点分配内存空间
    L->data = NULL;
    L->next = NULL;
    return SUCCESS;
}

//2.添加元素
StatusType AddLinkedList(LinkedList &L, ElemType content)
{
    if (!L->data)
    { //空节点自动覆盖
        L->data = content;
        return SUCCESS;
    }

    if (L->next)
    {
        AddLinkedList(L->next, content); //递归到最后一个链表元素
    }
    else
    {
        //新建一个新节点
        LinkedList temp;
        InitLinkedList(temp);
        temp->data = content;
        temp->next = NULL;

        //将新节点连接到最后节点位置
        L->next = temp;
        return SUCCESS;
    }
    return ERROR;
}

//3.插入元素
StatusType InsertLinkedList(LinkedList &L, ElemType content, int index)
{
    if (!L->next && index != 0)
    { //递归抵达最后元素,但仍未到指定元素,返回ERROR
        return ERROR;
    }

    if (index == 0)
    {
        LinkedList temp;
        InitLinkedList(temp);
        //将需要插入的元素与被插入的元素内容交换并连接,以实现前后位置的伪交换
        temp->data = L->data; 
        L->data = content;
        temp->next = L->next;
        L->next = temp;
        return SUCCESS;
    }
    else
    {
        return InsertLinkedList(L->next, content, index - 1);//递归到指定索引的元素
    }

    return ERROR;
}

//4.更新元素
StatusType UpdateLinkedList(LinkedList &L, int index, ElemType content)
{
    if (index)
    {
        UpdateLinkedList(L->next, index - 1, content); //递归到指定索引的元素
    }

    if (L && index == 0)
    { //到达指定元素且该链表不为空
        L->data = content;
        return SUCCESS;
    }

    return ERROR;
}

//5.删除元素
StatusType DeleteLinkedList(LinkedList &L, int index)
{
    if (index == 0)
    { //头结点删除
        LinkedList g;
        g = L;
        L = L->next;
        free(g);
        return SUCCESS;
    }

    if (index != 1)
    { //定位到要删除的指定位置前的元素
        DeleteLinkedList(L->next, index - 1);
    }

    if (L->next && index == 1)
    {
        LinkedList g = L->next;  //标记垃圾内存
        L->next = L->next->next; //跨连接后面的元素
        free(g);
        return SUCCESS;
    }
    return ERROR;
}

//6.清空表
StatusType ClearLinkedList(LinkedList &L)
{
    if (L->next)
    {
        ClearLinkedList(L->next); //遍历所有元素
    }
    free(L->next); //清空尾巴保留头结点
    L->data = NULL;
    L->next = NULL;
    return SUCCESS;
}

//7.查找元素数量
StatusType getLinkedListNum(LinkedList &L)
{
    if (L)
    {
        return 1 + getLinkedListNum(L->next);
    }
}

//8.获取指定索引的元素内容
ElemType getLinkedList(LinkedList &L, int index)
{
    if (!L->next && index != 0)
    { //抵达最后元素时还未到指定元素
        return ERROR;
    }

    if (index == 0)
    {
        return L->data;
    }
    else
    {
        return getLinkedList(L->next, --index);
    }

    return ERROR;
}

//9.查找元素所在的索引位置
int indexOfLinkedList(LinkedList &L, ElemType content)
{
    if (!L->next && L->data != content)
    { //递归到最后元素时仍未到找到要查找的元素,返回ERROR
        return ERROR;
    }

    if (L->data == content)
    {
        return 0;//当到达要查找的元素时,返回0以结束递归
    }
    else
    {
        int x = indexOfLinkedList(L->next, content);//检测后一个递归是否是未查找到(ERROR)
        return (x != ERROR ? 1 + x : ERROR);//三目运算,若后一个递归元素未查找到,告诉先一个递归元素未查找到(返回ERROR),以此循环,直到首个函数返回ERROR
    }

    return ERROR;
}

//10.导出指针数组
ElemType *toArrayLinkedList(LinkedList &L)
{
    StatusType getLinkedListNum(LinkedList & L);
    LinkedList s;
    s = L;

    ElemType *x;

    x = (ElemType *)malloc(sizeof(ElemType) * getLinkedListNum(L));
    for (int i = 0; s != NULL; i++)
    {
        *(x + i) = s->data;
        s = s->next;
    }
    return x;
}

//11.打印所以元素
StatusType PrintLinkedList(LinkedList &L)
{
    int foot = 0;
    int flag = 0;
    int num = 0;

    LinkedList s;
    s = L;

    printf("List Information\n");
    while (flag == 0)
    {
        if (s->next == NULL)
        { //当遍历到最后一个元素时退出
            flag = 1;
        }
        num++;
        printf(" |- List %d : %d\n", foot++, s->data);
        s = s->next;
    }
    printf("Num : %d\n", num);
    return SUCCESS;
}

int main(int argc, char const *argv[])
{
    LinkedList p;
    InitLinkedList(p);
    AddLinkedList(p, 123);
    AddLinkedList(p, 456);
    AddLinkedList(p, 789);
    InsertLinkedList(p, 666, 2);
    UpdateLinkedList(p, 1, 3333);
    DeleteLinkedList(p, 3);
    ClearLinkedList(p);
    PrintLinkedList(p);
    printf("%d", getLinkedListNum(p));
    printf("%d", indexOfLinkedList(p, 789));

    system("pause");
    return 0;
}

留下评论

电子邮件地址不会被公开。 必填项已用*标注