C语言与数据结构实验指导(完整版)

1 Harbin Institute of Technology C 语言与数据结构 实验指导书 刘梅 索莹 田文龙 哈工大电子与信息工程学院 电子工程系 2 实验实验 1 实验平台实验平台 一 实验目的 1 掌握 Microsoft Visual C 6 0 集成环境的使用方法 2 掌握 C 程序在 Microsoft Visual C 6 0 开发环境中的编辑 编译 链接和运 行全过程 二 实验内容 1 启动 Microsoft Visual C 6 0 开发环境 双击桌面应用程序图标或云兄 开始 菜单程序组中的 Microsoft Visual C 6 0 应用程序 启动 VC 如图所示 图 1 1 VC 初始界面 2 建立 C 源程序文件 方法 1 单机工具栏的 新建文本文件 按钮 打开文本文件编辑界面如下图 所示 图 1 2 文本文件编辑界面 方法 2 执行 文件 新建 命令 在 文件 选项卡下选择 C Source File 文 件类型 然后输入 C 源程序文件名和保存文职 如图 所示 然后单击 确定 按钮 打开源程序文件编辑界面 如图 1 4 所示 3 注意 注意 输入 C 源程序文件名时必须带上扩展 c 否则默认创建的是扩展 名为 cpp 的 C 文件 3 编辑源文件 方法 1 在如图 1 2 所示的文本文件编辑界面中输入源程序代码 如图 1 5 所示 方法 2 在如图 1 4 所示的 C 源程序文件编辑界面中编辑源程序代码 如图 1 6 所示 图 1 3 新建文件 图 1 4 C 源程序文件编辑界面 4 图 1 5 文本文件编辑界面编辑源文件 图 1 6 C 源程序编辑界面编辑源文件 4 保存源文件 源文件编辑结束后 执行 文件 保存 命令保存文件 文本文件编辑界面 中编辑的源文件保存时必须在文件名后加上扩展名 c 否则保存的是扩展名为 txt 的文本文件 不能编译运行 5 组件文件 执行 组建 组建 命令或直接按 F7 功能键或单机工具栏 Build 按钮 可 以对源文件进行编译 链接而不运行改程序 当然也可以先执行 组建 编译 快捷键 Ctrl F7 命令编译文件 再执行 组建 组建 快捷键 F7 命令链 接文件 由于 VC 有工作区的要求 所以组建时 系统提示需要建立工作区 如图 1 7 所示 单机 是 按钮 系统会自动建立工作区 组建后的结果如图 1 8 所示 5 图 1 7 提示建立工作区 图 1 8 组建源程序结果 注意 注意 图 1 8 下方的 组建 信息窗口中的内容说明了组建的结果 必须 保证错误 error s 数为 0 才能运行程序 6 运行文件 执行 组建 执行 命令或直接按 Ctrl F5 键或单机工具栏 BuildExecute 按 钮 可以运行程序 结果显示在用户输出窗口中 如图 1 9 所示 图 1 9 用户输出窗口 注意 注意 如果要编辑下一个 C 源程序 由于新建的文件不会自动加入工作区 因此需要先关闭当前工作区 方法是执行 文件 关闭工作空间 命令 或者关闭后重新启动 VC 再按照上述方法建立 编辑新的 C 源文件 让 VC 自动建立工作区 7 运行 加法 程序 在 VC 环境中建立并编辑实现加法运算的源程序 然后组建该文件 结果 如图 1 10 所示 运行该文件 并按要求输入数据 得到运行结果 6 图 1 10 VC 环境下组建 加法 程序后的界面 7 实验实验 2 顺序结构程序设计顺序结构程序设计 一 实验目的 1 掌握上机运行 C 程序的全过程 2 掌握各种格式说明符的使用方法 3 掌握格式输入输出函数 scanf 和 printf 的用法 4 熟悉字符输入输出函数 getchar 和 putchar 的用法 二 实验内容 1 格式说明符的使用 创建并编辑输入输出各个类型数据的程序 分析各个格式说明符的作用 2 编写 输入输出字符 程序 功能如下 使用 getchar 函数接收一个字符 用 printf 函数显示 使用 scanf 函数接收一个字符 用 putchar 函数显示 3 编写 求三角形面积 程序 功能如下 输入三角形三边长 求三角形的面 积 已知三角形的三边长 a b c 则该三角形的面积公式为 09okm 其中 2sabc 4 编写 圆柱体 程序 功能如下 设圆柱体的半径 r 2 5 圆柱高 h 5 0 求 出该圆柱体的表面积和体积 要求 用 scanf 函数输入数据 输出时要求有文 字说明 取小数点后两位数字 三 实验指导 1 格式说明符的使用 参考教材 2 输入输出字符 程序 1 编程分析 1 需要定义字符型变量存放输入的数据 2 用 scanf 函数输入字符时 要注意不要接收缓冲区中已有的字符 2 参考程序 include stdio h main char a b c printf 1 Input a character n a getchar c getchar 8 printf The character is c n n a printf 2 Input a character n scanf c printf The character is putchar b putchar n 3 求三角形面积 程序 1 编程分析 1 该问题的解决过程如下 定义变量输入三角形三边边长计算面积输出结果 2 需要定义实型 float 或 double 变量存放相应的数据 3 计算面积需要用到开平方函数 sqrt 该函数原型包含在头文件 math h 中 因此需要在程序开始将头文件包含进来 4 根据实际情况确定各个变量在输出时的宽度和小数位数 2 参考程序 include stdio h include math h main float a b c s area printf Input a b c n scanf f f f s a b c 2 area sqrt s s s a s b s c printf a 7 2f b 7 2f c 7 2f n a b c printf area 9 2f n area 3 圆柱体 程序 1 编程分析 1 该问题的解决过程如下 定义变量输入半径和高计算表面积和体积输出结果 2 需要定义实型 float 或 double 变量存放相应的数据 9 3 计算过程中需要用到常数 为使用方便 在程序开始用宏定义命令 define 将常数 3 14159 即 用 PI 表示 4 输出数据时根据要求确定各个变量的宽度和小数位数 本例采用 10 2 2 参考程序 include stdio h define PI 3 14159 main float r h double s v printf Input the value of r and h n scanf f f s 2 PI r r 2 PI r h v PI r r h printf The value of s is 10 2f n s printf The value of v is 10 2f n v 10 实验实验 3 选择结构程序设计选择结构程序设计 一 实验目的 1 学会使用逻辑表达式表示条件的方法 2 掌握 switch 语句的用法 二 实验内容 1 switch 语句的应用 编写计算器程序 要求从键盘任意输入两个数值 然后输入一个四则运算符 自动完成运算后输出结果 三 实验指导 1 switch 语句的应用 1 编程分析 1 四则运算共有加 减 乘 除 4 种运算 要做出判断需 使用 switch 语句 2 当输入符号为四则运算之外的符号时 不进行任何运算 但应给出相应的提 示信息 当使用提示信息时 switch 语句应含有 default 子句 2 参考程序 include stdio h void main float x y char p scanf f f p getchar switch p case printf f f f n x y x y break case printf f f f n x y x y break case printf f f f n x y x y break case printf f f f n x y x y break 11 default printf Input is error n 3 程序调试 调试程序时 及非四则运算符的情况都应予以调试 12 实验实验 4 循环结构程序设计循环结构程序设计 一 实验目的 1 通过本实验 加深对循环控制结构有关概念的理解 2 掌握二重循环结构程序的设计方法 二 实验内容 1 阶乘累加问题 编写程序 求 1 2 3 n 的值 2 取彩球问题 有 12 个彩球 3 个白色 5 个红色 4 个黄色 从中任意取 n 个球 求出所有不同的取法 12 2n 三 实验指导 1 阶乘累加问题 1 编程分析 1 本实验内容为求解阶乘问题 2 求 n 用一个循环即可实现 3 求 1 2 3 n 的值 需要在求阶乘程序之外增加一个外重循环 2 参考程序 include stdio h void main long int s 1 t int i j n printf n scanf d for i 2 i n i for t 1 j 1 j i j t j s t printf s ld n s 3 程序调试 1 输入一个不大的正整数 分析程序执行结果 2 输入一个零或者负数 分析程序执行结果 13 3 输入一个很大的正整数 分析程序执行结果 4 当程序结果不符合要求时 修改程序 直到对任何输入数据都能输出正确的 执行结果 或者给出一个明确的提示信息 例如 当输入数据非法时 给出一 个错误的提示信息 2 取彩球问题 1 编程分析 本题用到 穷举 算法 穷举的基本思想是对问题的所有可能性一一测试 直 到找到解或将全部可能状态都测试过为止 穷举 的核心是依次测试循环体 循环控制有两种办法 计数法和标志法 计数法要先确定循环次数 然后逐次 测试 完成测试次数后循环结束 标志法是达到某一目标后循环结束 2 参考程序 incude stdio h void main int n white red yellow count 0 printf Input scanf d printf white red yellow n for white 1 white 3 white for red 1 red 1 count printf Total d n count 3 程序调试 1 输入不小于 2 并且不大于 12 的整数值 查看并分析程序结果 2 输入小于 2 或者大于 12 的整数值 查看并分析程序结果 3 修改程序 使得程序运行时只接受的输入值 并能获得正确结果 12 2n 14 实验实验 5 数组数组 一 实验目的 1 了解数组的特点 掌握一维数组的定义 初始化及其使用方法 2 掌握二维数组的定义 初始化及其使用方法 3 能用一维数组和二维数组解决简单的实际问题 二 实验内容 1 鞍点问题 在二维数组中 若某一位置上的元素在该行中最大 而在该列中最小 则该元 素即为该二维数组的鞍点 要求从键盘输入一个二维数组 当鞍点存在时 把 鞍点找出来 2 选择法排序问题 将存储在一维数组中的 10 个整数用选择法进行排序 三 实验指导 1 鞍点问题 1 编程分析 1 对二维数组按行处理 2 对每一行首先找出它的最大值元素 然后看它在该列上是否为最小值 若是 则找到一个鞍点 3 找到鞍点后输出元素值及其所在的行列值 2 参考程序 define M 3 define N 4 void main int a M N i j k printf 请输入二维数组的数据 n for i 0 i M i for j 0 j N j scanf d for i 0 i M i k 0 15 for j 1 ja i k k j for j 0 j M j if a j k a i k break if j M printf d d d n a i k I k 3 程序调试 1 输入有鞍点的一组数据 查看并分析程序的运行结果 例如 9 80 215 40 60 60 89 1 210 3 101 89 2 输入没有鞍点的一组数据 查看并分析程序的运行结果 例如 9 80 215 40 60 60 189 1 210 3 101 89 2 选择法排序问题 1 编程分析 1 我们已经学习了冒泡法排序 冒泡法排序依次 就有可能交换一次 需要交 换的次数越多 效率越低 2 选择法的基本思路是 第一趟 从所有元素中选择一个最小元素后放在 a 0 中 最多交换一次 第二趟 从 a 1 开始到最后的各元素中选择一个最小元素 放 在 a 1 中 以此类推 M 个数需要进行 M 1 趟比较 但交换的次数比冒泡排序 法少得多 2 参考程序 define M 10 include stdio h void main int a M n i j min temp printf 请输入排序数据 n for i 0 i M i 16 scanf d printf 排序前数列 n for i 0 i M i printf d a i for i 0 i M 1 i min i for j i 1 j M j if a j a min min j temp a i a i a min a min temp printf n 排序后数列 n for i 0 i M i printf d a i 3 程序调试 1 运行程序 任意输入 10 个整数 查看并分析程序执行结果 2 运行程序 输入多余 10 个的整数 查看并分析程序执行结果 3 运行程序 输入一组升序排列的有序整数 查看并分析程序执行结果 4 运行程序 输入一组降序排列的有序的整数 查看并分析程序执行结果 17 实验实验 6 函数函数 一 实验目的 1 掌握自定义函数的一般结构及定义函数和函数调用的方法 2 熟练掌握一维数组作函数的参数时函数的定义和调用方法 熟悉用函数求解 二维数组问题的函数定义及调用方法 二 实验内容 1 选择法排序函数的定义及使用 编写一个用选择法对一维数组升序排序许的函数 并在主函数中调用该排序函 数 实现对任意 20 个整数的排序 三 实验指导 1 选择法排序函数的定义及使用 1 编程分析 这是一维数组作函数参数的问题 1 设计一个对一维数组的前 n 个数用选择法进行排序的函数 select select 函数有两个形参 一个是排序元素数形参 一个是一维数组形参 select 函数 不需要返回值 函数类型说明为 void 型 2 在进行函数调用时 实参和形参要按照参数的意义在位置上对应一致 2 参考程序 define M 20 include stdio h void select int int a 函数声明 void main int a M n i printf 请输入排序数据 n for i 0 i M i scanf d printf 排序前数列 n for i 0 i M i printf d a i select M a 18 printf n 排序后数列 n for i 0 i M i printf d a i void select int n int a int I j min temp for i 0 i n 1 i min i for j i 1 j n j if a j a min min j temp a i a i a min a min temp 3 程序调试 1 运行程序 任意输入 20 个整数 查看并分析程序执行结果 2 把主函数中的函数调用 select M a 改为 select M int i n p q printf 请输入要插入的数据 n scanf d a M n 将要插入的数据放在数组的最后位置 20 for p a i 0 i M i 确定要插入的位置 p if n p q 元素后移 q 1 q p n 插入数据 printf n 插入数据后的数列 n for p a i 0 i M i printf d p i 2 数据插入函数 1 编程分析 1 在实验内容 1 中 解决了用指针法在一维有序数组中插入数据的问题 现只 需对数据的插入处理部分函数化即可 2 插入函数 insert 需要有三个形参 第一个 int 型简单形参 表示要插入的数 据 第二个 int 型简单形参 表示数组中数据的个数 第三个为 int 型指针形参 它将指向一个一维数组 3 在进行函数调用时 insert 函数的第一个实参为要插入的数据 第二个实参 是数组数据个数 第三个实参是数组名 即数组首地址 2 参考程序 define M 10 include stdio h void insert int int int 函数声明 void main int a M 1 10 20 30 40 50 60 70 80 90 99 int i x printf 请输入要插入的数据 n scanf d insert x M a 在有 M 个元素的一维数组 a 中插入 x printf n 插入数据后的数列 n for i 0 i M i 21 printf d a i void insert int x int n int p int t q i t p n 将要插入的数据放在数组的最后位置 for i 0 i n i 确定要插入的位置 p if x t q 元素后移 q 1 q t x 插入数据 22 实验实验 8 线性表的顺序存储系统维护线性表的顺序存储系统维护 一 实验目的 1 掌握线性表的顺序存储的定义和基本使用方法 2 掌握线性表的顺序存储存储单元的排列特点 3 掌握线性表的顺序存储系统的建立 查找 修改 插入 删除操作 学会相 关的函数定义和调用 二 实验内容 1 建立一个顺序表 2 能够对建立的顺序表进行查找 修改 插入 删除等操作 当输入指令错误 时 能够提示错误信息 主函数中可以选择由 switch case 语句构成主菜单 再 根据提示进行相应操作 3 使用 C 语言程序编写 三 实验指导 1 编程分析 1 在线性表的建立时 可直接用数组赋初值 2 在查找功能中要实现的功能为 当能找到时该值时返回该值所在节点 找不 到时返回 1 3 修改功能是在查找的基础上 将找到的值加以修改 4 在插入功能中要实现的功能为 在找到指定节点后 当线性表满时 提示不 能插入 当线性表不满时 插入数据 5 删除功能主要实现 当线性表为空或者删除位置超出线性表长度时 都显示 位置错误 其他情形进行删除操作 2 参考程序 include define max 20 int last 20 23 int node max 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int find int find num void insert int insert pot int insert num void delet int delete pot void modify int renew pot int renew num void list printf int main printf please enter number n1 查找 n2 删除 n3 修改 n4 插入 n5 退出系 统 n int flag 0 int find num delete pot int renew pot renew num int insert pot insert num int findresult int choice do scanf d switch choice case 1 printf please enter the find num n scanf d findresult find find num printf findresult d n findresult break case 2 printf please enter the delete pot n scanf d list printf printf n delet delete pot printf after delete n list printf 24 break case 3 printf please enter the renew pot and renew num n scanf d d printf before modify n list printf modify renew pot renew num printf after modify n list printf break case 4 printf please enter the insert pot and insert num n scanf d d printf before insert n list printf insert insert pot insert num printf after insert n list printf break case 5 flag 1 break default printf input error n break while flag return 0 int find int find num 查找值为 find num 的节点 int k 0 findi int flag 0 findi 0 while klast 1 delete pot 0 printf wrong position n else for i delete pot i insert pot 1 i node i 1 node i node p 1 insert num last last 1 void list printf 输出表的内容 int i for i 0 i last 1 i printf d node i printf n 27 实验实验 9 线性表的链式存储系统维护线性表的链式存储系统维护 一 实验目的 1 掌握线性表的链式存储的定义和基本使用方法 2 掌握线性表的链式存储存储单元的排列特点 3 掌握线性表的链式存储系统的建立 遍历 插入 查找 删除操作 学会相 关的函数定义和调用 二 实验内容 1 建立一个链表 2 能够对建立的链表进行查找 修改 插入 删除等操作 当输入指令错误时 能够提示错误信息 主函数中可以选择由 switch case 语句构成主菜单 再根据 提示进行相应操作 3 使用 C 语言程序编写 三 实验指导 1 编程要求 1 以循环的方式建立一个有表头的链表 2 遍历链表 并计算链表结点个数 3 在查找功能中要实现 当能找到时打印该值的前驱结点 找不到时输出 没 找到 4 在插入功能中要实现 在某个特定的结点之后插入一个结点 5 在删除功能主要实现 删除特定值的结点 注意区分该节点是否为链表结尾 2 参考程序 include include struct Node int data struct Node next void Build struct Node L 建立一个带头结点的单链表 int n struct Node p q 28 p L printf 请输入 n 和 n 个数据元素 n scanf d while n q struct Node malloc sizeof struct Node scanf d q next NULL p next q p q void Print struct Node L 计算单链表的长度 然后遍历输出单链表 int num 0 struct Node p p L next while p num printf d p data p p next printf n 长度为 d n num void Tips 选择函数 printf 按数字键选择相应操作 n printf 输出单链表及其长度 n printf 查找值为 x 的前驱结点 n printf 删除值为 x 的结点 n printf 在值为 y 的结点后插入值为 x 的结点 n printf 退出 n void Find struct Node L int x 查找值为 x 的直接前驱结点 p 29 struct Node p p L while p next if p next printf d 的前驱结点为 d n x p data else printf 没找到 n void Delete struct Node L int x 删除值为 x 的结点 struct Node p q p L while p next if p next if p next next q p next p next q next free q else q p next p next NULL free q printf 删除成功 n else printf 链表中没有 d n x 30 void Insert struct Node L struct Node x int y 在值为 y 的结点后插入值为 x 的结点 struct Node p p L while p next NULL if p data y printf No Find Y else x next p next p next x printf 插入成功 n int main int choice x y flag struct Node L p L struct Node malloc sizeof struct Node L next NULL L data 1 Build L 建立一个带头结点的单链表 Tips 选择函数 scanf d while choice switch choice case 1 Print L 计算单链表的长度 然后遍历输出单链表 break 31 case 2 printf 请输入要查找的元素 X n scanf d Find L x 查找 break case 3 printf 请输入要删除的元素 X n scanf d Delete L x 删除 break case 4 printf 请输入要插入的元素 X 及其前结点 Y X Y n scanf d d p struct Node malloc sizeof struct Node p data x Insert L p y 插入 break default break Tips scanf d 下一步操作选择 return 0 32 实验实验 10 二叉树的遍历二叉树的遍历 一 实验目的 1 理解二叉树的原理 掌握二叉树的存储方法 2 掌握二叉树前 中 后序顺序遍历的过程 3 掌握前 中 后序遍历二叉树程序的编写 并用递归与非递归方法分别实现 二 实验内容 1 输入数据建立一棵二叉树 2 输出其前 中 后序遍历的结果 分别用递归与非递归方法实现 3 使用 C 语言程序编写 三 实验指导 1 编程分析 1 在二叉树的建立时 先用递归算法建立一颗二叉树 以所输入的字母为其数 据项 当输入为 时 所对应的节点为空 2 分别以前 中 后序遍历二叉树 打印相应的节点值 2 参考程序 1 前序非递归遍历二叉树 include include define MAX 100 struct node int data struct node llink struct node rlink shutree NULL void preorder struct node t int main struct node createtree struct node tree shutree createtree shutree preorder shutree 33 return 0 void preorder struct node tree struct node p struct node s MAX int top top 1 p tree do while p NULL printf c p data if p rlink NULL top top 1 s top p rlink p p llink if top 1 p s top top top 1 while p NULL top 1 struct node createtree struct node tree char ch scanf c if ch tree NULL else 34 tree struct node malloc sizeof struct node tree data ch createtree tree llink createtree tree rlink return tree 2 前序递归遍历二叉树 void PreOrder struct node tree struct node p p tree if p NULL printf c root data PreOrder p lchild PreOrder p rchild 3 中序非递归遍历二叉树 void Inorder struct node tree struct node p struct node s MAX int top top 1 p tree do while p NULL if p rlink NULL top top 1 35 s top p p p llink if top 1 p s top printf c p data top top 1 p p rlink while p NULL top 1 4 中序递归遍历二叉树 void InOrder struct node tree struct node p p tree if p NULL InOder p lchild printf c root data InOrder p rchild 5 后序非递归遍历二叉树 void postorder struct node tree struct node p struct node q NULL struct node s MAX int top top 1 p tree do 36 while p NULL if p rlink NULL top top 1 s top p rlink p p llink p s top top top 1 if p rlink NULL p rlink q printf c p data q p p NULL else p p rlink while p NULL top 1 6 后序递归遍历二叉树 void PostOrder struct node tree struct node p p tree if p NULL PostOrder p lchild PostOrder p rchild printf c root data 37 实验实验 11 二叉排序树系统维护二叉排序树系统维护 一 实验目的 1 掌握二叉排序树定义和基本使用方法 2 掌握二叉排序树存储数据的排列特点 3 掌握二叉排序树系统的建立 插入 查找 替换 删除操作 学会相关的函 数定义和调用 二 实验内容 1 输入数据自行建立一棵二叉排序树 2 能够对建立的二叉排序树进行查找 插入 替换 删除等操作 当输入指令 错误时 能够提示错误信息 主函数中可以选择由 switch case 语句构成主菜单 再根据提示进行相应操作 3 使用 C 语言程序编写 三 实验指导 1 编程分析 1 在建立一棵二叉排序树时 可以采用反复调用插入函数直到整个二叉排序树 建立完成 2 查找功能主要实现 若找到返回该节点指针并打印 找到了 否则返回空 并打印 没找到 3 在删除时 要充分考虑到被删除节点的各种情况 是否有左子女 是否有右 子女 是否有双亲 4 替换功能的实质是将一个节点删除 然后再插入一个新节点 2 参考程序 include include include define MAX 9 int a MAX struct node 38 int data struct node llink struct node rlink shutree NULL f fp int main int n i k x y int flag1 0 struct node find struct node tree int x 查找 struct node findparents struct node tree int x