同济大学数据结构作业

### 同济大学数据结构课程作业题目与资料

针对同济大学的数据结构课程，学生通常会接触到一系列经典的算法和数据结构练习题以及项目实践。这些内容旨在帮助学生深入理解并掌握各种抽象数据类型的表示方法及其操作实现。

#### 经典习题示例

1. **线性表的操作**
实现单链表的各种基本功能，如创建、销毁、清空、求长度、查找指定位置上的结点、按值查找结点的位置、插入新结点到指定位置之前或之后、删除指定位置上的结点等[^1]。

2. **栈的应用——括号匹配检测**
编写程序完成对给定字符串中的圆括号()、方括号[]、花括号{}是否正确配对的判断工作。当遇到左半边符号时将其压入堆栈；而每当碰到右半边符号，则尝试弹出顶部元素并与之比较看能否构成一对合法组合。

3. **队列模拟银行排队叫号系统**
设计一个简单的窗口服务模型来处理顾客到达事件和服务完成通知之间的关系。可以考虑引入优先级机制使得VIP客户能够得到更快速的服务响应。

4. **二叉树遍历方式的研究**
对于任意一棵由用户输入节点信息构建而成的二叉树对象，分别采用前序/中序/后序三种不同顺序访问其各个顶点，并输出相应的序列化结果以便后续验证正确性。

5. **图论基础：最短路径计算**
使用Dijkstra算法解决加权有向无环图上两点间的最小距离查询问题。此过程涉及到邻接矩阵或者列表形式存储权重信息，初始化源点可达性的估计代价数组dist[],并通过迭代更新直至收敛获得最终解集。

6. **哈希表冲突解决方案探讨**
探讨开放地址法(Open Addressing) 和拉链法(Separate Chaining)两种主流策略应对键值映射过程中可能出现重复散列码的情况。具体来说就是分析它们各自的优缺点，在实际编程环境中测试性能差异。

7. **汉诺塔问题的递归和非递归实现**
通过编写Python脚本展示如何利用函数调用自身的方式简洁优雅地解决问题的同时也给出基于显式维护状态转移记录的方法作为对比参考。

def hanoi_recursive(n, source='A', auxiliary='B', target='C'):
    if n == 1:
        print(f'Move disk from {source} to {target}')
        return
    hanoi_recursive(n - 1, source, target, auxiliary)
    print(f'Move disk from {source} to {target}')
    hanoi_recursive(n - 1, auxiliary, source, target)

def hanoi_nonrecursive(n):
    stack = [(n, 'A', 'B', 'C')]
    while stack:
        disks, src, aux, tgt = stack.pop()
        if disks == 1:
            print(f'Move disk from {src} to {tgt}')
        else:
            stack.append((disks - 1, aux, src, tgt))
            stack.append((1, src, None, tgt))  # Move topmost directly.
            stack.append((disks - 1, src, tgt, aux))

hanoi_recursive(3)
print("\nNon-Recursive:")
hanoi_nonrecursive(3)