C++ 单链表操作：查询、插入、删除函数实现

本文将介绍如何使用 C++ 语言编写三个函数，分别实现单链表（带头结点）的查询、插入和删除操作。

函数接口定义

int  Get_LinkList(LinkList H, ElemType key)；//H为单链表的头指针，key为待查找的值；
Status ListInsert(LinkList &H,int i,ElemType e)；//H为单链表的头指针，i为插入位置，e为新插入的值；
Status ListDelete(LinkList &H,int i)；//H为单链表的头指针，i为删除位置

数据结构定义

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

其中，LNode 为单链表的结点类型，LinkList 为指向单链表的指针类型。

函数实现

1. 查询函数

// 查询函数，查找单链表中是否存在指定值的结点
int Get_LinkList(LinkList H, ElemType key){
    LNode *p = H->next;
    int i = 1;
    while(p != NULL){
        if(p->data == key){
            return i;
        }
        p = p->next;
        i++;
    }
    return -1;  // 未找到
}

该函数从头结点开始遍历单链表，逐个比较结点数据与 key 的值。若找到匹配的结点，则返回该结点在链表中的位置（从 1 开始计数）。若未找到，则返回 -1。

2. 插入函数

// 插入函数，在指定位置插入新的结点
Status ListInsert(LinkList &H,int i,ElemType e){
    LNode *p = H;
    int j = 0;
    while(p != NULL && j < i-1){
        p = p->next;
        j++;
    }
    if(p == NULL || j > i-1){
        return ERROR;  // 插入位置非法
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

该函数先找到插入位置的前一个结点，然后创建一个新的结点，并将新结点的 data 设置为 e，next 指针指向插入位置的原结点。最后，将前一个结点的 next 指针指向新结点。

3. 删除函数

// 删除函数，删除指定位置的结点
Status ListDelete(LinkList &H,int i){
    LNode *p = H;
    int j = 0;
    while(p != NULL && j < i-1){
        p = p->next;
        j++;
    }
    if(p == NULL || j > i-1 || p->next == NULL){
        return ERROR;  // 删除位置非法
    }
    LNode *q = p->next;
    p->next = q->next;
    free(q);
    return OK;
}

该函数先找到要删除结点的前一个结点，然后将前一个结点的 next 指针指向要删除结点的下一个结点，最后释放要删除结点的内存空间。

总结

本文介绍了 C++ 实现单链表的查询、插入和删除操作的代码示例。希望这些代码能够帮助您理解单链表的基本操作。在实际应用中，您需要根据具体的需求对这些代码进行修改和完善。