自考《数据结构》实验指导.docx
《自考《数据结构》实验指导.docx》由会员分享,可在线阅读,更多相关《自考《数据结构》实验指导.docx(37页珍藏版)》请在咨信网上搜索。
1、计算机及应用专业数据结构实验指导书int j=0;listnode * p, *r;p=head;while (p&jnext; +j;if (!p-next | | jiT)return;r=p-next; p-next=r-next; free (r);void insertnode(linklist head, int x, int i) /在单链表中第i号位置处插入值为X的结点 (int j二0;listnode * p, *s;p=head;while(p&jnext; +j;if(!p|ji-l) exit (1);s=(linklist)malloc (sizeof (listn
2、ode); s-data=x;s-next=p-next; p-next=s;int _tmain(int argc, _TCHAR* argv)( linklist newlist=createlist;int i, x=20, y=25;doprintf (5d, newlist-data); newlist=newlist-next;while(newlist!=NULL); i=l; deletelist (newlist, i);i=3; deletelist(newlist, i); doprintf(5d,newlistdata); newlist=newlistnext;whi
3、le(newlist!=NULL);i=4; insertnode(newlist, x, i);i=8; insertnode(newlist, y, i); printf(n);doprintf(5d,newlist-data); newlist=newlistnext;while(newlist!二NULL); getchar;return 0;实验2二叉树的建立与遍历一、目的掌握二叉树的相关概念,能熟练完成二叉树的递归法建立、先序、中序和后 序遍历方法.二、题目二叉树的创建与遍历算法的设计三、实验内容及步骤要求要求:以下3个题中,任意选作一题.1、问题描述一一从键盘输入二叉树的元素,建
4、立二叉树,实现二叉树的遍历算法. 基本要求:(1) 从键盘输入二叉树的元素,建立二叉树.(2) 实现二叉树的先序遍历算法.2、问题描述一一从键盘输入二叉树的元素,建立二叉树,实现二叉树的遍历算法. 基本要求:(1) 从键盘输入二叉树的元素,建立二叉树.(2) 实现二叉树的中序遍历算法.3、问题描述一一从键盘输入二叉树的元素,建立二叉树,实现二叉树的遍历算法. 基本要求:(1) 从键盘输入二叉树的元素,建立二叉树.(2) 实现二叉树的后序遍历算法.四、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.五、范例参考include 甘include typedef
5、struct Nodeint data;struct Node *LChild;struct Node *RChild;BitNode, *BitTree;void CreatBiTree(BitTree *bt)/用先序遍历序列创建二叉树,如果是首当 前树根置为空,否则申请一个新节点/scanf (%d, &t);if(t二二0)*bt二NULL;else*bt二(BitTree)malloc(sizeof(BitNode); (*bt)-data=t:CreatBiTree(&(*bt)-LChild);CreatBiTree(&(*bt)-RChiId);void Visit (int
6、data)/访问根节点printf(%4d ,data);)void PreOrder(BitTree root)/*先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ if (root!=NULL)Visit (root -data) ; /*访问根结点*/PreOrder (root -LChild) ; /*先序遍历左子树*/PreOrder (root -RChild) ; /*先序遍历右子树*/void InOrder(BitTree root)/*中序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/if (root!二NULL)(InOrder (ro
7、ot -LChild) ;/*中序遍历左子树*/Visit (root -data) ;/*访问根结点*/InOrder (root -RChild) ;/*中序遍历右子树*/)void PostOrder(BitTree root)/*后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/if (root!二NULL)PostOrder (root -LChild) ; /*后序遍历左子树*/ PostOrder (root -RChild) ; /*后序遍历右子树*/ Visit (root -data) ;/*访问根结点*/void PrintTree(BitTree Boo
8、t, int nLayer) /按竖向树状打印的二叉树 /int i;if (Boot=NULL) return;PrintTree(Boot-RChild, nLayer+1);for (i=0;iLChiId, nLayer+1);int _tmain(int argc, _TCHAR* argv) BitTree T;int h;int layer;int treeleaf;layer=0;printf (请输入二叉树中的元素(以先序遍历序列输入,其中0代表空子 树):n);CreatBiTree (&T); printf (先序遍历序列为:);PreOrder (T);printf C
9、An中序遍历序列为:);InOrder (T);printf (n后序遍历序列为:);PostOrder (T);getch;return 0;实验3图的建立与遍历一、目的掌握图的定义,能熟练地运用邻接表和矩阵实现图的存储与深度优先和广度 优先的遍历方法.二、题目请以图1中给出的加权有向图完成实验内容与实验步骤要求中给出的2题.三、实验内容及步骤要求1、输出该图的邻解表和矩阵2种存放形式的存放结果;图1加权有向图2、编程输出该图的深度优先遍历和广度优先遍历的结果.(注意遍历得的结果不唯一,如下 的输出结果仅供参照)0040008000090050060005003000100040008000
10、09005006000500300010050700004000800009005006000500300010这是图的邻接表的形式0:311:22:503:524:35:40四、实验报告1、写出每个算法的思想.2、画出算法流程图.3、编写提交实验报告及程序清单.五、范例参考#include#includedefine max 100typedef struct(int number;int info;)VertexType;typedef struct(int edgesmaxmax: int n, e;VertexType vexsmax;define max 100typedef str
11、uct(int number;int info;)VertexType;typedef struct(int edgesmaxmax: int n, e;VertexType vexsmax;/最大顶点个数/以下定义临接矩阵类型顶点编号/顶点其他信息,边的权值顶点类型/图的定义邻接矩阵/顶点数和弧数/存放定点信息)MGraph;typedef struct ANodeint adjvex; /弧的重点位置,就是放值的 struct ANode nextarc;int info;)ArcNode;图的邻接矩阵类型/定义邻接表类型弧的结点结构类型/指向下一条弧的指针/存放弧的信息(权值)typed
12、ef struct Vnodeint data;ArcNode *firstarc;/邻接表/图中顶点数和和边数图的邻接表类型全局数组用于判断后面/输出邻接矩阵/将邻接矩阵g转换为邻邻接表头结点的的类型/指向第一条弧)VNode;typedef VNode AdjListmax; /AdjList是邻接表类型,把大表变成几个小的连接到一起typedef structAdjList adjlist:int n, e;ALGraph;int visitedmax: 节点是否被访问过 void DispMat(MGraph g)int i, j;for (i=0;ig. n;i+)for (j=0;
13、jadjlisti. firstarc=NULL;for (i=0; in; i+)/检查邻接矩阵的每个元素for (j=0;jadjvex=j: p-info=g. edges i j ;/存放边的权值p-nextarc=G-adjlisti. firstarc; 将*?连接到表后 G-adjlisti. firstarc=p;Ge=g. e;G-n=g. n;/输出邻接表弧的类型/这是那个大链表的头/顺着那个头向下查看/输出邻接表弧的类型/这是那个大链表的头/顺着那个头向下查看void DispAdj(ALGraph *G)(int i; ArcNode *p;for (i=0;in;i+
14、)p=G-adjlisti. firstarc; if (p!=NULL)printf ( %d: ,i);while(p!=NULL)printf ( %d ,p-adjvex) ;/输出弧的终点p=p-nextarc; printf(n);)void change (int visited, ALGraph *G) /给全局变量 visited 赋初值for (i=0;in;i+) visitedi=O;)void ListToMat (ALGraph *G, MGraph g)/将邻接表转换为邻接矩阵的形式(int i, j;int n=Gn:ArcNode *p;for (i=0;in
15、;i+)for (j=0;jn;j+)g. edgesi j=0;for(i=0;iadjlisti. firstarc;while (p!=NULL)g.edgesip-adjvex=p-info; p=p-nextarc;g. n=n;g. e=G-e;void DFS (ALGraph *G, int v)/递归深度优先遍历ArcNode *p;/change(visited, G):visitedv=l;/第一个点设为已被访问并输出,接着以他为主进行遍历 printf ( d, v);p=G-adjlistv. firstarc;while(p!=NULL)if (visitedp-a
16、djvex=0)DFS (G, p-adjvex); p=p-nextarc;)void BFS(ALGraph *G, int v) 广度优先遍历,一个点先找和其有关的所有节点,在 接着按步骤继续预备实验编制简单C+程序本部分主要介绍在Visual C+中编译和运行单个C程序的方法.1、打开VC,出现如图2. 1所示界面:图2.1 VC初始界面(新建)对话2、打开“file”(文件)菜单,选择“new”(新建),会出现“new” 框,如图2. 2所示:ArcNode *p;/定义循环队列并初始化int queuemax, front=0, rear=0; int visitedmax;int
17、 w, i;for (i=0;in;i+) visitedi=O;printfC %d ”, v);把输入的第v个作为第一个广度遍历的节点,一直这样进行下 去visitedv=l;rear=(rear+l)%max;queuerear=v;while(front!=rear)front= (front+l)%max;w=queuefront;p=Gadjlistw. firstarc:一个顶点了while(p!=NULL)rear=(rear+l)%max;queuerear=v;while(front!=rear)front= (front+l)%max;w=queuefront;p=Gad
18、jlistw. firstarc:一个顶点了while(p!=NULL)要入队了把V入队队列不为空的时候要出队了/跟前面差不多开始查找与顶点W邻接的第if (visitedp-adjvex=O)/就是当前节点未被访问printf (/z%d ,z, p-adjvex); visitedp-adjvex=l;rear= (rear+1) %max; 又要入队了,马上要重复之前的操作了 queuerear=p-adjvex;p=p-nextarc;void mainint i, j;MGraph g;/没有定义过的邻接表类型加上*ALGraph *G; int Amax6;printf (请输入邻
19、接矩阵:n);for (i=0;i6;i+)for(j=0;j6;j+) scanf (d,&Ai j);)g. n=6;g e = 10;for(i=0;ig. n;i+)for (j=0;jg. n;j+)g. edgesi j=Ai j ; /这是给邻接矩阵赋值 printf (这是图的邻接矩阵的形式:); printf (n);DispMat (g) ;/输出邻接矩阵的函数G= (ALGraph *)malloc(sizeof(ALGraph);MatToList(g, G);printf r这是图的邻接表的形式:);printf (n);DispAdj(G);printf (从顶点0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 自考 实验 指导
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。