2. 考研
  3. 有一个不带头结点的单链表list，链表中结点都有两个域：数据域data和指针域Iink。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)

有一个不带头结点的单链表list，链表中结点都有两个域：数据域data和指针域Iink。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)

admin2017-01-04  71
问题 有一个不带头结点的单链表list，链表中结点都有两个域：数据域data和指针域Iink。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求：
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
选项
答案(1)算法的基本设计思想：本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 (2)算法设计如下： typedef struct LNode{ int data； struct LNode *link； }*linkedlist； LinkedList LinkListSort(LinkedList list){ Lnode*p，*q； p=list一＞link； ／／p是工作指针，指向待排序的当前元素 list一＞link=null； ／／假定第一个元素有序，即链表中现只有一个结点 while(P!=null)f r=p一＞link； ／／r是P的后继 q=list； if(q一＞data＞p一＞data){ ／／处理待排序结点P比第一个元素结点小的情况 p一＞link=list： list=p；／／链表指针指向最小元素 } else{ ／／查找元素值最小的结点 while(q一＞link==null&&q一＞link一＞data＜p一＞data)q=q一＞link； p一＞link=q一＞link；／／将当前排序结点链入有序链表中 q一＞link=P； } P=r； ／／p指向下个待排序结点 } }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/YhRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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