《数据结构实验教案76页全.ppt》由会员分享,可在线阅读,更多相关《数据结构实验教案76页全.ppt(76页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构实验教案数据结构实验教案指导教师:李辉指导教师:李辉数据结构实验教学课件数据结构实验教学课件2020/12/191实实 验验 简简 介介本课程是结合理论课程本课程是结合理论课程数据结构数据结构安排的实践课程,目的是通过本课程的实践与操作,加安排的实践课程,目的是通过本课程的实践与操作,加深理论课程中数据结构与算法的理解,理论与实践密切结合,相辅相成。深理论课程中数据结构与算法的理解,理论与实践密切结合,相辅相成。实验着眼于原理与应用的结合,使学生学会如何把书上学到的知识用于解决实际问题,培养实验着眼于原理与应用的结合,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的
2、动手能力;另一方面,能使书上的知识变软件工作所需要的动手能力;另一方面,能使书上的知识变“活活”,起到深化理解和灵活掌,起到深化理解和灵活掌握教学内容的目的。握教学内容的目的。数据结构实验教学课件数据结构实验教学课件2020/12/192实实 验验 环环 境境硬件环境:微型计算机;硬件环境:微型计算机;软件环境:软件环境:windows操作系统;操作系统;VisualC+6.0或或Visual Studio数据结构实验教学课件数据结构实验教学课件2020/12/193实实 验验 教教 材材数据结构实验与实训教程数据结构实验与实训教程刘勇刘勇 等等 国防工业出版社国防工业出版社数据结构实验教学课
3、件数据结构实验教学课件2020/12/194实验一、线性结构基本算法的实现实验一、线性结构基本算法的实现实验目的:实验目的:1.掌掌握握线线性性表表的的顺顺序序存存储储结结构构的的定定义义及及C语语言言实实现现,掌掌握握顺顺序序表表中中的的各各种种基基本本操操作作(顺顺序表的建立、插入、删除等);序表的建立、插入、删除等);2.掌掌握握线线性性表表的的链链式式存存储储结结构构-单单链链表表的的定定义义及及C语语言言实实现现,掌掌握握单单链链表表中中的的各各种种基基本本操作(单链表的建立、合并、删除重复值等)。操作(单链表的建立、合并、删除重复值等)。数据结构实验教学课件数据结构实验教学课件20
4、20/12/195实验内容(一):实验内容(一):实验实验1主要实现创建一个顺序表,建立一个顺序表,输出一个顺序表。主要实现创建一个顺序表,建立一个顺序表,输出一个顺序表。实验实验2主要实现顺序表的插入操作。主要实现顺序表的插入操作。实验实验3主要实现顺序表的删除操作主要实现顺序表的删除操作自主编程实现顺序表的查找操作。自主编程实现顺序表的查找操作。数据结构实验教学课件数据结构实验教学课件2020/12/196实验要求:实验要求:认真看书,理解本节系列算法的思想认真看书,理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程
5、序的运行结果,并结合程序进行分析。保存和打印出程序的运行结果,并结合程序进行分析。按照你对线性表的操作需要,编写主程序并运行,打印出文件清单和运行结果按照你对线性表的操作需要,编写主程序并运行,打印出文件清单和运行结果写出实验报告写出实验报告数据结构实验教学课件数据结构实验教学课件2020/12/197顺序表的创建和输出:顺序表的创建和输出:数据结构实验教学课件数据结构实验教学课件主程序:#include#include SqList.h2020/12/198数据结构实验教学课件数据结构实验教学课件顺序表的插入:顺序表的插入:2020/12/199顺序表的删除操作:顺序表的删除操作:数据结构实
6、验教学课件数据结构实验教学课件2020/12/1910实验内容(二):实验内容(二):1实现创建一个单链表,建立一个单链表,输出一个单链表实现创建一个单链表,建立一个单链表,输出一个单链表2有序单链表的合并有序单链表的合并.3删除单链表的重复值(选作)。删除单链表的重复值(选作)。4主要实现单循环链表的逆置(选作)。主要实现单循环链表的逆置(选作)。数据结构实验教学课件数据结构实验教学课件2020/12/1911单链表的创建和输出:单链表的创建和输出:数据结构实验教学课件数据结构实验教学课件2020/12/1912单链表的合并:单链表的合并:数据结构实验教学课件数据结构实验教学课件2020/1
7、2/1913单链表的合并:单链表的合并:数据结构实验教学课件数据结构实验教学课件2020/12/1914数据结构实验教学课件数据结构实验教学课件删除单链表的重复值:删除单链表的重复值:2020/12/1915数据结构实验教学课件数据结构实验教学课件2020/12/1916数据结构实验教学课件数据结构实验教学课件单循环链表的逆置:单循环链表的逆置:2020/12/1917数据结构实验教学课件数据结构实验教学课件2020/12/1918实验二实验二 栈与队列的应用栈与队列的应用实验目的实验目的:1、熟悉栈的特点(先进后出)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈、熟悉栈的特点(先进后出
8、)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。的顺序存储结构和链式存储结构上的实现。2、熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的基本操、熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。作在队列的顺序存储结构和链式存储结构上的实现。数据结构实验教学课件数据结构实验教学课件2020/12/1919实验内容:(一)实验内容:(一)1、利用顺序栈各种基本运算的算法(实验、利用顺序栈各种基本运算的算法(实验1)2、实现链栈各种基本运算的算法(实验、实现链栈
9、各种基本运算的算法(实验2选作)选作)3、实现数值转换算法。(写在预习本上)。、实现数值转换算法。(写在预习本上)。数据结构实验教学课件数据结构实验教学课件2020/12/1920数据结构实验教学课件数据结构实验教学课件栈的基本操作:栈的基本操作:2020/12/1921数据结构实验教学课件数据结构实验教学课件栈的基本操作:栈的基本操作:2020/12/1922数据结构实验教学课件数据结构实验教学课件链栈的基本操作:链栈的基本操作:2020/12/1923数据结构实验教学课件数据结构实验教学课件链栈的基本操作:链栈的基本操作:2020/12/1924实验内容:(二)实验内容:(二)1、利用顺序
10、队列实现各种基本运算的算法(实验、利用顺序队列实现各种基本运算的算法(实验3)。)。2、利用链队列实现各种基本运算的算法(实验、利用链队列实现各种基本运算的算法(实验4)3、完成上次没完成的内容。、完成上次没完成的内容。数据结构实验教学课件数据结构实验教学课件2020/12/1925数据结构实验教学课件数据结构实验教学课件顺序队列的基本操作:顺序队列的基本操作:2020/12/1926数据结构实验教学课件数据结构实验教学课件顺序队列的基本操作:顺序队列的基本操作:2020/12/1927数据结构实验教学课件数据结构实验教学课件链队列的基本操作:链队列的基本操作:2020/12/1928数据结构
11、实验教学课件数据结构实验教学课件链队列的基本操作:链队列的基本操作:2020/12/1929实验要求:实验要求:认真看书,理解本节系列算法的思想认真看书,理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果,并结合程序进行分析。保存和打印出程序的运行结果,并结合程序进行分析。编写主程序并运行,打印出文件清单和运行结果。编写主程序并运行,打印出文件清单和运行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件2020/12/1930实验三实验三 串串实验目的实验目的:(1)掌握字符串的基本操
12、作。掌握字符串的基本操作。(2)熟悉串函数的实现方法。熟悉串函数的实现方法。数据结构实验教学课件数据结构实验教学课件2020/12/1931实验三实验三 串串实验内容实验内容:(1)完成实验指导书实验一内容。完成实验指导书实验一内容。(2)独立编程实现串的联接操作(写在预习本上)。独立编程实现串的联接操作(写在预习本上)。数据结构实验教学课件数据结构实验教学课件2020/12/1932实验四实验四 数组数组实验内容实验内容:(1)完成实验指导书完成实验指导书P71基础实验中建立三元组顺序表,输出三元组顺序表和矩阵的转置的内基础实验中建立三元组顺序表,输出三元组顺序表和矩阵的转置的内容。容。(2
13、)自主编程实现快速转置的算法。自主编程实现快速转置的算法。数据结构实验教学课件数据结构实验教学课件2020/12/1933#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型2020/12/1934121415-522-7313634282020/12/1935有两种解决方法:有两种解
14、决方法:1 1、按照矩阵、按照矩阵M M的列序来转置。的列序来转置。2020/12/19361 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 282020/12/1937Status 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;+c
15、ol)cpotcol=cpotcol-1+numcol-1;for(p=1;pdata=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTree2020/12/1943三、算法的递归描述三、算法的递归描述void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点 Preorder(T-lchild,visit);/遍历左子树 Preorder(T-rchild,v
16、isit);/遍历右子树 2020/12/1944void Inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)Inorder(T-lchild,visit);/遍历左子树 visit(T-data);/访问结点 Inorder(T-rchild,visit);/遍历右子树 2020/12/1945void Postorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)Postorder(T-lchild,visit);/遍历左子树 Postorder(T-rchild,visit
17、);/遍历右子树 visit(T-data);/访问结点 2020/12/1946void 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;2020/12/1947实验内容:实验内容:1、实验、实验3用递归算法实现统计二叉树叶子结点个数(必做)用递归算法实现统计二叉树叶子结点个数(必
18、做)2、实验、实验4实现二叉树深度的统计算法。(必做)实现二叉树深度的统计算法。(必做)3、实现二叉树深度统计的非递归算法。(选做)、实现二叉树深度统计的非递归算法。(选做)数据结构实验教学课件数据结构实验教学课件2020/12/1948void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf2020/12/1949int Depth(BiTree T)/返回二叉
19、树的深度 if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;2020/12/1950Int Depth(BTree*T)/注意讲解时候的level队列,里面的值与qu队列一一对应 int m,max,rear,front,levelMaxSize;BTree*quMaxSize,*p;/循环队列 max=0;rear=0;front=0;rear+;qur
20、ear=T;levelrear=1;/根结点入队 while(front!=rear)front=(front+1)%maxsize;/出队列 p=qufront;m=levelfront;if(mmax)max=m;2020/12/1951if(p-lchild!=NULL)rear=(rear+1)%Maxsize;/左孩子入队 qurear=p-lchild;levelrear=m+1;/子女层次加1 if(p-rchild!=NULL)rear=(rear+1)%Maxsize;/右孩子入队 qurear=p-rchild;levelrear=m+1;/子女层次加1 return ma
21、x;2020/12/1952实验要求:实验要求:认真看书,理解本节系列算法的思想认真看书,理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果,并结合程序进行分析。保存和打印出程序的运行结果,并结合程序进行分析。编写主程序并运行,打印出文件清单和运行结果。编写主程序并运行,打印出文件清单和运行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件2020/12/1953实验四实验四 图的基本实现与应用图的基本实现与应用 实验目的实验目的:1、理解图这种数据结构。、理解图这种数据结构。2、掌握
22、邻接矩阵、邻接表这种存储结构的实现方法。、掌握邻接矩阵、邻接表这种存储结构的实现方法。3、完成图的遍历的算法。、完成图的遍历的算法。数据结构实验教学课件数据结构实验教学课件2020/12/1954实验内容:实验内容:1、实现创建图的邻接矩阵结构的算法。图的邻接矩阵结构的算法。2、实现邻接矩阵与邻接表的转换算法。、实现邻接矩阵与邻接表的转换算法。3、实现创建图的邻接表的算法。、实现创建图的邻接表的算法。数据结构实验教学课件数据结构实验教学课件2020/12/1955Status CreateUDN(Mgraph*G)/建立无向网建立无向网 scanf(G-vexnum,G-arcnum,&inf
23、o);/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、v2在图中的位置在图中的位置 G-arcsij.adj=w;/弧的弧的的权值的权值 if
24、(info)InPut(*G-arcsij.info);/若弧有相关信息若弧有相关信息G-arcsji=G-arcsij;/置置的对称弧的对称弧/END2020/12/1956 无向图的邻接表创建算法无向图的邻接表创建算法无向图的邻接表创建算法无向图的邻接表创建算法 void createadjgraph(ALGraph*g)void createadjgraph(ALGraph*g)scanf(%d%d,&g-Vexnum,&g-Arcnum);/*scanf(%d%d,&g-Vexnum,&g-Arcnum);/*输入顶点数与边数输入顶点数与边数输入顶点数与边数输入顶点数与边数*/*/fo
25、r(i=0;iVexnum;i+)for(i=0;iVexnum;i+)scanf(“%c”,&g-Verticesi.data);/*scanf(“%c”,&g-Verticesi.data);/*读入顶点信息读入顶点信息读入顶点信息读入顶点信息*/*/g-verticesi.firstarc=NULL;g-verticesi.firstarc=NULL;/*/*初始化一维数组初始化一维数组初始化一维数组初始化一维数组 2020/12/1957/*/*建立各单链表建立各单链表建立各单链表建立各单链表*/*/for(k=0;kArcnum;k+)/*for(k=0;kArcnum;k+)/*循
26、环循环循环循环e e次建立边表次建立边表次建立边表次建立边表*/*/scanf(%d%d,&i,&j);/*scanf(%d%d,&i,&j);/*输入无序对(输入无序对(输入无序对(输入无序对(i,ji,j)*/*/s=(Arcnode*)malloc(sizeof(Arcnode);s=(Arcnode*)malloc(sizeof(Arcnode);s-adjvex=j;/*s-adjvex=j;/*邻接点序号为邻接点序号为邻接点序号为邻接点序号为j*/j*/s-next=g-Verticesi.firstarc;s-next=g-Verticesi.firstarc;g-Vertice
27、si.firstarc=s;/*g-Verticesi.firstarc=s;/*将新结点将新结点将新结点将新结点*s*s插入顶点插入顶点插入顶点插入顶点vivi的边表头部的边表头部的边表头部的边表头部*s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=i;/*s-adjvex=i;/*邻接点序号为邻接点序号为邻接点序号为邻接点序号为i*/i*/s-next=g-Verticesj.firstarc;s-next=g-Verticesj.firstarc;g-Verticesj.
28、firstarc=s;g-Verticesj.firstarc=s;/*/*将新结点将新结点将新结点将新结点*s*s插入顶点插入顶点插入顶点插入顶点vjvj的边表头部的边表头部的边表头部的边表头部*/*/2020/12/1958实验内容:实验内容:1、实现图遍历的算法。实验二。(必做)写到预习作业本。、实现图遍历的算法。实验二。(必做)写到预习作业本。2、求、求2点间边数最少的路径(选做)点间边数最少的路径(选做)3、实现图的拓扑排序的算法。(选做)、实现图的拓扑排序的算法。(选做)数据结构实验教学课件数据结构实验教学课件2020/12/1959实验要求:实验要求:认真看书,理解本节系列算法的
29、思想认真看书,理解本节系列算法的思想上机前写出各算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果,并结合程序进行分析。保存和打印出程序的运行结果,并结合程序进行分析。编写主程序并运行,打印出文件清单和运行结果。编写主程序并运行,打印出文件清单和运行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件2020/12/1960实验四实验四 查找与排序查找与排序 实验目的实验目的:1、理解动态查找表与静态查找表。、理解动态查找表与静态查找表。2、掌握各种查找的算法。、掌握各种查找的算法。数据结构实验教学课件数据结构实验教学课
30、件2020/12/1961实验内容:实验内容:1、顺序查找的设计与实现(必做)顺序查找的设计与实现(必做)2、折半查找的设计与实现(必做)、折半查找的设计与实现(必做)3、直接插入排序算法的实现(必做)、直接插入排序算法的实现(必做)4、快速排序算法的实现(选作)、快速排序算法的实现(选作)5、生死者游戏(选作)、生死者游戏(选作)6、迷宫的求解(选作)、迷宫的求解(选作)数据结构实验教学课件数据结构实验教学课件2020/12/1962ST.elemiST.elemi60ikey=64key=60i642020/12/1963int Search_Seq(SSTable ST,KeyType
31、key)/在顺序表ST中顺序查找其关键字等于 /key的数据元素。若找到,则函数值为 /该元素在表中的位置,否则为0。ST.elem0.key=key;/“哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找 return i;/找不到时,i为0/Search_Seq2020/12/1964ST.elemST.length例如例如:key=64 的查找过程如下:lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/22020/12/1965int Search_Bin(S
32、STable ST,KeyType key)low=1;high=ST.length;/置区间初值 while(low=high)mid=(low+high)/2;if(EQ(key,ST.elemmid.key)return mid;/找到待查元素 else if(LT(key,ST.elemmid.key)high=mid-1;/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return 0;/顺序表中不存在待查元素/Search_Bin2020/12/1966实验要求:实验要求:认真看书,理解本节系列算法的思想认真看书,理解本节系列算法的思想上机前写出各
33、算法语言的源代码。上机前写出各算法语言的源代码。上机运行代码。上机运行代码。保存和打印出程序的运行结果,并结合程序进行分析。保存和打印出程序的运行结果,并结合程序进行分析。编写主程序并运行,打印出文件清单和运行结果。编写主程序并运行,打印出文件清单和运行结果。写出实验报告。写出实验报告。数据结构实验教学课件数据结构实验教学课件2020/12/1967实验内容:实验内容:实验实验1主要实现创建一个顺序表,建立一个顺序表,输出一个顺序表主要实现创建一个顺序表,建立一个顺序表,输出一个顺序表实验实验2主要实现顺序表的插入操作。主要实现顺序表的插入操作。实验实验3主要实现顺序表的删除操作主要实现顺序表
34、的删除操作自主编程实现顺序表的查找操作。自主编程实现顺序表的查找操作。数据结构实验教学课件数据结构实验教学课件2020/12/1968实验内容:实验内容:1实现创建一个单链表表,建立一个单链表,输出一个单链表实现创建一个单链表表,建立一个单链表,输出一个单链表2有序单链表的合并有序单链表的合并.3删除单链表的重复值(选作)。删除单链表的重复值(选作)。4主要实现单循环链表的逆置(选作)。主要实现单循环链表的逆置(选作)。数据结构实验教学课件数据结构实验教学课件2020/12/1969实验内容:(一)实验内容:(一)1、利用顺序栈各种基本运算的算法(实验、利用顺序栈各种基本运算的算法(实验1)2
35、、实现链栈各种基本运算的算法(实验、实现链栈各种基本运算的算法(实验2)3、实现数值转换算法。(写在预习本上)。、实现数值转换算法。(写在预习本上)。数据结构实验教学课件数据结构实验教学课件2020/12/1970实验内容:(二)实验内容:(二)1、利用顺序队列实现各种基本运算的算法(实验、利用顺序队列实现各种基本运算的算法(实验3),做修改变成循环队列。),做修改变成循环队列。2、利用链队列实现各种基本运算的算法(实验、利用链队列实现各种基本运算的算法(实验4)3、完成上次没完成的内容。、完成上次没完成的内容。数据结构实验教学课件数据结构实验教学课件2020/12/1971实验内容:实验内容
36、:1、实验、实验1用递归算法实现创建一棵二叉树(必做)用递归算法实现创建一棵二叉树(必做)2、实验、实验2实现二叉树各种遍历算法。(选做)实现二叉树各种遍历算法。(选做)3、实现中序遍历的非递归算法。(写在预习本上)、实现中序遍历的非递归算法。(写在预习本上)数据结构实验教学课件数据结构实验教学课件2020/12/1972实验内容:实验内容:1、实验、实验3用递归算法实现统计二叉树叶子结点个数(必做)用递归算法实现统计二叉树叶子结点个数(必做)2、实验、实验4实现二叉树深度的统计算法。(必做)实现二叉树深度的统计算法。(必做)3、实现二叉树深度统计的非递归算法。(选做)、实现二叉树深度统计的非
37、递归算法。(选做)数据结构实验教学课件数据结构实验教学课件2020/12/1973实验内容:实验内容:1、实现创建图的邻接矩阵结构的算法。图的邻接矩阵结构的算法。2、实现邻接矩阵与邻接表的转换算法。、实现邻接矩阵与邻接表的转换算法。3、实现创建图的邻接表的算法。、实现创建图的邻接表的算法。数据结构实验教学课件数据结构实验教学课件2020/12/1974实验内容:实验内容:1、实现图遍历的算法。实验二。(必做)写到预习作业本。、实现图遍历的算法。实验二。(必做)写到预习作业本。2、求、求2点间边数最少的路径(选做)点间边数最少的路径(选做)3、实现图的拓扑排序的算法。(选做)、实现图的拓扑排序的算法。(选做)数据结构实验教学课件数据结构实验教学课件2020/12/1975实验内容:实验内容:1、顺序查找的设计与实现(必做)顺序查找的设计与实现(必做)2、折半查找的设计与实现(必做)、折半查找的设计与实现(必做)3、直接插入排序算法的实现(必做)、直接插入排序算法的实现(必做)数据结构实验教学课件数据结构实验教学课件2020/12/1976
限制150内