数据结构实验教案(76页全)

1、数据结构实验教案数据结构实验教案指导教师：李辉指导教师：李辉数据结构实验教学课件数据结构实验教学课件实实 验验 简简 介介 本课程是结合理论课程本课程是结合理论课程数据结构数据结构安排的实践安排的实践课程，目的是通过本课程的实践与操作，加深理课程，目的是通过本课程的实践与操作，加深理论课程中数据结构与算法的理解，理论与实践密论课程中数据结构与算法的理解，理论与实践密切结合，相辅相成。切结合，相辅相成。 实验着眼于原理与应用的结合，使学生学会如何实验着眼于原理与应用的结合，使学生学会如何把书上学到的知识用于解决实际问题，培养软件把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一

2、方面，能使书上的工作所需要的动手能力；另一方面，能使书上的知识变知识变“活活”，起到深化理解和灵活掌握教学内，起到深化理解和灵活掌握教学内容的目的。容的目的。数据结构实验教学课件数据结构实验教学课件实实 验验 环环 境境 硬件环境：微型计算机；硬件环境：微型计算机； 软件环境：软件环境：windows操作系统；操作系统； VisualC+6.0或或Visual Studio数据结构实验教学课件数据结构实验教学课件实实 验验 教教 材材 数据结构实验与实训教程数据结构实验与实训教程刘勇刘勇 等等 国防工业出版社国防工业出版社数据结构实验教学课件数据结构实验教学课件实验一、线性结构基本算法的实现实

3、验一、线性结构基本算法的实现实验目的实验目的：1. 掌握线性表的顺序存储结构的定义及掌握线性表的顺序存储结构的定义及C语言实现，语言实现，掌握顺序表中的各种基本操作（顺序表的建立、插入、掌握顺序表中的各种基本操作（顺序表的建立、插入、删除等）；删除等）；2. 掌握线性表的链式存储结构掌握线性表的链式存储结构-单链表的定义及单链表的定义及C语言语言实现，掌握单链表中的各种基本操作（单链表的建立、实现，掌握单链表中的各种基本操作（单链表的建立、合并、删除重复值等）。合并、删除重复值等）。数据结构实验教学课件数据结构实验教学课件实验内容（一）：实验内容（一）：实验实验1主要实现创建一个顺序表，建立一

4、主要实现创建一个顺序表，建立一个顺序表，输出一个顺序表。个顺序表，输出一个顺序表。实验实验2主要实现顺序表的插入操作。主要实现顺序表的插入操作。实验实验3主要实现顺序表的删除操作主要实现顺序表的删除操作自主编程实现顺序表的查找操作。自主编程实现顺序表的查找操作。数据结构实验教学课件数据结构实验教学课件实验要求：实验要求：认真看书，理解本节系列算法的思想认真看书，理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果，并结合程序进保存和打印出程序的运行结果，并结合程序进行分析。行分析。按照你对线性表的操作需要，编写

5、主程序并运按照你对线性表的操作需要，编写主程序并运行，打印出文件清单和运行结果行，打印出文件清单和运行结果写出实验报告写出实验报告数据结构实验教学课件数据结构实验教学课件顺序表的创建和输出：顺序表的创建和输出：数据结构实验教学课件数据结构实验教学课件主程序：#include #include SqList.h数据结构实验教学课件数据结构实验教学课件顺序表的插入：顺序表的插入：顺序表的删除操作：顺序表的删除操作：数据结构实验教学课件数据结构实验教学课件实验内容（二）：实验内容（二）：1实现创建一个单链表，建立一个单实现创建一个单链表，建立一个单链表，输出一个单链表链表，输出一个单链表2有序单链表

6、的合并有序单链表的合并.3删除单链表的重复值（选作）。删除单链表的重复值（选作）。4主要实现单循环链表的逆置（选主要实现单循环链表的逆置（选作）。作）。数据结构实验教学课件数据结构实验教学课件单链表的创建和输出：单链表的创建和输出：数据结构实验教学课件数据结构实验教学课件单链表的合并：单链表的合并：数据结构实验教学课件数据结构实验教学课件单链表的合并：单链表的合并：数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件删除单链表的重复值：删除单链表的重复值：数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件单循环链表的逆置：单循环链表的逆

7、置：数据结构实验教学课件数据结构实验教学课件实验二实验二 栈与队列的应用栈与队列的应用 实验目的实验目的: 1、熟悉栈的特点（先进后出）及栈的基本操作，、熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。存储结构和链式存储结构上的实现。 2、熟悉队列的特点（先进先出）及队列的基本、熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。队列的顺序存储结构和链式存储结构上的实现。数据结

8、构实验教学课件数据结构实验教学课件 实验内容：（一）实验内容：（一） 1、利用顺序栈各种基本运算的算法（实验、利用顺序栈各种基本运算的算法（实验1） 2、实现链栈各种基本运算的算法（实验、实现链栈各种基本运算的算法（实验2选选作）作） 3、实现数值转换算法。（写在预习本上）。、实现数值转换算法。（写在预习本上）。数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件栈的基本操作：栈的基本操作：数据结构实验教学课件数据结构实验教学课件栈的基本操作：栈的基本操作：数据结构实验教学课件数据结构实验教学课件链栈的基本操作：链栈的基本操作：数据结构实验教学课件数据结构实验教学课

