C语言数据结构链表的实例（十九种操作）

2023年5月17日上午2:10 • 数据结构

C语言数据结构链表的实例（十九种操作）攻略

简介

链表是一种动态数据结构，以链式存储方式让任意节点之间相互连接，链表中的每个节点包含两个部分：数据域和指针域，数据域存储节点的数据，指针域存储下一个节点的地址。链表的优点是可以动态地分配内存，其缺点是查询效率较低。

本攻略将介绍19种链表操作，其中包括创建链表、添加节点、删除节点、查找节点以及遍历链表等操作。

创建链表

创建链表需要动态分配内存，同时需要指向链表头的指针，以下是创建链表的代码：

typedef struct node{
    int data;
    struct node *next;
}LinkedList, *LinkedListPtr;

//创建链表
LinkedListPtr createList(){
    LinkedListPtr head = (LinkedListPtr)malloc(sizeof(LinkedList));
    head->next = NULL;
    return head;
}

添加节点

添加节点需要在链表尾部或者指定位置插入节点，以下是添加节点的代码：

在链表尾部添加节点

//在链表尾部添加节点
void addTail(LinkedListPtr head, int data){
    LinkedListPtr node = (LinkedListPtr)malloc(sizeof(LinkedList));
    node->data = data;
    node->next = NULL;
    LinkedListPtr p = head;
    while(p->next != NULL){//找到链表的尾节点
        p = p->next;
    }
    p->next = node;
}

在指定位置插入节点

//在指定位置插入节点
void insertNode(LinkedListPtr head, int pos, int data){
    LinkedListPtr node = (LinkedListPtr)malloc(sizeof(LinkedList));
    node->data = data;
    LinkedListPtr p = head;
    int i = 0;
    while(p != NULL && i < pos){//找到要插入位置的前一个节点
        p = p->next;
        i++;
    }
    if(p == NULL || i > pos){//如果节点不存在或插入位置非法，直接返回
        free(node);
        return;
    }
    node->next = p->next;
    p->next = node;
}

删除节点

删除节点需要找到要删除的节点的前一个节点，将其指向要删除的节点的指针指向要删除节点的下一个节点，以下是删除节点的代码：

//删除节点
void deleteNode(LinkedListPtr head, int data){
    LinkedListPtr p = head;
    while(p->next != NULL && p->next->data != data){//找到要删除节点的前一个节点
        p = p->next;
    }
    if(p->next == NULL){//如果要删除的节点不存在，直接返回
        return;
    }
    LinkedListPtr tmp = p->next;
    p->next = p->next->next;
    free(tmp);//释放要删除节点的内存空间
}

查找节点

查找节点可以根据节点的位置或者节点的值查找，以下是查找节点的代码：

根据节点的位置查找

//根据位置查找节点
LinkedListPtr findNodeByPos(LinkedListPtr head, int pos){
    LinkedListPtr p = head->next;
    int i = 0;
    while(p != NULL && i < pos){//找到要查找的节点
        p = p->next;
        i++;
    }
    return p;
}

根据节点的值查找

//根据节点的值查找节点
LinkedListPtr findNodeByData(LinkedListPtr head, int data){
    LinkedListPtr p = head->next;
    while(p != NULL && p->data != data){//找到要查找的节点
        p = p->next;
    }
    return p;
}

遍历链表

遍历链表可以按顺序输出链表中的每个节点的值，以下是遍历链表的代码：

//遍历链表
void traverseList(LinkedListPtr head){
    LinkedListPtr p = head->next;
    while(p != NULL){//遍历链表中的每个节点
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

示例

示例1：创建链表，向链表尾部添加元素，遍历链表

LinkedListPtr head = createList();
addTail(head,1);
addTail(head,2);
addTail(head,3);
addTail(head,4);
traverseList(head);

输出结果：

1 2 3 4

示例2：创建链表，向链表中插入元素，删除链表中的元素，遍历链表

LinkedListPtr head = createList();
addTail(head,1);
addTail(head,2);
addTail(head,3);
addTail(head,4);
insertNode(head, 1, 10);
traverseList(head);
deleteNode(head, 3);
traverseList(head);