现设计该线性表的如下存储结构： 0.顺序表 1.带头结点的单链表 2.带头结点的循环单链表 3.不带头结点仅有尾结点指针标识的循环单链表 4.带头结点的双链表 5.带头结点的循环双链表 （1）请分别指出各种存储结构中对应运算算法的时间复杂度。 （2）学号最后两位被6整除余数为几，就请在第几种存储结构下实现运算A、B、E、H。

（1）各种存储结构中对应运算算法的时间复杂度如下：

0. 顺序表
a. 访问元素：O(1)
b. 插入元素：最好情况O(1)，最坏情况O(n)，平均情况O(n)
c. 删除元素：最好情况O(1)，最坏情况O(n)，平均情况O(n)
1. 带头结点的单链表
a. 访问元素：O(n)
b. 插入元素：O(1)
c. 删除元素：O(1)
2. 带头结点的循环单链表
a. 访问元素：O(n)
b. 插入元素：O(1)
c. 删除元素：O(1)
3. 不带头结点仅有尾结点指针标识的循环单链表
a. 访问元素：O(n)
b. 插入元素：O(1)
c. 删除元素：O(1)
4. 带头结点的双链表
a. 访问元素：O(n)
b. 插入元素：O(1)
c. 删除元素：O(1)
5. 带头结点的循环双链表
a. 访问元素：O(n)
b. 插入元素：O(1)
c. 删除元素：O(1)

（2）如果学号最后两位被6整除余数为0，则在第0种顺序表中实现运算A、B、E、H；如果余数为1，则在第1种带头结点的单链表中实现运算A、B、E、H；如果余数为2，则在第2种带头结点的循环单链表中实现运算A、B、E、H；如果余数为3，则在第3种不带头结点仅有尾结点指针标识的循环单链表中实现运算A、B、E、H；如果余数为4，则在第4种带头结点的双链表中实现运算A、B、E、H；如果余数为5，则在第5种带头结点的循环双链表中实现运算A、B、E、H。

相关问题

逆位序输入线性表的n个数据元素，编写建立带头结点的单链表的算法

好的，下面是建立带头结点的单链表的算法，具体实现可以参考以下代码：

ListNode* createList(int n){
    ListNode* head = new ListNode(0); // 创建头结点
    ListNode* p = head;
    for(int i = n; i > 0; i--){
        int value;
        cin >> value; // 逆位序输入数据元素
        ListNode* node = new ListNode(value);
        node->next = p->next;
        p->next = node;
    }
    return head;
}

解释一下这个算法的实现过程：

1. 创建头结点，值为 0。
2. 定义一个指针 p，指向头结点。
3. 循环 n 次，每次输入一个数据元素，创建一个值为该数据元素的结点 node。
4. 将新结点 node 插入到头结点和指针 p 之间，即 node->next = p->next，p->next = node。
5. 返回头结点 head。

由于是逆位序输入数据元素，因此需要在创建新结点时将其插入到链表的头部，保证最后创建出来的链表中数据元素的顺序为输入时的顺序。

已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。

### 回答1：
算法步骤如下：

1. 定义指针p和q，分别指向头结点和第一个元素节点。

2. 从头结点开始遍历链表，当q指向的元素值大于等于min时，停止遍历。

3. 将p指向q，q指向p的下一个节点，即第二个元素节点。

4. 从q开始遍历链表，当q指向的元素值大于等于max时，停止遍历。

5. 将p的next指针指向q，即删除了所有值大于min且小于max的元素。

6. 返回头结点。

算法实现如下：

LinkList DeleteRange(LinkList L, int min, int max) {
    ListNode *p = L, *q = L->next;
    while (q && q->data < min) {
        p = q;
        q = q->next;
    }
    p->next = q;
    q = q->next;
    while (q && q->data < max) {
        q = q->next;
    }
    p->next = q;
    return L;
}

### 回答2：
要删除线性表中所有值大于min且小于max的元素，我们可以考虑遍历整个链表，对每一个元素都进行检查操作。如果这个元素的值更大或更小，那么我们就将其删除即可。

具体地，我们可以从链表的第一个元素开始遍历，在遍历的过程中记录当前元素的前一个结点pre和当前结点cur。如果当前结点的值大于min且小于max，那么我们就删除这个节点，然后将pre的next指向cur的next，即pre->next=cur->next。

遍历结束后，我们就能够删除所有符合条件的元素。下面给出具体的算法实现：

void delete_range(LinkList &L, int min, int max) {
    LNode *pre = L, *cur = L->next;
    while (cur != NULL) {
        if (cur->data > min && cur->data < max) {
            pre->next = cur->next;
            free(cur);
            cur = pre->next;
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
}

其中，L是带头结点的单链表，min和max分别是范围的下界和上界。我们在while循环中遍历整个链表，检查每一个结点的值是否符合要求。如果符合，那么就进行删除操作；否则，我们就将pre和cur往后移动，继续检查下一个元素。

最后，我们就能够得到删除后的链表。这个算法的时间复杂度为O(n)，其中n是链表的长度。

### 回答3：
算法思路：

1. 定位要删除的元素范围：根据输入的min和max值，遍历线性表，定位第一个大于等于min的元素和最后一个小于等于max的元素。这里可以用两个指针来实现，分别从表头遍历，直到找到大于等于min的元素时记录下该节点（preMin），继续往后遍历，直到找到小于等于max的元素，记录下该节点（postMax）。如果找不到符合要求的元素，则直接返回。

2. 删除范围内的元素：从preMin节点的下一个节点开始，一直遍历到postMax节点的前一个节点为止，依次删除这些节点即可。

代码实现：

void deleteRange(LinkList &L, int min, int max) {
    LNode *preMin = L, *postMax = L->next;
    // 定位删除范围
    while (preMin->next != NULL && preMin->next->data < min) {
        preMin = preMin->next;
    }
    if (preMin->next == NULL) {
        return;
    }
    postMax = preMin->next;
    while (postMax != NULL && postMax->data <= max) {
        postMax = postMax->next;
    }
    // 删除范围内的元素
    LNode *p = preMin;
    while (p->next != postMax) {
        LNode *q = p->next;
        p->next = q->next;
        delete q;
    }
}

注意事项：

1. 删除节点时需要注意内存泄漏，要记得释放删除的节点。

2. 在定位删除范围时，要注意链表中可能不存在符合要求的元素，需要对这种情况进行特判。