数据结构实验教案全省公共课一等奖全国赛课获奖课件.pptx

数据结构试验教案数据结构试验教案指导教师：李辉指导教师：李辉数据结构试验教学课件数据结构试验教学课件第1页实实 验验 简简 介介本课程是结合理论课程数据结构安排实践课程，目是经过本课程实践与操作，加深理论课程中数据结构与算法理解，理论与实践亲密结合，相辅相成。实验着眼于原理与应用结合，使学生学会如何把书上学到知识用于解决实际问题，培养软件工作所需要动手能力；其次，能使书上知识变“活”，起到深化理解和灵活掌握教学内容目。数据结构试验教学课件数据结构试验教学课件第2页实实 验验 环环 境境硬件环境：微型计算机；硬件环境：微型计算机；软件环境：软件环境：windows操作系统；操作系统；VisualC+6.0或或Visual Studio数据结构试验教学课件数据结构试验教学课件第3页实实 验验 教教 材材数据结构试验与实训教程数据结构试验与实训教程刘勇刘勇 等等 国防工业出版社国防工业出版社数据结构试验教学课件数据结构试验教学课件第4页试验一、线性结构基本算法实现试验一、线性结构基本算法实现试验目标试验目标：1.掌掌握握线线性性表表次次序序存存放放结结构构定定义义及及C语语言言实实现现，掌掌握握次序表中各种基本操作（次序表建立、插入、删除等）；次序表中各种基本操作（次序表建立、插入、删除等）；2.掌掌握握线线性性表表链链式式存存放放结结构构-单单链链表表定定义义及及C语语言言实实现现，掌掌握握单单链链表表中中各各种种基基本本操操作作（单单链链表表建建立立、合合并并、删删除重复值等）。除重复值等）。数据结构试验教学课件数据结构试验教学课件第5页试验内容（一）：试验内容（一）：试试验验1主主要要实实现现创创建建一一个个次次序序表表，建建立立一一个次序表，输出一个次序表。个次序表，输出一个次序表。试验试验2主要实现次序表插入操作。主要实现次序表插入操作。试验试验3主要实现次序表删除操作主要实现次序表删除操作自主编程实现次序表查找操作。自主编程实现次序表查找操作。数据结构试验教学课件数据结构试验教学课件第6页试验要求：试验要求：认真看书，了解本节系列算法思想认真看书，了解本节系列算法思想上机前写出各算法语言源代码。上机前写出各算法语言源代码。上机运行代码。上机运行代码。保留和打印出程序运行结果，并结合程序进行保留和打印出程序运行结果，并结合程序进行分析。分析。按照你对线性表操作需要，编写主程序并运行，按照你对线性表操作需要，编写主程序并运行，打印出文件清单和运行结果打印出文件清单和运行结果写出试验汇报写出试验汇报数据结构试验教学课件数据结构试验教学课件第7页次序表创建和输出：次序表创建和输出：数据结构试验教学课件数据结构试验教学课件主程序：#include#include SqList.h第8页数据结构试验教学课件数据结构试验教学课件次序表插入：次序表插入：第9页次序表删除操作：次序表删除操作：数据结构试验教学课件数据结构试验教学课件第10页试验内容（二）：试验内容（二）：1实现创建一个单链表，建立一个单实现创建一个单链表，建立一个单链表，输出一个单链表链表，输出一个单链表2有序单链表合并有序单链表合并.3删除单链表重复值（选作）。删除单链表重复值（选作）。4主要实现单循环链表逆置（选作）。主要实现单循环链表逆置（选作）。数据结构试验教学课件数据结构试验教学课件第11页单链表创建和输出：单链表创建和输出：数据结构试验教学课件数据结构试验教学课件第12页单链表合并：单链表合并：数据结构试验教学课件数据结构试验教学课件第13页单链表合并：单链表合并：数据结构试验教学课件数据结构试验教学课件第14页数据结构试验教学课件数据结构试验教学课件删除单链表重复值：删除单链表重复值：第15页数据结构试验教学课件数据结构试验教学课件第16页数据结构试验教学课件数据结构试验教学课件单循环链表逆置：单循环链表逆置：第17页数据结构试验教学课件数据结构试验教学课件第18页试验二试验二 栈与队列应用栈与队列应用试验目标试验目标:1、熟悉栈特点（先进后出）及栈基本操作，如入、熟悉栈特点（先进后出）及栈基本操作，如入栈、出栈等，掌握栈基本操作在栈次序存放结构栈、出栈等，掌握栈基本操作在栈次序存放结构和链式存放结构上实现。和链式存放结构上实现。2、熟悉队列特点（先进先出）及队列基本操作，、熟悉队列特点（先进先出）及队列基本操作，如入队、出队等，掌握队列基本操作在队列次序如入队、出队等，掌握队列基本操作在队列次序存放结构和链式存放结构上实现。存放结构和链式存放结构上实现。数据结构试验教学课件数据结构试验教学课件第19页试验内容：（一）试验内容：（一）1、利用次序栈各种基本运算算法（试验、利用次序栈各种基本运算算法（试验1）2、实现链栈各种基本运算算法（试验、实现链栈各种基本运算算法（试验2选作）选作）3、实现数值转换算法。（写在预习本上）。、实现数值转换算法。（写在预习本上）。数据结构试验教学课件数据结构试验教学课件第20页数据结构试验教学课件数据结构试验教学课件栈基本操作：栈基本操作：第21页数据结构试验教学课件数据结构试验教学课件栈基本操作：栈基本操作：第22页数据结构试验教学课件数据结构试验教学课件链栈基本操作：链栈基本操作：第23页数据结构试验教学课件数据结构试验教学课件链栈基本操作：链栈基本操作：第24页试验内容：（二）试验内容：（二）1、利用次序队列实现各种基本运算算法（试、利用次序队列实现各种基本运算算法（试验验3）。）。2、利用链队列实现各种基本运算算法（试验、利用链队列实现各种基本运算算法（试验4）3、完成上次没完成内容。、完成上次没完成内容。数据结构试验教学课件数据结构试验教学课件第25页数据结构试验教学课件数据结构试验教学课件次序队列基本操作：次序队列基本操作：第26页数据结构试验教学课件数据结构试验教学课件次序队列基本操作：次序队列基本操作：第27页数据结构试验教学课件数据结构试验教学课件链队列基本操作：链队列基本操作：第28页数据结构试验教学课件数据结构试验教学课件链队列基本操作：链队列基本操作：第29页试验要求：试验要求：认真看书，了解本节系列算法思想认真看书，了解本节系列算法思想上机前写出各算法语言源代码。上机前写出各算法语言源代码。上机运行代码。上机运行代码。保留和打印出程序运行结果，并结合程序进行保留和打印出程序运行结果，并结合程序进行分析。分析。编写主程序并运行，打印出文件清单和运行结编写主程序并运行，打印出文件清单和运行结果。果。写出试验汇报。写出试验汇报。数据结构试验教学课件数据结构试验教学课件第30页试验三试验三 串串试验目标试验目标:(1)掌握字符串基本操作。掌握字符串基本操作。(2)熟悉串函数实现方法。熟悉串函数实现方法。数据结构试验教学课件数据结构试验教学课件第31页试验三试验三 串串试验内容试验内容:(1)完成试验指导书试验一内容。完成试验指导书试验一内容。(2)独立编程实现串联接操作（写在预习本独立编程实现串联接操作（写在预习本上）。上）。数据结构试验教学课件数据结构试验教学课件第32页试验四试验四 数组数组试验内容试验内容:(1)完成试验指导书完成试验指导书P71基础试验中建立三基础试验中建立三元组次序表，输出三元组次序表和矩阵转元组次序表，输出三元组次序表和矩阵转置内容。置内容。(2)自主编程实现快速转置算法。自主编程实现快速转置算法。数据结构试验教学课件数据结构试验教学课件第33页#define MAXSIZE 12500 typedef struct int i,j;/该非零元行下标和列下标 ElemType e;/该非零元值 Triple;/三元组类型三元组类型一、三元组次序表一、三元组次序表typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型第34页121415-522-731363428第35页有两种处理方法：有两种处理方法：1 1、按照矩阵、按照矩阵M M列序来转置。列序来转置。第36页1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28第37页Status 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+numcol-1;for(p=1;pdata=ch;/生成根结点 CreateBiTree(T-lchild);/结构左子树 CreateBiTree(T-rchild);/结构右子树 return OK;/CreateBiTree第43页三、算法递归描述三、算法递归描述void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点 Preorder(T-lchild,visit);/遍历左子树 Preorder(T-rchild,visit);/遍历右子树 第44页void Inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)Inorder(T-lchild,visit);/遍历左子树 visit(T-data);/访问结点 Inorder(T-rchild,visit);/遍历右子树 第45页void Postorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)Postorder(T-lchild,visit);/遍历左子树 Postorder(T-rchild,visit);/遍历右子树 visit(T-data);/访问结点 第46页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;第47页试验内容试验内容：1、试验、试验3用递归算法实现统计二叉树叶子结用递归算法实现统计二叉树叶子结点个数（必做）点个数（必做）2、试验、试验4实现二叉树深度统计算法。（必做）实现二叉树深度统计算法。（必做）3、实现二叉树深度统计非递归算法。（选做）、实现二叉树深度统计非递归算法。（选做）数据结构试验教学课件数据结构试验教学课件第48页void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf第49页int Depth(BiTree T)/返回二叉树深度 if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;第50页Int Depth(BTree*T)/注意讲解时候level队列，里面值与qu队列一一对应 int m,max,rear,front,levelMaxSize;BTree*quMaxSize,*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;第51页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-rchild;levelrear=m+1;/儿女层次加1 return max;第52页试验要求：试验要求：认真看书，了解本节系列算法思想认真看书，了解本节系列算法思想上机前写出各算法语言源代码。上机前写出各算法语言源代码。上机运行代码。上机运行代码。保留和打印出程序运行结果，并结合程序保留和打印出程序运行结果，并结合程序进行分析。进行分析。编写主程序并运行，打印出文件清单和运编写主程序并运行，打印出文件清单和运行结果。行结果。写出试验汇报。写出试验汇报。数据结构试验教学课件数据结构试验教学课件第53页试验四试验四 图基本实现与应用图基本实现与应用 试验目标试验目标:1、了解图这种数据结构。、了解图这种数据结构。2、掌握邻接矩阵、邻接表这种存放结构实、掌握邻接矩阵、邻接表这种存放结构实现方法。现方法。3、完成图遍历算法。、完成图遍历算法。数据结构试验教学课件数据结构试验教学课件第54页试验内容试验内容：1、实现创建图邻接矩阵结构算法。图邻接矩阵结构算法。2、实现邻接矩阵与邻接表转换算法。、实现邻接矩阵与邻接表转换算法。3、实现创建图邻接表算法。、实现创建图邻接表算法。数据结构试验教学课件数据结构试验教学课件第55页Status CreateUDN(Mgraph*G)/建立无向网建立无向网 scanf(G-vexnum,G-arcnum,&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、v2在图在图中位置中位置 G-arcsij.adj=w;/弧弧权值权值 if(info)InPut(*G-arcsij.info);/若弧有相关信息若弧有相关信息G-arcsji=G-arcsij;/置置对称弧对称弧/END第56页 无向图邻接表创建算法无向图邻接表创建算法 void createadjgraph(ALGraph*g)scanf(%d%d,&g-Vexnum,&g-Arcnum);/*/*输入顶点数与边数输入顶点数与边数输入顶点数与边数输入顶点数与边数*/*/for(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;/*/*初始化一维数组初始化一维数组初始化一维数组初始化一维数组 第57页/*/*建立各单链表建立各单链表建立各单链表建立各单链表*/*/for(k=0;kArcnum;k+)/*for(k=0;kArcnum;k+)/*循环循环循环循环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-Verticesi.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.firstarc=s;g-Verticesj.firstarc=s;/*/*将新结点将新结点将新结点将新结点*s*s插入顶点插入顶点插入顶点插入顶点vjvj边表头部边表头部边表头部边表头部*/*/第58页试验内容试验内容：1、实现图遍历算法。试验二。（必做）写、实现图遍历算法。试验二。（必做）写到预习作业本。到预习作业本。2、求、求2点间边数最少路径（选做）点间边数最少路径（选做）3、实现图拓扑排序算法。（选做）、实现图拓扑排序算法。（选做）数据结构试验教学课件数据结构试验教学课件第59页试验要求：试验要求：认真看书，了解本节系列算法思想认真看书，了解本节系列算法思想上机前写出各算法语言源代码。上机前写出各算法语言源代码。上机运行代码。上机运行代码。保留和打印出程序运行结果，并结合程序保留和打印出程序运行结果，并结合程序进行分析。进行分析。编写主程序并运行，打印出文件清单和运编写主程序并运行，打印出文件清单和运行结果。行结果。写出试验汇报。写出试验汇报。数据结构试验教学课件数据结构试验教学课件第60页试验四试验四 查找与排序查找与排序 试验目标试验目标:1、了解动态查找表与静态查找表。、了解动态查找表与静态查找表。2、掌握各种查找算法。、掌握各种查找算法。数据结构试验教学课件数据结构试验教学课件第61页试验内容试验内容：1、次序查找设计与实现（必做）次序查找设计与实现（必做）2、折半查找设计与实现（必做）、折半查找设计与实现（必做）3、直接插入排序算法实现（必做）、直接插入排序算法实现（必做）4、快速排序算法实现（选作）、快速排序算法实现（选作）5、生死者游戏（选作）、生死者游戏（选作）6、迷宫求解（选作）、迷宫求解（选作）数据结构试验教学课件数据结构试验教学课件第62页ST.elemiST.elemi60ikey=64key=60i64第63页int 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_Seq第64页ST.elemST.length比如比如:key=64 查找过程以下：lowhighmidlow mid high midlow 指示查找区间下界high 指示查找区间上界mid=(low+high)/2第65页int Search_Bin(SSTable 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_Bin第66页试验要求：试验要求：认真看书，了解本节系列算法思想认真看书，了解本节系列算法思想上机前写出各算法语言源代码。上机前写出各算法语言源代码。上机运行代码。上机运行代码。保留和打印出程序运行结果，并结合程序保留和打印出程序运行结果，并结合程序进行分析。进行分析。编写主程序并运行，打印出文件清单和运编写主程序并运行，打印出文件清单和运行结果。行结果。写出试验汇报。写出试验汇报。数据结构试验教学课件数据结构试验教学课件第67页试验内容：试验内容：试验试验1主要实现创建一个次序表，建主要实现创建一个次序表，建立一个次序表，输出一个次序表立一个次序表，输出一个次序表试验试验2主要实现次序表插入操作。主要实现次序表插入操作。试验试验3主要实现次序表删除操作主要实现次序表删除操作自主编程实现次序表查找操作。自主编程实现次序表查找操作。数据结构试验教学课件数据结构试验教学课件第68页试验内容：试验内容：1实现创建一个单链表表，建立一个实现创建一个单链表表，建立一个单链表，输出一个单链表单链表，输出一个单链表2有序单链表合并有序单链表合并.3删除单链表重复值（选作）。删除单链表重复值（选作）。4主要实现单循环链表逆置（选作）。主要实现单循环链表逆置（选作）。数据结构试验教学课件数据结构试验教学课件第69页试验内容：（一）试验内容：（一）1、利用次序栈各种基本运算算法（试验、利用次序栈各种基本运算算法（试验1）2、实现链栈各种基本运算算法（试验、实现链栈各种基本运算算法（试验2）3、实现数值转换算法。（写在预习本上）。、实现数值转换算法。（写在预习本上）。数据结构试验教学课件数据结构试验教学课件第70页试验内容：（二）试验内容：（二）1、利用次序队列实现各种基本运算算法（试、利用次序队列实现各种基本运算算法（试验验3），做修改变成循环队列。），做修改变成循环队列。2、利用链队列实现各种基本运算算法（试验、利用链队列实现各种基本运算算法（试验4）3、完成上次没完成内容。、完成上次没完成内容。数据结构试验教学课件数据结构试验教学课件第71页试验内容试验内容：1、试验、试验1用递归算法实现创建一棵二叉树用递归算法实现创建一棵二叉树（必做）（必做）2、试验、试验2实现二叉树各种遍历算法。（选做）实现二叉树各种遍历算法。（选做）3、实现中序遍历非递归算法。（写在预习本、实现中序遍历非递归算法。（写在预习本上）上）数据结构试验教学课件数据结构试验教学课件第72页试验内容试验内容：1、试验、试验3用递归算法实现统计二叉树叶子结用递归算法实现统计二叉树叶子结点个数（必做）点个数（必做）2、试验、试验4实现二叉树深度统计算法。（必做）实现二叉树深度统计算法。（必做）3、实现二叉树深度统计非递归算法。（选做）、实现二叉树深度统计非递归算法。（选做）数据结构试验教学课件数据结构试验教学课件第73页试验内容试验内容：1、实现创建图邻接矩阵结构算法。图邻接矩阵结构算法。2、实现邻接矩阵与邻接表转换算法。、实现邻接矩阵与邻接表转换算法。3、实现创建图邻接表算法。、实现创建图邻接表算法。数据结构试验教学课件数据结构试验教学课件第74页试验内容试验内容：1、实现图遍历算法。试验二。（必做）写、实现图遍历算法。试验二。（必做）写到预习作业本。到预习作业本。2、求、求2点间边数最少路径（选做）点间边数最少路径（选做）3、实现图拓扑排序算法。（选做）、实现图拓扑排序算法。（选做）数据结构试验教学课件数据结构试验教学课件第75页试验内容试验内容：1、次序查找设计与实现（必做）次序查找设计与实现（必做）2、折半查找设计与实现（必做）、折半查找设计与实现（必做）3、直接插入排序算法实现（必做）、直接插入排序算法实现（必做）数据结构试验教学课件数据结构试验教学课件第76页