应用题 6.已知单链表L是一个递增有序表,试写一高效算法,删除表中值大于min且小于max的结点(若表中有这样的结点),同时释放被删结点的空间,这里min和max是两个给定的参数。
【正确答案】struet node{
Datatype data;
struet node * next;
}ListNode;
typedef ListNode * LinkList;
void DeleteList(LinkList L,DataType min,DataType max){
ListNode * p, *q, *h;
p=L一>next: //采用代表头结点的单链表
while(p&&p一>data<=min){ //找比rain大的前一个元素位置
q=p;
p=p一>next;
}
p=q: //保存这个元素位置
while(q&&q->data<max)q=q一>next;//找比max小的最后一个元素位置
while(p一>next!=q){
h=p一>next;
p=p一>next;
free(h); //释放空间
}
p一>next=q; //把断点链上
}
提示:首先想到的是拿链表中的元素一个个地与max和min比较,然后删除这个结点。其实因为已知其是有序链表,所以只要找到大于min的结点的直接前趋结点,再找到小于max的结点,然后一并把中间的全部摘掉就可以了。
【答案解析】