已知带头结点单链表中各结点的元素值为整形且递增有序,设计算法删除链表中所有大于mink且小于maxk的元素,并释放被删结点的空间
时间: 2023-05-29 21:07:26 浏览: 131
1. 初始化指针p为头结点,q为p的后继结点。
2. 如果q非空,则执行以下操作:
a. 如果q的元素值大于mink且小于maxk,则将p的后继结点指向q的后继结点,释放q结点的空间;
b. 否则,将p指向q,q指向p的后继结点。
3. 返回头结点。
代码实现如下:
```
void deleteRange(Node* head, int mink, int maxk) {
Node* p = head;
Node* q = p->next;
while (q != NULL) {
if (q->data > mink && q->data < maxk) {
p->next = q->next;
free(q);
q = p->next;
} else {
p = q;
q = p->next;
}
}
}
```
相关问题
已知线性表中的元素以值递增有序排列,并以单链表3作存储结构。试写一算法,删除表中所有值大于 mink 且小于 maxk 的元素,同时释放被删结点空间
算法思路:
遍历整个链表,找到值大于 mink 且小于 maxk 的结点,将其删除。
删除结点时需要注意:
- 删除头结点时,需要将头指针指向下一个结点。
- 删除非头结点时,需要将前一个结点的指针指向当前结点的下一个结点。
同时,需要释放删除结点的空间。
算法实现:
```
void deleteRange(LinkList &L, int mink, int maxk) {
LNode *p = L->next; // 指向第一个结点
LNode *pre = L; // 指向第一个结点的前一个结点
while (p != NULL) {
if (p->data > mink && p->data < maxk) {
pre->next = p->next; // 删除结点
free(p); // 释放空间
p = pre->next; // 指向下一个结点
} else {
pre = p; // 指向下一个结点
p = p->next;
}
}
}
```
注意:以上代码中,假设头结点的值为 -1。
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写两个不同的算法,删除表中所有值大于 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);
}
```