9、件链栈的基本操作：链栈的基本操作： 实验内容：（二）实验内容：（二） 1、利用顺序队列实现各种基本运算的算法、利用顺序队列实现各种基本运算的算法（实验（实验3）。）。 2、利用链队列实现各种基本运算的算法（实、利用链队列实现各种基本运算的算法（实验验4） 3、完成上次没完成的内容。、完成上次没完成的内容。数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件数据结构实验教学课件顺序队列的基本操作：顺序队列的基本操作：数据结构实验教学课件数据结构实验教学课件顺序队列的基本操作：顺序队列的基本操作：数据结构实验教学课件数据结构实验教学课件链队列的基本操作：链队列的基本操作：数据结构实验教学课

10、件数据结构实验教学课件链队列的基本操作：链队列的基本操作：实验要求：实验要求：认真看书，理解本节系列算法的思想认真看书，理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果，并结合程序进保存和打印出程序的运行结果，并结合程序进行分析。行分析。编写主程序并运行，打印出文件清单和运行结编写主程序并运行，打印出文件清单和运行结果。果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件实验三实验三 串串 实验目的实验目的: (1) 掌握字符串的基本操作。掌握字符串的基本操作。 (2) 熟悉串函数的实现

11、方法。熟悉串函数的实现方法。数据结构实验教学课件数据结构实验教学课件实验三实验三 串串 实验内容实验内容: (1) 完成实验指导书实验一内容。完成实验指导书实验一内容。 (2) 独立编程实现串的联接操作（写在预习独立编程实现串的联接操作（写在预习本上）。本上）。数据结构实验教学课件数据结构实验教学课件实验四实验四 数组数组 实验内容实验内容: (1) 完成实验指导书完成实验指导书P71基础实验中建立三基础实验中建立三元组顺序表，输出三元组顺序表和矩阵的元组顺序表，输出三元组顺序表和矩阵的转置的内容。转置的内容。 (2) 自主编程实现快速转置的算法。自主编程实现快速转置的算法。数据结构实验教学课

12、件数据结构实验教学课件 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型028003600070500140121415-522-731363428 有两种解决方法：有两种解决方法： 1 1、按照矩阵、按照矩阵M M的列序来转置。的列序来转置。1 2 1

13、41 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + n

