数据结构之单链表 | 雪与峰

单链表节点类型定义

    typedef int DataType; //定义数据类型，此处以整型为例
    typedef struct node{
        DataType data; //节点的数据域
        struct node *next; //节点的指针域
    }NODE,*LinkList;

单链表的运算函数

查找

    /**
    *
    * @function 在表中查找第k个元素，若找到，返回该元素节点的指针；否则返回空指针NULL
    * @parameter L 带头节点单链表的头指针
    * @parameter k 要查找元素的位置
    * @return 查找到元素节点的指针或者空指针NULL
    *
    */

    LinkList Find_List(LinkList L, int k){
        LinkList p = L->next; //令p指向第一个元素
        int i = 1; //初始化计数器
        while(p && i < k )&#123; //依次向后查找，直到p指向第k个元素节点或者p为空指针
            p = p->next;
            i++;
        &#125;
        return (p && i==k) ? p : NULL;
    &#125;

插入

    /**
    *
    * @function 将元素newElem插入表中的第k个元素之前即第k-1个元素之后,成功返回0，失败返回-1
    * @parameter L 带头节点单链表的头指针
    * @parameter k 要插入元素的位置
    * @parameter newElem 要插入的新元素
    * @return 0或-1
    *
    */

    int Insert_List(LinkList L, int k, DataType newElem){
        LinkList p, s; //临时指针
        p = (k == 1)? L : Find_List(L, k-1);
        if(!p) return -1; //表中不从在第k-1个元素
        s = (NODE*)malloc(sizeof(NODE)); //为新元素申请节点空间
        if(!s) return -1; //空间申请失败
        s->data = newElem;
        s->next = p->next;
        p->next = s; //插入元素
        return 0;
    }

删除

    /**
    *
    * @function 删除表中的第k个元素节点，即将第k-1个元素的指针域指向第k+1个元素所在节点，成功返回0，失败返回-1
    * @parameter L 带头节点单链表的头指针
    * @parameter k 要删除元素的位置
    * @return 0或-1
    *
    */

    int Delete_List(LinkList L, int k){
        LinkList p, q; //临时指针
        p = (k == 1)? L : Find_List(L, k-1);
        if(!p || !p->next) return -1; //表中不从在第k个元素
        q = p->next;
        p->next = q->next;
        free(q); //删除节点
        return 0;
    }

本博客遵循署名 4.0 协议国际版 (CC BY 4.0)协议
本文链接：https://xuefeng.is-a.dev/archives/linear-table-of-data-structures