98数据结构实验报告

本科实验报告课程名称：数据结构实验项目：线性表树图查找排序实验地点：专业班级：学号：学生姓名：指导教师：年月日实验名称实验一线性表实验目的和要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。实验内容1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。2．用单链表ha存储多项式A（x）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb存储多项式B（x）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x）=A（x）+B（x），结果存到单链表hc中。试写出程序。3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。主要仪器设备台式或笔记本计算机实验记录(可分栏或加页)#includestdio.h#includestdlib.h#includemalloc.hstructnode{charinfo;structnode*llink,*rlink;};typedefstructnodeNODE;NODE*creat(){charx;NODE*p;scanf(%c,&x);printf(%c,x);if(x!='.'){p=(NODE*)malloc(sizeof(NODE));p-info=x;p-llink=creat();p-rlink=creat();}elsep=NULL;returnp;}voidcountleaf(NODE*t,int&count){if(t){if((!t-llink)&&(!t-rlink))count++;countleaf(t-llink,count);countleaf(t-rlink,count);}}intmain(){inte=0;NODE*T;printf(qingshuruerchashu);T=creat();printf(\n);countleaf(T,e);printf(%d\n,e);system(PAUSE);}实验结果:#includestdio.h#includemalloc.htypedefstructdxs{inta;structdxs*next;}Dxs,*Dxss;voidStructure(Dxsshead,intn);voidShow(Dxsshead);voidAdd(Dxsshead1,Dxsshead2,Dxsshead3);voidfrees(Dxsshead);voidmain(){Dxssha,hb,hc;intn;ha=(Dxss)malloc(sizeof(Dxs));hb=(Dxss)malloc(sizeof(Dxs));hc=(Dxss)malloc(sizeof(Dxs));printf(请输入多项式1的项数\n);scanf(%d,&n);Structure(ha,n);printf(请输入多项式2的项数\n);scanf(%d,&n);Structure(hb,n);Add(ha,hb,hc);printf(多项式HC的式子是\n);Show(hc);frees(ha);frees(hb);frees(hc);printf(\n\n);}voidStructure(Dxsshead,intn){Dxssp,q;inta;printf(请输入要录入系统的多项式的系数，从次数较小的开始\n);p=head;do{scanf(%d,&a);q=(Dxss)malloc(sizeof(Dxs));q-a=a;p-next=q;q-next=NULL;p=q;}while(--n);}voidShow(Dxsshead){intm=0;Dxssp;p=head-next;while(p!=NULL){printf(%d*X^%d,p-a,m++);p=p-next;if(p!=NULL)printf(+);}printf(n);}voidAdd(Dxsshead1,Dxsshead2,Dxsshead3){Dxssp,q,l,m;p=head1-next;q=head2-next;l=head3;while((p!=NULL)&&(q!=NULL)){m=(Dxss)malloc(sizeof(Dxs));m-a=p-a;l-next=m;l=m;p=p-next;}l-next=NULL;}voidfrees(Dxsshead){Dxssp,q;p=head;while(p!=NULL){q=p;p=p-next;free(q);}}实验结果:心得：通过这次试验让我认识到了要注意细节，否则很容易出错实验名称实验二树实验目的和要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。实验内容[问题描述]任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。[输入]一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I..G..。[输出]若为空二叉树，则输出：THISISAEMPTYBINARYTREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。[存储结构]采用二叉链表存储。实习题1编写递归算法，计算二叉树中叶子结点的数目。2．编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。3．将上述例题用非递归程序实现。主要仪器设备台式或笔记本计算机实验记录(可分栏或加页)#includestdio.h#includestdlib.h#includemalloc.hintcount=0;structnode{charinfo;structnode*llink,*rlink;};typedefstructnodeNODE;NODE*creat(){charx;NODE*p;scanf(%c,&x);printf(%c,x);if(x!='.'){p=(NODE*)malloc(sizeof(NODE));p-info=x;p-llink=creat();p-rlink=creat();}elsep=NULL;returnp;}voidrun(NODE*t){if(t){run(t-llink);run(t-rlink);printf(%c,t-info);if(((t-llink)=NULL)&&((t-rlink)=NULL))count++;}}voidmain(){NODE*T;printf(qingshuruerchashu:\n);T=creat();printf(\n);if(!T)printf(Thisisaemptybinarytree);else{printf(Theresultofposttraveseis:\n);run(T);}printf(总共有叶子结点数%d,count);printf(\n);}实验结果:心得：树是数据结构非常重要的部分，要很好地掌握实验名称实验三图实验目的和要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。实验内容采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。主要仪器设备台式或笔记本计算机实验记录#includestdio.h#includemalloc.hintn;structVNode{intposition;structVNode*next;};structArcNode{intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w){structVNode*L;w-mark=1;L=w-first;while(L!=NULL){if((v+(L-position))-mark==0){DFS(v,(v+L-position));}L=L-next;}}intmain(){inti,j,k;intnum=0;structArcNode*p;structVNode*temp;structVNode*flag;printf(\n请输入顶点个数n:);scanf(%d,&n);while(n1){printf(你输入的值不合理，请重新输入:\n);scanf(%d,&n);}p=(structArcNode*)malloc(n*sizeof(structArcNode));for(i=0;in;i++){printf(\n请输入以V%d为弧尾的所有弧，并以-1结束输入\n,i+1);scanf(%d,&k);if(k==-1){p[i].mark=0;p[i].first=NULL;}else{temp=(structVNode*)malloc(sizeof(structVNode));temp-position=k;temp-next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf(%d,&k);while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp-position=k;temp-next=NULL;flag-next=temp;flag=temp;scanf(%d,&k);}}}i=0;while(p[i].mark==0){DFS(p,(p+i));num++;i=0;while(p[i].mark!=0&&in){i++;}}printf(此图的连通分量个数为：%d\n,num);system(pause);return0;}实验结果:心得：图比较复杂，要注意算法的复杂度，减少程序代码实验名称实验四查找实验目的和要求:实验内容主要仪器设备台式或笔记本计算机实验记录(可分栏或加页)#includestdio.htypedefstruct{inta[30];intlength;}sqtable;sqtablest;intb=0;voidcreatest(intk){inti;printf(Pleaseinputdata:);st.a[0]=-100;for(i=1;(!b&&(i=k));i++){scanf(%d,&(st.a[i]));if(st.a[i]st.a[i-1]){printf(Inputdataerror.\n);b=1;}}if(!b){st.length=k;printf(Thetableisbuilted.\n);}}intstfind(sqtablest,intl,inth,inty){intm;while(l=h){m=(l+h)/2;if(y==st.a[m]);returnm;elseif(yst.a[m])returnstfind(st,l,m-1,y);elsereturnstfind(st,m+1,h,y);}}main(){intn,x,l,h,s;l=1;h=st.length;printf(\nPleaseinputn:);scanf(%d,&n);createst(n);h=st.length;if(b==0){printf(Pleaseinputyouwantfindvalue:);scanf(%d,&x);s=stfind(st,l,h,x);}printf(Find%dinposition%d.\n,x,s);}实验结果:心得：本次试验让我明白了查