【数据结构与算法 CC++】单链表的实现

单链表

文章目录

• 单链表
• 
  

  一、数据结构定义

• 
  

  二、特点与说明

• • 1. 头指针与头结点
• 
  

  三、数据结构与 *** 作

• • 1.结构定义
  • 2. *** 作
  • • (1) 初始化
    • (2)插入
    • (3)删除
• 
  

  四、仓库地址

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、数据结构定义

---

单链表是由若干个链表结点构成的, 每个结点除了需要存储自身节点外, 还需要存储后继结点的地址

结点定义为

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

二、特点与说明 1. 头指针与头结点

1. 头指针 : 通常使用头指针来标记单链表, 头指针为NULL时表示空表;
2. 头结点 : 头指针的指针域指向链表的第一个元素结点

头指针和头结点的区别 :

• 如果链表有头结点, 则头结点是链表的第一个结点
• 不论链表有无头结点, 头指针始终指向链表的第一个结点

三、数据结构与 *** 作 1.结构定义

链表(含虚拟头结点)如下（示例）：

typedef struct LinkList{
    // 虚拟头结点, 不使用指针变量作为头结点
    // 优点 : 指针p永远处于待插入结点的前一个结点
    ListNode head;
    // 顺序表的大小和当前元素数
    int length;
};

2. *** 作 (1) 初始化

• 初始化结点如下（示例）：

/**
 * 初始化结点
 * */
ListNode* initListNode(int val){
    // 初始化一个结点
    ListNode* p = (ListNode*) malloc(sizeof(ListNode));
    // 赋值
    p->data = val;
    p->next = NULL;
    return p;
}

• 初始化链表如下（示例）：

/**
 * 初始化链表
 * */
LinkList* initLinkList(){
    LinkList* linkList = (LinkList*) malloc(sizeof(LinkList));
    // 让虚拟头结点的下一位指向空
    linkList->head.next = NULL;
    linkList->length = 0;
    return linkList;
}

(2)插入

• 头插法如下（示例）：

/**
 * 头插法建立单链表
 * @param linkList,length 仅含头结点的单链表,初始化单链表的长度
 * @return LinkList* 单链表
 * */
LinkList* initLinkListHead(LinkList* linkList,int length){
    // 合法性判断
    if(linkList == NULL) return 0;

    // 随机种子
    srand(time(0));

    while (linkList->length < length){
        // 随机生成数据域
        int val = rand() % 100;
        printf("%d \n",val);
        // 生成一个链表结点(即要插入的结点)
        ListNode* node = initListNode(val);

        node->next = linkList->head.next; // 将 待插入结点的next指针 指向链表真实头结点
        linkList->head.next = node; // 将链表真实头结点 置为 插入的新节点

        linkList->length += 1;
    }
    return linkList;
}

输出示例

测试头插法初始化链表
46, 7, 7, 5, 26;
LinkList->length(5):26 -> 5 -> 7 -> 7 -> 46 -> NULL

头插法先插入的元素会留在链表的后部, 后插入的元素会留在链表的前部

由于头插法插入的链表元素并不符合一般的思路,因此下面讲讲尾插法的代码

• 尾插法代码如下（示例）：

/**
 * 尾插法简历单链表
 * @param linkList,length 仅含头结点的单链表,初始化单链表的长度
 * @return LinkList* 单链表
 * */
LinkList* initLinkListTail(LinkList* linkList,int length){
    // 合法性判断
    if(linkList == NULL) return 0;

    // 随机种子
    srand(time(0));

    // 定义指针r并使其始终指向链表的尾结点
    ListNode* r = &(linkList->head); // 初始化为虚拟头结点的位置

    while (linkList->length < length){
        // 随机生成数据域
        int val = rand() % 100;
        printf("%d \n",val);
        // 生成一个链表结点(即要插入的结点)
        ListNode* node = initListNode(val);
        // 插入
        r->next = node; // 将表尾结点域新插入结点连接上
        r = node; // 将r指向新的表尾结点
        linkList->length += 1;
    }
    r->next = NULL; // 尾结点指针置空
    return linkList;
}

输出示例

测试尾插法初始化链表
46, 7, 7, 5, 26
LinkList->length(5):46 -> 7 -> 7 -> 5 -> 26 -> NULL

**头插法和尾插法的时间复杂度一样, 都是 ** O ( n ) O(n) O(n)

• 插入单结点

插入单结点时, 辅助指针会停在需要插入的位置的前一个结点处

/**
 * 插入结点
 * */
int insert(LinkList* linkList,int ind, int val){
    // 合法性判断
    if(linkList == NULL) return 0;
    // ind = linkList->length是合法的, 表示插入到链表的最后一位
    if(ind < 0 || ind > linkList->length) return 0;
    // 指针p需要一开始指向虚拟头结点的地址
    ListNode* p = (ListNode *)(&(linkList->head));
    // 再新生成一个链表结点(即要插入的结点)
    ListNode* node = initListNode(val);
    // 先找到待插入结点的前一个位置
    while (ind --){ // 找到索引所在位置
        p = p->next; // p会最终停在ind-1的位置
    }
    /*******/
    // 王道P30头插法关键代码
    node->next = p->next;
    p->next = node;
    /*******/
    linkList->length += 1;
    return 1;
}

(3)删除

/**
 * 销毁结点
 * */
void clearListNode(ListNode* listNode){
    if(listNode == NULL) return;
    free(listNode);
    return;
}

/**
 * 结点删除
 * */
int erase(LinkList* linkList, int ind){
    if(linkList == NULL) return 0;
    if(ind < 0 || ind >= linkList->length) return 0;

    // 删除结点 (先找到待删除结点的前一个位置)
    // p是虚拟头结点, q是空指针
    ListNode* p = (ListNode *)&(linkList->head),*q;
    while (ind--){
        p = p->next;
    }
    q = p->next->next;
    clearListNode(p->next);
    p->next = q;
    linkList->length -= 1;
    return 1;
}

---

四、仓库地址

https://gitee.com/JHumpy/da_algo_code