链表(C语言版)

发布时间:2023年12月21日

链表是一种基于指针实现的线性表,它的特点是动态存储,可以方便地进行插入和删除操作。以下是一个简单的单向链表的实现(C语言版)。

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

typedef struct ListNode {
    int data;               // 数据元素
    struct ListNode *next;  // 指向下一个节点的指针
} ListNode, *ListPtr;

// 初始化链表
void InitList(ListPtr *L) {
    *L = NULL;
}

// 判断链表是否为空
int isEmpty(ListPtr L) {
    return L == NULL ? 1 : 0;
}

// 获取链表长度
int getLength(ListPtr L) {
    int len = 0;
    for (ListPtr p = L; p != NULL; p = p->next) {
        len++;
    }
    return len;
}

// 获取指定位置的元素
int getElem(ListPtr L, int i) {
    if (i < 1 || i > getLength(L)) {
        printf("Error: Index out of range.\n");
        exit(1);
    }
    ListPtr p = L;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    return p->data;
}

// 在指定位置插入元素
void insertElem(ListPtr *L, int i, int e) {
    if (i < 1 || i > getLength(*L)+1) {
        printf("Error: Index out of range.\n");
        exit(1);
    }
    ListPtr newNode = (ListPtr)malloc(sizeof(ListNode));
    newNode->data = e;
    if (i == 1) {  // 插入到头结点
        newNode->next = *L;
        *L = newNode;
    } else {  // 插入到其他位置
        ListPtr p = *L;
        for (int j = 1; j < i-1; j++) {
            p = p->next;
        }
        newNode->next = p->next;
        p->next = newNode;
    }
}

// 删除指定位置的元素
void deleteElem(ListPtr *L, int i) {
    if (i < 1 || i > getLength(*L)) {
        printf("Error: Index out of range.\n");
        exit(1);
    }
    if (i == 1) {  // 删除头结点
        ListPtr p = *L;
        *L = (*L)->next;
        free(p);
    } else {  // 删除其他位置
        ListPtr p = *L;
        for (int j = 1; j < i-1; j++) {
            p = p->next;
        }
        ListPtr q = p->next;
        p->next = q->next;
        free(q);
    }
}

// 输出链表中的所有元素
void printList(ListPtr L) {
    printf("List: ");
    for (ListPtr p = L; p != NULL; p = p->next) {
        printf("%d ", p->data);
    }
    printf("\n");
}

int main() {
    ListPtr L;
    InitList(&L);

    // 插入元素
    insertElem(&L, 1, 1);
    insertElem(&L, 2, 2);
    insertElem(&L, 3, 3);
    insertElem(&L, 4, 4);
    insertElem(&L, 5, 5);
    printList(L);  // List: 1 2 3 4 5

    // 删除元素
    deleteElem(&L, 3);
    printList(L);  // List: 1 2 4 5

    // 获取元素
    printf("Element at index 2 is %d\n", getElem(L, 2));  // Element at index 2 is 2

    // 获取长度
    printf("Length of the list is %d\n", getLength(L));  // Length of the list is 4

    return 0;
}

在这个实现中,我们使用结构体 ListNode 来表示链表中的节点,其中 data 表示数据元素,next
表示指向下一个节点的指针。我们实现了初始化链表、判断链表是否为空、获取链表长度、获取指定位置的元素、在指定位置插入元素、删除指定位置的元素、输出链表中所有元素等操作。

文章来源:https://blog.csdn.net/xue_bian_cheng_/article/details/135138355
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。