数据结构2实验指导书

《数据结构2实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构2-C语言版》实验指导书（第3版）姓名：学号：班级：商务班指导教师：石林山东建筑大学商学院电子商务教研室2010年3月一、买验13的：掌握串的存储结构，以及对其的各种操作。二、实验内容：实现串的模式匹配算法。三、实验步骤：1、编程：参考程序。intIndex_KMP(SStringS,SStringT,int*next){intij；i=l；j=l；while(i<=S[O]&&j<=T[O]){if(j==0IIS[i]==TU]){++i；++j；}elsej=nextlj];}if(j>T[O])

2、returni-T[O];elsereturn0;}2、调试所编辑的程序。3、运行结果。4、存盘。四、注意事项：1、next函数的实现voidget_next(SStringS,int*next)mtij;i=l;next[l]=O;j=0;while(i

3、的各种操作。二、实验内容：实现二叉树的建立、遍历算法。三、实验步骤：1编程：参考程序。节点结构:TypedefstructBiTNode{intdata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;先序遍历：BiTreeCreatBiTree(){BiTreeT;scanf(&ch);if(ch=0)T=NULL;else{T=(BiTNode*)malloc(sizeof((BiTNode));T->data=ch;/*生成根结点*/T->lchild=Creat

4、BiTree();/*构造左子树*/T->rchild=CreatBiTree();/*构造右子树*/}return(T);}2、调试所编辑的程序。3、运行结果。4、存盘。四、注意事项：1、掌握二叉树的递归定义和递归操作特点。五、思考题1、阐述二义树的5个基本性质。2、阐述二叉树的三种遍历方法。实验3图的应用一、实验H的：掌握图的存储结构，以及对其进行的各种操作。二、实验内容：深度优先遍历图。三、实验步骤：1、编程：参考程序图的邻接表类型定义structnode〃边(弧)结点的类型定义{intvertex;〃边(

5、弧)的另一顶点的在数组中的位置structnode*link;//指向下一，条边(弧)结点的指针};typedefstructNODE；NODEadjlist[MAXJ;//邻接点链表的头指针所对应的数组辅助数组intvisit[MAX];〃顶点标志数组，全局变虽NODE*ptr[MAX];〃顶点链表指针数组建立无向邻接表intcreate(NODE*adjlist[]){NODE*p;intnum,i,vl,v2;scanfC<%d,&num);〃读入结点数for(i=0;i

6、系图{adjlist[i].link=NULL;adjlist[i].vertex=i;}for(;；){scanf(“％dto%d",&vl,&v2);〃读入一条边if(vl<0IIv2<0)break;//数据输入的终止条件p=(NODE*)malloc(sizeof(NODE));p->vertex=v2;p->link=adjlist[vl].link;adjlist[vl].link=p;//插入在链表首部p=(NODE*)malloc(sizeof(NODE));p・>vertex=v1;p->l

7、ink=adjlist[v2].link;adjlist[v2].link=p;}return(num);//返回图的结点数}voiddepthfirst(NODEadjlist[],intnum){inti;for(i=0;i

8、dfs(intv){intw;printf(“％d,",v);visit[v]=l;〃访问此结点while(ptr[v]!=NULL){w=ptr[v]->vertex;取结点的邻接顶点wif(visit[w]==0;)dfs(w);ptr[vj=ptr[v]->link;//记住顶点v的邻接顶点位置，}该邻接点在wZ后}调用深度优先遍历算法的主函数main(){NODE