【数据结构-C】单链表基本操作及图解分析

单链表介绍

单链表结点：数据域+指针域(指向下一个结点)

结点的表示方式：

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode;

单链表头指针：恒指向线性表中的第一个结点，没有结点指向NULL

线性表链式的存储特点：是一组任意的存储单元存储线性表的数据元素（物理地址可连续可不连续）。

线性表链式的逻辑特点：数据元素之间的关系是由头指针和结点中的指针指示的。

总结：

单链表能通过头指针找到第一个结点，第一个结点又能通过其指针域找到下一个结点，依次类推，只要有头指针指向单链表，那么该单链表中的元素就能被找到。

单链表基本操作及图解分析

1.创建一个新结点

LNode * NewNode(EleType data)
{
    LNode* newNode = (LNode*)malloc(sizeof(LNode));//创建新结点

    //初始化结点
    newNode->data = data;
    newNode->next = NULL;

    return newNode;//返回新结点指针
}

2.头插法向单链表中插入结点

当链表为空时：

当链表不为空时

void LinkListPushFront(LinkList** pphead, EleType data)
{
    LNode* newNode = NewNode(data);

    if (*pphead == NULL)//如果链表为空，将头指针指向新结点
    {
        *pphead = newNode;
    }
    else 
    {
        newNode->next = *pphead;//新结点的指针域指向头结点
        *pphead = newNode;//头指针指向新结点
    }
}

3. 尾插法向单链表中插入结点

当链表为空时：

当链表不为空时

void LinkListPushBack(LinkList** pphead, EleType data)
{
    LinkList* tail = *pphead;
    LNode* newNode = NewNode(data);
    if (*pphead == NULL)//链表为空，直接将头指针指向该节点
     {
        *pphead = newNode;
        return;
    }
    else
    {    
        while (tail->next != NULL)//找到最后一个节点
        {
            tail = tail->next;
        }

    }
    tail->next = newNode;//将最后一个节点和新节点连接
}

4.头删法删除单链表结点

当链表为空时，不删除。

当链表中有多个元素时：

void LinkListPopFront(LinkList **pphead)
{
    if (NULL == *pphead)//检查链表是否为空链表
    {
        perror("NULL\n");
        return;
    }
    else
    {
        LinkList *temp = *pphead;
        *pphead = (*pphead)->next;//头指针指向第二个结点
        free(temp);//释放第一个结点空间
    }

}

5.尾删法删除单链表结点

当链表为空时，不删除。

当链表中只有一个元素时，释放该结点，头指针指向空。

当链表中有多个结点时：

void LinkListPopBack(LinkList **pphead)
{
    if (NULL == *pphead)//空
    {
        perror("链表为空\n");
        return;
    }
    else if ((*pphead)->next == NULL)//一个节点，直接删除
    {
        free(*pphead);
        *pphead =NULL;
    }
    else
    {
        LinkList *tail = *pphead;
        LinkList *pre = NULL;//保存倒数第二个结点的地址
        while (tail->next !=NULL)//寻找尾结点
        {
            pre = tail;
            tail = tail->next;
        }
        free(tail);//释放删除的结点
        pre->next = NULL;
    }
}

6.返回单链表长度

时间复杂度：O(n)

int SizeLinkList(LinkList* pphead)
{
    int count = 0;//计数器

    if (pphead == NULL)
    {
        return 0;
    }
    else
    {
        while (pphead != NULL)
        {
            count++;
            pphead = pphead->next;
        }
        return count;
    }
}

7.删除单链表任意一个结点

时间复杂度：O(n)

删除第一个位置为头删

int DeletElem(LinkList** pphead, int pos)
{
    if (*pphead == NULL)
    {
        return 0;
    }
    else if (pos == 1)
    {
        LinkListPopFront(pphead);
        return 1;
    }
    else
    {
        if (pos > SizeLinkList(*pphead))//判断删除的位置是否大于链表长度
        {
            return 0;
        }
        LinkList* tail = *pphead;//遍历链表节点 
        LinkList* pre = NULL;//删除结点的前驱结点
        while (tail->next != NULL && pos>1)
        {
            pre = tail;
            tail = tail->next;
            pos--;
        }
        pre->next=tail->next;//将前驱结点和tail->next连接
        free(tail);
        return 1;
    }
}

8.查找某结点

时间复杂度：O(n)

LNode* FindElem(LinkList* pphead, EleType data)
{
    if (pphead == NULL)
    { 
        return NULL;
    }
    else
    {
        while (pphead != NULL)
        {
            if(pphead->data == data)
            {
                return pphead;
            }
            pphead = pphead->next;
        }
        return NULL;
    }

9.在某结点前插入新结点

时间复杂度：O(n)

void LinkListInsert(LinkList** head, LNode* pos, EleType data)
{
    if (pos == *head)
    {
        //头插
        LinkListPushFront(head,data);
    }
    else if (pos == NULL)
    {
        return;
    }
    else 
    {
        LNode* newNode = NewNode(data);
        LNode* tail = *head;
        while (tail->next != pos )//查找待插入结点的前一个结点
        {
            tail = tail->next;
        }
        tail->next = newNode;
        newNode->next = pos;
    }
}

总结：

单向链表的优点：在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

单向链表的缺点：

1、没有解决连续存储分配带来的表长难以确定的问题。

2、失去了顺序存储结构随机存取的特性。

最后祝大家：阖家欢乐，学有所成。