題目

設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同）。

算法思想

通過遍歷鏈表能夠定位待刪除元素的下邊界和上邊界，即可找到第一個(gè)值大于mink的結(jié)點(diǎn)和第一個(gè)值大于等于maxk的結(jié)點(diǎn)。

完整代碼

#include <iostream>
using namespace std;

//設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同） 

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

//創(chuàng)建鏈表
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指向首元結(jié)點(diǎn) 
    while(p && p -> data <= mink){     //查找第一個(gè)值大于mink的結(jié)點(diǎn) 
        pre = p;                       //pre指向前驅(qū)結(jié)點(diǎn) 
        p = p -> next;
    }
    while(p && p -> data < maxk){      //查找第一個(gè)值大于等于maxk的結(jié)點(diǎn) 
        p = p -> next;
    }
    q = pre -> next;
    pre -> next =p;                    //修改待刪除結(jié)點(diǎn)的指針 
    while(q != p){                     //依次釋放待刪除結(jié)點(diǎn)的空間 
        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 << "請依次輸入要存入的數(shù)據(jù)：" << endl;
    CreateList(L, n);
    cout << "鏈表如下：" << endl;
    display(L);
    cout << "請輸入左邊界：";
    cin >> mink;
    cout << "請輸入有邊界：";
    cin >> maxk;
    DeleteMinMax(L, mink, maxk);
    cout << "刪除邊界內(nèi)的值之后的鏈表如下：" << endl;
    display(L);
    return 0;
} 

結(jié)果顯示

TIM圖片20191026125756.png