基于Python的数据结构实验——循环顺序队列与递归（附详细代码和注释）

1、创建名为 prac04_01.py 的文件，在其中编写一个循环顺序队列的类，该类必须包含 循环顺序队列的定义及基本操作，并通过以下步骤测试各种基本操作的实现是否正确。

(1)初始化一个循环顺序队列 CircularSequenceQueue。

(2)判断队列是否为空。

(3)遍历队列内的所有元素。

(4)将元素 1，3，5，7，9，......依次进队至队满。

(5)遍历队列内的所有元素。

(6)获取队头元素。

(7)获取队列的长度。

(8)出队一个元素并输出。

(9)尝试能否将一个新元素进队

class CircularSequenceQuene:
    def __init__(self):
        self.maxlength = 5  # 循环队列的空间
        self.s = []
        for i in range(0, self.maxlength):
            self.s.append(i)  # 先赋一定的值
        self.front = 0  # 队头位置
        self.rear = 0  # 队尾位置
        
    def EmptyJudgement(self):
        if self.front == self.rear:  # 如果头尾重合，则判定队空
            return True
        else:
            return False
        
    def SelectAll(self):
        if self.EmptyJudgement() is True:
            print("队列为空")
        else:
            if self.front < self.rear:
                for i in range(self.front + 1, self.rear + 1):  # 循环打印元素，此时rear在front后，直接打印即可
                    print(self.s[i], end=" ")
            else:
                for i in range(self.front, self.maxlength - 1):  # 此时rear转了一圈又回到了front前，因此分两段打印，一部分是front到列表末端，一部分是列表首端到rear
                    print(self.s[i], end=" ")
                for i in range(0, self.rear + 1):
                    print(self.s[i], end=" ")
    
    def Length(self):
        if self.front < self.rear:
            return self.rear - self.front  # 仍然要分情况讨论，这种事胡直接减就行
        else:
            return self.rear + self.maxlength - self.front  # 这种情况下就两部分拼起来（化简之前有个加一减一）
    
    def Append(self):
        while True:
            if self.front == (self.rear + 1) % self.maxlength:  # 判断队满
                print("队列已满")  # 队列满了就算了
                break
            else:
                info = input("请输入要入队的元素，依次输入一个，或输入“终止”以结束输入：")
                if info == "终止":
                    break
                else:
                    self.rear = (self.rear + 1) % self.maxlength  # 不用讨论了，直接一步到位通过求余找到实际的修改位置，相当于循环起来了
                    self.s[self.rear] = info  # 写入数据
                    print("元素%s成功入队" % info)
 
    def Delete(self):
        if self.EmptyJudgement() is True:
            print("队列为空")
        else:
            self.front = (self.front + 1) % self.maxlength
            print("元素%s成功出队" % self.s[self.front])
            self.s[self.front] = self.front  # 最后这一步没有实际意义，毕竟对于一个列表来说，实在没必要清除掉数据
    
    def SelectHead(self):
        if self.EmptyJudgement() is True:
            print("队列为空")
        else:
            print("队首元素为：%s" % self.s[(self.front + 1) % self.maxlength])  # 查找队首元素也是采用传统方法，这样的话不用高出一些乱七八糟的问题
        
    def Choice(self):
        self.__init__()
        while True:
            info = input("请选择操作（数据入队，数据出队，队列长度，查找队头元素，查找全部元素，队列是否非空）或输入“终止”以结束：")
            if info == "数据入队":
                self.Append()
            elif info == "数据出队":
                self.Delete()
            elif info == "队列长度":
                data = self.Length()
                print("队列长度为", data)
            elif info == "查找队头元素":
                self.SelectHead()
            elif info == "查找全部元素":
                self.SelectAll()
            elif info == "队列是否非空":
                data = self.EmptyJudgement()
                if data is True:
                    print("队列为空")
                else:
                    print("队列不为空")
            elif info == "终止":
                break
            else:
                print("无效指令")
                
if __name__ == "__main__":
    demo = CircularSequenceQuene()
    demo.Choice()

 创建名为 prac04_02.py 的文件，在其中编写 n! 函数的递归算法及非递归算法。

(1)编写出计算 n! 的递归算法。

(2)将(1)中的递归算法转换为非递归算法。

(3)设置适当的 n 值，比较两种算法的运行时间。

# 递归算法
from timeit import timeit
 
 
def FactorialRecursion(n):
    if n > 1:
        return n * FactorialRecursion(n - 1)
    elif n == 1:
        return 1
    else:
        return 0
 
while True:
    try:
        a = int(input("输入阶乘的阶数或输入-1以终止："))
        if a != -1 and a >= 0:
            answer = FactorialRecursion(a)
            print("结果为：", answer)
            print("用时：", timeit('FactorialRecursion(%d)' % a, 'from __main__ import FactorialRecursion', number=100), "s")
        elif a == -1:
            print("已终止。")
            break
        else:
            print("请输入自然数。")
    except(ValueError):
        print("请输入自然数。")

# 非递归算法
from timeit import timeit
 
 
def FactorialNonRecursion(n):
    answer = 1
    for i in range(0, n):
        answer = answer * n
    return answer
 
while True:
    try:
        a = int(input("输入阶乘的阶数或输入-1以终止："))
        if a != -1 and a >= 0:
            answer = FactorialNonRecursion(a)
            print("结果为：", answer)
            print("用时：", timeit('FactorialNonRecursion(%d)' % a, 'from __main__ import FactorialNonRecursion', number=100), "s")  # 函数计时器
        elif a == -1:
            print("已终止。")
            break
        else:
            print("请输入自然数。")
    except(ValueError):
        print("请输入自然数。")