C++实现单链表的各种操作（数据结构）

拼搏现实的明天。 2024-04-23 20:12 9阅读 0赞

链表又可以分为：单链表，双链表，循环链表和静态链表。

**单链表的定义**：*线性表的链式存储又叫单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素。*  
![在这里插入图片描述][451affb710a94018aee2a1844b0736d1.png]

--------------------

**头指针**：把链表中第一个结点的存储位置叫做头指针。  
**头结点**：在单链表的第一个结点前附设一个结点，称为头结点。  
**尾指针**：尾指针是相对于头指针而言的，形式与头指针相同，内容指向链表的最后一个节点。

**头指针与头结点的异同：**

> 头指针
> 
>  *  头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
>  *  头指针具有标志作用，所以常用头指针冠以链表的名字。
>  *  无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

> 头结点
> 
>  *  头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
>  *  有了头结点，对在第一元素结点前插入和删除第一结点，其操作与其他结点的操作就统一了。  
>     头结点不一定是链表的必要元素。

**C++实现如下：**

/**
     * 单链表：带头节点(大多数情况下创建链表都是用这种方式)
     */
    
    #include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    
    /**
     * LNode是一个结构体类型，指向的是包含某个数据类型的数据域和指针域的结构体类型。
     * 
     * 而LinkList是LNode的指针类型，它占用一定内存空间，内存空间中的值是一个LNode类型结构体的地址。
     * 
     * 用typedef将结构体等价于类型名LNode，将结构体指针等价于LinkList
     */
    typedef struct LNode{
        
        int data;
        struct LNode *next;
    }LNode, *LinkList;
    
    
    /**
     * 初始化单链表(带头结点)
     */
    bool InitList(LinkList &L) {
        
        // 给头节点申请一块空间(数据域不存数据)，并将指针L指向头节点
        // 注意：这里的 L 是LinkList类型，分配内存的时候是 LNode 类型，
        // malloc()函数返回值是 void(*) 类型，所以要强转为LinkList
        L = (LinkList)malloc(sizeof(LNode));// 将L指向第一个结点(头结点)
        if(L == NULL) {
        
            return false;// 内存不足,分配失败
        }
        L->next = NULL;// 头节点之后暂时还没有节点
        return true;
    }
    
    /**
     * 判断单链表是否为空
     * @return true--链表为空; false--链表不为空
     */
    bool Empty(LinkList L) {
        
        if(L->next == NULL) {
        
            return true;
        }
        return false;
    }
    
    
    /**
     * 按位置插入(带头结点)
     * 描述：先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新节点。
     * @param L: 头指针，永远指向头结点
     */
    bool ListInsert(LinkList &L, int i, int e) {
        
    
        if(i < 1) return false; // 位置不合法
    
        // 找到i-1位置的结点
        LNode *p = L;
        int j = 0;
        while(p != NULL && j < i-1) {
        
            p = p->next;
            j++;
        }
        if(p == NULL) return false; // i-1位置的结点为空，说明i不合法
    
        // 插入元素
        LNode *temp = (LNode *)malloc(sizeof(LNode));
        if(temp == NULL) return false;// 内存分配失败
        temp->data = e;
        temp->next = p->next;
        p->next = temp;
    
        return true;
    
    }
    
    /**
     * 按序号查找结点值
     * LNode * :强调返回的是一个结点
     * @param i: 链表序号
     */
    LNode *GetElemByIndex(LinkList L, int i) {
        
        int j = 1; // 计数，初始为1
        LNode *p = L->next; // p指针指向第一个结点
        if(i == 0) return L; // 返回头节点 
        if(i < 1) return NULL;
        while(p && j < i) {
        
            p = p->next;
            j++;
        }
        return p; // 返回第i个结点的指针，若i大于表长，则会返回NULL
    }
    
    /**
     * 按值查找表结点
     * @param target: 目标值
     */
    LNode * GetElemByVal(LinkList L, int target) {
        
        LNode *p = L->next; // p指针指向第一个结点
        while(p != NULL && p->data != target) {
        
            p = p->next;
        }
        return p; // 没找到则返回NULL，找到返回该结点
    }
    
    /**
     * 删除结点操作
     * 描述：先检查删除位置的合法性，然后查找表中第i-1个结点，即被删除结点的前驱结点，再将其删除。
     */
    bool ListDel(LinkList &L, int i) {
        
        // 1.判断i的合法性
        if(i < 1) return false;
    
        int j = 0;
        LNode *p = L; // p指针指向头结点
        // 2.找到位置i-1的结点
        while(p!=NULL && j < i-1) {
        
            p = p->next;
            j++;
        }
        LNode *q = p->next; // 令q指针指向被删除的指针
        p->next = q->next;
        free(q); // 释放结点的存储空间
    	return true;
    }
    
    /**
     * 求单链表的长度(带头结点)
     */
    int GetLength(LinkList L) {
        
        int i = 0;
        LNode *cur = L; // 指向头结点
        while(cur->next != NULL) {
        
            i++;
            cur = cur->next;
        }
        return i;// 如果是空表，则会直接返回0
    }
    
    /**
     * 输出链表
     */
    void PrintList(LinkList L) {
        
        if(L->next == NULL) {
        
            cout << "此链表为空!" << endl;
            return;
        }
        LNode *cur = L;
        cur = cur->next;
        cout << "输出链表: ";
        while(cur != NULL) {
        
            cout << cur->data << " ";
            cur = cur->next;
        }
        cout << endl;
    }
    
    // 头插法建立单链表
    LinkList List_HeadInsert(LinkList &L) {
        
        LNode *s;
        int x;
        L = (LinkList)malloc(sizeof(LNode));// 创建头结点
        L->next = NULL;// 初始为空链表
        while (cin.peek() != '\n') {
        
        	cin >> x;
            s = (LNode *)malloc(sizeof(LNode));// 创建新结点
            s->data = x;
            s->next = L->next;
            L->next = s;
        }
        return L;
        
    }
    
    // 尾插法建立单链表
    LinkList List_TailInsert(LinkList &L) {
        
        int x;
        L = (LinkList)malloc(sizeof(LNode));// 创建头结点
        LNode *s, *r = L;// r为表尾指针
        while (cin.peek() != '\n') {
        
        	cin >> x;
            s = (LNode *)malloc(sizeof(LNode));// 创建新结点
            s->data = x;
            r->next = s;
            r = s;// r指向新的表尾结点
        }
        r->next = NULL;// 尾结点指针置空
        return L;
    }
    
    int main() {
        
    
        LinkList L; // 声明一个指向单链表的指针
        List_TailInsert(L); // 尾插法创建链表
        PrintList(L); // 打印链表
        cout << "单链表的长度为："<< GetLength(L) <<endl;
    
        LNode *p = GetElemByVal(L, 33); // 查找链表中结点值为33的结点
        if(p == NULL) cout << "未找到目标值" << endl;
        else cout << "目标值为: " << p->data << endl;
    
        LNode *q = GetElemByIndex(L,2); // 查找位序为2的结点
        if(q == NULL || (q->data)==NULL) cout << "位序2处的结点不存在。" << endl;
        else cout << "位序2处的结点值为: " << q->data << endl;
    
        if(Empty(L) == true) cout << "链表为空。" << endl;
        else cout << "链表不为空。" << endl;
    
        ListInsert(L, 1, 100);// 在位置1处插入值为100的结点
        PrintList(L);
        ListDel(L, 3);// 删除位置3处的结点
        PrintList(L);
    
        return 0;
    }

[451affb710a94018aee2a1844b0736d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b04d01ef02744700aec617cb1a7aaa7e.png