还剩24页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》实验指导实验一抽象数据类型一实验任务抽象数据类型Triplet的表示和实现二实验目的1理解和掌握抽象数据类型的概念2熟悉数据结构的定义及基本操作3实践系统程序开发的规范步骤三实验原理
1.抽象数据类型的定义抽象数据类型ADT,Abstract DataType由具有一定关系的一组数据和定义在该组数据上的操作组成抽象数据类型为我们提供了一个描述数据结构的架构抽象数据类型的定义一般包括数据定义和操作定义两个部分一个含抽象数据类型的模块通常包含定义、表示和实现3个部分抽象数据类型的形式表示为如下三元组D,S,0其中D是数据对象,S是D上的关系集合,是D上的基本操作集合我们习惯上把抽象数据类型表示成如下格式ADT抽象数据类型名{数据对象〈数据对象的定义,数据关系〈数据关系的定义〉基本操作〈基本操作的定义》}ADT抽象数据类型名例如,抽象数据类型Triplet的三元组定义ADT Triplet{数显对象D={el,e2,e3|el,e2,e3I ElemSet数据关系Rl={E1,e2,E2,e3}基本操作InitTripletTz vl,v2,v3操作结果构造了三元组T,元素el,e2和e3分别被赋以参数vl,v2和v3的值DestroyTripletT操作结果三元组T被销毁GetT,i,e初始条件三元组T已存在,l£i£3o操作结果用e返回T的第i元的值PutT,i,e初始条件三元组T已经存在,l£i£3操作结果改变T的第i元的值为e IsAscendingT队列的链接存储结构,简称链队列链队列所需要的具体数据类型描述如下:typedef struct QNode{ElemType data;〃值域structQNode*next;〃链接指针域}QNode,*QueuePtr;typedef struct{QueuePtr front;〃头指针QueuePtr rear;〃尾指针}LinkQueue;四实验设备、仪器、工具与材料微机、VC五实验内容
(1)实验任务1栈的应用一迷宫求解编制C程序完成迷宫问题程序基本要求用户输入迷宫数据初始化迷宫;利用栈的顺序表示以及入栈、出栈等基本操作,实现迷宫路径的求解;输出求解得到的完整路径(或提示迷宫无通路)
(2)实验任务2队列的表示与实现编写一个C程序实现顺序队列的各种基本操作,并在此基础上设计一个主程序,完成如下功能1)建立循环队列2)入队列3)出队列4)判断队列是否为空5)遍历队列6)取队首元素六实验步骤
(1)实验预习1)预习本实验原理中关于栈与队列的定义、顺序存储表示2)分析掌握教材48-50页中的算法3-1〜3-4,为完成实验任务1做好准备3)分析掌握教材57〜60页中迷宫问题及求解算法3-13,为完成实验任务1做好准备4)分析掌握教材70〜73页中的算法3-15〜3-20,为完成实验任务2做好准备
(2)实验步骤1)问题分析充分地分析和理解此实验任务,弄清要求作什么,限制条件是什么2)系统的结构设计按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计3)详细设计详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节4)编码在详细设计的基础上,对详细设计的结果进一步求精,用C语言表示出来5)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验任务
1、2的程序清单及运行结果八思考题如果一个程序中用到两个栈,为了不发生溢出错误,就必须给每个栈预先一个较大的存储空间若每个栈都预先分配过大的存储空间,势必造成系统空间紧张,如何解决这个问题?实验四树和二叉树一实验任务1)二叉树的表示与实现2)Huffman编码二实验目的1)掌握二叉树的类型定义和结构特点2)掌握二叉树的链式存储表示和实现3)掌握赫夫曼树及其应用三实验原理
1.二叉树的定义所谓二叉树,是指结点的一个有限集合,它或为空集,或为满足下列性质的非空集合有且只有一个根结点,其余结点分成左右两个互不相交的集合TL、TR,且TL、TR均为二叉树二叉树的抽象数据类型定义如下ADT BinaryTree{数据对或DD={ai|aiEEIemSet,i=l,2,…,n,n0}数据关系R若D为空集,则称为空二叉树若D仅含一个数据元素,则R为空集,否则R={H},H满足关系!-[if!supportLists]-(l)!-[endif]-T中存在唯一的一个结点,它没有前驱,称为树的根,用root表示,在集合D中用ai表示;!-[if!supportLists]-
(2)v!-[endif]--若D中元素个数大于1,对于任意的数据元素aj£D且心2,存在唯一的数据元素a任D,有〈A,a j£H;!-[if!supportLists]-
(3)v!--[endif]--若D中元素个数大于1,对于任意的数据元素aiED,仅存在不多于2个数据元素aj,ak£D且j,ki,W ai,aj,ai,ak eH,其中,若jvKvspan,则称两为ai的左孩子节点,ak为ai的右孩子节点基本操作PInitBiTree(T);操作结果构造空二叉树T CreateBiTreeT,tree;初始条件tree给出二叉树T的表示形式操作结果按tree构造二叉树T BiTreeEmptyT;初始条件二叉树T存在操作结果若T为空树,则返回TRUE,否则返回FALSE BiTreeDepthT;初始条件二叉树T存在操作结果返回T的深度RootT;初始条件二叉树T存在操作结果返回T的根ValueTz e;初始条件二叉树T存在,e是需寻找的结点的值操作结果若找到该结点,则函数返回TRUE,否则返回FALSE AssignT,e,value;初始条件二叉树T存在,e是需寻找的结点的值操作结果若找到该结点,结点e赋值为value,则函数返回TRUE,否则返回FALSEo ParentT,e,P;初始条件二叉树T存在,e是需寻找的结点的值操作结果若树中存在值为e的结点,则函数返回TRUE,否则返回FALSE;若存在该结点,用P返回双亲结点的位置,若结点为根结点,则P返回空LeftChildT,e,P;初始条件二叉树T存在,e是需寻找的结点的值操作结果若树中存在值为e的结点,则函数返回TRUE,否则返回FALSE;若存在该结点,用P返回左孩子结点的位置,若结点无左孩子结点,则P返回空RightChildT,e,P;初始条件二叉树T存在,e是需寻找的结点的值操作结果若树中存在值为e的结点,则函数返回TRUE否则返回FALSE;若存在该结点,用P返回右孩子结点的位置,若结点无右孩子结点,则P返回空DelBiTreeNodeT,P;初始条件二叉树T存在,P指向该二叉树中的一个结点操作结果删除P所指向的结点及其子树TraverseBiTreeT,visit;初始条件二叉树T存在,visit是对结点操作的应用函数操作结果按某种次序对T的每个结点调用函数visit一次且至多一次一旦visit失败,则操作失败ClearBiTreeT;初始条件二叉树T存在操作结果将二叉树T清空}ADT BinaryTree
2.二叉树的链式存储表示二叉树的链式存储结构通常采用二叉链表形式,即在每个结点中设置三个域,分别为数据域data、左指针域left和右指针域right其中,数据域用于存储对应的数据元素,left和right用来分别存储左孩子和右孩子结点的存储位置二叉链表的结点类型可定义为typedef struct BiTreeNode{ElemType data;struct BiTreeNode*left;structBiTreeNode*right;}BiTreeNode,*BiTreePtr;
3.二叉树的遍历二叉树的遍历是二叉树中最重要的运算,也是各种操作的基础二叉树的遍历是指按照某个搜索路径寻访树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次在遍历的过程中,可以对结点进行各种操作根据二叉树的递归定义,一棵非空二叉树由根结点、左子树和右子树组成,因此,遍历一棵二叉树可以分解为三个问题访问根结点、遍历左子树、遍历右子树若分别用D、L、R表示上述三个子问题,则可能有DLR、LDR、LRD、DRL、RDL、RLD几种情况若限定先左后右,则只有前3种情况1DLR,此时访问根结点的操作在遍历左、右子树之前,故称之为先序遍历或先根遍历;2LDR,此时访问根结点的操作在遍历左子树之后、右子树之前,故称之为中序遍历或中根遍历;3LRD,此时访问根结点的操作在遍历左、右子树之后,故称之为后序遍历或后根遍历
4.赫夫曼树n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树称作赫夫曼树权值越大的结点离根越近的二叉树才是最优二叉树赫夫曼树构造算法,具体叙述如下1给定n个权值{Wi,W2,…,Wn},对应n个结点,构成具有n棵二叉树的森林F={TI,T2,其中每棵二叉树Ti lWiWn都只有一个权值为四的根结点,其左右子树均为空2在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树,且置新树的根结点的权值为其左、右子树上根结点的权值之和3从F中删除构成新树的那两棵树,同时把新树加入F中4重复2和3,直到F中只含有一棵树为止,此树就是赫夫曼树
5.赫夫曼编码若要设计长短不等的编码,则要求字符集中任一个字符的编码都不是另一个字符的编码的前缀,这种编码称做前缀编码为了使不等长编码为前缀编码,可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树,将每个字符出现的次数作为字符结点的权值赋予该结点上,求出此树的最小带权路径长度,也就是传送电文的最短长度因此,求传送电文的最短长度问题就转化为求由字符集中的所有字符作为叶子结点且由字符的出现频率作为其权值所产生的赫夫曼树的问题四实验设备、仪器、工具与资料微机、VC五实验内容
(1)实验任务1:二叉树建立和遍历编制C程序实现下列功能1)建立二叉树2)按先序、中序、后序方式遍历二叉树程序的基本要求采用二叉链表存储结构表示二叉树;通过二叉树广义表输入所有结点建立二叉树;通过递归算法实现二叉树的遍历并输出结点数据信息
(2)实验任务2赫夫曼编码从键盘上输入n个字符及其权值,编制C程序建立赫夫曼树,并编码输出六实验步骤
(1)实验预习1)预习本实验原理中关于二叉树的定义、二叉链表存储表示2)分析掌握教材93~99页中的算法4-1~4-
4、算法4-7~4-7,为完成实验任务1做好准备3)预习本实验原理中关于赫夫曼树、赫夫曼编码的含义及赫夫曼树的构造方法4)分析掌握教材页中的算法4-14~4-15,为完成实验任务2做好准备
(2)实验步骤1)问题分析充分地分析和理解此实验任务,弄清要求作什么,限制条件是什么2)系统的结构设计按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计3)详细设计详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节4)编码在详细设计的基础上,对详细设计的结果进一步求精,用C语言表示出来5)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验任务
1、2的程序清单及运行结果八思考题1如何以广义表的形式输出二叉树?2如何用非递归算法实现二叉树的中序遍历?3如何利用已建好的赫夫曼编码对输入的正文进行译码实验五图一实验任务1图的邻接表存储与遍历2图的最短路径求解二实验目的1图的基本存储方法2掌握图的两种搜索路径的遍历方法3掌握图的有关应用最短路径三实验原理
1.图图G由两个集合组成顶点结点集合V和连接顶点的边的集合E,集合E由集合V中的不同的顶点对组成,通常记为6=V,E o图是一种较线性表和树更为复杂的数据结构在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能有关图的抽象数据类型定义如下ADT Graph/Digraph{数据对象VV是具有相同特性的数据元素的集合,称为顶点集数据关系RR={VR}八对于有向图VR={V span,w|v,wfv且Pv,w,V span,w表示从V到w的弧,谓词Pv,w定义了弧V span,,w的意义或信息}八一对于无向图VR={v,w|v,wfv且Pv,w,v,w表示从v到w的边,谓词Pv,w定义了边v,w的意义或信息}基本操作P:CreateGraph G,V,VR返回结果V是图的顶点集,VR是图中边或弧集合按V和VR的定义构造图Go DestoryGraphG初始条件G是已经存在的一个图操作结果销毁图G ExistG,v,w初始条件G是已经存在的一个图,v、w是两个顶点操作结果如果存在边v,w或弧vV span,w,则返回TRUE,否则返回FALSEo EdgesG初始条件G是已经存在的一个图操作结果返回图中边的数目Vertices G初始条件G是已经存在的一个图操作结果返回图中顶点的数目AddG,v,w初始条件图G已存在,v,w是两个顶点操作结果如果G是有向图,则在G中添加一条弧vVv span,,w;如果G是无向图,则在G中添加一条边v,w oDeleteG,v,w初始条件图G已存在,v,w是两个顶点操作结果如果G是有向图,则在G中删除一条弧vVv span,w;如果G是无向图,则在G中删除一条边v,w oDegree G,v初始条件图G及顶点v已存在操作结果返回图G中顶点v的度Indegree G,v初始条件图G及顶点v已存在操作结果如果G是有向图,则返回顶点v的入度;如果G是无向图,则返回图G中顶点v的度Outdegree G,v初始条件图G及顶点v已存在操作结果如果G是有向图,则返回顶点v的出度;如果G是无向图,则返回图G中顶点v的度DFSTraverse G,v,visit初始条件图G已存在,v是G中的某个顶点,visit是顶点的应用函数操作结果从顶点v起深度优先遍历图G,并对顶点调用函数visit一次且仅一次一旦visit失败,则操作失败BFSTraverse G,v,visit初始条件图G已存在,v是G中的某个顶点,visit是顶点的应用函数操作结果从顶点v起广度优先遍历图G,并对顶点调用函数visit一次且仅一次一旦visit失败,则操作失败}ADT Graph/Digr叩h
2.图的存储结构1邻接矩阵一个n个顶点的图G=V,E的邻接矩阵Adjacency Matrix是一个nxn矩阵AdjMatrix,AdjMatrix中的每个元素是0或1假设图G中顶点集合:V={1,2,…,n},那么AdjMatrix中的元素定义如下AdjMatrix[i]U]=i-[jf!vml]-!-[endif]-!vml]-图的邻接矩阵存储结构的C语言描述形式如下:#define INFINITYINT MAX#define MAX_VERTEX_NUM20typedef enum{DG=1,AG,DN,AN}GraphKind;〃{有向图、无向图;有向网、无向网}typedef struct node{VertexType vextex;〃顶点信息}Node;typedef structarcs{int adj;//顶点邻接关系...〃该边或弧的相关信息指针}Arcs;typedef struct{Node nodes[MAX_VERTEX_NUM];〃顶点集合Arcs arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃邻接矩阵int vexnum,arcnum;〃顶点数和弧数GraphKind kind;〃kind取值
1、
2、
3、4分别表示有向图、无向图、有向网、无向网}Graph;
(2)邻接表邻接表(Adjacency List)是一种顺序存储与链式存储相结合的存储结构,顺序存储部分用来保存图中顶点信息,链式存储部分保存图中边或弧的信息具体做法是图G被表示为一个数组或向量v[l],v
[2],v[n],每个元素对应图中一个顶点每个v[i]存储顶点%的信息,以及一个指向包含所有依附于顶点%的边组成的单链表的指针,v[i]称之为头结点头结点结构如下图所示data^I其中data存放与顶点相关的信息、,firstarc是指针;邻接单链表中每个结点表示依附于该顶点的一条边(对于有向图则是以顶点w为尾的弧),称为边(弧)结点,其结构如下图所示其中adjvex存放依附于该边的另一个顶点在一维数组中的序号,对于有向图,存放的是该弧结点所表示的弧的弧头顶点在一维数组中的序号;nextarc为指向下一条边(或弧)结点的指针;inf存储和边或弧相关的信息,如权值等图的邻接表存储结构的C语言描述形式如下#define MAXLEN10typedef structnode{/*边结点结构*/int adjvex;/*存放与头结点相邻接的顶点在数组中的序号*/int info;/*权值等信息*/structnode*nextarc;/*指向与头结点相邻接下一个顶点的表结点*/}EdgeNode;typedef struct{/*头结点结构*/int id;/*顶点入度*/char data;/*顶点信息*/EdgeNode*firstarc;/*指向头结点对应的单链表中的表结占*/
八、、/}VexNode;typedef struct{/*邻接表结构*/VexNode adjs[MAXLEN];/*邻接表的头结点集合*/int vexnum,arcnum;/*顶点数,边数*/int kind;/*图的种类*/}Adj List;
3.图的遍历图有两种搜索路径的遍历方法深度优先搜索遍历和广度优先搜索遍历图的深度优先搜索Depth-First Search,DFS策略是从给定顶点v出发,在回溯之前,沿着从v出发的一条路径尽可能深入前进其遍历规则为从v出发,访问v的一个未被访问的邻接顶点wl,再从wl出发,访问wl的一个未被访问的邻接顶点w2,然后从w2出发,访问w2的一个未被访问的邻接顶点w3,・・・,如此下去,直到一个所有邻接点都被访问过的顶点为止然后回溯到尚有邻接点未被访问的顶点,重复上述过程,直到图中所有与v有路径相通的顶点都被访问过;此时,若图中还存在未被访问过的顶点,则从其中一个未被访问过的顶点出发,重复上述过程,直到图中所有顶点都被访问为止图的广度优先搜索B「oad-First Search,BFS策略是在访问给定顶点v之后,先访问与V邻接的所有顶点Wl、W
2、…、Wk,然后再依次从Wl、W
2、…、Wk出发,访问它们的未被访问过的邻接顶点,重复上述操作,直到图中所有被访问过的顶点的邻接顶点都被访问为止若此时图中还有未被访问过的顶点,则从一个未被访问过的顶点出发,重复上述过程,直到图中所有的顶点都被访问过为止
4.最短路径图的最短路径问题有一是求从一个顶点源点到其它各顶点的最短路径;二是求每对顶点之间的最短路径第一种情况采用迪杰斯特拉算法解决,这是一个按路径长度递增的顺序逐步产生最短路径的算法第二种情况采用Floyd算法求解
(1)Dijkstra算法的实现设有向网G=V,E,它采用邻接矩阵作为存储结构若邻接矩阵为Cost,并规定顶去点到顶点之间有直接边,且权值为Wg Cost[i][j]=0i=j,顶点i与顶点j是同一个顶点8顶点i和顶点j之间没有边-设立两个一维数组S和Distance,其中S存放已经找到最短路径的顶点,它的初始状态为集合S中只含有起始顶点(源点)并规定.二[0未找到源点到顶点》的最短路径S[1J=11已经找到源点到顶点门的最短路径Distance的每个分量Distance]表示当前所找到的从起始顶点v到每个目的顶点%的最短路径长度它的初始状态为若从v到%有弧,则Distance[i]为弧上的权值,否则置Distance]为8,即Distance[i]=Cost[LocateVex(v)][i],LocateVex用于确定顶点v在G中的位序利用Distance的各个分量的值,选取当前具有的最短路径的顶点勺使得Distance[j]=min{Distance[i]|v®V—S}然后将顶点巧加入集合S中,即令同时对于所有S[i]=0的顶点切,修改源点到它们可达的最短路径为Distance[i]=min{Distance[i],Distance[j]+Cost|j][i]}上述过程重复执行n-1次,就可以得到源点到其它顶点的最短路径值
(2)Floyd算法的思想假设求从顶点%到顶点Vj的最短路径如果从顶点Vi到顶点Vj有弧,则从顶点%到顶点巧存在一条长度为Cost[i][j]的路径,该路径不一定是最短路径,尚需进行n次试探首先考虑路径(s,vo,巧)是否存在(即判断弧(w,vo)和(Vo,Vj)是否存在)如果存在,则比较(Vi,Vo,Vj)和(Vi,Vj)的路径长度,然后取长度较短者为顶点Vi到顶点Vj的中间顶点的序号不大于0的最短路径假如在路径上再增加一个顶点vl,山就是说,如果(Vi,…,V1)和(VI,…,Vj)分别是当前找到的中间顶点的序号不大于0的最短路径,那么(Vi,…,V1,…,Vj)就有可能是从Vi到顶点Vj的中间顶点的序号不大于I的最短路径将它和已经得到的从Vi到顶点Vj的中间顶点序号不大于0的最短路径相比较,从中选出中间顶点的序号不大于1的最短路径之后,再增加一个顶点V2,继续进行试探依次类推在一般情况下,若(Vi,…,Vk)和(Vk,…,Vj)分别是从Vi到顶点Vk和从Vk到顶点Vj的中间顶点的序号不大于k-1的最短路径,则将(Vi,…,Vk,・・.,Vj)和已经得到的从vi到Vj且中间顶点序号不大于k-1的最短路径相比较,其长度较短者便是从顶点Vi到顶点Vj的中间序号不大于k的最短路径这样,在经过n次比较后,最后求得的必是从顶点%到顶点巧的最短路径按此方法,可以同时求得各对顶点的最短路径四实验设备、仪器、工具与资料微机、VC五实验内容
(1)实验任务1图的遍历针对下图所示的有向图,编写c程序完成如下功能1)建立有向图的邻接表2)并在邻接表存储基础上完成深度优先遍历和广度优先遍历初始条件三元组T已存在操作结果如果T的三个元素按升序排列,则返回1,否则返回0IsDescendingT初始条件三元组T已存在操作结果如果T的三个元素按降序排列,则返回1,否则返回0Max T,e初始条件三元组T已存在操作结果用e返回T中三个元素的最大值Min T,e初始条件三元组T已存在操作结果用e返回T中三个元素的最小值}ADT Triplet
2.抽象数据类型的表示与实现我们可以通过固有数据类型来表示和实现抽象数据类型,即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作我们约定以C语言作为数据结果的描述工具例如,抽象数据类型Triplet的表示和实现如下typedef ElemType*Triplet;//-------基本操作的实现--------Status InitTripletTripletT,ElemType vlzElemType v2,ElemType v3{〃构造三元组T,依次设置T的三个元素的初值为vl,v2和v3T=日emType*malloc3*sizeof日emType;if!TexitOVERFLOW;T
[0]=vl;T
[1]=v2;T
[2]=v3;return OK!}Status DestroyTripletTripletT{free T;T=NULL;return OK!}Status GetTriplet T,int i,日emTypee{if i111i3return ERROR;e=T[i-l];return OK!}Status PutTripletT,int i,日emType e{if i111i3return ERROR;T[i-1]=e;return OK!}图5-1有向图
(2)实验任务2求解图的最短路径给出五个城市的交通图如图5-2所示,弧上数字表示城市之间的道路长度现要在五个城市中选择一个城市建造一个物流配送中心问这个物流配送中心应设在哪个城市到其他城市的路程之和最短?请编程解决这个问题图5-2六实验步骤
(1)实验预习1)预习本实验原理中关于图的存储表示2)分析掌握教材128页中C程序以及133〜134页算法5-3,为完成实验任务1做好准备3)分析掌握教材139〜142页中的算法5-5〜5-6,为完成实验任务1做好准备4)分析掌握教材158〜160页中的算法5-10〜5-11,为完成实验任务2做好准备
(2)实验步骤1)问题分析充分地分析和理解此实验任务,弄清要求作什么,限制条件是什么2)系统的结构设计按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计3)详细设计详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节4)编码在详细设计的基础上,对详细设计的结果进一步求精,用C语言表示出来5)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验任务
1、2的程序清单及运行结果八思考题1)为什么实现图的遍历操作时采用邻接表存储结构,而求解最短路径问题时采用邻接矩阵存储结构?2)如何由图的邻接矩阵得到图的邻接表?实验六查找/检索一实验任务1)静态查找方法的实现2)动态查找方法的实现二实验目的1)掌握典型的查找方法(折半查找、二叉树查找)2)了解各种查找方法的适用范围和效率三实验原理
1.查找表表(Table)是由同一种类型数据元素(记录)构成的集合表的抽象数据类型定义如下ADT Table{数据对象具有同种数据类型的数据元素的集合;数据关系数据元素之间无特定的次序关系,同属一个集合;基本操作CreateTable(L)操作结果创建一个空表L TableEmpty(L)初始条件表L已存在操作结果若L为空表,则返回TRUE,否则返回FALSE TableInsert(L,newltem)初始条件表L已存在,newltem为给定元素操作结果在表L中插入一个新数据元素newltem TableDelete(L,search Key)初始条件表L已存在,searchKey为给定元素操作结果:在表L中删除一个关键字值等于searchKey的数据元素TableSearch L,searchKey初始条件表L已存祇searchKey为给定元素操作结果在表中查找一个关键字值等于searchKey的数据元素TableTraverse L,visit初始条件表L已存在,visit是对元素操作的应用函数操作结果按某种次序对L中元素调用函数visit一次且仅一次一旦visit失败,则操作失败}ADT Table若对表只作查找〃的操作,则称此类表为静态查找表Static SearchTable□若在查找过程中同时插入表中不存在的数据元素,或者在表中删除已存在的某个数据元素,则称此类表为动态查找表Dynamic SearchTableo
2.静态查找1顺序查找顺序查找Sequential Search的方法是从表的一端开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,若找遍了表中所有记录,也未找到关键字与给定值相等的记录,则查找不成功2折半查找折半查找Binary Serach的查找过程是首先将给定的值key与有序表中间位置的记录的关键字相比较,若两者相等,则查找成功,否则根据比较结果确定下次查找范围是在中间记录的前半部分还是后半部分,然后在新的查找范围内进行同样操作,如此重复迭代,直到查找成功或失败折半查找优点是比较次数少,查找速度快,尤其当表的规模较大n值较大时,它的查找效率较高但是,折半查找只适用于有序表,且限于顺序存储结构对线性链表无法进行折半查找因此,在查找之前必须将顺序表按关键字的大小排序
3.动态查找1二叉查找树二叉查找树Binary SearchTree又称二叉排序树Binary SortTree,是这样一棵二叉树,它或为空,或者每个结点中包含一个关键字,并满足如下条件1若它的左子树存在,则左子树上所有结点的关键字值均小于根结点2若它的右子树存在,则右子树上所有结点的关键字值均大于根结点3它的左、右子树也是一棵二叉查找树二叉查找树结构兼有顺序存储结构和链式存储结构的最佳特性,是实现动态查找的最佳选择2二叉查找树的建立从空树出发,经过一系列的插入操作之后,可以构建一棵二叉查找树若在二叉查找树上插入一个元素,具体操作如下将一个新结点插入到一棵空二叉查找树中非常容易实现,只需将root指针指向新结点即可如果树不空,则必须将插入结点的关键字值与根结点的关键字值比较如果新插入结点的关键字值较小,则插入结点必须插入到该根结点的左子树中;如果较大,则插入结点必须插入到该根结点的右子树中新插入结点一定是一个新添加的叶子结点,并且是在查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点
(3)二叉查找树的查找为了查找给定的目标,首先将它与树根结点的关键字进行比较如果相等,则完成查找,否则将依据给定的关键字值和根结点的关键字之间的大小关系,分别转向左子树或右子树继续查找,直到查找成功或命中一棵空子树四实验设备、仪器、工具与资料微机、VC五实验内容
(1)实验任务1静态查找设计一个程序,演示顺序查找、折半查找方法,要求采用菜单的形式进行选择
(2)实验任务2动态查找设计一个程序,实现二叉查找树的建立、查找、删除结点等操作
(3)实验任务3散列表查找(选做)针对你所在的班级的同学姓名设计一个散列表,使得平均查找长度不超过2,并完成相应的建表和查表程序要求散列函数采用质数除余法,冲突采用拉链法解决六实验步骤
(1)实验预习1)预习本实验原理中静态查找和动态查找的实现原理2)分析掌握教材168~171页中的算法6-1~6-2,为完成实验任务1做好准备3)分析掌握教材177~184页中的算法6-5~6-8,为完成实验任务1做好准备
(2)实验步骤1)问题分析充分地分析和理解此实验任务,弄清要求作什么,限制条件是什么2)系统的结构设计按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计3)详细设计详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节4)编码在详细设计的基础上,对详细设计的结果进一步求精,用C语言表示出来5)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验任务
1、2的程序清单及运行结果八思考题1)针对实验任务1中折半查找,如何求解其平均查找长度?2)在散列表查找中,已知平均查找长度和散列表存储的纪录数,如何求出散列表的长度?实验七排序一实验任务常用排序算法的实现二实验目的1)掌握常用排序方法的思想,并用C语言实现这些排序算法2)了解各种常用排序算法的性能(时间复杂性、空间复杂性、算法稳定性、算法简单性等)三实验原理
1.插入排序插入排序有直接插入排序、折半插入排序和希尔排序等方法直接插入排序类似于线性表中有序表的插入它由n-1趟排序组成,第i趟排序是向第1到i-1个有序记录之间插入一个新记录,使插入后的记录序列仍为有序在并向有序表中插入记录时,如果通过折半查找来确定插入位置,这就是折半插入排序希尔排序使用一个序列hi,h2,…,ht,叫做增量序歹U(Inc「ement Sequence)在使用增量hk的一趟排序之后,对于每一个记录i有P[i]WP[i+hJ即所有相隔hk的记录都被排序此时称该序列是hk-排序(hk-sorted)的
2.快速交换排序它的基本思想是,按一定的规则选择某个控制记录作为枢轴(Pivot),首先通过交换各个记录间的位置将它放置在它应该在的位置,使它之前的记录的关键字都比它的关键字小,它之后的记录的关键字都比它的关键字大对它前后的记录各自形成的子序列,再按同样的规则处理,直到所有记录都被安置在相应的位置上
3.选择排序选择排序(Selection Sort)的基本思想是在对n个记录进行的多趟排序过程中,第i趟排序是在n-i+1个记录中选择关键字最小的记录作为有序序列中的第i个记录,其中,i=l,2,n-lo选择排序主要包括简单选择排序和堆排序简单选择排序(Simple SelectionSort)是一种简单的排序方法它每次从待排序的记录序列中(范围从i到n)选择出关键字最小的记录,把该记录与序列中的第i个记录交换位置堆是一个序列,其中每个记录包含一个关键字,序列中的位置k处的关键字,至少大于位置2k和2k+l处(假设这些位置存在于序列中)的关键字堆排序的过程分为两个步骤首先,必须重新组合列表中的记录项,使它们满足堆的要求第二,重复移去堆的顶层,并提升另一个记录项顶替他的位置
4.归并排序把两个或多个有序表合并成一个有序表的过程称为归并(Merge)若归并的有序表有两个,叫做二路归并对有序表反复利用归并过程进行排序的方法称为归并排序(Merging Sort)利用二路归并操作的排序称为二路归并排序二路归并排序的过程是
(1)把无序表中的每一个元素都看作是一个有序表,则有n个有序子表;
(2)把n个有序子表按相邻位置分成若干对(若n为奇数,则最后一个子表单独作为一组),每对中的两个子表进行归并,归并后子表数减少一半;
(3)反复进行这一过程,直到归并为一个有序表为止四实验设备、仪器、工具与资料微机、VC五实验内容根据键盘输入的数据建立一个待排序表,利用C语言设计一个主程序完成下列排序运算1)插入排序(直接插入排序、折半插入排序和Shell排序)2)交换排序(快速排序)3)选择排序(堆排序)4)归并排序5)结束程序运行六实验步骤
(1)实验预习1)预习本实验原理中的各种排序方法的思想2)分析掌握教材212〜226页中的算法7-1〜7-10,为完成实验任务做好准备
(2)实验步骤1)问题分析充分地分析和理解此实验任务,弄清要求作什么,限制条件是什么2)系统的结构设计按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计3)详细设计详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节4)编码在详细设计的基础上,对详细设计的结果进一步求精,用C语言表示出来5)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验任务的程序清单及运行结果八思考题如何在本试验任务的实现程序中统计出各种排序算法中关键字的比较次数和纪录移动次数?四实验设备、仪器、工具及资料微机、VC五实验内容通过C语言实现一个可无误运行的完整程序,完成抽象数据类型Triplet的表示和实现要求程序运行时显示基本操作的菜单,由用户选择执行相应操作(如可利用switch语句等),以此整合Triplet的各基本操作,实现程序设计六实验步骤
(1)实验预习1)预习本实验原理中关于抽象数据类型Triplet的定义、表示及实现2)熟悉程序运行环境VC的使用
(2)实验步骤1)问题分析与系统的结构设计充分地分析和理解此实验项目,弄清要求作什么,限制条件是什么按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计2)详细设计和编码详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节在编码时,可以对详细设计的结果进一步求精,用高级语言表示出来3)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验项目的程序清单及运行结果八思考题为什么用抽象数据类型描述数据结构?实验二线性表一实验任务1)线性表的顺序表示和实现2)线性表的链式结构表示和实现二实验目的1)掌握线性表的类型定义和结构特点2)掌握线性表的顺序存储表示、链式存储表示及其C语言实现3)掌握顺序表的各种基本操作的实现4)掌握线性表在链式存储结构上的各种操作三实验原理
1.线性表的逻辑结构及特性所谓线性表LinearJJst,就是nn20个数据元素的集合{a%…,an},这些数据元素之间有逻辑上的线性关系线性表的抽象数据类型定义如下ADT List数据对象D={aj|ajGEIemSet,i=l,2,n0}数据关系Ri={aj-i,ai|aj-1,ajeD,i=2,…,n基本操作CreatList8iL操作结果生成一个空的线性表L ListLengthL初始条件线性表L已存在操作结果返回L中数据元素个数ListInsertL,i,e初始条件线性表L已存在,lWiWListLengthL+l操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加lo ListDeleteL,i,e初始条件线性表L已存在且非空,lWiWListLengthL操作结果删除L的第i个数据元素,并用e返回其值,L的长度减lo Get日emL,i,e初始家件线性表L已存在,lWiWListLengthL操作结果用e返回L中第i个数据元素的值LocateElemL,e,compare初始条件线性表L已存在,compare是数据元素判定函数操作结果返回L中第1个与e满足关系compare的数据元素的位序若这样的数据元素不存在,则返回值为0ListEmptyL初始条件线性表L已存在操作结果若L为空表,则返回TRUE,否则返回FALSE ClearListL初始条件线性表L已存在操作结果将L重置为空表DestroyListL初始条件线性表L已存在操作结果销毁线性表L}ADT List
2.线性表的顺序表示线性表的顺序表示就是利用一组地址连续的内存空间依次存储线性表的各个数据元素,即以元素在计算机内物理位置相邻〃来表示线性表中数据元素之间的逻辑关系由于顺序存储结构是一种随机存取的存储结构,所以通常利用C语言中动态分配的一组连续的存储单元作为顺序存储结构所需要的存储空间可通过定义结构体类型来实现线性表的动态分配顺序存储结构具体数据类型描述如下#define MAXLEN100#define LISTJNCREASE10〃线性表存储空间的动态分配增量typedef struct{ElemType*list;〃线性表的存储空间的基地址int length;〃线性表的当前长度int maxsize;〃线性表当前分配的存储容量}List_Sq;
3.^性表的链式结构链式存储结构具有以下特点不要求逻辑上相邻的元素在物理结构上也相邻;允许迅速简单地插入或删除结点,而不必移动大量元素;但只能顺序存取而不能随机存取线性表中任一元素线性表的链式存储结构可通过单链表来实现此时,线性表中的每个元素对应单链表中的一个结点,每个结点的数据域存储线性表的数据元素,每个结点的指针域存储其后继元素所在结点的地址,可以通过每个结点的指针域访问到其后继结点,如图
2.1所不头指针第一个结点al叫图
2.1线性链表示例因此,单链表中每个结点都是由包含这个数据元素的信息和一个指示其直接后继的指针组成的一个结构体类型,具体描述如下typedef struct LNodeElemType data;structLNode*next;}LNode,*List_Link;每个单链表的反指针L是ListJJnk型的变量,指向链表中第一个结点由表头指针出发可以依次访问到每个结点,存取相应的数据元素值线性表中数据元素间的线性关系都可以通过单链表中结点指针域的链接关系反映出来当L=NULL时,意味着所表示的线性表为空〃表,其长度n为零〃四实验设备、仪器、工具及资料微机、VC五实验内容1实验任务L顺序表的表示与实现请编制C程序,利用顺序存储方式来实现下列功能1建立主程序菜单,使之具有建立线性表、插入元素、删除元素、查找元素、销毁线性表、结束程序运行等菜单项2根据键盘输入数据生成一个线性表,并输出该原始线性表3)根据屏幕菜单的提示选择,进行数据插入、删除、查找等操作4)最后,输出修改之后的线性表并结束程序的运行
(2)实验任务2线性表的链式存储表示与实现请编制C程序,利用链式存储方式来实现下列功能1)建立主程序菜单,使之具有建立线性表、插入元素、删除元素、查找元素、销毁线性表、结束程序运行等菜单项2)根据键盘输入数据生成一个单链表,并输出该原始单链表3)根据屏幕菜单的提示选择,进行数据插入、删除、查找等操作4)最后,输出修改之后的单链表并结束程序的运行
(3)实验任务3线性表的合并(选做)编制C程序实现下列功能1)建立两个线性表(顺序存储表示或链式存储表示)2)对已建立的两个线性表进行升序排序3)合并这两个有序表六实验步骤
(1)实验预习1)预习本实验原理中关于线性表的定义、顺序存储表示和链式存储结构2)分析掌握教材21~23页中的算法2-1~2-5,为完成实验任务1做好准备3)分析掌握教材27~30页中的算法2-9~2・13,为完成实验任务2做好准备4)分析掌握教材25页中的算法2-7~2-8或教材31-32页中的算法2-15-2-16,为完成实验任务3做好准备
(2)实验步骤1)问题分析充分地分析和理解此实验任务,弄清要求作什么,限制条件是什么2)系统的结构设计按照以数据结构为中心的原则划分模块最后写出每个子程序(过程或函数)的规格说明,列出它们之间的调用关系,可以使用调用关系图表示则更加清晰,这样便完成了系统结构设计3)详细设计详细设计的目的是对子程序(过程或函数)的进一步求精用IF、WHILE和赋值语句等,以及自然语言写出算法的框架利用自然语言的目的是避免陷入细节4)编码在详细设计的基础上,对详细设计的结果进一步求精,用C语言表示出来5)在VC环境下调试程序七实验报告要求实验报告包含程序开发过程所形成的所有文档资料,包括如下内容1)需求分析及规格说明问题描述,求解的问题是什么2)概要设计本程序所用的数据类型定义;主程序流程;程序模块及相互关系3)详细设计采用C语言定义的数据结构;各模块的伪码算法;各函数调用关系4)调试报告5)本实验任务
1、2的程序清单及运行结果八思考题1通过实验任务
1、2的实现比较线性表的两种存储结构的优缺点2实现任务3种采用哪种存储表示更容易些?实验三栈与队列一实验任务1栈的应用2队列的表示与实现二实验目的1了解栈与队列的特性2掌握栈的顺序、链式存储表示及实现3掌握队列的顺序、链式存储表示及实现4掌握栈与队列在实际问题中的应用三实验原理
1.栈的特性栈Stack又称堆栈,是一种特殊的线性表,可定义为插入、删除和访问只能在某一端进行的线性数据结构堆栈允许插入、删除和访问的一端称为栈顶Top,另一端称为栈底Bottom栈顶的第一个元素被称为栈顶元素堆栈的性质决定它的数据是按先进后出〃的顺序被访问,即最先存储的元素最后被访问、删除,最后存储的元素最先被访问、删除,所以栈也称为LIFO LasJIn,First_Out栈由抽象数叠类型定义如下ADT Stack{数据对象D={ai|a;G ElemSet,i=1,2,n0}数据关系R={ai-i,ai|ai-i,ai ED,i=2,…,n约定an端为栈顶,dl端为栈底基本操作InitStackS操作结果构造一个空栈S PushS,e初始条件栈S已存在操作结果插入元素e为新的栈顶元素PopS,e初始条件栈S已存在且非空操作结果删除S的栈顶元素,并用e返回其值GetTopS,e初始条件栈S已存在且非空操作结果用e返回S的栈顶元素StackEmptyS初始条件栈S已存在操作结果若S为空栈,则返回TRUE,否则返回FALSE StackLengthS初始条件栈S已存在操作结果返回S的元素个数,即栈的长度StackTraverseS,visit初始条件栈S已存在且非空操作结果从栈底到栈顶依次对S的每个数据元素调用函数visit o一旦visit失败,则操作失败ClearStackS初始条件栈S已存在操作结果将S清为空栈DestroyStackS初始条件栈S已存在操作结果栈S被销毁}ADT Stack
2.栈的顺序表示栈的顺序存储结构,即顺序栈,是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时通过指针top指示栈顶元素在顺序栈中的位置由于很难估计栈在使用过程中所需要的最大空间的大小,所以通常利用C语言中动态分配的一组连续的存储单元作为顺序栈所需要的存储空间顺序栈所需要的具体数据类型描述如下#define MAXLEN100#define STACKJNCREASE10〃顺序栈存储空间的动态分配增量typedef struct{Elemlype*base;〃栈的存储空间的基地址,即栈底指针ElemType*top;〃栈顶指针int maxsize;〃栈当前分配的存储容量}SqStack;其中,maxsize指示栈当前可使用的最大容量;base为栈底指针,在顺序栈中,它始终指向栈底的位置,若base=NULL,则表明栈结构不存在;top为栈顶指针,起初值为栈底指针值,即top=base,这也可作为栈空的标记栈插入新元素时,将新元素插入到栈顶指针所指向的位置,同时指针top增1,删除栈顶元素时,指针top减
13.栈的链式存储表示栈的链式存储结构,即链栈,与线性表的链式存储结构类似,是通过由结点构成的单链表实现的,但每个结点的指针指向其前驱结点在其之前进栈的结点此时,表头指针称为栈顶指针,其指向的结点即为栈顶结点所需要的具体数据类型描述如下typedef struct SNode{Elemlype data;structSNode*prior;prior将指向其前一次入栈的元素}SNode,*SLink;
4.队列的特性队列Queue简称队,也是一种特殊的线性表,可定义为只允许在表的一端进行插入,而在表的另一端进行删除的线性结构队列允许插入的一端称为队尾Rear,允许删除的一端称为队首Front o由于队列的插入和删除分别在不同的两端进行,因而先插入者自然先从另一端删除,所以队列具有先进先出〃的特点,简称为FIFO FirstTn,First-Out队列的抽象数据类型定义如下ADT Queue{数据对象D={ai|a;e ElemSet,i=1,2,…,n,n0}数据关系:Rl={ai-i,ai|api,ai GD,i=2,…,n约定其中ai端为队首,an端为队尾基本操作InitQueueQ操作结果构造一个空队列Q QueueEmptyQ初始条件队列Q已存在操作结果若Q为空队列,则返回TRUE,否则FALSE QueueLengthQ初始条件队列Q已存在操作结果返回Q的元素个数,即队列的长度EnQueueQ,e初始条件队列Q已存在操作结果插入元素e为Q的新的队尾元素DeQueueQ,e初始条件Q为非空队列操作结果删除Q的队首元素,并用e返回其值GetHeadQ,e初始条件Q为非空队列操作结果用e返回Q的队首元素QueueTraverseQ,visit初始条件Q已存在且非空操作结果从队首到队尾,依次对Q的每个数据元素调用函数visit o一旦visit失败,则操作失败ClearQueueQ初始条件队列Q已存在操作结果将Q清为空队列DestroyQueueQ初始条件队列Q已存在操作结果队列Q被销毁,不再存在}ADT Queue
5.队列的顺序表示队列的顺序存储结构,用一组地址连续的存储单元依次存放从队首到队尾的元素,同时附设两个指针front和rear分别指示队首元素及队尾元素的位置循环队列所需要的具体数据类型描述如下#define MAXQSIZE100〃最大队列长度typedef struct{ElemType*base;〃初始化的动态分配存储空间int front;〃头指针,若队列不空,指向队首元素int rear;〃尾指针,若队列不空,指向队尾元素的下一个位置}SqQueue;
6.队列的链式存储表示。