数据结构上机实验源代码

1、数据结构上机实验源代码栈的应用十进制数转换为八进制数，逆序输出所输入的数实验代码：/stack.h,头文件classstackpublic:stack();boolempty()const;boolfull()const;error_codegettop(elementtype&x)const;error_codepush(constelementtypex);error_codepop();private:intcount;elementtypedatamaxlen;stack:stack()count=0;boolstack:empty()constreturncount=0;boolst

2、ack:full()constreturncount=maxlen;error_codestack:gettop(elementtype&x)constif(empty()returnunderflow;elsex=datacount-l;returnsuccess;errorcodestack:push(constelementtypex)if(full()returnoverflow;datacount=x;count+;returnsuccess;errorcodestack:pop()if(empty()returnunderflow;count；returnsuccess;主程序#i

3、ncludeenumerror_codeoverflow,underflowsuccess;typedefintelementtype;constintmaxlen=20;#include,stack.hMvoidread_write()逆序输出所输入的数stacks;inti;intn,x;coutHpleaseinputnumintn:;cinn;for(i=l;i二n;i+)coutHpleaseinputanum:;cinx;s.push(x);while(!s.empty()s.gettop(x);coutxspop();coutendl;voidDec_to_Ocx(intn)十进

4、制转换为八进制stacksi;intmod,x;while(n!=0)mod=n%8;sl.push(mod);n二n/B;coutHtheocxofthedecis:;while(!sl.empty()sl.gettop(x);coutx;sl.pop();coutendl;voidmain()intn;/read_write();coutHpleaseinputadec:;cinn;Dec_to_Ocx(n);队列的应用打印n行杨辉三角实验代码：/queue.hclassqueuepublic:queue()count=0;front=rear=0;boolempty()returncou

5、nt=0;boolfull()returncount=maxlenl;error_codeget_front(elementtype&x)if(empty()returnunderflow;x=data(front+l)%maxlen;returnsuccess;error_codeappend(constelementtypex)if(full()returnoverflow;rear=(rear+l)%maxlen;datarear=x;count+;returnsuccess;error_codeserve()if(empty()returnunderflow;front=(front+

6、l)%maxlen;count-;returnsuccess;privatesntcount;intfront;intrear;intdatamaxlen;；主程序#includeenumerror_codeoverfIow,underflow,success;typedefintelementtype;constintmaxlen二20;打印前n行的杨辉三角#include,打印前n行的杨辉三角voidout_number(intn)intsl，s2;inti;intj;intk;queueq;for(i=l;i=(n-l)*2;i+)coutcoutlendl;q.append(l);fo

7、r(i=2;i二n;i+)sl=0;for(k=l;k=(n-i)*2;k+)coutfor(j=l;j=i-l;j+)q.get_front(s2);q.serve();coutsl+s2Hq.append(sl+s2);sl=s2;coutlMencll;q.append(l);voidmain()intn;coutpleaseinputn:;cinn;out_number(n);单链表实验实验目的：实验目的理解线性表的链式存储结构。熟练掌握动态链表结构及有关算法的设计。根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。实验任务说明1：本次实验中的链表结构均为带头结点的单

8、链表。说明2：为使实验程序简洁直观，卞面的部分实验程序中将所需要的函数以调用库函数的形式给出，并假设将库函数放在程序文件“linklist.h”中，同时假设该库函数文件中定义了链表结构中的指针类型为link,结点类型为node,并定义了部分常用运算。例如构建链表、以某种方式显示链表、从文件中读入一个链表、跟踪访问链表结点等。各运算的名称较为直观，并有相应的注释，因而易于理解和实现。读者在上机实验时，需要自己设计出所涉及到的库函数，或者将函数放在实验程序中，以方便实验程序的调试。如时间紧的话，也可到作者的网站下载以供参考(不完全相同)。编写算法实现下列问题的求解。求链表中第i个结点的指针(函数)

9、，若不存在，则返回NULL。实验测试数据基本要求：第一组数据：链表长度n10,i分别为5,n,0,n+1,n+2第二组数据：链表长度n=0,i分别为0,2在第i个结点前插入值为x的结点。实验测试数据基本要求：第一组数据：链表长度n10,x=100,i分别为5,n,n+l,0,l,n+2第二组数据：链表长度n=0,x=100,i=5删除链表中第i个元素结点。实验测试数据基本要求：第一组数据：链表长度n10,i分别为5,n,l,n+l,0第二组数据：链表长度n=0,i=5在一个递增有序的链表L中插入一个值为x的元素，并保持其递増有序特性。实验测试数据基本要求：链表元素为(10,20,30,40,5

10、0,60,70,80,90)00),x分别为25,85,110和8将单链表L中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据基本要求：第一组数据：链表元素为(1,2,3,4,5,6,7,8,9,10,20,30,40,50,60)第二组数据：链表元素为(10,20,30,40,50,60,70,80,90,100)求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验测试数据基本要求：第一组第一个链表元素为(1,3,6,10,15,16,17,18,19,20)第二个链

11、表元素为(1,2,3,4,5,6,7,8,9,10,18,20,30)第二组第一个链表元素为(1,3,6,10,15,16,17,18,19,20)第二个链表元素为(2,4,5,7,8,9,12,22)第三组第一个链表元素为()第二个链表元素为(1,2,3,4,5,6,7,8,9,10)实验代码：/linklist.henumerror_codearrange_errocnull,success;typedefstructnodeelementtypedata;structnode才next;node;classlistprivate:node*head;intcount;public:lis

12、t()链表的初始化head=newnode;head-next=NULL;count=0;intlength()求链表的长度returncount;取链表中第i个节却的扌取链表中第i个节却的扌*node*locate(constinti)node*p=head;intj=0;if(ilength()returnNULL;while(p!=NULL)讦(j=i)returnp;p=p-next;j+；returnNULL;*在第i节点之前插入数为error_codeinsert(constinti,constelementtypex)node*p=head;intj=0;while(j!=i-l

13、&p!=NULL)p=p-next;j+；if(icount+l)coutdata=x;snext=p-next;pnext=s;count+;cout插入成功!endl;returnsuccess;删除第i个节点error_codedelete_element(constinti)node*p=head;intj=0;while(j!=i-l&p!=NULL)p=p-next;j+;if(ilength()cout此元素不存ffiendl;returnarrange_error;node*u=p-next;pnext=u-next;count-;deleteu;cout,删除成功tcendl

14、;returnsuccess;/*若原链表递增，插入一个元素保持其递增的顺序*/error_codeinsertl(constelementtypex)node*p=head-next;if(head-next-datax)nodeSunewnode;u-data=x;unext=head-next;head-next=u;returnsuccess;while(p-next!=NULL)if(p-next-datax)node*u=newnode;u-data=x;unext=p-next;pnext=u;returnsuccess;p=p-next;node*u=newnode;u-dat

15、a=x;unext二NULL;pnext=u;returnsuccess;取链表头结点的地址node*gethead()returnhead;输出链表中的所有元素error_codeprint()node*p=head-next;while(p!=NULL)coutp-dataHp=p-next;coutendl;returnsuccess;error_codedepart()lista;listb;node*pa=a.gethead();node*pb=b.gethead();node*p=head-next;while(p!=NULL)if(p-data)%2=l)node*u=newno

16、de;u-data=p-data;pa-next=u;pa=u;pa-next=NULL;if(p-data)%2=0)node承u二newnode;u-data=p-data;pbnext=u;pb=u;pb-next=NULL;p=p-next;cout“链表所有的奇数项为：“endl;print();coutH链表所有的偶数项为：next;pb=b.gethead()-next;rc=c.gethead();while(pa!=NULL&pb!二NULL)if(pa-datadata)pa=pa-next;elseif(pa-datapb-data)pb=pb-next;elseu=ne

17、wnode;u-data=pa-data;onext=u;rc=u;count+;pa=pa-next;pb=pb-next;rc-next=NULL;cout两链表中的公共元素为：endl;c.print();/主程序#includetypedefintelementtype;#include,linklist.h,voidmain()lista;listb;listc;intm;intn;intj;inti;intchoice;elementtypetemp;docoutnO,实验结束endl;coutl,实验要求lendl;cout2,实验要求2endl;cout3,实验要求3endl;

18、cout4,实验要求4endl;cout5,实验要求5endl;coutn6,实验要去6Hendl;coutchoice;switch(choice)case0:cout实验结束endl;break;case1:/*实验要求case1:/*实验要求1cout请输入a链表的长度:endl;cinm;for(j=l;jtemp;a.insert。,temp);coutiW输入i的值endl;cini;if(a.locate(i)!=NULL)cout链表第idataendl;elsecout,NULL,endl;coutiW输入i的值endl;cini;if(a.locate(i)!=NULL)c

19、out链表第idataendl;elsecoutn;for(j=0;jdataendl;elsecout“链表第n+j”个元素的值为:NULLHendl;break;case2:/实验要求2case2:/cout%青输入a链表的长度:uendl;cinm;for(j=l;jtemp;a.insert。,temp);cout谓输入x的值:Mendl;cintemp;for(j=l;j=3;j+)cout请输入插入点的位置：endl;cini;a.insert(i,temp);cout谓输入n的值endl;cinn;for(j=0;j3;j+)a.insert(n+j,temp);break;ca

20、se3:/*实验要求3case3:/*cout%青输入a链表的长度:endl;for(j=l;j=m;j+)coutniw输入元素的值”temp;a.insert。,temp);intnl;cout“请输入要删除的元素的位置“endl;cini;a.delete_element(i);cout请输入n的值endl;cinn;a.delete_element(n);nl=n+l;cout“请输入要删除的元素的位置“endl;cini;a.delete_element(i);cout删除n+l位置的元素endl;a.delete_element(nl);cout“请输入要删除的元素的位置“endl

21、;cini;a.delete_element(i);break;case4:/*实验要求4coutH请输入a链表的长度：“endl;cinm;for(j=l;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);coutM表未插入前的，其中的只有：Hendl;a.print();for(j=l;j=4;j+)cout请输入要插入的元素x的值：temp;a.insertl(temp);cout插入后链表中的值为：nendl;a.print();break;case5：/*实验要求5cout请输入a链表的长度:uendl;cinm;for(j=l;jtemp;a.inse

22、rt。,temp);a.depart();break;cout请输入a链表的长度:uendl;cinm;for(j=l;jtemp;a.insert(j,temp);coutH请输入链表的长度:Hendl;cinm;for(j=l;jtemp;b.insert(j,temp);erset(b,c);cout链表中的元素有：next=Head;Head-prior=Head;count=0;DLinkList:DLinkList()/析构函数,释放链表所占空间Node*p,*q;while(q-next!=Head)q=q-next;/定位q到尾结点？while(Head!=Head-

23、next)从头结点开始，依次释放结点p=Head;Head=Head-next;qnext=Head;Head-prior=q;deletep;count；Head=NULL;/头结点指向空voidDLinkList:CreateList(intn)尾插法(正序)创建具有n个元素的双循环链表Node*p,*s;设置工作指针。p指向尾结点p=Head;cout请依次输An个元素值:endl;for(inti=l;idata;/输入新建数据元素值s-next=p-next;/新结点链入表尾pnext=s;s-prior=p;Head-prior=s;P=s；count+;voidDLinkList

24、:ListDisplay()显示链表Node*p;p=Head-next;inti=l;while(p!=Head)couti,t,1;coutp-dataendl;p=p-next;i+；voidDLinkList:symmetry()Node*p,*s;inti;p=Head-next;s=Head-prior;for(i=l;idata!=s-data)cout链表不对Hendl;break;p=p-next;s=s-prior;if(i=count/2+l)cout链表对称endl;主程序#include/coutzcintypedefintT;#includedLinklisthvo

25、idmain()主函数inti;DLinkListL;/intchoice;do/显示主菜单coutl-创建双循环链表n;cout2-判断链表是否对称n“;cout3-显示链表n;cout4-退出n;coutHEnterchoice:1;cinchoice;switch(choice)case1:/创建链表cout请输入要创建的链表中元素个数:“;cini;将创建的链表中数据元素的个数coutendl;L.CreateList(i);break;case2:/判断链表是否为空L.symmetry();break;case3:/显示表L.ListDisplay();coutendl;break;

26、case4:/退出cout结束运行”endl;break;default:/coutHlnvalidchoicen;break;while(choice!=4);结束二叉树的试验试验要求:二叉树的构建,二叉树的前序，中序，后序遍历算法,查找替换树中的节点，交换一棵树的左右子树试验代码：#includeenumerror_codesuccess;typedefcharelementtype;typedefstructbnodeelementtypedata;structbnode*lchild,*rchild;bnode,*bitree;classbitreprivate:bnode*root;

27、voidcreate(bitree&T);inthigh(bnode*T);voidpreorder(bnode*T);/先序遍历voidinorder(bnode*T);中序遍历voidpostorder(bnode*T);后序遍历public:bnode*getroot()returnroot;voidcreate()create(root);inthigh()returnhigh(root);voidpreorder()preorder(root);/先序遍历voidinorder()inorder(root);/中序遍历voidpostorder()postorder(root);/后

28、序遍历voidsearch(bnode*T,char&num,bitree&m);查找voidjhuan(bnode*T,char&num,char&temp);/替换voidjbitree(bnode*Tchar&num);/交换一个节点的左右子树;voidbitre:jbitree(bnode*7；char&num)交换一个节点的左右子树if(T!二NULL)if(T-data=二num)bnode*temp;temp=T-lchild;T-lchild=T-rchild;prchild=temp;jbitree(lchilcLnum);jbitree(T-rchild,num);void

29、bitre:jhuan(bnode*T,char&num,char&temp)替换树中的元素if(T!二NULL)if(T-data=num)T-data=temp;coutn交换成功Hendl;jhuan(lchildum,temp);jhuan(Trchild,numztemp);voidbitre:search(bnode*l；char&num,bitree&m)查找元素并返回该元素的地址if仃!=NULL)if(T-data=num)m=T;search(lchild,num,m);search(rchild,nurrLm);intmax(intm,intn)求最人值return(m=

30、n)?m:n;intbitre:high(bnode*T)if(T=NULL)return0;elsereturnmax(high(T-lchild),high(T-rchild)+l;创建一颗二叉树创建一颗二叉树voidbitre:create(bitree&T)charx;cinx;if(x=,.1)T=NULL;elseT=newbnode;T-data=x;create(T-Ichild);create(T-rchild);voidbitre:preorder(bnode*T)if(T!二NULL)coutT-data;preorder(T-lchild);preorder(T-rch

31、ild);voidbitre:inorder(bnode*T)if(T!二NULL)inorder(T-lchild);coutT-data;inorder(Trchild);voidbitre:postorder(bnode*T)if(T!=NULL)postorderCPlchild);postorderCPrchild);coutT-data;voidmain()charch;chardh;bitret;bitreea;cout请按先序序列输入二叉树中元素的值endl;t.create();cout树的先序序列为endl;t.preorder();coutendl;coutH树的中序序列

32、为endl;t.inorder();coutendl;cout树的后序序列为endl;t.postorder();coutendl;coutch;t.search(t.getroot(),ch,a);couta-dataendl;cout请先后输入待交换的元素与交换的元素endl;cinch;cindh;t.jhuan(tgetroot()，ch,dh);cout请输入待交换节点的元素值endl;cinch;t.jbitree(t.getroot()zch);t.preorder();coutendl;图的试验试验要求：图的构建，实现图的深度遍历算法与广度遍历算法，以及图的有关操作试验代码：/

33、*单链队歹U*/linkqueue.h#ifndefLINKNODE#defineLINKNODEtemplatestructLinkNodeTdata;LinkNode*next;；templateclassLinkedQueuefprotected:LinkNode*front;LinkNode*rear;intlength;public:LinkedQueue();LinkedQueue();voidClearQueue();boollsEmpty()const;intGetLength()const;LinkNode*GetHead()const;/返回对头元素boolEnQueue(

34、T&elem);boolDeQueue(T&receive);boolQueueTraverse(bool(*Visit)(T&elem);templateLinkedQueue:LinkedQueue()front=newLinkNode;if(!front)return;rear=front;front-next=false;length=O;templateLinkedQueue:LinkedQueue()ClearQueue();deletefront;templatevoidLinkedQueue:ClearQueue()/从队头清到队尾LinkNode*temp=front-nex

35、t;while(frontnext)front-next=temp-next;deletetemp;temp=front-next;rear=front;length=O;templateboolLinkedQueue:lsEmpty()constreturn(front=rear)?true:false;templateintLinkedQueue:GetLength()constreturnlength;templateLinkNode*LinkedQueue:GetHead()constreturnfront;templateboolLinkedQueue:EnQueue(T&elem)

36、LinkNode*temp=newLinkNode;if(!temp)returnfalse;temp-data=elem;temp-next=false;rear-next=temp;rear=temp;+length;returntrue;templateboolLinkedQueue:DeQueue(T&receive)if(front=rear)returnfalse;LinkNode*temp=front-next;指向队头元素receive=temp-data;front-next=temp-next;deletetemp;if(!frontnext)rear=front;leng

37、th;returntrue;templateboolLinkedQueue:QueueTraverse(bool(*Visit)仃&elem)/从队头到队尾进行一次遍历LinkNode*temp=frontnext;while(temp)if(!Visit(temp-data)returnfalse;temp=temp-next;returntrue;#endif主程序/数组表示法#includeiostream#includestring#include,iomanipM#include”LinkQueue.husingnamespacestd;#defineMAX_VERTEX_NUM20

38、/最人顶点数constintinfinity=INT_MAX;structArcCellintadj;对无权图有1,0表示是否相邻，对带权图，则为权值类型char*info;/该弧的相关信息；templatestruct_MGraphTvexsMAX_VERTEX_NUM;/顶点表ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵，即边表intvexnum;顶点数intarcnum;/边数intkind;/是以邻接矩阵存储的图类型;templateclassMGraph_MGraphmgraph;boolvisitedMAX_VERTEX_NUM;pub

39、lic:intLocateVex(Tu);的位置TGetVex(intindex);index的顶点voidPutVex(Tv,Tvalue);接点的序号若无领接点则返回空intNextAdjVex(Tv,Tw);intFirstAdjVex(Tv);图存在，图中存在顶点u则返回该顶点在图中图存在，index是图中某个顶点的序号则返回图存在，v是，v是G中某个顶点返回v的第一个临图存在，v是图中某个顶点则对v赋值value图存在图中某个顶点，w是V的邻接点返回V的相对于w的下一个邻接点的序号若w是v的最后一个邻接点则返回空boolCreateUDG();voidDFS(intindex);bo

40、ol(*VisitFunc)(Tv);voidDisPlay();构造无向图从第index出发递归的深度优先遍历图访问顶点V的方式输出邻接矩阵boolDFSTraverse(bool(*visit)(Tv);图存在,对图进行深度优先遍历boolBFSTraverse(bool(*visit)(Tv);图存在，对图进行广度优先遍历；templateboolvisit(Tv)coutvreturntrue;templateTMGraph:GetVex(intindex)/okif(index=mgraph.vexnum)returnfalse;/越界返回空returnmgraph.vexsinde

41、x;templatevoidMGraph:PutVex(Tv,Tvalue)/okintindex=LocateVex(v);if(index0)return;mgraph.vexsindex=value;templateboolMGraph:CreatellDG()/ok构造无向图intiJ;Tvlzv2;coutmgraph.vexnummgrapharcnum;cout请输入各个顶点:for(i=O;imgraph.vexsi;for(i=O;imgraph.vexnum;i+)初始化邻接矩阵for(j=O;jmgraph.vexnum;j+)mgraph.arcsij.adj=0;mg

42、=false;for(i=0;imgraph.arcnum;i+)构造邻接矩阵cout-请输入一条边依附的两个顶点:“；cinvlv2;intm=LocateVex(vl);intn=LocateVex(v2);mgraph.arcsmn.adj=1;/mgraph.arcsnm.adj=1;/mgraph.kind=2;returntrue;templateintMGraph:LocateVex(Tu)/okfor(inti=0;iMAX_VERTEX_NUM;i+)if(u=mgraph.vexsi)returni;returntemplateintMGra

43、ph:FirstAdjVex(Tv)/okinttemp=LocateVex(v);intj=0;if(mgraph.kind=l11mgraph.kind=3)j=infinity;for(inti=0;imgraph.vexnum;i+)if(mgraph.arcstempi.adj!=j)returni;return-1;/无邻接点返回空templateintMGraph:NextAdjVex(Tv,Tw)/okintid_v=LocateVex(v);intid_w=LocateVex(w);intj=0;if(mgraph.kind=l11mgraph.kind=3)j=infini

44、ty;for(inti=id_w+l;imgraph.vexnum;i+)if(mgraph.arcsid_vi.adj!=j)returni;return-1;templatevoidMGraph:DisPlay()inti,j;chargraphkind7;chararckind3;switch(mgraph.kind)caseO:strcpy(graphkind/有向图);strcpy(arckindz弧”)；break;casel:strcpy(graphkind有向网”)；strcpyfarckind/弧”)；break;case2:strcpy(graphkind/1无向图”)；s

45、trcpyfarckind/1边);break;case3:strcpy(graphkind/无向网);strcpy(arckind/边,)；break;,arckind的coutmgraph.vex,arckind的graphkindendl;输出顶点cout顶点为；for(i=O;imgraph.vexnum;i+)coutmgraph.vexsi输出权值的邻接矩阵cout“权值的邻接矩阵为:endl;for(i=O;imgraph.vexnum;i+)for(j=O;jmgraph.vexnum;j+)if(mgraph.arcsij.adj=infinity)coutsetw(5)8”t；elsecoutsetw(5)mgraph.arcsij.adj,t,;couten