已知线性表中的元素按值递增有序排列,用带头结点的单链表L表示,现设计算法删除其中重复的多余元素并释放所占空间 typedef struct lnode { elemtpdata; struct lnode* next; } lnode, * linklist; void dessame ( linklist &L ) { }
时间: 2024-03-16 17:45:41 浏览: 23
可以使用双指针法,一个指针p指向当前处理的节点,另一个指针q指向p的后继节点,如果p的值等于q的值,则将q节点从链表中删除,释放其空间,否则将p指向q继续处理下一个节点。
具体实现如下:
```
void dessame(linklist &L) {
if (L == NULL || L->next == NULL) {
return;
}
lnode *p = L->next;
while (p != NULL) {
lnode *q = p->next;
if (q != NULL && p->data == q->data) {
p->next = q->next;
free(q);
} else {
p = q;
}
}
}
```
其中,如果链表本身为空或只有一个节点,则直接返回,否则从第二个节点开始处理。如果p的后继节点q存在且值相等,则删除q节点并将p的next指针指向q的后继节点;否则将p指向q的后继节点继续处理下一个节点。
相关问题
已知线性表中的元素以值递增有序排列,并以单链表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);
}
```