首页 > 其他分享 >【数据结构-链表】链表的基本操作

【数据结构-链表】链表的基本操作

时间：2022-10-27 10:02:33浏览次数：63  
标签：结点 posNode pos next 链表 newNode 基本操作 数据结构 LinkNode

目录

编写插入函数和删除函数的思路：

  • 先考虑一般情况；
  • 再考虑在链表头部的操作；
  • 最后考虑在链表尾部的操作。

1 单向链表

1.1 有头结点的单向链表

1.1.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *next;
} *LinkNode, LinkList;

1.1.2 初始化建立链表

  • 头插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = head->next; // 新结点的指针域指向头结点的后继结点
        head->next = newNode; // 头结点的指针域指向新结点
    }
    
    return L;
}
  • 尾插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}

1.1.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始指向头结点
    
    if (pos == 0) // 第 0 个结点即头结点
        return L;
    else if (pos < 0) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}

1.1.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L;
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}

1.1.5 插入操作

  • 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next;
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->next = posNode; // 新结点的指针域指向原先第 pos 个结点
    posPrev->next = newNode; // 第 pos-1 个结点的指针域指向新结点
    
    return true;
}
  • 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行伪前插操作，实质是新结点插入到第 pos 个结点的后面，然后交换数据域）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = posNode->data; // 交换数据，posNode 变为新结点，newNode 变为旧结点
    newNode->next = posNext; 
    posNode->data = x;
    posNode->next = newNode; 
    
    return true;
}

1.1.6 删除操作

  • 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next; // 记录第 pos 个结点
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    posPrev->next = posNext; // 第 pos-1 个结点的指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
    free(posNode);
    
    return true;
}
  • 删除第 pos 个结点（找到该结点即第 pos 个结点，将其后继结点的值赋值给第 pos 个结点，然后删除其后继结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posNode = GetNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
        posNode->data = posNext->data; // 将其后继结点的值赋值给第 pos 个结点
        posNode->next = posNext->next; // 更新指针域
        free(posNext);
    }
    else{ // 如果第 pos 个结点是最后一个结点
        free(posNode);
        前驱结点的指针域 = NULL; // 这里还是需要再遍历一遍链表找到前驱结点，比较麻烦
    }
    
    return true;
}

1.2 无头结点的单向链表

1.2.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *next;
} *LinkNode, LinkList;

1.2.2 初始化建立链表

  • 头插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = head;
        head = newNode; // 头指针指向新结点
        L = head; // 更新头指针（即链表的入口）
    }
    
    return L;
}
  • 尾插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}

1.2.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    if (pos < 1) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}

1.2.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}

1.2.5 插入操作

  • 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    if (pos == 1){ // 如果要插入到第 1 个位置
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = L; // 指针域指向头结点
        L = newNode; // 更新头指针（即链表的入口）
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = posNode; // 新结点的指针域指向原先第 pos 个结点
        posPrev->next = newNode; // 第 pos-1 个结点的指针域指向新结点
    }
    
    return true;
}
  • 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行伪前插操作，实质是新结点插入到第 pos 个结点的后面，然后交换数据域）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next;
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = posNode->data; // 交换数据，posNode 变为新结点，newNode 变为旧结点
    newNode->next = posNext; 
    posNode->data = x;
    posNode->next = newNode; 
    
    return true;
}

1.2.6 删除操作

  • 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0)
        return false;
    
    if (pos == 1){ // 如果要删除第 1 个结点
        posNext = L->next; // 记录第 2 个结点
        free(L);
        L = posNext; // 头指针指向第 2 个结点
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        posNext =  posNode->next; // 记录第 pos+1 个结点
        posPrev->next = posNext; // 第 pos-1 个结点的指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
        free(posNode);
    }
    
    return true;
}
  • 删除第 pos 个结点（找到该结点即第 pos 个结点，将其后继结点的值赋值给第 pos 个结点，然后删除其后继结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0)
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
        posNode->data = posNext->data; // 将其后继结点的值赋值给第 pos 个结点
        posNode->next = posNext->next; // 更新指针域
        free(posNext);
    }
    else{ // 如果第 pos 个结点是最后一个结点
        free(posNode);
        前驱结点的指针域 = NULL; // 这里还是需要再遍历一遍链表找到前驱结点，比较麻烦
    }
    
    return true;
}

2 双向链表

2.1 有头结点的双向链表

2.1.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *prev;
    LinkNode *next;
} *LinkNode, LinkList;

2.1.2 初始化建立链表

  • 头插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->prev = NULL;
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = head;
        newNode->next = head->next; // 新结点的指针域指向头结点的后继结点
        head->next = newNode; // 头结点的指针域指向新结点
    }
    
    return L;
}
  • 尾插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->prev = NULL;
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = tail;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}

2.1.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始指向头结点
    
    if (pos == 0) // 第 0 个结点即头结点
        return L;
    else if (pos < 0) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}

2.1.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L;
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}

2.1.5 插入操作

  • 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next; // 记录第 pos 个结点
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
    newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
    posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
    posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    
    return true;
}
  • 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行前插操作）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posPrev = posNode->prev; // 记录第 pos-1 个结点
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
    newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
    posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
    posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    
    return true;
}

