数据结构与算法实验练习（四）（排序及线性表的应用）

数据结构与算法分析课下实验练习，现记录一下解答过程，欢迎大家批评指正。

声明：本题目来源于西安交通大学电信学院原盛老师，任何单位或个人在使用、转载或引用本题目时，请务必标明出处为“西安交通大学电信学院原盛老师”。

练习四：关于队列-基数排序的扩展

---

利用队列实现对某一个数据序列的排序（采用基数排序），对数据序列的数据（第 1 和第 2 条进行说明）有如下的要求：

1. 当数据序列是整数类型的数据的时候，数据序列中每个数据的位数不要求等宽，比如：

1、21、12、322、44、123、2312、765、56

2. 当数据序列是字符串类型的数据的时候，数据序列中每个字符串都是等宽的，比如：

"abc","bde","fad","abd","bef","fdd","abe"

---

第一问

本题是利用基数排序进行的。

基数排序即从个位开始排序，然后排十位，百位等，最后得到一个排序好的结果。

在进行基数排序之前，我们还要先创建队列数据类型。 然后创建 10 个队列并将其放进一个数组中。其次计算输入的数的最大位数，这决定着循环次数。接着遍历列表，将其放入队列中，然后得到新的列表，在进行十位数的遍历然后依次类推。

先创建队列数据类型：

#顺序队列(没有头结点，有状态变量)
class Queue1:def __init__(self,maxsize):self.maxsize=maxsizeself.arrq=maxsize*[None]self.front=0self.rear=0self.size=0def clear(self):self.front=self.rearself.size=0def enqueue(self,data):if self.size==self.maxsize:return print('当前队列为满，无法进队！')self.arrq[self.rear]=dataself.rear=(self.rear+1)%self.maxsizeself.size+=1def dequeue(self):if self.size==0:return print('当前队列为空，无法进行出队！')self.front=(self.front+1)%self.maxsizeself.size-=1def print(self):m=[]if self.size==0:return m       x=self.frontwhile x!=self.rear:m.append(self.arrq[x])x=(x+1)%self.maxsizereturn m

接着对数字类型进行排序：

#对不等宽的数字而言
from queue1 import Queue1
#创建桶 桶由队列构成
stack=[]
for i in range(10):stack.append(Queue1(10))
x=[1,12,21,322,123,44,2312,765,56]
#首先要测出最大位数，决定着循环几次
def w(array):max = array[0]for i in array:if max < i:max = itimes = 0while max > 0:max = int(max/10)times += 1return times
for i in range(w(x)):for k in range(len(x)):m=x[k]//(10**i)%10stack[m].enqueue(x[k])x=[]for a in range(10):x=x+stack[a].print()stack[a].clear()print(x)

结果输出：

第二问

对字母排序和对数字排序相差不大。这里我没有考虑字母的大小写，如有需要，请自改代码。

from queue1 import Queue1
# 字母情形
x=["abc","bde","fad","abd","bef","fdd","abe"]
w=len(x[0])
#需要创建26个栈
stack=[]
for i in range(26):stack.append(Queue1(10))
#a的ASCII是97  z的ASCII是122
for i in range(w):for k in range(len(x)):m=x[k][-i-1]stack[ord(m)-97].enqueue(x[k])x=[]for a in range(10):x=x+stack[a].print()stack[a].clear()
print(x)

结果输出：