数据结构c语言带有头节点的单链表的操作

带有头节点的单链表是指在单链表的头部添加一个虚拟节点，它的作用是方便对链表进行操作。下面是带有头节点的单链表的常见操作：

1. 初始化链表

#include <stdio.h>
#include <stdlib.h>

//定义链表节点结构体
typedef struct Node {
    int data;           //数据域
    struct Node* next;  //指针域
}Node;

//定义带有头节点的链表
typedef struct List {
    Node* head;         //头节点指针
    int length;         //链表长度
}List;

//初始化链表
void initList(List* list) {
    list->head = (Node*)malloc(sizeof(Node));    //为头节点动态分配内存
    list->head->next = NULL;    //将头节点的指针域置为NULL
    list->length = 0;           //链表长度初始化为0
}

//测试代码
int main() {
    List list;
    initList(&list);
    return 0;
}

2. 插入节点

//在第pos个节点之后插入元素x
void insertNode(List* list, int pos, int x) {
    if (pos < 1 || pos > list->length + 1) {     //判断插入位置是否合法
        printf("插入位置不合法！\n");
        return;
    }
    Node* p = list->head;
    for (int i = 1; i < pos; i++) {     //查找插入位置的前驱节点
        p = p->next;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));     //创建新节点
    newNode->data = x;
    newNode->next = p->next;          //将新节点插入到链表中
    p->next = newNode;
    list->length++;                  //链表长度加1
}

//测试代码
int main() {
    List list;
    initList(&list);
    insertNode(&list, 1, 1);
    insertNode(&list, 2, 2);
    insertNode(&list, 3, 3);
    return 0;
}

3. 删除节点

//删除第pos个节点
void deleteNode(List* list, int pos) {
    if (pos < 1 || pos > list->length) {     //判断删除位置是否合法
        printf("删除位置不合法！\n");
        return;
    }
    Node* p = list->head;
    for (int i = 1; i < pos; i++) {     //查找删除位置的前驱节点
        p = p->next;
    }
    Node* q = p->next;      //将要删除的节点保存到临时变量q中
    p->next = q->next;      //将前驱节点指向后继节点，实现删除操作
    free(q);                //释放节点的内存空间
    list->length--;         //链表长度减1
}

//测试代码
int main() {
    List list;
    initList(&list);
    insertNode(&list, 1, 1);
    insertNode(&list, 2, 2);
    insertNode(&list, 3, 3);
    deleteNode(&list, 2);
    return 0;
}

4. 查找节点

//查找值为x的节点，返回节点的位置
int searchNode(List* list, int x) {
    Node* p = list->head->next;
    int pos = 1;
    while (p != NULL && p->data != x) {     //遍历链表，查找值为x的节点
        p = p->next;
        pos++;
    }
    if (p == NULL) {        //未找到节点，返回0
        return 0;
    }
    else {                  //找到节点，返回位置
        return pos;
    }
}

//测试代码
int main() {
    List list;
    initList(&list);
    insertNode(&list, 1, 1);
    insertNode(&list, 2, 2);
    insertNode(&list, 3, 3);
    int pos = searchNode(&list, 2);
    printf("节点2的位置是：%d\n", pos);
    return 0;
}

5. 遍历链表

//遍历链表，输出所有元素
void traverseList(List* list) {
    Node* p = list->head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

//测试代码
int main() {
    List list;
    initList(&list);
    insertNode(&list, 1, 1);
    insertNode(&list, 2, 2);
    insertNode(&list, 3, 3);
    traverseList(&list);
    return 0;
}