已知线性表中的元素以值递增有序排列，并一单链表作存储结构。试写一高效的算法，删除表中所有值大于 mink 且小于 maxk 的元素，并释放其内存空间。

NOTICE: 代码是按照源码顺序依次贴上来的，直接复制就能跑！

环境：

Visual Stdio Code

 

题目：

已知线性表中的元素以值递增有序排列，并一单链表作存储结构。试写一高效的算法，删除表中所有值大于 mink 且小于 maxk 的元素 (若表中存在这样的元素)，同时释放被删除节点空间。（注意：mink 和 maxk 是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同）

分析：

先遍历找到这些节点(只需要找到从首元结点到第一个 data 域大于等于 maxk 的节点就行)，再找到第一个 data 域大于等于 mink 的节点，并让该节点指向他的 next->next 同时释放该节点的 next 的内存空间。（有点儿难以理解，没关系，接下来我会在代码中注释，我觉得代码比这些文字要好理解一些.....）。

代码：

初始化单链表：

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct LNode
{
    ElemType data;   // 数据域
    LNode *next;     // 指针域
}LNode, *LinkList;

Status InitList(LinkList &L)
{   // 初始化单链表 L
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;

    return OK;
}// InitList

创建单链表：

Status CreateList(LinkList &L, int e)
{   // 创建单链表 L
    LinkList p = L;
    while(p->next)
        p = p->next;
    LinkList temp = (LinkList)malloc(sizeof(LNode));
    temp->data = e;
    temp->next = NULL;
    p->next = temp;

    return OK;
}// CreateList

打印单链表：

Status DispList(LinkList &L)
{   // 打印单链表
    LinkList p = L->next;
    int i = 0;
    while(p)
    {
        printf("%d\t", p->data);
        i ++;
        p = p->next;
    }
    return OK;
}// DispList

删除相关节点：

Status DeleteMiddleElem(LinkList &L, int mink, int maxk)
{   // 删除单链表中大于 mink 到小于 maxk 之间的数据元素
    LinkList p, q, prev=NULL;
    if(mink > maxk) return ERROR;      // mink，maxk 大小不合法
    p = L;
    prev = p;       // prev 指向头结点
    p = p->next;  // 为了保证 prev 指向 p 的直接前驱节点

    while(p && p->data < maxk)          // 只需要遍历从首元结点到 data 域为 maxk 节点的数据元素
    {
        if(p->data <= mink)       
        {
            prev = p;              // prev 指向第 1 个 data 域 大于等于 mink 的节点
            p = p->next;
         } 
        else                      // data 域大于 mink  
        { 
            prev->next = p->next;       // prev(指向 mink)指向 p 的直接后继节点
            q = p;
            p = p->next; 
            free(q);             // 释放内存空间
        }
    }

    return OK;

}// DeleteMiddleElem

说明：在该函数中可以看出，prev 始终指向 p 的直接前驱节点，其目的就是：将 prev 指向最后一个 data 域小于或等于 mink ，方便之后的删除操作。当 p->data > mink 时，将 prev 不断地与 p 的直接后继节点连接，同时利用 q = p，free(q) 来删除已经被移除单链表 L 的节点。

主函数：

int main()
{
    int i;
    LinkList L;

    InitList(L);

    for(i=1;i<=10; i++)
        CreateList(L, i);
    
    DispList(L);

    DeleteMiddleElem(L, 1, 4.5);

    printf("\n");
    DispList(L);

    return OK;
}

END