已知线性表中的元素(整数)以值递增有序排列,并以单链表作为存储结构。试用c++语言编写一个高效算法,实现删除表中所有大于mink 且小于 maxk 的元素(若表中存在这样的元素),分析所设计算法的时间复杂度(注意mink 和maxk是给定的两个参变量,它们的值为任意的整数)。
时间: 2023-05-14 11:06:18 浏览: 52
可以使用双指针法来实现删除表中所有大于mink且小于maxk的元素。具体步骤如下:
1. 定义两个指针p和q,初始时p指向表头,q指向p的后继节点。
2. 从头开始遍历整个链表,如果q指向的节点的值大于等于mink且小于等于maxk,则将q节点删除,并将p的next指针指向q的后继节点,即p->next = q->next。
3. 如果q指向的节点的值小于mink,则将p指针向后移动一位,即p = q。
4. 如果q指向的节点的值大于maxk,则将q指针向后移动一位,即q = q->next。
5. 重复步骤2-4,直到q指向链表尾部。
时间复杂度为O(n),其中n为链表的长度。
相关问题
已知线性表中的元素(整数)以值递增有序排列,并以单链表作为存储结构。试用c++语言编写一个高效算法,删除表中所有大于mink 且小于 maxk 的元素(若表中存在这样的元素),分析所设计算法的时间复杂度(注意mink 和maxk是给定的两个参变量,它们的值为任意的整数)。
可以使用双指针法来解决这个问题。定义两个指针,一个指向当前节点,一个指向前一个节点,遍历整个链表,如果当前节点的值大于mink且小于maxk,则将前一个节点的next指向当前节点的next,即删除当前节点。如果当前节点的值不在这个范围内,则将两个指针都向后移动一个节点。最后返回链表的头节点即可。
时间复杂度为O(n),其中n为链表的长度。
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写两个不同的算法,删除表中所有值大于 mink 且小于 maxk 的元素,同时释放被删结点空间
算法1:
1. 找到第一个值大于等于 mink 的结点 p,将其前驱结点记为 prev。
2. 从 p 开始遍历链表,找到第一个值大于 maxk 的结点 q,将其前驱结点记为 last。
3. 将 prev 的 next 指针指向 last 的 next 指针,释放 p 到 last 之间的所有结点空间。
示例代码:
```
void deleteRange1(LinkList L, ElemType mink, ElemType maxk) {
Node *prev = L, *p = L->next;
while (p != NULL && p->data < mink) {
prev = p;
p = p->next;
}
Node *last = p;
while (last != NULL && last->data <= maxk) {
last = last->next;
}
prev->next = last;
while (p != last) {
Node *tmp = p;
p = p->next;
free(tmp);
}
}
```
算法2:
1. 创建一个新的头结点 newHead,并将其 next 指针指向原链表的头结点。
2. 找到第一个值大于等于 mink 的结点 p,将其前驱结点记为 prev。
3. 从 p 开始遍历链表,找到第一个值大于 maxk 的结点 q,将其前驱结点记为 last。
4. 将 prev 的 next 指针指向 last 的 next 指针,从 p 开始,释放被删结点空间。
示例代码:
```
void deleteRange2(LinkList L, ElemType mink, ElemType maxk) {
Node *newHead = (Node*)malloc(sizeof(Node));
newHead->next = L;
Node *prev = newHead, *p = L;
while (p != NULL && p->data < mink) {
prev = p;
p = p->next;
}
Node *last = p;
while (last != NULL && last->data <= maxk) {
last = last->next;
}
prev->next = last;
while (p != last) {
Node *tmp = p;
p = p->next;
free(tmp);
}
L = newHead->next;
free(newHead);
}
```