已知一个带有头结点的单链表L,其结点结构由两部分组成:数据域data,指针域link。设计一个算法,以最高效的方法实现在单链表中删除数据域最小值结点。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处

admin2019-01-16  29

问题 已知一个带有头结点的单链表L,其结点结构由两部分组成:数据域data,指针域link。设计一个算法,以最高效的方法实现在单链表中删除数据域最小值结点。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。

选项

答案(1)算法的基本思想:单链表中删除结点,为使结点删除后不出现“断链”,应知道被删结点的前驱。而 “最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表,求得最小值结点及其前驱。遍历 结束后再执行删除操作。 (2)算法的设计如下: 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一>datadata){pre=P; q=P一>nexti} //查最小值结点 P=P一>next; //指针后移 } pre一>next=q一>next; //从链表上删除最小值结点 free(q); //释放最小值结点空间 }//结束算法delete

解析
转载请注明原文地址:https://kaotiyun.com/show/kYRi777K
0

相关试题推荐
最新回复(0)