14、umcol-1; for (p=1; pdata = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; / CreateBiTree三、算法的递归描述三、算法的递归描述void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树 if (T) visit(T-data); / 访问结点 Preorder(T-lchild, visit); / 遍历左子树 Preorder(T-rchild, visi

15、t);/ 遍历右子树 void Inorder (BiTree T, void( *visit)(TElemType& e) / 中序遍历二叉树 if (T) Inorder(T-lchild, visit); / 遍历左子树 visit(T-data); / 访问结点 Inorder(T-rchild, visit);/ 遍历右子树 void Postorder (BiTree T, void( *visit)(TElemType& e) / 中序遍历二叉树 if (T) Postorder(T-lchild, visit); / 遍历左子树 Postorder(T-rchi

16、ld, visit);/ 遍历右子树 visit(T-data); / 访问结点 void Inorder_I(BiTree T, void (*visit) (TelemType& e) InitStack S; p=T; while(p|！StackEmpty(S) if (p)Push(S,p);p=p-lhild; else Pop(S,p); if(!Visit(p-data) return ERROR; p=p-rhild ; / else/ WhileReturn OK; 实验内容实验内容： 1、实验、实验3用递归算法实现统计二叉树叶子结用递归算法实现统计二叉树叶子结点个

17、数（必做）点个数（必做） 2、实验、实验4实现二叉树深度的统计算法。（必实现二叉树深度的统计算法。（必做）做） 3、实现二叉树深度统计的非递归算法。（选、实现二叉树深度统计的非递归算法。（选做）做）数据结构实验教学课件数据结构实验教学课件void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafint De

18、pth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; Int Depth(BTree *T)/注意讲解时候的level队列，里面的值与qu队列一一对应 int m,max,rear,front,levelMaxSize; BTree *quMaxSize

19、,*p; /循环队列 max=0;rear=0;front=0; rear+;qurear=T;levelrear=1;/根结点入队 while(front!=rear) front=(front+1)%maxsize;/出队列 p=qufront;m=levelfront; if(mmax) max=m; if(p-lchild!=NULL) rear=(rear+1)%Maxsize； /左孩子入队 qurear=p-lchild; levelrear=m+1;/子女层次加1 if(p-rchild!=NULL) rear=(rear+1)%Maxsize； /右孩子入队 qurear=p

20、-rchild; levelrear=m+1;/子女层次加1 return max; 实验要求：实验要求：认真看书，理解本节系列算法的思想认真看书，理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果，并结合程保存和打印出程序的运行结果，并结合程序进行分析。序进行分析。编写主程序并运行，打印出文件清单和运编写主程序并运行，打印出文件清单和运行结果。行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件实验四实验四 图的基本实现与应用图的基本实现与应用 实验目的实验目的: 1、理解图这种数据

21、结构。、理解图这种数据结构。 2、掌握邻接矩阵、邻接表这种存储结构的、掌握邻接矩阵、邻接表这种存储结构的实现方法。实现方法。 3、完成图的遍历的算法。、完成图的遍历的算法。数据结构实验教学课件数据结构实验教学课件 实验内容实验内容： 1、实现创建图的邻接矩阵结构的算法。图的邻接矩阵结构的算法。 2、实现邻接矩阵与邻接表的转换算法。、实现邻接矩阵与邻接表的转换算法。 3、实现创建图的邻接表的算法。、实现创建图的邻接表的算法。数据结构实验教学课件数据结构实验教学课件 Status CreateUDN(Mgraph *G) /建立无向网建立无向网 scanf(G- vexnum,G-arcnum,&

22、amp;info);/info为为0,表示各弧无表示各弧无信息信息 for (i=0 ; ivexnum; +i) scanf(G-vexsi); /构造顶点向构造顶点向量量 for (i=0 ; ivexnum; +i) /初始化邻接矩阵初始化邻接矩阵 for(j=0 ; jvexnum; +j) G-arcsij=INFNITY,NULL; for (k=0;karcnum;k+) scanf(&v1,&v2,&w); /输入一条边依附的及权值输入一条边依附的及权值 i=LocateVex(G,v1) ; j= LocateVex(G,v2) ; /确定确定v1、v

23、2在图在图中的位置中的位置 G-arcsij.adj=w; /弧的弧的的权值的权值 if (info) InPut(*G-); /若弧有相关信息若弧有相关信息 G-arcsji= G-arcsij; /置置的对称弧的对称弧 /END 实验内容实验内容： 1、实现图遍历的算法。实验二。（必做）、实现图遍历的算法。实验二。（必做）写到预习作业本。写到预习作业本。 2、求、求2点间边数最少的路径（选做）点间边数最少的路径（选做） 3、实现图的拓扑排序的算法。（选做）、实现图的拓扑排序的算法。（选做）数据结构实验教学课件数据结构实验教学课件 实验要求：实验要求：认真看书，理解本节

24、系列算法的思想认真看书，理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果，并结合程保存和打印出程序的运行结果，并结合程序进行分析。序进行分析。编写主程序并运行，打印出文件清单和运编写主程序并运行，打印出文件清单和运行结果。行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件实验四实验四 查找与排序查找与排序 实验目的实验目的: 1、理解动态查找表与静态查找表。、理解动态查找表与静态查找表。 2、掌握各种查找的算法。、掌握各种查找的算法。数据结构实验教学课件数据结构实验教学课件 实验内

25、容实验内容： 1、 顺序查找的设计与实现（必做）顺序查找的设计与实现（必做） 2、折半查找的设计与实现（必做）、折半查找的设计与实现（必做） 3、直接插入排序算法的实现（必做）、直接插入排序算法的实现（必做） 4、快速排序算法的实现（选作）、快速排序算法的实现（选作） 5、生死者游戏（选作）、生死者游戏（选作） 6、迷宫的求解（选作）、迷宫的求解（选作）数据结构实验教学课件数据结构实验教学课件21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80

26、 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq05 13 19 21 37 56 64 75

27、 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid = (low+high)/2int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if （EQ (key , ST.elemmid.key) ) ret

28、urn mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin 实验要求：实验要求：认真看书，理解本节系列算法的思想认真看书，理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果，并结合程保存和打印出程序的运行结果，并结合程序进行分析。序进行分析。编写主程序并运行，

29、打印出文件清单和运编写主程序并运行，打印出文件清单和运行结果。行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件实验内容：实验内容：实验实验1主要实现创建一个顺序表，建主要实现创建一个顺序表，建立一个顺序表，输出一个顺序表立一个顺序表，输出一个顺序表实验实验2主要实现顺序表的插入操作。主要实现顺序表的插入操作。实验实验3主要实现顺序表的删除操作主要实现顺序表的删除操作自主编程实现顺序表的查找操作。自主编程实现顺序表的查找操作。数据结构实验教学课件数据结构实验教学课件实验内容：实验内容：1实现创建一个单链表表，建立一个实现创建一个单链表表，建立一个单链表，输出一个单链表单链表，输出一个单链表2有序单链表的合并有序单链表的合并.3删除单链表的重复值（选作）。删除单链表的重复值（选作）。4主要实现单循环链表的逆置（选主要实现单循环链表的逆置（选作）。作）。数据结构实验教学课件数据结构实验教学课件 实验内容：（一）实验内容：（一） 1、利用顺序栈各种基本运算的算法（实验、利用顺序栈各种基本运算的算法（实验1） 2、实现链栈各种基本运算的算法（实验、实现链栈各种