新编工作范文数据结构试验指导新

1、# include<stdio.h> #include<iostream.h> #include<stdlib.h> #define MAX 100 struct node char data;struct node *next;int ishs(struct node *head,int n) char stackMAX/2; struct node *p=head;int top=0; while(top<n/2) stacktop=p->data; top+;p=p->next; if(n%2=1)p=p->next; top-

2、; while(p!=NULL&&top>=0&&p->data=stacktop) top-;p=p->next; if(top=-1&&p=NULL) return(1);else return(0); void main() char sMAX;struct node *head=NULL,*p,*q; int i=0;cout«"输入一个回文数："<<e ndl;scanf("%s",s);while(si!='0') p=new node;p

3、->data=si;p->next=head;head=p;i+;if(ishs(head ,i)printf("%s 是回文数 n",s);else printf("%s 不是回文数 n",s); 目录一、?顺序表根本操作的实现?实验二、?顺序表?实验 学生成绩治理三、?链表的应用?实验 求两个一元多项式之和四、?链表的应用?实验五、?栈的应用?实验 判断一个数是否是回文数六、?队列的应用?实验 利用队列解决分油问题七、?串的应用?实验 求两个串的最长公共子串八、?二叉树的应用?实验 设计一个表示家谱的二叉树九、?二叉树的应用?实验 借助二

4、叉树实现排序十、?二叉树的三种遍历?实验一 十一、?二叉树的三种遍历?实验二 十二、?图?实验一十三、?图?实验二 十四、?图的应用?实验 最小生成树十五、?快速排序的设计?实验 十六、?哈希表查找设计?实验一、?顺序表根本操作的实现?实验练习实验一实验目的1、掌握用 Visual C+ 6.0 上机调试线性表的根本方法.2、掌握线性表的根本操作, 插入、删除及查找等运算在顺序存储结构上的运算.二实验内容与要求 掌握线性表在顺序存储结构上的根本操作,插入、删除及查找等运算.三算法*定义一个线性表的顺序存储类型：#define MAX 50typedefchar或 int 类型等elemtype

5、;struct listelemtype listMAX;int size;注意：在后面的算法中,成员 list 数组的下标是从 0 开始,而 顺序表结点编号是从 1 开始的,因此进行它们之间的转换 要小心.1. 置空表运算void setnul(struct list *p )p->size=0; 2. 求顺序表长度运算int length(struct list *p)return (p->size);3. 取顺序表中第 i 个结点运算elemtype get(struct list *p,int i) if(i<1&&i<p->size)pr

6、intf( “位置参数不正确 n); else return(p->listi-1);4. 按值查找：int locate(struct list *p,elemtype x)int i=0;while (i<p->size&&p->listi!=x)i+;if(i=p->size)return(-1);else return(i+1);5插入结点：该操作在顺序表 list 的第 i 个位置上插入新结点 X viod insert(struct list *p,elemtype x,int i) int j;if(i<1&&i

7、<p->size+1)printf( “位置参数不正确,不能进行插入操作 )； elsep->size+;for(j=p->size-1;j>=i;j-)p->listj=p->listj-1;p->listj=x;6、删除结点该操作删除顺序表 list 的第 i 个结点.viod delete(struct list *p,int i) int j;if(i<1|i>p->size)printf “位置参数不正确,不能进行删除操作 ；else for(j=;j<p->size-1;j+)p->listj=p-

8、>listj+1;p->size-;7、显示顺序表：void display(struct list *p)int j;if(p->size=0)printf( “该顺序表为空,不能显示 )；elseprintf( “顺序表： )；if(p->size=1)printf( “%c,p->listp->size);else /*有一个以上结点 */for(j=0;j<p->size-1;j+)printf( “%c> ,p->listj); printf( “%c,p->listj);printf( “n);8、当顺序表的根本操作

9、设计好后,给出调用这些根本操作函数： void main()struct list q;setnull(&q);insert(&q, 'a',1);insert(&q, 'b',2);insert(&q, 'a',1);insert(&q, 'c',2);insert(&q, 'd',1);insert(&q, 'e',2);display(&q);printf( “值： %c 位置： %dn,'a',locate(&a

10、mp;q,'a');printf( “位置： %d 值： %cn,4,get(&q,4);printf( “删除第 2 个结点后顺序表： )； delete(&q,2);display(&q);printf( “删除第 2 个结点后顺序表： )； delete(&q,2);display(&q);printf( “删除第 1 个结点后顺序表： )；delete(&q,1);display(&q);printf( “删除第 1 个结点后顺序表： )； delete(&q,1);display(&q);9、本程

11、序的执行结果如下：顺序表： d e a c a b值：a位置：3位置： 4 值： c删除第 2 个结点后顺序表： d a c a b 删除第 2 个结点后顺序表 : d c a b 删除第 1 个结点后顺序表 : c a b 删除第 1 个结点后顺序表 : a b四)分析程序写出小结、体会.二、?顺序表应用?实验一 学生成绩治理一实验目的3、 掌握用 Visual C+ 6.0 上机调试线性表的根本方法.4、掌握线性表的根本操作, 插入、删除及查找等运算在顺序存储结构上的运 算.二实验内容与要求1、问题描述学生成绩治理是学校教务治理的重要局部,其处理的信息量很大.本实验对 学生的成绩治理做一个

12、简单的模拟,用菜单项选择择操作方式完成以下功能： *登记学生成绩*插入学生成绩*删除学生成绩2、算法输入3、操作要求：学生信息.5、算法要点： 此问题可看成对线性表的操作. 将学生成绩组织成顺序表, 那么 登记学生成绩既即是建立顺序表操作, 查询学生成绩、 插入学生成绩和删 除学生成绩即是建立在顺序表中进行查找、插入和删除操作.三算法1、数据类型定义学生成绩存储结构定义为：#define MAXNUM 100struct studentint number;char name10;int score;struct lstudentstudent sMAXNUM;int length;2、操作算

13、法( 1) 登记成绩算法void create(struct lstudent *ls)int n,i;cout<<n 请输入学生人数： ；cin>>n;ls->length=n;for(i=0;i<n;i+)printf( “n 请输入学生 %d 的数据： n,i+);cout<<n 学号： ；cin>>ls->si.number; 或 scanf(“%d,&ls->si.number);cout<<n 姓名： ；scanf(“%s,ls->);cout<<n 成绩 :

14、;scanf(“%d,&ls->si.score);( 2)查询成绩算法： void find(struct lstudent *ls) 请同学们自己完成 ( 3)插入成绩算法 : void insert(struct lstudent *ls)请同学们自己完成 根据输入插入学生数 N 将记录插入表尾( 4)删除成绩算法 : void del(struct lstudent *ls) 请同学们自己完成 根据输入要删除成绩学生号 X 将该记录删除3、程序#in cludeviostream.h #in clude<sdtio.h>#include<sdlib.h&

15、gt;#define MAXNUM 100struct studentint number;char name10;int score;struct lstudentstudent sMAXNUM;int length;void main( ) struct lstudent *ls;ls=new lstudent;int k;cout<<n cout<<学生成绩治理ncout<<n cout<<1、登记成绩n;cout<<2、查询成绩n;cout<<3、插入成绩n;cout<<4、删除程序n;cout<

16、<0、退出程序n;coutn;while( 1 )coutn 请输入选择的功能号： n;cin>>k;switch(k)case 1:create(ls);break;case 2:find(ls);break;case 3:insert(ls);break;case 4 :del(ls);break;case 0:return;default:cout<< 选择错误！ ;(四) 测试数据1、登记成绩数据学生数据：学号姓名分数1王红772李平853张军762、插入成绩数据插入学生数：2插入学生数据：学号姓名分数5王小红798陈红953、程序运行结果程序运行后显示菜

17、单：学生成绩治理1、登记成绩2、查询成绩3、插入成绩4、删除程序0、退出程序 请输入选择的功能号： 在菜单的提示下做如下操作： 1 选择功能项 1；登记成绩.可按测试数据输入,或自拟. 2 选择功能项 2；查询成绩.输入学号 2,显示如下：学号姓名分数2李平85 3选择功能项 3；插入成绩.输入待插入的人数及插入学生的信息. 4选择功能项 4；输入学号 2,显示：己删除！ 5在做插入或删除操作后,应随时选择功能 2 查看操作是否成功4、小结、体会.三、?链表的应用一?实验二 求两个一元多项式之和或P70页实习题1题一实验目的 掌握单链表的各种根本操作,包括单链表的建立和查找.二实验内容与要求1

18、 、用单链表存储一元多项式,将两个存储一元多项式的单链表相加产生结果 单链表.2、假设要求用户按幂从大到小次序输入各结点,并且没有两个结点具有相 同幂,这样一个一元多项式的链表是按幂 expn 从大到小顺序排列的.将这 两个有序单链表pa和pb按幕expn值相加得到一个新的有序单链表.三算法1 、数据类型定义结点存储结构定义为：struct polynodeint coef;系数int expn;幂struct polynode *next;2、操作算法1建立单链表算法struct polynode *create int a,n,i=1;struct polynode *head,*s,*p

19、;coutvv输入一元多项式(以0, 0标志结束)：n；coutvv要求：1.按幕从大到小次序输入各结点n；cout<<2.没有两个结点具有相同的幂 n；head=new polynode；head->next=NULL；p=head；doprintf(第%d 次->系数,幕：,i+);scanf(“%d,%d,&a,&n)；if(a!=0|n!=0)s=new polynode；s->coef=a； s->expn=n；s->next=NULL；p->next=s； p=s；while(a!=0|n!=0)；cout<&l

20、t;n；return(head)；显示由head指向的一个一元多项式算法void display(struct polynode *head) 同学们自己写 ( 3) 两个一元多项式相加算法struct polynode *addpoly(struct polynode *pa, struct polynode *pb) int n；struct polynode *pc,*s,*p；pa=pa->next； pb=pb->next；pc=new polynode； pc->next=NULL； p=pc；while(pa!=NULL&&pb!=NULL)同学

21、们自己写.return(pc);(4)主函数main( ) struct polynode *poly1,*poly2,*poly3;coutvv建立第一个一元多项式=>n;poly1=create( );cout«建立第二个一元多项式=>n;poly2=create( );poly3=addpoly(poly1,poly2);coutvv第一个一元多项式为：n；display(poly1);coutvv第二个一元多项式为：n；display(poly2)；coutvv相加后一元多项式为：n；display(poly3)；(四) 调试程序并给出实验结果1、给出两个一元多项

22、式：323x3+2x2-5x+632-2x3-2x2+5x+42、请同学们写出程序执行过程和显示结果并分析程序3、小结、体会.四、?链表的应用二?实验三一实验目的 掌握单链表的各种根本操作,包括单链表的建立和查找.二实验内容与要求1、设计一个算法,将以单链表作存储结构实现线性表的就地逆置,即在原来 的存储空间中将线性表ai,a2,a3,an逆置为&,an-i,an-2,.ai.2、设计一个算法,采用单链表作存储结构,实现将X 插入到一个有序从小到大排序的线性表的适当位置上,并保持线性表有序性.三算法同学们自己写 要求：1、写出完整的程序：建立单链表算法、显示单链表算法、操作算法、主 函

23、数.2、调试程序并写出程序执行过程3、分析程序并小结、体会.五、?栈的应用?实验四 判断一个数是否是回文数一实验目的 掌握栈的特点即先进后出的原那么及其根本操作,包括入栈、退栈与栈空判断 等.二实验内容与要求1、将用户输入的数以单链表方式存储.2、问题描述 从头扫描该单链表,将前面的一半元素入栈,假设元素总个数 为奇数,那么跳过中间的哪个元素,然后开始循环：边退栈边在单 链表中后移指针,假设当前栈顶元素与单链表中当前结点的值域不 相等,那么推出循环.最后如果栈空且链表比拟完毕,那么是回文数, 否那么不是回文数.三算法1、数据类型定义 结点存储结构定义为： struct node char da

24、ta;struct node *next;2、操作算法(1) 输入一个回文数,建立字符串的单链表算法(2) 判断是否是回文数算法. int ishs(struct node *head,int n) char stackMAXCHAR/2;struct node *p=head;int top=0;.同学们补充完整 3、主函数 main( ) char sMAXCHAR;struct node *head=NULL,*p,*q;int i=0;coutvv输入一个回文数：；scanf(“%s,s);while(si!= '0') 建立字符串的单链表,请同学们自己写. . if(

25、ishs(head ,i)pri ntf( s 是回文数 n,s);else printf(s不是回文数 n,s);(四) 调试程序并给出实验结果1、判别两个数 1234567890987654321和 123456789是否是回文数.2、程序执行过程如下：请同学们给出.3、分析程序并小结、体会.六、?队列的应用?实验五实验目的1、掌握队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用.2、掌握队列的特点,即先进先出的原那么.3、掌握队列的根本运算,如入队与出队等运算在顺序存储结构和链式存储结构上的实现.二实验内容与要求1、建立顺序存储循环队列,输入 N 个整型数据,编写与此结构相应的

26、入队与 出队算法,编写计算队列长度算法并显示该队列.2、假设以带头结点的循环链表表示队列,并且只设一个指向队尾元素结点, 建立顺序链式存储循环队列,输入 N 个字符型数据,编写相应的队列入队和出 队的算法,并显示该队列.3、程序运行结果：请同学们写出.4、分析程序并小结、体会七、?串的应用?实验 -六 求两个串的最长公共子串一实验目的 掌握顺序串的根本操作.二实验内容与要求1、采用顺序存储结构用户输入的两个串,输出这两个串的最长公共子串2、问题描述先给最长公共子串的下标 index 和长度 maxlen 均赋值为 0.设s=aoaia/,t= bobibm,扫描串s,对于当前字符a,扫描t,

27、假设bj=a,计算它们其后相同字符的个数,并赋给leng假设leng>maxlen,说明它是当前最长公共子串,那么index=i,然后继续扫描t,直到t完毕.当t完毕后,又继续 扫描s,直到s完毕.这样s串中从index开始的 maxlen个字符构成的串便是 最长子串.三算法1、数据类型定义struct strchar vecMAXCHAR;int len;2、操作算法(1) 找最长公共子串算法void maxcomstr(struct str *s, struct str *t) 补充完整,s->vec,t->vec)；printf( n字符串s'和's&#

28、39;的最长公共子串: for(i=0;i<maxlen;i+)printf( “%c,s->vecindex+i); (2)主函数 main( )3、程序#include<stdio.h> #include< iostream.h > #include<string.h.> #define MAXCHAR 30struct strchar vecMAXCHAR;int len; 找最长公共子串算法 void main( ) struct str *r,*r1;r=new str; r1= new str;coutvv输入第一个字符串：； san

29、f(“%s,r->vec);r->len=strlen(r->vec)； coutvv输入第二个字符串：； sanf(“%s,r1->vec)； r1->len=strlen(r1->vec)； maxcomstr(r,r1)；(二) 实验结果1、求两个串ababcabcdabcde和Xyabcdxy的最长公共子串2、程序执行过程：请同学们写出3、分析程序并给出小结、体会.八、?二叉树的三种遍历?实验七一实验目的1 、掌握链式存储方式下二叉树结点数据结构.2、掌握前序二叉树的创立二叉树算法.3、掌握二叉树前序遍历、中序遍历、后序遍历的递归算法.二实验内容与要

30、求1 、问题描述 1 采用链式存储方式,动态指针变量方法建立一棵给定的二叉树同学自 己给定,根据其前序遍历的顺序输入结点值,遍历过程遇到空子树时,必须使 用#代替.2二叉树前序遍历、中序遍历、后序遍历的递归算法实现.三操作算法1 、数据类型定义struct nodechar data;struct node *lchild,*rchild;2、操作算法前序遍历的顺序输入结点值建立二叉树以代替空子树算法struct node *set补充完整前序遍历递归算法void perorder(struct node *p) 同学自己写 中序遍历递归算法void inorder(struct node *

31、p) 同学自己写 后序遍历递归算法void postorder(struct node *p) 同学自己写 按树状打印二叉树算法Void display(struct node *p,int n) 补充完整3、完整的算法#include<stdio.h>#include< iostream.h >struct nodechar data;struct node *lchild,*rchild;前序遍历的顺序输入结点值建立二叉树(以 代替空子树)算法 前序遍历递归算法中序遍历递归算法后序遍历递归算法 按树状打印二叉树算法 void main()struct node *b

32、; int x;cout<<" 输入字符 :"<<endl;b=set();perorder(b);inrorder(b);postorder(b);cin>>x;displayb,x四实验结果1、画出一棵二叉树并采用前序遍历的顺序输入结点值.2、测试数据： ABDEFGC<CR>写出程序运行的结果 :测试数据： abcdefg<CR> 写出程序运行的结果并画出该二叉树 : 测试数据： abdefgc<CR> 写出程序运行的结果并画出该二叉树 :3、小结、体会.九?二叉树的应用一?实验八 设计一个表示家

33、谱的二叉树一实验目的1、进一步掌握指针变量、动态变量的含义.2、掌握二叉树的结构特征,以及各种存储结构的特点及适应范围.3、掌握用指针类型描述、访问和处理二叉树的运算.二实验内容与要求1、问题描述采用一棵链式存储结构二叉树表示一个家谱关系, 对于给定的父亲显示所有的 儿子.由于家谱为树形,但不是一棵二叉树, 所以在存储时要转换二叉树形式. 规定： 一个父亲结点的左子树根结点表示母亲结点, 母亲结点的右子树表示他们的所有 儿子.这样就将家谱树转换成二叉树了,对于二叉树的操作是比拟容易实现的.三算法1、数据类型定义struct treenodechar name10;struct treenode

34、 *left,*right;2、操作算法(1) 建立家谱二叉树(以 #结尾)算法struct treenode *craetree()int contin=1;int first=1;/int n;int m;int i;char xm10;struct treenode *btree,*s,*t,*p;cout«endlvv"建立一个家谱二叉树(以#结尾)：n"«endl; while(contin)if(first=1)btree=new treenode;coutvv"姓名："cin>>btree->name;

35、 btree->right=NULL;s=new treenode;coutvv"妻子："；cin>>s->name; s->right=s->left=NULL; btree->left=s; first=0;else coutvv"父亲："cin>>xm; 或 gets(xm);或 /scanf("%s",&xm);if(strcmp(xm,"#")=0)contin=0; else p=findfather(btree,xm);if(p!=NULL

36、)p=p->left; if(p=NULL)coutvv"不能有儿子,由于没有妻子"<<endl;else while(p->right!=NULL)p=p->right; s=new treenode; s->right=NULL; p->right=s;coutvv"儿子："cin>>s->name;/gets(s->name); coutvv"儿妻："cin>>xm; if(strcmp(xm," ")!=0)t=new treen

37、ode;strcpy(t->name,xm); t->left=t->right=NULL;s->left=t;else s->left=NULL;else cout<<" 不存在这样的父亲结点！ "<<endl;return(btree);(2) 找父亲结点算法struct treenode *findfather(struct treenode *p,char xm) 补充完整 (3) 显示家谱凹入表示法算法void disptree(struct treenode *bt) struct treenode *sta

38、ckMAXSIZE,*p;int levelMAXSIZE2,top,n,i,width=4;if(bt!=NULL)cout<<" 家谱凹入表示法 "<<endl;top=1;stacktop=bt;leveltop0=width; while(top>0)p=stacktop;n=leveltop0;for(i=1;i<=n;i+) printf(" "); printf("%6s",p->name);for(i=n+1;i<=MAXWIDTH-6;i+=2) printf(&quo

39、t;-"); printf("n"); top-;if(p->right!=NULL)top+;stacktop=p->right;leveltop0=n+width;leveltop1=2;if(p->left!=NULL) top+; stacktop=p->left; leveltop0=n+width; leveltop1=2;(4) 查找指定父亲的所有儿子算法void findson(struct treenode *bt) 补充完整 3、完整算法#include<stdio.h>#include< iostre

40、am.h >#include<string.h.>#define MAXSIZE 30#define MAXWIDTH 40struct treenodechar name10;struct treenode *left,*right;找父亲结点算法建立家谱二叉树算法显示家谱凹入表示法算法 查找指定父亲的所有儿子算法 void main( ) struct treenode *bt;bt=creatree( );disptree(bt);findson(bt);6、 实验结果1) 画出一个家谱关系树并转换为二叉树.2) 输入家谱关系树元素并查找“张德所有儿子. (设有父亲张德

41、) 测试数据 姓名：张德 CR 妻子：陈氏 CR 父亲：张德 CR 儿子：张文 CR 儿妻：刘氏 CR 父亲：张德 CR 儿子：张武 CR 儿妻：王氏 CR 父亲：张文 CR 儿子：张兵 CR 儿妻：李氏 CR 父亲：张文 CR 儿子：张强 CR儿妻：CR父亲：张武 CR儿子：张华 CR儿妻： CR父亲： # CR3) 调试程序并写出运算过程、画出树形结构、小结、体会.十、?二叉树的应用二?实验九 借助二叉树实现排序一实验目的1、进一步掌握指针变量、动态变量的含义.2、掌握二叉树的结构特征,以及各种存储结构的特点及适应范围.3、掌握用指针类型描述、访问和处理二叉树的运算.二实验内容与要求1、问

42、题描述1对于给定的 N 个关键字值,采用二叉排序树方法对其进行排序.2算法输入： N 个关键值.3算法输出：排序结果.4算法要点：采用建立二叉排序树的方法,将N 个关键值为结点值,生成一棵二叉排序树.对生成的二叉排序树进行中序遍历,得到递增序列.三算法1、数据类型定义struct treenodeint data;struct treenode *lchild,*rchild;2、操作算法二叉排序树的插入算法 在二叉排序树上插入关键值为 K 的结点,假设二叉树为空, 那么插入结点 为新结点,否那么根据 K 的大小插入到 *t 的左子树(或右子树)中. struct treenode *inse

43、rt(struct treenode *t, int x) 补充完整 建立二叉排序树算法struct treenode *create( ) struct treenode *t;int x; t=NULL;coutvv输入一组正整数(以-1作为结束标志)：<<endl; .补充完 中序遍历二叉排序树算法void inorder(struct treenode *t) 同学们自己编写 3、完整算法#include<stdio.h>#include< iostream.h >#include<stdlib.h.>#define NULL 0stru

44、ct treenode int data;struct treenode *lchild,*rchild;算法清单void main( )struct treenode *root; root= create( );cout« 排序结果： <<e ndl;inorder(root);4、测试数据输入 3 9 2 8 5 6 1-1注意：为了防止出现单枝树,不要输入有序序列5、写出程序运行结果并画出该二叉排序树、小结、体会.十一、?二叉树的静态链表?实验一实验目的1、掌握静态二叉链式存储方式下二叉树结点数据结构.2、掌握后序二叉树的创立和扩展后序序列输入创立二叉树算法.3、

45、掌握二叉树前序遍历、中序遍历、后序遍历的递归算法.二实验内容与要求1、问题描述1采用链式存储方式,静态指针变量方法建立一棵给定的二叉树同学自 己给定,根据扩展后序序列输入结点值,遍历过程遇到空子树时,必须使用 # 代替.根本思想：读入扩展后序序列,从左往右检测每一个符号,如果是#,那么将空地址压入栈中； 如果是字母, 那么首先为新结点分配存储空间, 将读入的字母 存入新结点的数值字段中； 然后从栈顶弹出两个元素, 分别作为新结点的右孩子 指针和左孩子指针,最后将新结点压入栈中.2二叉树前序遍历、中序遍历、后序遍历的递归算法实现.三操作算法1、数据类型定义struct nodechar data

46、;itn lchild, rchild;struct node treeN+1;int root;2、操作算法( 1)“扩展后序序列“插入表示空子树(以 #代替空子树) ( 以 表示结束 )的符 号值建立二叉树算法int settree( )int sN+1;int t=0,i=0;char c;coutvv请输入结点值(以#代替空子树,以表示结束)：vvendl;cin>>c;while(c!= '')if(c= '#')s+t=0;elsei+;treei.data=c;treei.rchild=st; treei.lchild=st-1;st-

47、1=i;t-;cin>>c;return(i);(2)前序遍历递归算法void perorder(int p)if(p>0)coutvvtreep.data;perorder(treep.lchild); perorder(treep.rchild);(3) 中序遍历递归算法void inorder(int p) 同学自己写 (4) 后序遍历递归算法void postorder(int p) 同学自己写 3、程序#define N 20#include<stdio.h>#include< iostream.h >struct nodechar data

48、;int lchild, rchild;struct node treeN+1;int root;“扩展后序序列“插入表示空子树 (以#代替空子树)(以表示结束 )的符号值建 立二叉树算法；前序遍历递归算法；中序遍历递归算法；后序遍历递归算法；void main()int root;coutvv"输入字符:"<<endl; root=settree( );perorder(root); inrorder(root);postorder(root);(四) 实验结果1、画出一棵二叉树并采用 “扩展后序序列“插入表示空子树 (以#代替空子树) 的符号序列.2、测试数

49、据： #ji#fed#hg#cb#a<CR> 写出程序运行的结果 :测试数据： #db#e#fca<CR>写出程序运行的结果 :测试数据： #dc#b#g#fea<CR>写出程序运行的结果 :2、写出程序运行的结果.3、小结、体会.十二、?图的应用一?实验十一实验目的1、掌握图的根本存储方法.2、掌握图的两种搜索路径的遍历方法.二实验内容与要求1、问题描述采用邻接矩阵实现图的深度优先遍历和广度优先遍历三操作算法1、数据类型定义#define MAXVEX 100struct vertexint num;char data;struct graphstruct

50、 vertex vexsMAXVEX;int edgesMAXVEX MAXVEX;2、操作算法1创立一个有向图的邻接矩阵算法struct graph creatgraphint *n 补充完整 (2) 显示邻接矩阵表示图算法void dispgraph(struct graph adj, int n) int i,j,k;printf( “n 显示邻接矩阵表示图： n);for(i=1;i<=n;i+) for(j=1;j<=n;j+) printf( “(%c,%c):%dn,adj.vexsi.data,adj.vexsj.data, adj.edgesij);3、完整算法#

51、define MAXVEX 100 #include<stdio.h> #include< iostream.h > struct vertexint num;char data;struct graphstruct vertex vexsMAXVEX;int edgesMAXVEX MAXVEX; 创立一个有向图的邻接矩阵算法； 显示邻接矩阵表示图算法；void main( ) struct graph adj;int n;adj= creatgraph(&n); dispgraph(adj, n);(三)实验结果1、测试数据：顶点数(n)和边数(e):5,7

52、 <CR> 第1个顶点的信息： a <CR> 第 2个顶点的信息： b <CR>第 3 个顶点的信息： c<CR>第 4 个顶点的信息： d<CR>第 5 个顶点的信息： e<CR>第1条边=> 起点：a终点：b权值：1<CR>第2条边=> 起点： a 终点: c 权值: 2<CR>第3条边=> 起点： c 终点： e 权值： 3<CR>第4条边=> 起点： b 终点： d 权值： 4<CR>第5条边=> 起点： b 终点： e 权值： 5<

53、;CR>第6条边=> 起点： a 终点： d 权值： 6<CR> 第7条边=> 起点： e 终点： d 权值： 7<CR>2、写出程序运行的结果并画出该图 ：3、分析程序并写出小结、体会.十三、?图得应用二?实验十一一实验目的1、掌握图的根本存储方法.2、掌握图的两种搜索路径的遍历方法.二实验内容与要求1、问题描述采用邻接表实现图的深度优先遍历和广度优先遍历三操作算法1、数据类型定义#define MAXVEX 30struct edgenodeint adjvex;char data;struct edgenode *next;struct vexn

54、odechar data;struct edgenode *link;struct vexnode adjlistMAXVEX;2、操作算法(1) 创立一个无向图的邻接表算法 void creagraph(struct vexnode g,int *n) 补充完整 (2) 显示邻接表表示图算法 void dispgraph(struct vexnode g, int n) int i;struct edgenode *p;cout«图的邻接表表示如下： <<e ndl;for(i=1;i<=n;i+) printf( “%d,%c=>,i,gi.data);p

55、=gi.link;while(p!=NULL) printf(%d,%c ,p->adjvex,p->data);p=p->next;coutvv <<e ndl; (3) 深度优先搜索递归算法void dfs(struct vexnode adj, int v, int visited) 补充完整 (4) 宽度优先搜索递归算法int queueMAXVEX;void bfs(struct vexnode adj, int vi, int visited) 补充完整3、完整的算法 #define MAXVEX 30#include<stdio.h> #include< iostream.h >struct edgenodeint adjvex;char data; struc