经典数据结构上机题—答案

精品文档 1欢迎下载 数据结构上机实验题目数据结构上机实验题目 实验一 线性表的顺序存储结构 实验学时 2学时 背景知识 顺序表的插入 删除及应用 目的要求 1 掌握顺序存储结构的特点 2 掌握顺序存储结构的常见算法 实验内容 1 输入一组整型元素序列 建立顺序表 2 实现该顺序表的遍历 3 在该顺序表中进行顺序查找某一元素 查找成功返回1 否则返回 0 4 判断该顺序表中元素是否对称 对称返回1 否则返回0 5 实现把该表中所有奇数排在偶数之前 即表的前面为奇数 后面为 偶数 6 输入整型元素序列利用有序表插入算法建立一个有序表 7 利用算法6建立两个非递减有序表并把它们合并成一个非递减有 序表 8 利用该顺序结构实现循环队列的入队 出队操作 8 编写一个主函数 调试上述算法 include include 精品文档 2欢迎下载 define OVERFLOW 0 define MAXSIZE 100 typedef int ElemType typedef struct list ElemType elem MAXSIZE int length Sqlist void Creatlist Sqlist printf 请输入顺序表的长度 请输入顺序表的长度 输入一组整型元素序列 建立一个顺输入一组整型元素序列 建立一个顺 序表 序表 scanf d for i 0 i L length i scanf d void printlist Sqlist for i 0 i L length i printf d L elem i printf n void Searchlist Sqlist for i 0 i i j L elem j L elem j 1 L elem j x L length void Delete Sqlist for j i j L length j L elem j 1 L elem j L length 精品文档 3欢迎下载 void Insert Sqlist if L length MAXSIZE exit OVERFLOW 表满 不能插入表满 不能插入 for i 1 i L lengthj L elem j L elem j 1 L elem i 1 x L length void Creatlist sorted Sqlist ElemType x L length 0 printf 请输入顺序表的长度 请输入顺序表的长度 scanf d for i 1 i num i scanf d Insert L x void Merger Sqlist a b c length p length r length while i p lengthb k j else c elem k a a k i if j r length for k c length k c elem k a a else if i p length for k c length k c elem k b b void main Sqlist L M N 精品文档 4欢迎下载 int x i n printf 1 建立一个顺序表建立一个顺序表 n printf 2 以输出的形式对该顺序表遍历以输出的形式对该顺序表遍历 n printf 3 在顺序表中进行顺序查找某一元素在顺序表中进行顺序查找某一元素 x n printf 4 在顺序表的第在顺序表的第 i 个位置上插入一个元素个位置上插入一个元素 x n printf 5 删除顺序表中第删除顺序表中第 i 个元素个元素 n printf 6 利用有序表插入算法建立一个有序表利用有序表插入算法建立一个有序表 n printf 7 建立两个非递减有序表 并把它们合并成一个非递减有序表建立两个非递减有序表 并把它们合并成一个非递减有序表 n printf 8 输入一个元素输入一个元素 x 把它插入到有序表中 使顺序表依然有序 把它插入到有序表中 使顺序表依然有序 n while 1 printf 请选择 请选择 scanf d switch n case 1 Creatlist L break case 2 printlist L break case 3 printf 请输入要查找的元素请输入要查找的元素 x scanf d Searchlist L x break case 4 printf 请输入要插入的位置请输入要插入的位置 i scanf d if iL length 1 printf error n break printf 请输入要插入的值请输入要插入的值 x scanf d Inseri L i x printlist L break case 5 printf 请输入要删去的元素的位置请输入要删去的元素的位置 i scanf d if iL length printf error n break Delete L i printlist L break case 6 Creatlist sorted L printlist L break case 7 Creatlist sorted L Creatlist sorted M Merger L M N printlist N break case 8 Creatlist sorted L printf 请输入要插入的元素请输入要插入的元素 x scanf d Insert L x printlist L break 精品文档 5欢迎下载 实验二 链式存储结构 一 单向链表的有关操作 实验学时 3学时 背景知识 单向链表的插入 删除及应用 目的要求 1 掌握单向链表的存储特点及其实现 2 掌握单向链表的插入 删除算法及其应用算法的程序实现 实验内容 1 随机产生或键盘输入一组元素 建立一个带头结点的单向链表 无序 2 遍历单向链表 3 把单向链表中元素逆置 不允许申请新的结点空间 4 在单向链表中删除所有的偶数元素结点 5 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数 并利用该函数建立一个非递减有序单向链表 6 利用算法5建立两个非递减有序单向链表 然后合并成一个非递 增链表 7 利用算法5建立两个非递减有序单向链表 然后合并成一个非递 减链表 8 利用算法1建立的链表 实现将其分解成两个链表 其中一个全 精品文档 6欢迎下载 部为奇数 另一个全部为偶数 尽量利用已知的存储空间 9 采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果 10 在主函数中设计一个简单的菜单 分别调试上述算法 11 综合训练 利用链表实现一个班级学生信息管理 数据录入 插入 删除 排序 查找等 并能够实现将数据存储到文件中 单向链表的有关操作示例 类型定义及头文件部分 文件名为 sllink h include include typedef int ElemType 元素实际类型 typedef struct LNode ElemType data struct LNode next LNode LinkList 定义结点 指针类型名 头插法建立无序链表 void CreateList LinkList ElemType e L LinkList malloc sizeof LNode L next NULL printf 头插法建立链表 以 0 结束 n scanf d while e p LinkList malloc sizeof LNode p data e p next L next L next p scanf d 非递减有序单向链表 L 插入元素 e 序列仍有序 void Insert Sort LinkList s LinkList malloc sizeof LNode s data e p L while p next 查找插入位置 s next p next 插入语句 p 结点后插入 s 结点 p next s 精品文档 7欢迎下载 建立递增有序的单向链表 void Create Sort LinkList L LinkList malloc sizeof LNode L next NULL printf 建立有序表 输入任意个整型数据以 0 结束 n scanf d while e Insert Sort L e scanf d 单向链表的遍历 void Traverse LinkList L LinkList p printf 遍历链表 for p L next p p p next printf 5d p data printf n 在单向链表删除元素 e void Delete LinkList p L q L next while q q q next if q printf nnot deleted 未找到元素 e else p next q next 找到删除 free q 单向链表的逆置 void exch LinkList p L next L next NULL while p s p p p next s next L next L next s 精品文档 8欢迎下载 两个非递减有序单向链表合并后仍为非递减序列 void MergeIncrease LinkList La LinkList Lb LinkList p La next q Lb next Lc rear La free Lb while pp p next else s q q q next rear next s 较小元素插入表尾 rear rear next if p rear next p else rear next q 实验三 迷宫问题求解 实验学时 3学时 背景知识 栈的操作 目的要求 1 掌握栈的存储特点及其实现 2 掌握栈的出栈和入栈操作 实验内容 以一个 mxn 的长方阵表示迷宫 0 和 1 分别表示迷宫中的通路和 障碍 设计一个程序 对任意设定的迷宫 求出一条从入口到出口 的通路 或得出没有通路的结论 要求 首先实现一个顺序或链表做存储结构的栈类型 然后编写一 个求解迷宫的非递归程序 求得的通路以三元组 i j d 的形式输出 其中 i j 表示迷宫的坐标 d 表示走到下一坐标的方向 如对下面 精品文档 9欢迎下载 的迷宫 输出的一条通路为 1 1 1 1 2 2 2 2 2 3 2 3 3 1 2 迷宫约定 x 方向为行方向 y 方向为列方向 迷宫开始坐标 左上 角 为 1 1 include include include struct node int sign 标识 0 什么都不在 1 在 open 中 2 在 closed 中 int flag 标志位 0 1 0 可以走 1 不可以走 int f g h 判断函数 int x y 坐标 int old 是否 old 节点 0 非 1 是 struct link node fnode link next link pri 精品文档 10欢迎下载 link open closed bestnode successor p q r s int maze flag 7 7 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 表示迷宫的数组 0 可以走 1 不可以走 node maze 7 7 int judge node n 判断函数 判断 n 节点是否可以走 if n flag 1 return 1 else return 0 void in open node n 将 n 节点放入 open 表 p open while p next open if n f p fnode f p next pri link malloc sizeof link p next pri pri p p p next p pri next p p pri pri next p pri p p pri p fnode flag n flag p fnode f n f p fnode g n g p fnode h n h p fnode x n x p fnode y n y p fnode old n old p fnode sign n sign 1 else p p next 精品文档 11欢迎下载 open pri link malloc sizeof link open pri pri p open pri next open p next open pri p p next p fnode flag n flag p fnode f n f p fnode g n g p fnode h n h p fnode x n x p fnode y n y p fnode old n old p fnode sign n sign 1 void out open node n 将 n 节点从 open 表中移出 p open while p next open if n f p fnode f link p1 p1 p next p next p next next p next pri p free p1 n sign 0 else p p next void in closed node n 将 n 节点放入 closed 表 while q next closed if n f q fnode f q next pri link malloc sizeof link q next pri pri q q q next 精品文档 12欢迎下载 q pri next p q pri pri next q pri q q pri q fnode flag n flag q fnode f n f q fnode g n g q fnode h n h q fnode x n x q fnode y n y q fnode old n old q fnode sign n sign 2 else q q next closed pri link malloc sizeof link closed pri pri q closed pri next closed q next closed pri q q next q fnode flag n flag q fnode f n f q fnode g n g q fnode h n h q fnode x n x q fnode y n y q fnode old n old q fnode sign n sign 2 void out closed node n 将 n 节点从 closed 表中移出 q closed while q next closed if n f q fnode f link q1 q1 q next q next q next next q next pri q free q1 n sign 0 精品文档 13欢迎下载 else q q next void in bestnode node n 将 n 节点设为 bestnode 节点 while r next bestnode if n f r fnode f r next pri link malloc sizeof link r next pri pri r r r next r pri next r r pri pri next r pri r r pri r fnode flag n flag r fnode f n f r fnode g n g r fnode h n h r fnode x n x r fnode y n y r fnode old n old else r r next bestnode pri link malloc sizeof link bestnode pri pri r bestnode pri next bestnode r next bestnode pri r r next r fnode flag n flag r fnode f n f r fnode g n g r fnode h n h r fnode x n x r fnode y n y r fnode old n old void out bestnode node n 将 n 节点的 bestnode 去掉 精品文档 14欢迎下载 r bestnode while r next bestnode if n f p fnode f link r1 r1 r next r next r next next r next pri r free r1 else r r next void in successor node n 将 n 节点设置为 successor 节点 s successor while s next successor if n f s fnode f s next pri link malloc sizeof link s next pri pri s s p next s pri next s s pri pri next s pri s s pri s fnode flag n flag s fnode f n f s fnode g n g s fnode h n h s fnode x n x s fnode y n y s fnode old n old else s s next successor pri link malloc sizeof link successor pri pri s successor pri next successor s next successor pri 精品文档 15欢迎下载 s s next s fnode flag n flag s fnode f n f s fnode g n g s fnode h n h s fnode x n x s fnode y n y s fnode old n old void out successor node n 将 n 节点的 successor 去掉 s successor while s next successor if n f p fnode f link s1 s1 s next s next s next next s next pri s free s1 else s s next void print link n 输出 link 类型的表 n link forprint forprint n printf the key is while forprint next n printf d d n forprint fnode x forprint fnode y int main 初始化部分 这部分的功能是将二维的整形数组赋值给 node 型的二维数组 int i 0 j 0 for i 0 i 7 i for j 0 j 7 j 精品文档 16欢迎下载 maze i j x i maze i j y j maze i j flag maze flag i j if maze i j flag 0 maze i j h 6 i 6 j maze i j sign maze i j f maze i j g maze i j old 0 else maze i j h 1 for i 0 i 7 i 输出迷宫示意图 for j 0 jnext open open pri open q closed link malloc sizeof link closed next closed closed pri closed r bestnode link malloc sizeof link bestnode next bestnode bestnode pri bestnode 将第一个元素即 0 0 节点放入 open 表 开始算法 in open maze 0 0 maze 0 0 f maze 0 0 h link s2 s2 successor if open next open open 表为空时则失败退出 while 1 in bestnode open fnode 将 open 表的第一个元素放入 bestnode 中 in closed maze open fnode x open fnode y 将 open 表的第一个元素放入 closed 中 maze open fnode x open fnode y g 将 open 表的第一个元素的 g 值加一 表示已经 精品文档 17欢迎下载 走了一步 out open maze open fnode x open fnode y 将 open 表的第一个元素删除 if bestnode fnode x 6 print closed break else 若 bestnode 不是目标节点 则扩展其临近可以走的节点为 successor if i 0 j 0 i 6 j 6 if i 0 if judge maze i 1 j 0 in successor maze i 1 j else if i 0 if judge maze i 1 j 0 in successor maze i 1 j else if i 6 if judge maze i j 1 0 in successor maze i j 1 else if i 6 if judge maze i j 1 0 in successor maze i j 1 else if i 0 若为第一行的元素 不在角上 则判断左边 下边和右边 if judge maze i j 1 0 精品文档 18欢迎下载 in successor maze i j 1 if judge maze i j 1 0 in successor maze i j 1 if judge maze i 1 j 0 in successor maze i 1 j else if i 6 若为第七行的元素 不在角上 则判断左边 上边和右边 if judge maze i j 1 0 in successor maze i j 1 if judge maze i j 1 0 in successor maze i j 1 if judge maze i 1 j 0 in successor maze i 1 j else if j 0 若为第一列的元素 不在角上 则判断右边 下边和上边 if judge maze i 1 j 0 in successor maze i 1 j if judge maze i 1 j 0 in successor maze i 1 j if judge maze i j 1 0 in successor maze i j 1 else if j 6 若为第七列的元素 不在角上 则判断左边 上边和上边 if judge maze i 1 j 0 in successor maze i 1 j if judge maze i 1 j 0 in successor maze i 1 j if judge maze i j 1 0 in successor maze i j 1 else 若为中将的元素 则判断四个方向的节点 if judge maze i j 1 0 in successor maze i j 1 if judge maze i j 1 0 in successor maze i j 1 if judge maze i 1 j 0 in successor maze i 1 j if judge maze i 1 j 0 in successor maze i 1 j 精品文档 19欢迎下载 while s2 next successor 对所有的 successor 节点进行下列操作 maze s2 fnode x s2 fnode y g bestnode fnode g bestnode fnode h 计算 g suc g bes h bes suc if s2 fnode sign 1 若在 open 表中 则置为 old 记下较小的 g 并从 open 表中移出 放 入 closed 表中 s2 fnode old 1 if s2 fnode gfnode x s2 fnode y g maze s2 fnode x s2 fnode y g s2 fnode g maze s2 fnode x s2 fnode y f maze s2 fnode x s2 fnode y g maze s2 fnode x s2 fnode y h out open maze s2 fnode x s2 fnode y in closed maze s2 fnode x s2 fnode y maze s2 fnode x s2 fnode y old 0 else continue else if s2 fnode sign 2 若在 closed 表中 则置为 old 记下较小的 g 并将 old 从 closed 表中移出 将较小的 g 的节点放入 closed 表中 s2 fnode old 1 if s2 fnode gfnode x s2 fnode y g maze s2 fnode x s2 fnode y g s2 fnode g maze s2 fnode x s2 fnode y f maze s2 fnode x s2 fnode y g maze s2 fnode x s2 fnode y h out closed maze s2 fnode x s2 fnode y in closed maze s2 fnode x s2 fnode y maze s2 fnode x s2 fnode y old 0 else continue else 若即不再 open 表中也不在 closed 表中 则将此节点放入 open 表中 并计算此节点 的 f 值 in open maze s2 fnode x s2 fnode y maze s2 fnode x s2 fnode y f maze s2 fnode x s2 fnode y g maze s2 fnode x s2 fnode y h 精品文档 20欢迎下载 s2 s2 next s2 successor else printf error This maze does not have the answer return 0 实验内容 以一个 m n 的长方阵表示迷宫 0 和 1 分别表示迷宫中的通路和障 碍 设计一个程序 对任意设定的迷宫 求出一条从入口到出口的通 路 或得出没有通路的结论 要求 首先实现一个顺序或链表做存储结构的栈类型 然后编写一个 求解迷宫的非递归程序 求得的通路以三元组 i j d 的形式输出 其 中 i j 表示迷宫的坐标 d 表示走到下一坐标的方向 如对下面的 迷宫 输出的一条通路为 1 1 1 1 2 2 2 2 2 3 2 3 3 1 2 迷宫约定 x 方向为行方向 y 方向为列方向 迷宫开始坐标 左上 角 为 1 1 基本相同 include include include typedef struct QElemType int x y struct QElemType parent 用于存储节点的前一个节点 QElemType typedef struct QNode 队列节点 QElemType data struct QNode next QNode QueuePtr typedef struct QueuePtr front QueuePtr rear 精品文档 21欢迎下载 LinkQueue void InitQueue LinkQueue Q 创建队列 Q front Q rear QueuePtr malloc sizeof QNode Q rear next NULL Q front Q rear NULL void EnQueue LinkQueue Q QElemType e 将元素入队 QueuePtr p p QueuePtr malloc sizeof QNode p data e p next NULL Q rear next p Q rear p QElemType DeQueue LinkQueue Q 将元素出对 QElemType e QueuePtr p p Q front next e p data Q front next p next if Q rear p Q rear Q front free p return e int QueueEmpty LinkQueue Q 判断队列是否为空 if Q front Q rear return 1 else return 0 QElemType NextPos QElemType e int i 节点的下一个位置 QElemType t QElemType malloc sizeof QElemType t e 精品文档 22欢迎下载 switch i case 1 t y t y 1 break case 2 t x t x 1 break case 3 t y t y 1 break case 4 t x t x 1 break return t QElemType MazePath int maze 10 LinkQueue Q 迷宫函数 int i QElemType e p e QElemType malloc sizeof QElemType InitQueue e x 1 入口位置 即为第一个节点 e y 1