2. 考研
  3. 输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。

输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。

admin2017-01-04  81
问题 输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。
选项
答案typedef struct{ int key； int next； }SLRecType； SLRecType R[N+1]； typedef struct{ int f，e： }SLQueue； SLQueue B[10]； int Radixsort(SLRecType R[]，int n){ ／／设各关键字已输入到R数组中 for(i=1；i＜n；i++)R[i]．next=i+l； R[n]．next=一1；P=1； ／／一1表示静态链表结束 for(i=0；i＜=9：i++){ ／／设置队头队尾指针初值 B[i]．f=一1；B[i]．e=一1； } while(p!=一1){ ／／一趟分配 k=R[p]．key； ／／取关键字 if(B[k]．f==一1)B[k]．f=p； ／／修改队头指针 else R[B[k]．e]．next=p： B[k]．e=p； p=R[p]．next； ／／下一记录 } i=0： ／／一趟收集 while(B[i]．f==一1)i++； t=B[i]．e；p=B[i]f： while(i＜9){ i++： if(B[i]．f!=一1){R[t]．next=B[i]．f；t=B[i]．e：} } R[t]．next=一1； return p；／／返回第一个记录指针 } 提示：此题考查的知识点是基数排序。基数排序法又称“桶子法”(Bucket Sort)，它是透过键值的部分信息，将要排序的元素分配至某些“桶”中，达到排序的目的。基数排序法是属于稳定性的排序，其时间复杂度为O(dn)，其中d为所采取的基数，而n为关键字数。本题是基数排序的特殊情况，关键字只含一位数字的整数。若关键字含d位，则要进行d趟分配和d趟收集。关键字最好放入字符数组，以便取关键字的某位。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/nQRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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