已知线性表中的元素以值递增有序,并以单链表作存储结构。试写一高效的算法,删除有序表中所有其值大于 mink 且小于maxk的数据元素。
时间: 2023-05-03 16:00:53 浏览: 107
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
题目要求删除程序表中所有元素值大于mink且小于maxk的数据元素。可能的算法有很多种,以下是其中一种高效的算法:
将链表头指针p指向程序表的第一个节点,用q指向p的后继节点。用r指向p,然后开始遍历整个链表:
1. 如果q节点的元素值大于等于mink且小于等于maxk,则将r的后继指针指向q的后继节点,同时删除q节点。
2. 如果q节点的元素值小于mink,则p指向q,q指向q的后继节点,r不变。
3. 如果q节点的元素值大于maxk,则r指向q,q指向q的后继节点,p不变。
4. 重复以上操作,直到q指向链表尾节点。
最后返回链表头指针p。
这个算法的时间复杂度是O(n),其中n是程序表中的元素个数。
阅读全文