第一篇：数据结构图的遍历实验报告
实验报告
课程名：数据结构（实验名：图的遍历姓
名：班
级：学
号：时
间：
C语言版）
2014.11.15
一 实验目的与要求
1.掌握图的遍历的方法
2.利用 C 语言实现图的遍历
二 实验内容
• 将一个图存储起来
• 对该图分别进行先深和先广遍历
三 实验结果与分析
程序：
#include
#define QUEUE_SIZE(MAX_VEX+1)//队列长度 //using namespace std;bool *visited;//访问标志数组,避免同一顶点多次访问 /****图的邻接矩阵存储结构******/ typedef struct{ char *vexs;//顶点向量
int arcs[MAX_VEX][MAX_VEX];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数 }Graph;/*********队列类************/ class Queue{ public: void InitQueue(){ base=(int *)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;} void EnQueue(int e){ base[rear]=e;rear=(rear+1)%QUEUE_SIZE;} void DeQueue(int &e){ e=base[front];front=(front+1)%QUEUE_SIZE;} public: int *base;int front;int rear;};/*图G中查找元素c的位置*/ int Locate(Graph G,char c){ for(int i=0;i G.vexs=(char *)malloc(G.vexnum*sizeof(char));//分配顶点数目 printf(“输入%d个顶点.n”,G.vexnum);for(i=0;i printf(“输入顶点%d:”,i);scanf(“%c”,&G.vexs[i]);temp=getchar();//接收回车 } for(i=0;i for(j=0;j printf(“输入弧%d:”,i);scanf(“%c %c %d”,&a,&b,&w);//输入一条边依附的顶点和权值 temp=getchar();//接收回车 s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;} } /*****图G中顶点k的第一个邻接顶点***********/ int FirstVex(Graph G,int k){ if(k>=0 && k for(int i=0;i for(int k=j+1;k visited[k]=true;printf(“%c ”,G.vexs[k]);//访问第k个顶点 for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS } } /****************广度优先遍历***************/ void BFS(Graph G){ int k;Queue Q;//辅助队列Q Q.InitQueue();for(int i=0;i visited[i]=true;printf(“%c ”,G.vexs[i]);Q.EnQueue(i);//i入列 while(Q.front!=Q.rear){ Q.DeQueue(k);//队头元素出列并置为k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))if(!visited[w]){ //w为k的尚未访问的邻接顶点 visited[w]=true;printf(“%c ”,G.vexs[w]);Q.EnQueue(w);} } } } /***********主函数***************/ void main(){ int i;Graph G;CreateUDN(G);visited=(bool *)malloc(G.vexnum*sizeof(bool)); printf(“n广度优先遍历: ”);for(i=0;i 图1.图的遍历程序运行结果 实验报告 课程名：数据结构（C语言版）实验名：二叉树的遍历 姓名： 班级： 学号： 时间：2014.11.03 一 实验目的与要求 1.掌握二叉树的存储方法 2.掌握二叉树的三种遍历方法 3.实现二叉树的三种遍历方法中的一种 二 实验内容 • 接受用户输入一株二叉树 • 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序 三 实验结果与分析 //*********************************************************** //头文件 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 //*********************************************************** typedef struct BiTNode { //二叉树二叉链表存储结构 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树 //构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} } //*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} } //*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树 printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);} 图1:二叉树的遍历运行结果 班级：380911班 学号：57000211 姓名：徐敏 实验报告 一，实验目的： ·掌握二叉树的链式存储结构； ·掌握构造二叉树的方法； ·加深对二叉树的中序遍历的理解； 二，实验方法： ·用递归调用算法中序遍历二叉树。三，实验步骤： ·通过链式存储建立一颗二叉树。 ·设计一个算法实现中序遍历二叉树。四，具体实验步骤： #include typedef struct _BTNODE{ char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE; void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p); void main(){ PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf(“Input the data:”);ConstructBTree(p);PrintBTree(p,0);printf(“Now InorderTraverse:”);InorderTraverse(p);printf(“nPress any key to continue...”);getchar();} void PrintBTree(PBTNODE p,int depth){ 班级：380911班 学号：57000211 姓名：徐敏 int i;if(p==NULL){ return;}else{ for(i=0;i printf(“--”);} printf(“>”); printf(“%cn”,p->c); PrintBTree(p->lchild,depth+1); PrintBTree(p->rchild,depth+1);} } void ConstructBTree(PBTNODE p){ int side;char c;side=LEFT;while(TRUE){ scanf(“%c”,&c); if(c=='n'){ //printf(“EOFn”); return; } // printf(“%dn”,c); switch(c){ case '|': break; case')': return; case',': side=RIGHT; break; case'(': if(side==LEFT){ if(p->lchild==NULL){ p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE)); } ConstructBTree(p->lchild); }else{ if(p->rchild==NULL){ p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE)); } 班级：380911班 学号：57000211 姓名：徐敏 ConstructBTree(p->rchild); } break; default: if(side==LEFT){ p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE)); p->lchild->c=c; }else{ p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE)); p->rchild->c=c; } } } } void InorderTraverse(PBTNODE p){ if(p==NULL){ return;}else{ InorderTraverse(p->lchild); printf(“[%c] ”,p->c); InorderTraverse(p->rchild);} return;} 五，实验过程： ·输出：Input the date; ·输入：1(2(3,4),5(6,7)); ·输出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上机实验体会： ·体会到熟练掌握各种程序算法的重要性； ·通过上机练习，充分理解了链式建立二叉树的算法； ·形象的了解二叉树的结构，能够熟练的进行先序，中序，后序遍历二叉树。 《数据结构》 第六次实验报告 学生姓名 学生班级 学生学号 指导老师 重庆邮电大学计算机学院 计算机专业实验中心 一、实验内容 1)采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。2)输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根 左 右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左 根 右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历： 后序遍历的顺序是左 右 根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码： #include typedef struct Tnode //定义结点 { char data;//存储结点数据 struct Tnode *left;//定义结点左子指针 struct Tnode *right;//定义右子指针 }Tnode,*Pnode;//声明Tnode类型的变量和指针 typedef struct Stack//定义栈 { Pnode pnode[MAX];//存放数据 int p;//栈顶指针 }Stack,*Pstack;//定义Stack类型的变量和指针 void Push(Pstack pstack,Pnode pnode)//入栈 { } Pnode Pop(Pstack pstack)//出栈 { } Pnode Top(Pstack pstack)//看栈顶元素 { } int Isempty(Pstack pstack)//栈判空 { } int Isfull(Pstack pstack)//栈满 { } void Initstack(Pstack pstack)//初始化栈 if(pstack->p==FULL)else return 0;return 1;if(pstack->p==EMPTY)else return 0;;return 1;return pstack->pnode[pstack->p];return pstack->pnode[pstack->p--];pstack->p ++;pstack->pnode[pstack->p] = pnode;//赋值 { } void Inittnode(Pnode root,Pnode left,Pnode right,char data)//初始化结点 { } void PreorderR(Pnode proot)//递归先序遍历算法 { } void InorderR(Pnode proot)//递归中序遍历算法 { } void PostorderR(Pnode proot)//递归后序遍历算法 { } void PreorderI(Pnode proot,Pstack pstack)//非递归先序遍历算法 { Initstack(pstack);//初始化栈 while(proot||!Isempty(pstack))//如果栈空并且结点指针空，则结束循环 { if(proot){ printf(“%2c”,proot->data);if(proot){ } PostorderR(proot->left);PostorderR(proot->right);printf(“%2c”,proot->data);if(proot){ } InorderR(proot->left);printf(“%2c”,proot->data);InorderR(proot->right);if(proot){ } printf(“%2c”,proot->data);PreorderR(proot->left);PreorderR(proot->right);root->left=left;root->right = right;root->data = data;pstack->p=EMPTY; } } } else { } if(Isfull(pstack))//如果栈满不能执行入栈操作 { } Push(pstack,proot);//入栈 proot=proot->left;//指针指向左子 printf(“栈满，不能执行入栈操作！”);return;if(Isempty(pstack))//栈空时不能出栈 { } proot = Pop(pstack);//执行出栈操作 proot=proot->right;//指针指向右子 printf(“栈空，不能执行出栈操作！”);return;void InorderI(Pnode proot,Pstack pstack)//非递归中序遍历算法 { Initstack(pstack);//初始化栈 while(proot||!Isempty(pstack))//循环结束条件 { if(proot){ } else { if(Isempty(pstack)){ } proot = Pop(pstack);//出栈 printf(“%2c”,proot->data);//打印数据 printf(“栈空，不能执行出栈操作！”);return;if(Isfull(pstack)){ } Push(pstack,proot);//执行入栈操作 proot = proot->left;//指针指向左子 printf(“栈满，不能执行入栈操作！”);return; } } } proot=proot->right;//指针指向右子 void PostorderI(Pnode proot,Pstack pstack)//非递归后续遍历算法 { } void main(){ int flags[MAX];//定义标志位栈 int p =-1;//初始化标志位栈 int flag;//存放标志位 Initstack(pstack);//初始化栈 while(proot||!Isempty(pstack))//循环结束条件 { } if(proot){ } else { } proot = Pop(pstack);//指针出栈 flag = flags[p--];//相应标志位出栈 if(flag==0)//如果标志位为0表示右子还未访问过 { } else { } printf(“%2c”,proot->data);//打印数据 proot = NULL;//将结点指针置空 flag =1;//将标志位置1，右子已访问 flags[++p] = flag;//标志位入栈 Push(pstack,proot);//结点入栈 if(Isfull(pstack)){ } flags[++p] = 0;//标志位置0，并入栈 Push(pstack,proot);//结点入栈 proot=proot->left;//指针指向左子 printf(“栈满，不能执行入栈操作！”);return; proot = proot->right;//指针指向右子 Tnode A,B,C,D,E,F,G;//声明结点变量 Stack stack;//声明栈 Inittnode(&A,&B,&C,'A');//初始化结点 Inittnode(&B,NULL,&D,'B');Inittnode(&C,&E,&F,'C');Inittnode(&D,NULL,NULL,'D');Inittnode(&E,NULL,NULL,'E');Inittnode(&F,&G,NULL,'F');Inittnode(&G,NULL,NULL,'G');printf(“你定义的树的结构是：n”);printf(“A(B(D)C(E F(G)))n”);printf(“=====================下面是遍历结果====================n”);printf(“=====================递归先序遍历：====================n”);PreorderR(&A);printf(“n”);printf(“=====================非递归先序遍历：==================n”);PreorderI(&A,&stack);printf(“n”);printf(“=====================递归中序遍历：====================n”);InorderR(&A);printf(“n”);printf(“=====================非递归中序遍历：==================n”);InorderI(&A,&stack);printf(“n”);PostorderR(&A);printf(“n”);PostorderI(&A,&stack); printf(“n”); /*一下是调用相应的函数输出遍历结果*/ } printf(“=====================递归后序遍历：====================n”); printf(“=====================非递归后序遍历：==================n”); 五、遇到的问题及解决办法 这部分我主要遇到如下两个问题，其内容和解决方法如下所列： 执行程序时程序停止运行，其效果如图： 解决方法：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不合理，因此对调用的自定义函数进行相应的改动，将参数由具体类型改为指针类型后，程序正常运行。 程序不停的输出同一个结点的数据，其效果入图： 解决方法：分析运行结果可知，第一不停的输出证明遇到了死循环，第二输出的是同一个结点的数据，表示指针没有按预期进行指向，首先对程序进行调试，发现程序没有添加循环结束条件，添加循环结束条件后，只能输出树的部分结点的数据，对标志位进行修改后，程序运行正常，也能正确输出遍历结果。 六、心得体会 通过这次作业真的受益匪浅，感触良多： 首先，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，更不能眼高手低。眼高手低，懒得动手，这就犯了编程人员的大忌。大一我们开始接触C语言，这是我们接触到的第一种编程语言，但是当时徒有对编程的兴趣，却没有付诸行动，动手少，结果考试险过，通过这次作业，我再次看了C语言课本，边看边写代码，理解快，印象深刻，思维也活跃许多，状态也好，真正的意识到，编程能力需要靠实践来提升。当自己写出意想的程序后，真的有些成就感。再者，在吴老师的指导和要求下，我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很多，认真完成好每一项任务，这样无形中提高了对自己的要求，同时也增强了我们的动手能力和编程能力。 七、附录 运行结果截图。 实验三 数据选择器 实验人员： 班号： 学号： 一、实验目得 (1)熟悉并掌握数据选择器得功能.(２） 用双 4 选 1 数据选择器 74LS１５3 设计出一个 16 选 1 得数据选择器。 (3)用双 4 选 1 数据选择器 7４LS１53 设计出一个全加法器。 二、实验设备 数字电路实验箱，74LS0０,7４LS153.三、实验内容(1） 测试双 4 选 1 数据选择器７4LＳ153 得逻辑功能。 ７4LS153 含有两个 4 选 1 数据选择器,其中 与 为芯片得公共地址输入端，与 分别为芯片得公共电源端与接地端.Figure1 为其管脚图: Figｕｒe 错误 错误!未定义书签。 未定义书签。 ：路电接连图下按ﻩ Fｉｇuｒe 错误 错误!未定义书签。 (2)设某一导弹发射控制机构有两名司令员 A、B 与两名操作员Ｃ、Ｄ,只有当两名司令员均同意发射导弹攻击目标且有操作员操作,则发射导弹 F．利用所给得实验仪器设计出一个符合上述要求得１６选１数据选择器，并用数字电路实验箱上得小灯与开关组合表达实验结果。 思路 : 由于本实验需要有四个地址输入端来选中 16 个数据输入端得地址之中得一个,进而实现选择该数据输入端中得数据得功能，即 1６选１。而公共得、两 个地址输入端与 使能端(用于片选,已达到分片工作得目得,进而扩展了一位输入)一共可以提供三个地址输入端,故需要采用降维得方法，将一个地址输入隐藏到一个数据输入端 中。本实验可以降一维,也可以降两位。由于两位比较复杂,本实验选择使用降一维得方式。 做法 : :图诺卡得能功需所现实中题用应如出画ﻩ 00 0１ １1 1０ 0０ 01 0 0 0 ０ 0 0 １ 0 １1 ０ ０ １ ０ 10 0 0 1 0 将 D 降到数据输入端中。对应得卡诺图如下: ０0 01 1 0 0 Ｄ 0 0 0 1 0 按上述卡诺图连接电路，用开关控制送给各输入高低电平。其中,“1”表示高电平,“0”表低电平，均由开关上下拨动来控制；A、Ｂ、C、Ｄ分别为题中得两个司令员得同意情况与两个操作员得操作情况;F 为导弹发射情况,将Ｆ接到小灯上即可。电路如 Figuｒｅ 1 所示(图中 即，后面得图均为如此）: Ｆｉgure 3 AB CD C AB (3)用 74LS００与 74LＳ153 设计一位全加器，并用数字电路实验箱上得小灯与开关组合表达实验结果。 一位全加器得功能如下面两个卡诺图所示。其中 A、B 分别表示被加数与加数，CI 表示低位向本位得进位，S 表示运算结果，CO 表示向高位得进位。 CＯ: S: 00 经分析,此全加器有三个输入，而公共得、两个地址输入端与 使能端(用于片选，已达到分片工作得目得，进而扩展了一位输入）刚好一共可以提供三个地址输入端。故按上面得卡诺图,分析后应采用下面得端口解法: 按上面得接法连接电路。用开关控制送给各输入高低电平,“1“表示高电平,“0”表低电平,均由开关上下拨动来控制； 表示低位送进来得进位信号,A、B分别表示被加数与加数;S 与 分别表示加法结果与向高位得进位信号。电路如Ｆｉgure 4 所示： Figｕre 4 四、实验结果(１） 测试双 4 选 1 数据选择器７４ＬＳ153 得逻辑功能: ：下如录记果结将,)亮灯小或(平电高示表”１“,)灭灯小或(平电低示表”0“用ﻩ 0 0 1 0 １ B A A B 1Ｑ ０ 0 ０ 0 0 1 0 1 0 0 1 1０ 0 ０ 1 0 1 0 1 1 0 0 1 1 1 ０ 2Q ０ 0 0 ０ ０ 1 0 1 0 0 １ 1 １ 0 ０ 0 1 0 1 0 1 1 0 ０ 1 1 １ ０(2） 设计出一个符合题目要求得 16 选 1 数据选择器 :下如录记果结将,）亮灯小或(平电高示表”1“，)灭灯小或(平电低示表”0“用ﻩA B C D Ｆ 0 0 0 0 0 0 0 0 1 0 0 0 １ ０ 0 0 0 1 1 0 0 １ 0 0 0 ０ 1 ０ 1 1 0 1 1 0 1 ０ 1 1 1 1 1 0 0 ０ ０ 1 0 0 1 1 １ 0 １ 0 1 1 0 １ 1 1 1 1 0 ０ 0 1 １ 0 1 1 1 １ １ 0 1 １ 1 １ 1 1 。能功辑逻得出计设求要所足满以可路电此，得可表值真得面上由ﻩ(3） 设计一位全加器 :下如录记果结将,)亮灯小或(平电高示表“1“，）灭灯小或(平电低示表＂0“用ﻩA B CI S CO ０ 0 0 0 ０ 0 0 1 1 ０ 0 1 0 1 ０ ０ 1 1 0 1 １ ０ 0 1 ０ 1 0 1 0 1 1 1 0 0 １ 1 1 1 １ 1 由上面得真值表可得,此电路可以满足所要求设计出得逻辑功能。 五、故障排除 在实验(１)中，发现所连接电路与预期得逻辑功能不一致.在检验了导线与小灯都正常后,发现将芯片得管脚接错了，误将 Q 与 接错地方。分析原因，就是由于芯片管脚设置得位置与管脚图上面不一致,两侧均有两个管脚接口.六、心得体会 连了道知中除排得障故在且并，计设得路电辑逻了握掌地好更我,验实次这过通ﻩ接时要瞧引脚上面得标号而不能一味地只认准位置。 我还学会了降维得方法．本来以为只能用使能端扩展出一位输入,结果却可以通过降维扩展出更多。我感觉非常做电路实验。第二篇：数据结构-二叉树的遍历实验报告
第三篇：数据结构实验报告——中序遍历二叉树
第四篇：数据结构实验报告-二叉树的实现与遍历
第五篇：数据选择器实验报告
点击咨询 