应用题
已知一个带有头结点的单链表L,其结点结构由两部分组成:数据域data,指针域link。设计一个算法,以最高效的方法实现在单链表中删除数据域最小值结点。要求:
问答题
42.给出算法的基本设计思想。
【正确答案】算法的基本思想:单链表中删除结点,为使结点删除后不出现“断链”,应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表,求得最小值结点及其前驱。遍历结束后再执行删除操作。
【答案解析】
问答题
43.根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
【正确答案】算法的设计如下:
typedef struct LNode{
int data;
struct LNode:*next;
}LNode *Linkedlist;
LinkedList Delete(LinkedList L){//L是带头结点的单链表,本算法删除其最小值结点
Linkedlist*P,*q,*pre;
p=L一>next; //p为工作指针,指向待处理的结点。假定链表非空
pre:L; //pre指向最小值结点的前驱
q=p; //q指向最小值结点,初始假定第一元素结点是最小值结点
while(p->next!=null){
if(p一>next一>data<q一>data){pre=P; q=P一>next;} //查最小值结点
P=P->next: //指针后移
}
pre一>next=q->next: //从链表上删除最小值结点
free(q); //释放最小值结点空间
}//结束算法delete
【答案解析】