2. 考研
  3. 直接插入排序法的基本思想是：对于参加排序的原始序列(k0,1，k0,2，…，k0,n)，第i趟排序将序列的第i+1个元素插入到大小为i、且已经按值有序的子序列(ki-1,1，ki-1,2，…，ki-1,i)的合适位置，得到一个大小为i+l、且仍然按值有序的

直接插入排序法的基本思想是：对于参加排序的原始序列(k0,1，k0,2，…，k0,n)，第i趟排序将序列的第i+1个元素插入到大小为i、且已经按值有序的子序列(ki-1,1，ki-1,2，…，ki-1,i)的合适位置，得到一个大小为i+l、且仍然按值有序的

admin2014-07-18  66
问题 直接插入排序法的基本思想是：对于参加排序的原始序列(k0,1，k0,2，…，k0,n)，第i趟排序将序列的第i+1个元素插入到大小为i、且已经按值有序的子序列(ki-1,1，ki-1,2，…，ki-1,i)的合适位置，得到一个大小为i+l、且仍然按值有序的子序列(ki,1，ki,2，…，ki,i+1)，其中，ki,j表示第j趟排序结束时序列的第j个元素，1≤i≤n-1，1≤j≤n。已知一个整数序列的各元素依次存放于无头结点的非循环双向链表的各链结点。链结点构造为：第一个链结点的指针为lisl，请写出直接插入排序算法。算法中不得使用任何新的链结点空间，也不允许出现修改链结点数据域内容的动作。
  (1)给出算法的主要思想；
  (2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。
选项
答案(1)本题实际上是通过修改双向链表的指针实现直接插入排序。 (2)算法的实现过程如下： void insertion(LinkList*list){ LinkNode *P，*q； int min； ／／min用来记录链表中的最小值 P=list； if(P==null)return； ／／空表的情况 q=list->next： if(q==null) retum； ／／只有一个结点的情况 if(q->datadata： P->next=q->next； ／／插入排序修改指针 q->next->prior=P： q->next=P： list=q； }／／第一个结点的处理 P=list； q=P->next： min=P->data： while(q!=null){ ／／非首元素的链结点的处理 if(q->datadata； P->next=q->next： q->next->prior=P： q->next=P： q=P->next： } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/Qaxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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