2.1.6 删除操作

  • 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next; // 记录第 pos 个结点
    posNext = posNode->next; // 记录第 pos+1 个结点
    posPrev->next = posNext; // 第 pos-1 个结点的后继指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
    posNext->prev = posPrev; // 第 pos+1 个结点的前驱指针域指向原先第 pos 个结点的前驱结点（即原先第 pos-1 个结点）
    free(posNode);
    
    return true;
}
  • 删除第 pos 个结点（找到该结点即第 pos 个结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    posPrev = posNode->prev; // 记录第 pos-1 个结点
    
    if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
        posPrev->next = posNext;
        posNext->prev = posPrev;
        free(posNode);
    }
    else{ // 如果第 pos 个结点是最后一个结点
        posPrev->next = NULL;
        free(posNode);
    }
    
    return true;
}

2.2 无头结点的双向链表

2.2.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *prev;
    LinkNode *next;
} *LinkNode, LinkList;

2.2.2 初始化建立链表

  • 头插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->prev = NULL;
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = NULL;
        newNode->next = head;
        head = newNode; // 头指针指向新结点
        L = head; // 更新头指针（即链表的入口）
    }
    
    return L;
}
  • 尾插法：
LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->prev = NULL;
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = tail;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}

2.2.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    if (pos < 1) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}

2.2.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}

2.2.5 插入操作

  • 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要插入到第 1 个位置
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = NULL;
        newNode->next = L;
        L = newNode; // 更新头指针（即链表的入口）
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
        newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
        posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
        posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    }
    
    return true;
}
  • 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行前插操作）：
bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posPrev; // 记录第 pos+1 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要插入到第 1 个位置
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = NULL;
        newNode->next = L;
        L = newNode; // 更新头指针（即链表的入口）
    }
    else{
        posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
        if (posPrev == NULL)
            return false;
        posPrev = posNode->prev; // 记录第 pos-1 个结点
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
        newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
        posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
        posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    }
    
    return true;
}

2.2.6 删除操作

  • 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要删除第 1 个结点
        posNext = L->next; // 记录第 2 个结点
        free(L);
        L = posNext; // 更新头指针（即链表的入口）
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        posNext = posNode->next; // 记录第 pos+1 个结点
        posPrev->next = posNext; // 第 pos-1 个结点的后继指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
        posNext->prev = posPrev; // 第 pos+1 个结点的前驱指针域指向原先第 pos 个结点的前驱结点（即原先第 pos-1 个结点）
        free(posNode);
    }
    
    return true;
}
  • 删除第 pos 个结点（找到该结点即第 pos 个结点）：
bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要删除第 1 个结点
        posNext = L->next; // 记录第 2 个结点
        free(L);
        L = posNext; // 更新头指针（即链表的入口）
    }
    else{
        posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
        if (posNode == NULL)
            return false;
        posNext = posNode->next; // 记录第 pos+1 个结点
        posPrev = posNode->prev; // 记录第 pos-1 个结点
        
        if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
            posPrev->next = posNext;
            posNext->prev = posPrev;
            free(posNode);
        }
        else{ // 如果第 pos 个结点是最后一个结点
            posPrev->next = NULL;
            free(posNode);
        }
    }
    
    return true;
}

标签：结点,posNode,pos,next,链表,newNode,基本操作,数据结构,LinkNode
From： https://www.cnblogs.com/Mount256/p/16831113.html

相关文章

  • 链表——删除链表倒数第n个节点
    classSolution{public: ListNode*deleteback(ListNode*head,intn) { ListNode*dummyHead=newListNode(0); dummyHead->next=head; ListNode*fast......
  • 数据结构：7种哈希散列算法，你知道几个？
    作者：小傅哥博客：https://bugstack.cn沉淀、分享、成长，让自己和他人都能有所收获！......
  • 数据结构 玩转数据结构 3-8 数组队列和循环队列的比较
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13425 1重点关注1.1数组队列和循环队列的比较循环队列出队的复杂度循环队列为O(1......
  • 数据结构 玩转数据结构 3-7 循环队列的实现
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13424 1重点关注1.1循环队列代码实现（出队复杂度为O(1)）见3.1 2课程内......
  • gcc基本操作
    25P-gcc编译4步骤26P-gcc编译常用参数当头文件和源码不在一个目录下时，需要指定头文件下图是头文件和源码在同一个目录下将hello.h放入新建的文件夹hellodir之后，编译会失败g......
  • gdb调试基本操作
    38P-gdb调试基础指令使用gdb之前，要求对文件进行编译时增加-g参数，加了这个参数过后生成的编译文件会大一些，这是因为增加了gdb调试内容gdb调试工具：大前提：程序是你自己写的......
  • Linux基本操作
    01P-Linux命令基础习惯-Linux系统编程date显示系统当前时间cat/etc/shells 查看当前可使用的shellecho$SHELL 查看当前使用的shell主键盘快捷键：上 Ctrl-p 下 Ct......
  • Vim基本操作
    18P-vim的三种工作模式19P-vim基本操作-跳转和删字符i进入编辑模式，光标前插入字符a进入编辑模式，光标后插入字符o进入编辑模式，光标所在行的下一行插入I进入编辑模式，光标......
  • 单链表翻转
    使用语言：c++。#include<iostream>usingnamespacestd;//链表structListNode{intval;ListNode*next;ListNode(intval,ListNode*next=NULL):val(val),......
  • 链表--链表平均分割成几个子链表的方案
    725. SplitLinkedListinPartsMedium36682FavoriteShareGivena(singly)linkedlistwithheadnode ​​root​​​,writeafunctiontosplitthelinkedlisti......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99