C语言数据结构-链表删除范围内结点

àì夳堔傛蜴生んèń 2022-10-23 04:58 100阅读 0赞

# 链表删除范围内结点 #

已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。

链表结点定义如下：

struct _lnklist{
        ElemType data;
        struct _lnklist *next;
    };
    typedef struct _lnklist Node;
    typedef struct _lnklist *LinkList;

函数原型如下：  
`void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)`

其中L指向链表的头结点。

### 提供代码 ###

#include <stdio.h>
    #include <stdlib.h>
    #include "list.h" // 请不要删除，否则检查不通过
    
    void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk) {
    
    }

### 参考代码 ###

/*
    链表 删除范围内结点
    
    已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。
    试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），
    分析你的算法的时间复杂度。
    链表结点定义如下：
    
    struct _lnklist{
        ElemType data;
        struct _lnklist *next;
    };
    typedef struct _lnklist Node;
    typedef struct _lnklist *LinkList;
    
    函数原型如下：
    void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)
    其中L指向链表的头结点。
    */
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    //#include "list.h" // 请不要删除，否则检查不通过
    #define ElemType int
    
    struct _lnklist {
        ElemType data;
        struct _lnklist* next;
    };
    typedef struct _lnklist Node;
    typedef struct _lnklist* LinkList;
    
    //L指向链表的头结点
    void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)
    {
        LinkList left = NULL;
        LinkList right = NULL;
        LinkList tmp = NULL;
        //找到左指针
        while (L->next != NULL)
        {
            if ((L->next->data > mink) && (L->next->data < maxk))
            {
                left = L;
                L = L->next;
                break;
            }
            else
            {
                L = L->next;
            }
        }
        //找到右指针
        while (L->next != NULL)
        {
            if ((L->data > mink) && (L->data < maxk))
            {
                tmp = L;
                L = L->next;
                free(tmp);
            }
            else
            {
                right = L;
                break;
            }
        }
        if (right == NULL) return;
        left->next = right;
    }
    
    LinkList creatList(int m)
    {
        LinkList Head = (LinkList)malloc(sizeof(Node) * 2);
        if (Head == NULL) return NULL;
        Head->data = m;
        Head->next = NULL;
        return Head;
    }
    void pushByEnd(LinkList L, int n)
    {
        LinkList Node = (LinkList)malloc(sizeof(Node) * 2);
        if (Node == NULL) return;
    
        while (L->next != NULL)
        {
            L = L->next;
        }
    
        L->next = Node;
        Node->data = n;
        Node->next = NULL;
    }
    
    
    void print(LinkList L)
    {
        while (L->next != NULL)
        {
            printf("%d", L->data);
            L = L->next;
        }
        printf("%d", L->data);
        printf("\n");
    }
    
    int main()
    {
        int mink,maxk;
        printf("请输入最小值:>");
        scanf("%d", &mink);
        printf("请输入最大值:>");
        scanf("%d", &maxk);
        printf("请输入从大到小的链表，按回车输入下一个数字，按ctrl+z结束输入:>\n");
        int m = 0;
        scanf("%d", &m);
        LinkList L = creatList(m);
        if (L == NULL) return;
        int n = 0;
        while (scanf("%d", &n) != EOF)
        {
            pushByEnd(L, n);
        }
        print(L);
    
        lnk_del_x2y(L, mink, maxk);
    
    
        print(L);
        return 0;
    }
    /*
    请输入最小值:>2
    请输入最大值:>4
    请输入从大到小的链表，按回车输入下一个数字，按ctrl+z结束输入:>
    5
    4
    3
    2
    1
    ^Z
    ^Z
    ^Z
    54321
    5421
    */