《数据结构》实验教案113.docx
- 文档编号:18384492
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:21
- 大小:25.12KB
《数据结构》实验教案113.docx
《《数据结构》实验教案113.docx》由会员分享,可在线阅读,更多相关《《数据结构》实验教案113.docx(21页珍藏版)》请在冰点文库上搜索。
《数据结构》实验教案113
数据结构
实验报告
实验课程:
数据结构
学号:
2016031124
学生姓名:
郑世林
班级:
16软件
2017年月日
实验一函数与结构体(复习)
一、实验目的:
巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点,加强学习数据结构语言基础.
二、实验要求
1、学生提前准备好实验报告,预习并熟悉实验步骤;
2、遵守实验室纪律,在规定的时间内完成要求的内容;
3、1~2人为1小组,实验过程中独立操作、相互学习。
三、实验内容:
1.用数组处理Fibonacci数列问题。
已知Fibonacci数列:
112358132134……输出数列的前20项.
#include〈stdio。
h〉
intmain()
{
inta[22],i,n;
a[0]=a[1]=1;
for(i=2;i<21;i++)
a[i]=a[i-1]+a[i-2];
printf(”%d”,a[0]);
for(i=1;i<21;i++)
printf(”%d”,a[i]);
printf(”\n”);
return0;}
2.下面的程序的功能是:
输入三个整数,输出其中最大的数,补足所缺语句.
#include h〉 intmax(intx,inty);/*函数max的声明*/ intmax3(intx,inty,intz);/*函数max3的声明*/ voidmain() { inta,b,c,m; printf(”请输入三个整数,用逗号隔开: \n”); scanf("%d,%d,%d",&a,&b,&c);/*从键盘接收3个整数*/ m=max3(a,b,c); printf("Maxis%d\n”,m); getch(); } intmax(intx,inty)/*函数功能: 返回x、y的最大值*/ { return(x>y? x: y); } intmax3(intx,inty,intz)/*函数功能: 返回x、y、z的最大值*/ { intm; m=max(max(x,y),z); returnm; } 3。 学生信息的显示,具体要求如下: 1)定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址); 2)设计一个函数,用于显示单个学生信息,函数的参数为前面定义的结构体类型; 3)设计一个主函数,在主函数中输入学生的信息,并调用前面定义的函数进行显示(学生人数不少于5人)。 提示: 可用结构体数组保存学生信息。 4.输入若干个整数作为数组元素值,然后按输入时顺序的就地逆置排序,最后打印出逆置后的元素值.例如输入: 1023045,逆置后显示为: 5430210。 四、程序运行结果和源代码为: 此处写程序源代码,请在程序中适当注释,便于老师更快地看懂你的程序. 此处写出程序运行的结果,即输入数据是什么,输出数据是什么,分析结果是否正确,如果不正确是什么原因。 五、实验总结 1、收获 2、存在的问题 实验二线性表的算法实现 一、实验目的: 1、掌握线性表的定义方法; 2、。 掌握线性表基本操作的实现方法; 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习. 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处。 1、线性表的定义: #defineMAX最大长度值 typedefstruct {datatypedata[MAX]; intlast; }list; 2、线性表的初始化 思路: 顺序表的初始化就是构造一个空表,或者说是为了给线性表l分配存储空间。 由于采用的是静态存储结构(数组),线性表的存储空间是由编译系统分配的,因此,只要对线性表的长度进行初始化即可。 3、求线性表的长度 4、插入运算 思路: 在保证所给插入位置i合理的前提下,必须先将第i个及其以后的数据元素,向后移动一个元素的位置,然后才能将新的元素x存入留出的空位置上,插入后使原表长last的长度值加1。 5、删除运算 思路: 在此讨论线性表的删除运算是指将表中第i个元素从线性表中去掉,因为是顺序存储结构,在保证所给删除位置i合理的前提下,删除后必须将第i+1个及其以后的元素前移一个位置,最后表的长度减1。 6、查找 思路: 在此讨论线性表的查找是指在线性表中查找与给定值x相等的数据元素。 从线性表的第一个元素l->data[1]起依次和x比较,直到找到一个与x相等的数据元素,则返回它在线性表中的存储下标;或者查遍整个表都没有找到与x相等的元素,返回0. 7、线性表元素的输出 8、主函数main() 程序结构: (1)声明变量及线性表; (2)初始化线性表; (3)输入线性表的元素(提示: 用插入算法来实现); (4)输出线性表中的元素; (5)显示线性表的长度; (6)在线性表中进行元素查找(可提供元素值,也可以提供元素位置); (7)往线性表中插入数据元素(提供元素值及位置); (8)删除线性表中的数据元素(提供元素值或位置); (9)输出线性表中最后的结果. 四、程序运行结果和源代码为: 五、实验总结: 1、收获 2、存在的问题 实验三线性表的应用 一、实验目的: 1、进一步掌握线性表的定义方法; 2、进一步掌握线性表基本操作的实现方法; 3、掌握线性表的应用。 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习. 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处。 1、有两个线性表la和lb,类型为list。 编写一个算法将它们合并成一个线性表la,要求将lb接到la的后面,并且要求lb中的元素在la中已存在,则不把该元素合进去。 算法思路: 把线性表la和lb的长度分别赋给n和m;从lb中的第一个元素起,对每一个元素与la中的每一个元素进行查找比较,若未找到则将这个lb元素插入到la表尾,否则继续比较下一个,直到lb中所有元素比较完,则合并完成;并应保证la表足够长. 2、已知一个线性表la中的元素已按升序排列,其类型为list。 编写一个算法将该线性表中的重复元素删除(即在表中不能有相同的元素)。 算法思路: 由于线性表la中的元素已按升序排列,所以值相同的元素必为相邻的元素,因此依次比较相邻的两个元素,若值相等,则删除其中的一个,否则继续向后比较,直到表尾。 3、有顺序表A和B,其元素均按从小到大的升序排列,编写一个算法将它们合并成一个顺序表C,要求C的元素也是从小到大的升序排列。 算法思路: 依次扫描通过A和B的元素,比较当前的元素的值,将较小值的元素赋给C,如此址到一个线性表扫描完毕,然后将未完的那个顺序表中余下部分赋给C即可。 C的容量要能够容纳A、B两个线性表相加的长度。 4、主函数main() 程序结构: (1)声明变量及线性表; (2)初始化线性表; (3)输入线性表的元素(提示: 用插入算法来实现); (4)输出线性表中的元素; (5)对两个线性表进行按升序合并 (6)输出合并后线性表中元素. 四、程序运行结果和源代码为: 五、实验总结: 1、收获 2、存在的问题 实验四栈的实现 一、实验目的: 1、理解栈的线性结构的特点; 2、掌握栈的顺序表示; 2、掌握栈基本操作的实现方法; 3、能够应用栈设计算法解决实际问题。 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习。 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处. 1、栈的定义: #defineMAX栈中允许存放元素的最大个数 typedefstruct {datatypedata[MAX]; inttop; }stack; 2、栈的基本算法的实现 ⑴栈初始化: init(s)构造了一个空栈; ⑵判栈空: empty(s)若栈s为空栈返回为1,否则返回为0; ⑶入栈: push(s,x)在栈s的顶部插入一个新元素x,使x成为新的栈顶元素; ⑷出栈: pop(s)栈s的顶部元素从栈中删除; ⑸读栈顶元素: get(s)取栈顶元素作为结果返回; ⑹置栈空: clear(s)清除栈s中的所有元素,使之成为空栈。 利用主函数main()调用上述函数. 3、利用栈结构实现“数制转换”问题 要求: 输入的一个十进制数,能够转换成相应的八进制数,并输出. 思路: 把十进制数转换为八进制数采用的方法是“除8取余”,直到商为0。 依次得到的余数是k1,k2,k3,……,km,而转换后的八进制数是kmkm-1…k3k2k1,从结果看恰好与计算过程相反,因此转换过程中每得到一位八进制数则进栈保存,转换完毕后依次出栈则正好是转换结果.此种方法同样适用于将十进制数转换为r进制的数。 把十进制整数11转换为八进制的过程如下: (1)定义“栈”的结构 (2)实现“栈"的基本操作 ①栈初始化操作InitStack ②进栈操作Push ③出栈操作Pop ④判断栈是否为空操作Empty (3)实现主程序main() 主程序主要是用来控制程序的执行过程,实现数制的转换操作,以及输入、输出。 程序结构: ①声明变量及栈; ②初始化栈; ③输入要转换的十进制数; ④进行进制转换,余数入栈,商作为被除数继续运算; ⑤显示转换后的八进制数(利用出栈)。 (4)程序的编译、链接 (5)程序的调试 4、双栈操作 设有两个栈s1和s2共享一个连续的存储空间ds[1]~ds[m],它们对应的栈顶指针分别是top1和top2,s1的栈底设在ds[1]处,s2的栈底设在ds[m]处,分别编写s1和s2的进栈函数push(ds,x,k)和出栈函数pop(ds,k)。 提示: 利用一个变量判断应对s1还是s2进行操作。 算法思路: 按提示设当K=1时对s1进行操作,否则对s2进行操作。 当top2=top1+1表示栈满,都不能进栈,当top1=0时s1不能出栈,而top2=m+1时s2不能出栈。 四、程序运行结果和源代码为: 五、、实验总结: 1、收获 2、存在的问题 实验五栈的应用和队列的实现 一、实验目的: 1、理解栈和队列的定义及线性存储; 2、掌握栈和队列的运算方法; 3、了解循环队列的定义及相关算法; 3、能够应用栈和队列设计算法,解决实际问题. 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习。 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处。 1、队列的定义: #defineMAX队列的最大容量 typedefstruct {datatypedata[MAX]; intf,r; }queue; 2、队列的基本算法的实现 (1)队列初始化: init(q) (2)入队操作: insert(q,x) 思路: 入队时,首先判队是否满了,队满的条件为: q—〉r==MAX—1,队满时,不能入队,可以进行溢出错误处理,若可以入队则先将队尾指针后移(q-〉r++),再将元素赋给队尾单元。 (3)出队操作: delete(q,x) 思路: 先判队列是否为空,为空时不能出队,若可以出队,则可先将队首元素赋给指定变量(若不需要保留,可以省去这一步),队首指针后移(q->f—-). (4)读队头元素: get(q,x) 思路: 先判队列是否为空,为空时不能取元素,否则取出队首元素,但队首指针保持不变。 (5)判队空操作: empty(q) (6)置队空: clear(q) 3、利用栈结构实现“算术表达式”问题 要求: 输入的一个十进制数,能够转换成相应的八进制数,并输出。 思路: 1、先将输入的中缀表达式,存入字符数组a中,取出a数组中的每一个字符存于c变量中,对于每一个c变量的值做如下处理: ①若c为数字,则存于数组b中; ②若c为左括号'(',则将其压入栈s; ③若c为右括号')',则将栈s中左括号’(’以后的运算符依次出栈,存于数组b中,然后将左括号'('出栈; ④若c为’+’或'—',则将栈s中左括号’('以后的所有运算符依次出栈,存于数组b中,然后将c压入栈s中; ⑤若c为’*’或’/',则将栈s中的栈顶端连续的'*'或'/’出栈,存于数组b中,然后将c压入栈s中 ⑥若c为’=',则将栈S中的所有运算符依次出栈,存于数组b中,然后将c存于数组b中,最后得到的后缀表达式存储在字符数组b中。 2、后缀表达式求值 具体思路: 需要一个存放数值的栈s1,当从左向右扫描表达式时,每遇到一个操作数就送入栈中保存,每遇到一个运算符就从栈中取出两个操作数进行当前的计算,然后把结果再入栈,直到整个表达式结束,这时栈顶存放的值就是后缀表达式的结果. 4、主程序主要是用来控制程序的执行过程. 四、程序运行结果和源代码为: 五、、实验总结: 1、收获 2、存在的问题 实验六—-八链表的建立及应用、链栈及链队列 一、实验目的: 1、理解单链表的定义及存储结构; 2、掌握单链表的基本运算方法; 3、了解链栈和链队列的应用方法; 4、能够应用单链表设计算法,解决实际问题。 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习。 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处。 单链表的定义: typedefstructnode {datatypedata; structnode*next; }linklist; 1、利用首插法和尾插法实现单链表的创建. 2、单链表的插入运算。 要求: 在单链表的第i个元素之前插入一个元素x。 实现思想: (1)找到第i—1个元素 (2)在i-1个元素之后插入x 3、在单链表中按值查找。 算法思路: 从链表的第一个元素结点起,判断当前结点其值是否等于x,若是,返回该结点的地址,否则继续向后查找,直到链表结束为止。 找不到时返回空。 4、单链表的删除运算。 (1)在指定位置删除。 要求: 删除单链表的第i个元素 实现思想: 1、找到第i—1个元素;2、删除第i个元素。 (2)根据所给条件找到位置再进行删除。 5、试写一算法求带头结点的单链表L的长度。 思路: 单链表的长度是指单链表中结点的个数。 求单链表表长的基本操作是移动指针,将指针从表头移动到表尾。 在指针移动过程中,累计扫描过的结点数即为表长。 由此需要设一个指针p,顺链向后移动;还要设一个整型变量j,作为计数器.指针p的初始值指向头结点,计数器j的初始值为0。 程序参考: intLength_LinkList1(LinkListL) {Lnode*p=L;/*p指向头结点*/ intj=0; while(p->next) {p=p—〉next;j++}/*p所指的是第j个结点*/ returnj; } 6、已知带头结点的动态单链表L中的结点是按整数值递增排列的,试写一算法将值为x的结点插人表中,使L仍然有序. 7、试写一算法对带头结点的单链表实现就地逆置. 算法描述: (1)空表或长度为1的表不做任何处理 (2)长度大于等于2时,做如下处理: 从表中第二个结点开始,依次取原链表中的结点,将其作为第一个结点插入到新链表中去。 8、编程序判断一个字符序列是否是回文,要求采用链式队列和链式堆栈。 算法提示: 设字符数组str中存放了要判断的字符串.把字符数组中的字符逐个分别存入队列和堆栈,然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等,若全部相等则该字符序列是回文,否则就不是回文。 四、程序运行结果和源代码为: 五、、实验总结: 1、收获 2、存在的问题 实验九——十二叉树的建立及遍历 一、实验目的: 1、熟悉二叉链表表示的二叉树结构及其递归遍历; 2、掌握建立二叉链表要领; 3、理解递归遍历二叉链表的执行路径; 4、掌握二叉树的中序遍历的非递归思路;了解二叉树的后序遍历的非递归思路 5、能利用二叉树的遍历策略解决实际问题; 6、了解哈夫曼编码的思路及方法. 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习。 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处. 二叉树的二叉链表存储表示可描述为: typedefstructbitnode {elemtypedata; structbitnode*lchild,*rchild; /*左、右孩子指针*/ }bintree; 1、建立一颗二叉链表表示的二叉树. 思路: 先将二叉树通过加入虚节点的方式使其完全化,然后按层将其输入。 可以用二叉树中不会出现字符表示虚节点例如#,用例二叉树如图1所示。 图1 输入该二叉链表时,应按如下顺序: AB#DE###C##. 2、对其进行先序,中序,后序输出。 (用递归方法实现) (1)先序遍历 (2)中序遍历 (3)后序遍历 3、实现二叉树的中序遍历的非递归算法。 提示: 二叉树以二叉链表存放,一维数组stack[MAX]用以实现栈,变量top用来表示当前栈顶的位置. 4、统计二叉树中叶结点的数目 算法思想: (1)若二叉树为空,则它的叶结点的数目为0 (2)若二叉树只有一个结点,则它的叶结点的数目为1 (3)否则,它的叶结点的数目等于左子树的叶结点的数目和右子树叶结点的数目之和。 5、求二叉树的深度 算法思想: (1)若二叉树为空,则它的深度等于0 (2)否则,它的深度等于左子树和右子树中的最大深度加1。 6、在二叉树中查找数据元素 算法思想: 在二叉树中查找数据元素x。 查找成功时返回该结点的指针;查找失败时返回空指针. 7、实现哈夫曼编码 实现哈夫曼编码的算法可分为两大部分: (1)构造哈夫曼树; (2)在哈夫曼树上求叶子结点的编码. 求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0,1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码为所求编码的高位码。 可以设置一结构数组huffcode用来存放各字符的哈夫曼编码信息,数组元素的结构如下: bit start 其中,分量bit为一维数组,用来保存字符的哈夫曼编码,start表示该编码在数组bit中的开始位置。 所以,对于第i个字符,它的哈夫曼编码存放在huffcode[i]。 bit中的从huffcode[i].start到n的分量上. 8、完成知识实践九。 四、程序运行结果和源代码为: 五、、实验总结: 1、收获 2、存在的问题 实验十一静态查找 一、实验目的: 1、加深对查找的理解; 2、掌握静态查找表的存储结构; 3、掌握顺序查找、二分查找及其查找的算法. 4、了解分块查找的思路。 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习。 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处。 静态查找表的顺序存储结构 typedefstruct {elemtypeelem[MAX];/*数组基址*/ intlength;/*表长度*/ }s_tbl; 静态查找表的链式存储结构 typedefstructnode {elemtypeelem;/*结点的值域*/ structnode*next;/*下一个结点指针域*/ }nodetype; (一)顺序查找算法的实现 1、正确设计程序,并编译、链接成可执行文件 (1)首先正确写出查找表的结构体typedefstructSSTable (2)正确写出顺序查找算法Search_Seq (3)写出主程序main,提供输入与输出操作 本程序的特点是对于用户给定的一组关键字序列(64,80,13,56,37,92,19,05,88,21,75),采用顺序查找算法找到给定的关键字,并返回其在查找表中的下标. 2、进行程序测试 直接运行可执行文件,通过不同的值来观察输出结果。 (二)折半查找算法的实现 1、正确设计程序,并编译、链接成可执行文件 (1)首先正确写出查找表的结构体typedefstructSSTable (2)正确写出折半查找算法Search_Bin (3)写出主程序main,提供输入与输出操作 本程序的特点是对于用户给定的一组有序的关键字序列(05,13,19,21,37,56,64,75,80,88,92),采用折半查找算法找到给定的关键字,并返回其在查找表中的下标。 2、进行程序测试 直接运行可执行文件,通过不同的值来观察输出结果。 四、程序运行结果和源代码为: 五、、实验总结: 1、收获 2、存在的问题 实验十二——十三排序 一、实验目的: 1理解排序的定义和各种排序方法的特点,并能灵活运用。 2。 掌握常用的排序方法,并掌握用高级语言实现排序算法的方法。 3.了解各种方法的排序过程及其依据的原则。 二、实验要求 1、学生提前准备好实验报告,预习并熟悉实验步骤; 2、遵守实验室纪律,在规定的时间内完成要求的内容; 3、1~2人为1小组,实验过程中独立操作、相互学习. 三、实验内容及思路: 要求: 将调试好的代码存放到各算法的空白处。 1、对于给定的整数序列(49,38,65,97,76,13,27,49),实现直接插入排序。 思路: 将R[i]插入到有序表R[1.。 i-1]中,进行如下操作: (1)暂存记录R[i],即R[0]=R[i] (2)用顺序查找的方法对有序表进行倒序扫描,并将关键字大于R[0]的记录后移,直到找到一个记录R[j],其关键字小于R[0]结束 (3)将记录R[0]存于R[j+1]中 2、对于给定的整数序列(49,38,65,97,76,13,27,49),实现折半插入排序. 思路: 折半查找时,将待插入记录的关键字和处于有序序列中间位置记录的关键字比较,若待插入的记录关键字小于有序序列中间位置记录的关键字,则high=mid—1;否则,low=mid+1。 依此查找下去,直到low〉high时,由折半查找得到的插入位置为low或high+1。 3、对于给定的整数序列(49,38,65,97,76,13,27,49),实现冒泡排序。 思路: 每趟排序都从头开始扫描待排记录的序列,并按顺序依次比较相邻两个记录关键字的大小,若与排序要求相逆,则将两者交换.不断将相邻的两记录中关键字大的记录向后移动,最后将待排记录序列中的关键字最大的记录换到待排序列的末尾。 通过第一趟排序,将最大关键字记录移动到第n个位置,然后进行第二趟排序,这趟只需对前n—1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 教案 113