中南大学数据结构实验报告

中南大学中南大学 数据结构实验报告数据结构实验报告 实验题目 1 单链表的实现 2 栈和队列 3 二叉树的遍历 4 查找与排序 学生姓名 代巍 学生学号 指导老师 余腊生 所在学院 信息科学与工程学院 专业班级 信息安全 1201 班 指导教师评定 签 名 实验一实验一 单链表的实现单链表的实现 一 实验目的一 实验目的 了解线性表的逻辑结构和各种存储表示方法 以及定义在逻辑结构上的各 种 基本运算及其在某种存储结构上如何实现这些基本运算 在熟悉上述内容 的基础上 能够针对具体应用问题的要求和性质 选择合适的存储结构设计出 相应的有效算法 解决与线性表相关的实际问题 二 实验内容二 实验内容 用 C C 语言编写程序 完成以下功能 1 运行时输入数据 创建一个单链表 2 可在单链表的任意位置插入新结点 3 可删除单链表的任意一个结点 4 在单链表中查找结点 5 输出单链表 三 程序设计的基本思想 原理和算法描述三 程序设计的基本思想 原理和算法描述 包括程序的结构 数据结构 输入 输出设计 符号名说明等 用一组地址任意的存储单元存放线性表中的数据元素 以元素 数据元素 的映象 指针 指示后继元素存储位置 结点 表示数据元素 或 数据元素 的映象 以 结点的序列 表示线性表称作线性链表 单链表 单链表是指数据接点是单向排列的 一个单链表结点 其结构类型分为两 部分 1 数据域 用来存储本身数据 2 链域或称为指针域 用来存储下一个结点地址或者说指向其直接后 继的指针 1 单链表的查找 对单链表进行查找的思路为 对单链表的结点依次扫描 检测其数据域是 否是我们所要查好的值 若是返回该结点的指针 否则返回 NULL 2 单链表的插入 因为在单链表的链域中包含了后继结点的存储地址 所以当我们实现的时 候 只要知道该单链表的头指针 即可依次对每个结点的数据域进行检测 假设在一个单链表中存在 2 个连续结点 p q 其中 p 为 q 的直接前驱 若我们需要在 p q 之间插入一个新结点 s 那么我们必须先为 s 分配空间并赋 值 然后使 p 的链域存储 s 的地址 s 的链域存储 q 的地址即可 p link s s link q 这样就完成了插入操作 3 单链表的删除 删除运算思想方法删除运算是将表的第 i 个结点删去 具体步骤 找到 i 1 的存储位置 p 令 p next 指向 i 的直接后继结点释放结点 i 的空间 将其归 还给 存储池 四 源程序及注释四 源程序及注释 include include include include include define ElemType int 链表类型 typedef struct LNode ElemType data struct LNode next LNode LinkList int EmptyList LinkList else return 1 手动建立一个带头结点的线性链表 L void SCreateList L LinkList int i ElemType d l LinkList malloc sizeof LNode L LinkList malloc sizeof LNode 生成头结点 l L L next NULL cout 请依次输入结点值 以 0 为结束 d if d 0 p LinkList malloc sizeof LNode 生成新结点 p data d p next l next l next p l l next else break if EmptyList L cout 生成链表成功 else cout next NULL srand unsigned time NULL for int i n i 0 i p LinkList malloc sizeof LNode 生成新结点 p data rand 100 1 p next l next l next p l l next cout 生成链表成功 cin get cin get ZCreate L 建立一个带头结点的线性链表 LinkList CreateList L char c int n LinkList L cout 建立线性链表 endl cout 1 手动建立 endl cout 2 自动建立 endl cout c if c 1 SCreateList L L else if c 2 cout n ZCreateList L L n else cout 输入错误 请重新输入 next int i 0 while p i p p next return i cin get cin get LengthList 在线性链表 L 中第 i 个结点之前插入新的数据元素 e void ListInsert L LinkList ElemType e cout i while iLengthList L cout i LinkList p s p L int j 0 while p j if p j i 1 cout 输入错误 cin get cin get else cout e s LinkList malloc sizeof LNode s data e s next p next p next s cout 插入成功 cin get cin get ListInsert L 删除线性链表 L 中的第 i 个结点 void ListDelete L LinkList ElemType e cout i while iLengthList L cout i LinkList p q p L int j 0 q LinkList malloc sizeof LNode while p next j 寻找第 i 个结点 if p next j i 1 cout next p next q next e q data cout 删除成功 endl 删除的结点值为 next cout 所有数据如下所示 endl while p cout data next cin get cin get PrintList void SearchList LinkList ElemType n cout n if L NULL cout next while p data n i i 1 if p data n cout 找到了对应的结点 在链表的第 i 1 位上 else cout next free p L NULL cout 线性链表 L 已销毁 endl DestroyList int menu select 选择函数 char m 7 1 建立线性链表 2 某一结点前插入一个结点 3 删除一个结点 4 计算结点个数并输出 5 查找并显示某一结点位置 6 输出所有节点 0 退出系统 int i char c1 do system cls 清屏 cout n n 链表的基本操作 n n for i 0 i 7 i cout m i endl cout n n cout c1 while c1 6 return c1 0 void main LinkList L NULL for switch menu select case 1 L CreateList L system pause break case 2 if L NULL ListInsert L L else cout 链表为空 请先建链表 cin get cin get break system pause break case 3 if L NULL ListDelete L L else cout 链表为空 请先建链表 cin get cin get break system pause break case 4 if L NULL int i LengthList L cout 结点的个数为 i cin get cin get else cout 链表为空 请先建链表 cin get cin get break system pause break case 5 if L NULL SearchList L else cout 链表为空 请先建链表 cin get cin get break system pause break case 6 if L NULL PrintList L else cout 链表为空 请先建链表 cin get cin get break system pause break case 0 if L NULL DestroyList L exit 0 五 实验结果五 实验结果 实验二实验二 栈和队列栈和队列 一 实验目的一 实验目的 了解栈和队列的特性 掌握栈的顺序表示和实现 掌握栈的链式表示和实现 掌握队列的顺序表示和实现 掌握队列的链式表示和实现 掌握栈和队列在实际问题中的应用 二 实验内容二 实验内容 编写一个程序实现顺序栈的各种基本运算 并在此基础上设计一个主程序 完成如下功能 初始化顺序栈 插入元素 删除栈顶元素 取栈顶元素 遍历 顺序栈 置空顺序栈 三 程序设计的基本思想 原理和算法描述三 程序设计的基本思想 原理和算法描述 栈的修改时按照先进后出的原则进行的 试验中用到构造空栈 及入栈出 栈操作 队列是一种先进先出的线性表 只允许在表的一端插入 而在另一端 删除元素 试验中构造队并且入队出队 立顺序栈 SeqStack 存放测试数据 建立队列 SeqQueue 存放出栈数据 建立 InitStack StackEmpty StackFull Pop Push GetTop 函数用作 顺序栈的基本操作 建立 InitQueue QEmpty Qfull InQueue OutQueue ReadFront 函数用作队列的 基本操作 建立主函数依次按序对子函数进行操作 InitStack 初始化栈 Push 压入 数据 InitQueue 初始化队列 Pop 弹出数据 InQueue 存入队列 OutQueue 出 队列 Push 压入栈 Pop 弹出数据 free 清空栈与队列 在数据的输入与数据 的输出时提供必要的提示信息 四 源程序及其注释四 源程序及其注释 include include stack h include define MAXSIZE 100 作用 对栈进行初始化 参数 无 返回值 SeqStack SeqStack SeqStackInit SeqStack S S top 1 return S 作用 对栈进行判断是否为空 参数 传入要判断的栈 返回值 返回 TRUE 为空 返回 FLASE 为非空 int SeqStackEmpty SeqStack S if S top top printf n 清空 n 作用 把元素 x 压入栈 使其成为新的栈顶元素 参数 传入栈和要输入的数字 返回值 无 void SeqStackPush SeqStack S DataType x S top 要求是先挖坑 再种萝卜 S data S top x 作用 出栈 参数 要从该栈出来 返回值 从栈中出来的数 DataType SeqStackPop SeqStack S DataType temp if SeqStackEmpty S printf sorry 为空栈 exit 1 else temp S data S top 出栈是当前出栈 要求先挖萝卜再填坑 S top printf n d n temp 作用 取栈顶元素 参数 要操作的栈 返回值 从栈中出来的数 DataType SeqStackGetTop SeqStack S DataType temp if SeqStackEmpty S printf sorry 为空栈 exit 1 else temp S data S top 出栈是当前出栈 要求先挖萝卜再填坑 printf n d n temp 作用 输出顺序栈中的元素 参数 要操作的栈 返回值 从栈中出来的数 void SeqStackPrint SeqStack S DataType temp SeqStack p p S printf 输出栈中的所有元素 while SeqStackEmpty p temp p data p top 出栈是当前出栈 要求先挖萝卜再填坑 p top printf n d n temp 当这里位置数据类型怎么办 void main void int num int input SeqStack p p SeqStackInit 这里调用入栈函数 把 10 20 30 进栈 SeqStackPush SeqStackPush SeqStackPush while 1 printf n t 实验二 n n printf n1 入栈 printf n2 栈顶元素弹出 printf n3 取栈顶元素 printf n4 输出顺序栈中的元素 printf n5 清空栈 n printf t 请输入要实现的功能 n scanf d switch num case 1 printf n 请输入要入栈的数 t t n scanf d SeqStackPush break case 2 SeqStackPop break case 3 SeqStackGetTop p break case 4 SeqStackPrint p break case 5 ClearStack break 五 实验结果五 实验结果 实验三实验三 二叉树的建立和遍历二叉树的建立和遍历 一 实验目的一 实验目的 1 学会实现二叉树结点结构和对二叉树的基本操作 2 掌握对二叉树每种操作的具体实现 学会利用递归方法编写对二叉树这种递 归数据结构进行处理的算法 二 实验内容二 实验内容 编写程序任意输入二叉树的结点个数和结点值 构造一棵二叉树 采用三种递 归遍历算法 前序 中序 后序 对这棵二叉树进行遍历并计算出二叉树的高度 三 程序设计的基本思想 原理和算法描述三 程序设计的基本思想 原理和算法描述 1 数据结构的定义 二叉树是另一种树型结构 它的特点是每个结点至多只有两棵子树 并且二叉 树有左右之分 其次序不能任意颠倒 二叉树的存储结构分为顺序存储和链式 存储结构 本次我们主要应用二叉树的二叉链表的方式存储方式 实验中首先 必须对二叉树的数据结构进行定义 即定义一个二叉链表 其中其数据成员包 括节点的数据 左子树的指针 右子树的指针 2 二叉树的建立 在实验开始前我们要建立一个以先序形式的二叉树 先序的二叉树就是先访问 根结点 然后访问左子树 最后访问右子树的遍历 3 二叉树的遍历 二叉树的遍历分为先序 中序 后序 需先取遍历的节点的数据存入队列中 然后输出 4 程序中要的函数的介绍 1 二叉树的类型定义 2 定义链式队列类型 3 初始化链式队列的函数 4 主函数 四 源程序及注释四 源程序及注释 include include typedef struct BiTNode char data struct BiTNode lchild rchild BiTNode BiTree void CreatBiTree BiTree if ch getchar n T NULL else T BiTNode malloc sizeof BiTNode if T exit 1 T data ch CreatBiTree T lchild CreatBiTree T rchild void PreTravel BiTree PreTravel T lchild PreTravel T rchild void MidTravel BiTree printf c T data MidTravel T rchild void PostTravel BiTree PostTravel T rchild printf c T data void main BiTree T printf please input the bitree n CreatBiTree T printf The Pretravel is n PreTravel T printf n printf The Midtravel is n MidTravel T printf n printf The PostTravel is n PostTravel T printf n 五 实验结果五 实验结果 实验四实验四 查找和排序查找和排序 一 一 实验目的实验目的 1 掌握查找的不同方法 并能用 c 语言实现查找算法 2 掌握常用的排序方法 并掌握用 c 语言实现排序算法的方法 3 熟练掌握顺序表的选择排序 冒泡排序 直接插入排序等算法的实现 4 了解各种方法的排序过程及其时间复杂度的分析方法 二 实验内容二 实验内容 1 完整理解有关排序和查找的相关算法和基本思想以及种种算法使用的数据存 储结构 2 通过线性表对一组数据中的某个数据进行查找 对该组数据进行从小到大的顺序进行排序 三 程序设计的基本思想 原理和算法描述三 程序设计的基本思想 原理和算法描述 开始的时候提示输入一组数据 并存入一维数组中 接下来调用一系列查找算 法对其进行处理 顺序查找只是从头到尾进行遍历 二分查找则是先对数据进 行排序 然后利用三个标志 分别指向最大 中间和最小数据 接下来根据待 查找数据和中间数据的比较不断移动标志 直至找到 二叉排序树则是先构造 构造部分花费最多的精力 比根节点数据大的结点放入根节点的右子树 比根 节点数据小的放入根节点的左子树 其实完全可以利用递归实现 这里使用的 循环来实现的 感觉这里可以尝试用递归 当二叉树建好后 中序遍历序列即 为由小到大的有序序列 查找次数不会超过二叉树的深度 这里还使用了广义 表输出二叉树 以使得更直观 哈希表则是利用给定的函数式建立索引 方便 查找 四 源程序及其注释四 源程序及其注释 include define LENGTH 100 include include define INFMT d define OUTFMT d define NULL 0L define BOOL int define TRUE 1 define FALSE 0 define LEN 10000 typedef int ElemType typedef struct BSTNode ElemType data struct BSTNode lchild rchild BSTNode BSTree typedef BSTree BiTree 插入新节点 void Insert BSTree tree ElemType item BSTree node BSTree malloc sizeof BSTNode node data item node lchild node rchild NULL if tree tree node else BSTree cursor tree while 1 if item data if NULL cursor lchild cursor lchild node break cursor cursor lchild else if NULL cursor rchild cursor rchild node break cursor cursor rchild return void showbitree BiTree T 递归显示二叉树的广义表形式 if T printf 空 return printf d T data 打印根节点 if T lchild T rchild putchar showbitree T lchild 递归显示左子树 putchar showbitree T rchild 递归显示右子树 putchar 查找指定值 BSTree Search BSTree tree ElemType item BSTree cursor tree while cursor if item cursor data return cursor else if item data cursor cursor lchild else cursor cursor rchild return NULL 中缀遍历 void Inorder BSTree tree BSTree cursor tree if cursor Inorder cursor lchild printf OUTFMT cursor data Inorder cursor rchild 回收资源 void Cleanup BSTree tree BSTree cursor tree temp NULL if cursor Cleanup cursor lchild Cleanup cursor rchild free cursor void searchtree BSTree root char choice printf 中序遍历的结果为 n Inorder root printf n n ElemType item BSTree ret 二叉排序树的查找测试 do printf n 请输入查找数据 scanf d getchar printf Searching n ret Search root item if NULL ret printf 查找失败 else printf 查找成功 printf n 继续测试按 y 退出按其它键 n choice getchar while choice y choice Y Cleanup root searchhash int arr int n int a 10 int b i j c j 1 for i 0 i 9 i a i 0 printf 以下为哈希表输出 n for i 0 i n i c arr i 7 A if a c 0 a c arr i else c c 1 7 j a c goto A printf n d 在哈希表的第 d 位 第 d 次放入哈希表 n arr i c j j 1 void SequenceSearch int fp int Length void Search int fp int length void Sort int fp int length void SequenceSearch int fp int Length int data printf 开始使用顺序查询 n 请输入你想要查找的数据 n scanf d for int i 0 i Length i if fp i data printf 经过 d 次查找 查找到数据 d n i 1 data return printf 经过 d 次查找 未能查找到数据 d n i data void Search int fp int length int data printf 开始使用顺序查询 n 请输入你想要查找的数据 n scanf d printf 由于二分查找法要求数据是有序的 现在开始为数组排序 n Sort fp length printf 数组现在已经是从小到大排列 下面将开始查找 n int bottom top middle bottom 0 top length int i 0 while bottom top middle bottom top 2 i if fp middle data top middle 1 else printf 经过 d 次查找 查找到数据 d n i data return printf 经过 d 次查找 未能查找到数据 d n i data void Sort int fp int length printf 现在开始为数组排序 排列结果将是从小到大 n int temp for int i 0 i length i for int j 0 jfp j 1 temp fp j fp j fp j 1 fp j 1 temp printf 排序完成 n 下面输出排序后的数组 n for int k 0 k length k printf 5d fp k printf n struct hash int key int si struct hash hlist 11 int i adr sum d float average void chash int arr int n for i 0 i 11 i hlist i key 0 hlist i si 0