线性表算法设计题（八）

题目

设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

算法思想

通过遍历链表能够定位待删除元素的下边界和上边界，即可找到第一个值大于mink的结点和第一个值大于等于maxk的结点。

完整代码

#include <iostream>
using namespace std;

//设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同） 

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

//创建链表
int CreateList(LinkList &L,int n){
    LNode *p,*r;
    int i;
    L = new LNode;
    L -> next = NULL;
    r = L;
    for(i = 0;i < n;i ++)
    {
        p = new LNode;
        cin >> p -> data;
        p -> next = NULL;
        r -> next = p;
        r = p;
    }
    return 0;
}

void DeleteMinMax(LinkList &L, int mink, int maxk){
    //删除递增有序链表L中值大于mink且小于maxk的所有元素 
    LinkList p, pre, q, s;
    p = L -> next;                     //p指向首元结点 
    while(p && p -> data <= mink){     //查找第一个值大于mink的结点 
        pre = p;                       //pre指向前驱结点 
        p = p -> next;
    }
    while(p && p -> data < maxk){      //查找第一个值大于等于maxk的结点 
        p = p -> next;
    }
    q = pre -> next;
    pre -> next =p;                    //修改待删除结点的指针 
    while(q != p){                     //依次释放待删除结点的空间 
        s = q -> next;
        delete q;
        q = s;
    }
} 

//输出链表
void display(LinkList L){
    LNode *p;
    p = L-> next;
    cout << "(";
    while(p){
    cout << p -> data << " ";
    p = p -> next;
    }
    cout << ")" << endl;
}

int main(){
    LinkList L;
    int n;
    int mink, maxk;
    cout << "请输入链表的长度：";
    cin >> n;
    cout << "请依次输入要存入的数据：" << endl;
    CreateList(L, n);
    cout << "链表如下：" << endl;
    display(L);
    cout << "请输入左边界：";
    cin >> mink;
    cout << "请输入有边界：";
    cin >> maxk;
    DeleteMinMax(L, mink, maxk);
    cout << "删除边界内的值之后的链表如下：" << endl;
    display(L);
    return 0;
} 

结果显示

TIM图片20191026125756.png