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

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

admin2019-08-01  60
问题 已知一个带有头结点的单链表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一＞data＜q一＞data){pre=P； q=P-＞next；} ／／查最小值结点 p=p一＞next； ／／指针后移 } pre一＞next=q-＞next； ／／从链表上删除最小值结点 free(q)： ／／释放最小值结点空间 }／／结束算法delete
解析
转载请注明原文地址:https://kaotiyun.com/show/iCCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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