数据结构项目实践.pdf

数据结构项目实践数据结构项目实践 一 顺序表一 顺序表 1 顺序表的实现 顺序表的实现 要求 1 用 C 语言实现顺序表结构以及各算法 至少包含以下操作接口 InitList 初始化线性表 GetLength 计算表长 GetElem 按位置查询元素值 Locate 按元素值查询位置 InsElem 插入元素 DelElem 删除元素 DispList 打印线性表 2 实现一个对顺序表进行各操作的用户界面 如流程图所示 2 约瑟夫问题 约瑟夫问题 据说著名犹太历史学家 Josephus 有过以下的故事 在罗马人占领乔塔帕特后 39 个犹太人与 Josephus 及他的朋友 躲到一个洞中 39 个犹太人决定宁愿死也不要被敌人抓到 于是决定了一个自杀方式 41 个人排成一个圆圈 由 第 1 个人开始报数 每报数到第 3 人该人就必须自杀 然后再由下一个重新报数 直到所有人都自杀身亡为止 然 而 Josephus 和他的朋友并不想遵从 Josephus 要他的朋友先假装遵从 他将朋友与自己安排在第 16 个与第 31 个 位置 于是逃过了这场死亡游戏 问题 对于任意给定的 n s m 求出按出列次序的得到的 n 个人员的序列 设 n 个人排成一个圆圈 从第 s 个人开始报数 如此反复直到所有人都出列 结束 初始化线性表 菜单选择 1 打 印 线 性 表 2 插 入 元 素 3 删 除 元 素 4 查 询 元 素 值 5 查 询 元 素 位 置 6 获 得 表 长 7 清 空 表 0 退 出 开始 二二 单链表 单链表 1 单链表单链表的实现的实现 要求 1 用 C 语言实现单链表结构以及各算法 至少包含以下操作接口 InitList 初始化链表 DestroyList 销毁链表 ListLength 计算表长 DispList 打印链表 GetElem 按位置查询元素值 LocateElem 按元素值查询位置 ListInsert 插入元素 ListDelete 删除元素 2 实现一个对顺序表进行各操作的用户界面 如流程图所示 2 多项式运算问题 多项式运算问题 三三 栈 顺序栈 链 栈 顺序栈 链式式栈 栈 1 栈的实现 栈的实现 要求 1 用 C 语言实现栈结构以及各算法 至少包含以下操作接口 InitStack 初始化栈 Push 入栈 Pop 出栈 GetTop 获取栈顶元素 2 实现一个对栈进行各操作的用户界面 如流程图所示 结束 初始化栈 菜单选择 1 入 栈 2 出 栈 3 取 栈 顶 元 素 4 清 空 栈 5 打 印 栈 0 退 出 开始 四 队列 顺序队列 链式队列 四 队列 顺序队列 链式队列 1 队列的实现 队列的实现 要求 1 用 C 语言实现线性表结构以及各算法 至少包含以下操作接口 InitQueue 初始化队列 EnQueue 入队 DeQueue 出队 GetHead 获对头元素 2 实现一个对队列进行各操作的用户界面 如流程图所示 2 杨辉三角问题 杨辉三角问题 根据输入的行数 打印杨辉三角 结束 初始化队列 菜单选择 1 入 队 2 出 队 3 取 对 头 元 素 4 清 空 队 列 5 打 印 队 列 0 退 出 开始 五五 二叉树二叉树 1 二叉 二叉链表链表树的实现树的实现 要求 1 用 C 语言实现二叉链表树结构以及各算法 至少包含以下操作接口 CreateBTNode 创建二叉树 Insert 插入 Delete 删除子树 FindNode 查找结点 PreOrder InOreder PostOrder 前序 中序 后序深度遍历 LevelOrder 层次遍历 2 实现一个对二叉树进行各操作的用户界面 2 家谱管理 家谱管理 树型结构是一种非常重要的非线性结构 它用于描述数据元素之间的层次关系 如人类社会的族谱和各种组织机构 的表示等等 家谱是一个家族兴衰繁衍的记录 它记载了一个家族若干世代中的所有家庭 每个家庭中各个成员的 主要情况 通常用文字记录 但查询其关系时不能一目了然 我们可以用树型结构来表示家族关系 对其查询及修 改方便快捷 简要需求分析 建立输入文件以存放最初家谱中各成员的信息 成员的信息中均应包含以下内容 姓名 出生日期 婚否 地址 健在否 也可附加其它信息 但不是必需的 能对修改后的家谱存盘以备以后使用 能从文件中读出已有的家谱 形成树状关系 家谱建立好之后 以图形方式显示出来 显示第 n 代所有人的信息 按照姓名查询 输出成员信息 包括其本人 父亲 孩子的信息 按照出生日期查询成员名单 输入两人姓名 确定其关系 某人添加孩子 删除某人 若其还有后代 则一并删除 修改某人信息 按出生日期对家谱