本文主要向大家介绍了C/C++知识点之单链表的基本操作（C语言），通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

一、简介
　　链表是动态分配存储空间的链式存储结构。
　　链表包括一个“头指针”变量，其中第0个结点称为整个链表的头结点，头结点中存放一个地址，该地址指向一个元素，头结点一般不存放具体数据，只是存放第一个结点的地址。链表中每一个元素称为“结点”，每个结点都由两部分组成：存放数据元素的数据域和存储直接后继存储位置的指针域。指针域中存储的即是链表的下一个结点存储位置，是一个指针。多个结点链接成一个链表。最后一个结点的指针域设置为空(NULL)，作为链表的结束标志，表示它没有后继结点。
　　示意图：
　　
二、链表的结构体


typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node *next;
}Node, *PNode;

View Code
三、链表的创建


///创建节点
PNode createNode(DataType value)
{
    PNode node = (PNode)malloc(sizeof(Node));
    node->data = value;
    node->next = NULL;
    return node;
}
///创建单链表
PNode createList()
{
    int len, value;
    PNode pHead = (PNode)malloc(sizeof(Node));  ///头节点
    pHead->next = NULL;
    PNode pTail = pHead;  ///移动的节点
    puts("请输入单链表的节点数:");
    scanf("%d", &len);
    for (int i = 0; i < len; ++i)
    {
        scanf("%d", &value);
        PNode pNode = createNode(value);
        pTail->next = pNode;
        pTail = pNode;
    }
    return pHead;
}

View Code
四、链表的长度


///获取链表长度
int getListLength(PNode pHead)
{
    int len = 0;
    while (pHead->next != NULL)  ///实际上计算的是头节点开始到倒数第二个节点的个数，但仍是节点的个数
    {
        pHead = pHead->next;
        len++;
    }
    return len;
}

View Code
五、链表是否为空


///判断链表是否为空
bool isEmpty(PNode pHead)
{
    if (pHead->next == NULL)
        return false;
    else
        return true;
}

View Code
六、链表的节点插入


///单链表插入节点
bool insertNode(PNode pHead, DataType value, int pos)
{
    PNode pPos =  pHead;
    if (pos < 1 || getListLength(pPos) < pos)
        return false;
    for (int i = 0; i < pos - 1; ++i)  ///所需要的是pos-1的指针
    {
        pPos = pPos->next;
    }
    PNode pNode = createNode(value);
    pNode->next = pPos->next;  ///插入节点时，只需修改要插入的节点的next和插入位置的上一个节点的next
    pPos->next = pNode;
    return true;
}

View Code
七、链表的节点删除


///单链表删除节点
bool deleteNode(PNode pHead, int pos)
{
    PNode pPos = pHead;
    if (pos < 1 || getListLength(pPos) < pos)
        return false;
    for (int i = 0; i < pos - 1; ++i)
    {
        pPos = pPos->next;
    }
    if (pos == getListLength(pHead))  ///如果pos刚好是单节点链表的节点位置，则直接释放该节点，并将头节点next为null
    {
        free(pPos->next);
        pPos->next = NULL;
        return true;
    }
    PNode p = pPos->next->next;  ///先拷贝要释放的指针，以便后面使用
    free(pPos->next);  ///释放指针内存
    pPos->next = p;  ///使用前面拷贝的指针
    return true;
}

View Code
八、整合


#include<stdio.h>
#include<malloc.h>
typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node *next;
}Node, *PNode;
///创建节点
PNode createNode(DataType value)
{
    PNode node = (PNode)malloc(sizeof(Node));
    node->data = value;
    node->next = NULL;
    return node;
}
///创建单链表
PNode createList()
{
    int len, value;
    PNode pHead = (PNode)malloc(sizeof(Node));  ///头节点
    pHead->next = NULL;
    PNode pTail = pHead;  ///移动的节点
    puts("请输入单链表的节点数:");
    scanf("%d", &len);
    for (int i = 0; i < len; ++i)
    {
        scanf("%d", &value);
        PNode pNode = createNode(value);
        pTail->next = pNode;
        pTail = pNode;
    }
    return pHead;
}
///遍历单链表
void traverseList(PNode pHead)
{
    puts("单链表的遍历：");
    PNode pTail = pHead;
    while (pTail->next != NULL)  ///遍历节点的时候，每次遍历的结束返回的节点都是下一个节点
    {
        printf("%d ", pTail->next->data);
        pTail = pTail->next;
    }
    puts();
}
///判断链表是否为空
bool isEmpty(PNode pHead)
{
    if (pHead->next == NULL)
        return false;
    else
        return true;
}
///获取链表长度
int getListLength(PNode pHead)
{
    int len = 0;
    while (pHead->next != NULL)  ///实际上计算的是头节点开始到倒数第二个节点的个数，但仍是节点的个数
    {
        pHead = pHead->next;
        len++;
    }
    return len;
}
///单链表插入节点
bool insertNode(PNode pHead, DataType value, int pos)
{
    PNode pPos =  pHead;
    if (pos < 1 || getListLength(pPos) < pos)
        return false;
    for (int i = 0; i < pos - 1; ++i)  ///所需要的是pos-1的指针
    {
        pPos = pPos->next;
    }
    PNode pNode = createNode(value);
    pNode->next = pPos->next;  ///插入节点时，只需修改要插入的节点的next和插入位置的上一个节点的next
    pPos->next = pNode;
    return true;
}
///单链表删除节点
bool deleteNode(PNode pHead, int pos)
{
    PNode pPos = pHead;
    if (pos < 1 || getListLength(pPos) < pos)
        return false;
    for (int i = 0; i < pos - 1; ++i)
    {
        pPos = pPos->next;
    }
    if (pos == getListLength(pHead))  ///如果pos刚好是单节点链表的节点位置，则直接释放该节点，并将头节点next为null
    {
        free(pPos->next);
        pPos->next = NULL;
        return true;
    }
    PNode p = pPos->next->next;  ///先拷贝要释放的指针，以便后面使用
    free(pPos->next);  ///释放指针内存
    pPos->next = p;  ///使用前面拷贝的指针
    return true;
}
int main()
{
    PNode linkedList = createList();
    traverseList(linkedList);
    if (insertNode(linkedList, -2, 3))
    {
        puts("插入成功");
    }
    else
    {
        puts("插入失败");
    }
    traverseList(linkedList);
    if (deleteNode(linkedList, 3))
    {
        puts("删除成功");
    }
    else
    {
        puts("删除失败");
    }
    traverseList(linkedList);
}

View Code

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！