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

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

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

计算机408

学硕统考专业

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