数据结构算法c实现

数据结构算法实现计算机科学与技术系TOC\o"1-5"\h\z\o"CurrentDocument"算法一学会简单开发与程序调式 1\o"CurrentDocument"算法二线性表操作 3\o"CurrentDocument"算法三 单链表操作 7\o"CurrentDocument"算法四栈基本操作 13\o"CurrentDocument"算法五表达式求值 18\o"CurrentDocument"算法六 队列操作 24\o"CurrentDocument"算法七 稀疏矩阵运算 27\o"CurrentDocument"算法八 广义表操作 30\o"CurrentDocument"算法九 二叉树操作 33\o"CurrentDocument"算法十 二叉排序树的操作 39\o"CurrentDocument"算法H图的操作 45\o"CurrentDocument"算法十二 排序操作 63\o"CurrentDocument"算法十三 查找操作 67\o"CurrentDocument"算法十四 哈希表操作 69算法一学会简单开发与程序调式1、目的熟悉C或C++集成开发环境的基本命令及功能键，熟悉常用功能菜单命令理解C或C++程序结构理解函数声明、定义和调用方法理解标准库函数、自定义函数掌握参数的不同传送方式及作用2、要求学习如何根据编译信息，定位语法错误将警告与错误一律看作错误学习C或C++程序书写风格写出上机调试后的体会3、内容(1)编程实现输出一组数的最大值(或最小值)参考程序如下：#include<iostream.h>constintn=10;voidmain(){inti,x,a[n];cout«ninputin10num:**;fbr(i=0;ivn;i++)cin»a[i];x=a[0];i=l；while(i<n){if(a[i]>x)x=a[i];i++；cout«M10nummaxis:"«x«endl;(2)阅读下列程序，体会参数传递的变化，并上机调试。#include<iostream.h>#include<iomanip.h>voidfiinl(inta,intb);voidfun2(int&a,int&b);voidfun3(int*a,int*b);voidmain()intx=5,y=10;cout«nanzhichuansong:"«endl;cout«,'main:H«setw(10)«,,x=,,«setw(3)«x«setw(10)<<My=M«setw(3)«y«endl;funl(x,y);cout«Hmain:H«setw(10)<<Hx=,,«setw(3)«x«setw(10)«My=M«setw(3)«y«endl;cout«endl;cout«nyyong:H«endl;cout«"main:H«setw(10)«nx=H«setw(3)«x«setw(10)«My=n«setw(3)«y«endl;fim2(x,y);cout«"main:M«setw(10)<<nx="«setw(3)«x«setw(10)«My=M«setw(3)«y«endl;cout«endl;cout«nzhizhen:M«endl;cout«nmain:H«setw(10)«,'x=,,«setw(3)«x«setw(10)«Hy=,'«setw(3)«y«endl;fiin3(&x,&y);cout«Hmain:H«setw(10)«Hx=,,«setw(3)«x«setw(10)<<Hy=M«setw(3)«y«endl;cout«endl;)voidfun1(inta,intb){a=a+b;b=2*a+3*b;cout«Mfunl:M«setw(l0)«na=,,«setw(3)«a«setw(10)«Mb=M«setw(3)«b«endl;}voidfiin2(int&a,int&b)a=a+b;b=2*a+3*b;cout«Hfun2:n«setw(10)<<na="«setw(3)«a«setw(10)«Mb=M«setw(3)«b«endl;}voidfun3(int*pa,int*pb)♦pa+=*pb;*pb-=l;cout«Hfun3:M«setw(10)«n*Pa=,,«setw(3)«*pa«setw(l0)<<H*pb=H«setw(3)«*pb«endl;算法二顺性表操作1、目的会定义线性表的顺序存储类型掌握线性表的基本运算和具体函数的定义2、要求编写对线性表的建立、插入、删除、查找等算法，并判断插入、删除的位置是否合法。认真编写源程序，并进行调试，写出输入、输出和溢出判断结果写出上机调试后的体会3、内容编写线性表的顺序存储结构上的：初始化线性表、清空线性表、求线性表的长度、判空、判满、查找、插入、删除、线性表的有序输出等算法。参考程序如下：#include<iostream.h>#include<stdlib.h>typedefintelemtype;structlist{elemtype*list;intlen;intmaxsize;);voidinitlist(list&l,intms){l.list=newelemtype[ms];if(!l.list){cerr«Mmemoryallocationfailure!M«endl;exit(l);)l.len=0;Lmaxsize=ms;}voidclearlist(list&1){l.len=0;}intlength(list&1){returnLien;}intlistempty(list&1){returnl.len=0;}intlistfull(list&1){returnl.len=l.maxsize;}voidlooklist(list&1){for(inti=0;i<l.Ien;i+4-)coutvvl.list[i]vv-;cout«endl;)intfindlist(list&l,elemtypex){fbr(inti=O;i<l.len;i-H-)ifi(l.list[i]==x){x=Llist[i];return1;}return0;intinsertlist(list&l,elemtypex,intk){if(listfull(l))return0;ififk>0){fbr(inti=l.len-l;i>=0;i-)l.list[i+l]=Llist[i];l.list[0]=x;)elseif(k<0)l.list[l.len]=x;else{for(inti=0;i<l.len;i++)if(x<l.list[i])break;fbr(intj=l.len-l;j>=ij-)l.Ust[j+l]=l.list|j];l.list[i]=x;)l.len++;return1;)intdeletelist(Iist&l,elemtype&x,intk){if(listempty(l))return0;if(k>0){x=l.list[0];fbr(inti=l;i<l.len;i-H-)l.list[i-l]=l.list[i];}elseif(k<0)x=l.list[l.len-l];else{fbr(inti=0;i<I.len;i++)if(l.list[i]=x)break;if(i>=l.len)return0;elsex=Llist[i];fbr(intj=i+l;j<Llen;j++)l.len—;return1;voidoutputlist(list&l,intm){int*b=newint[l.len];inti,k;fbr(i=O;i<l.len;i-H-)b[i]=i;fbr(i=l;i<l.len;i-l-+){k=i-l;fbr(intj=i;j<l.len;j-H-){if(m=l&&l.list[b[j]]<l.list[b[k]])k=j;if(m!=l&&l.list[b|j]]>l.list[b[k]])k=j;}ifi(k!=i-l){intx=b[i-l];b[i-l]=b[k];b[k]=x;}}fbr(i=O;i<LIen;i-H-)cout«l.list[b[i]]«'tcout«endl;)voidmain(){constintml=20;lista;initlist(a,ml);inti;elemtypex;cout«ninput5intnum:"；for(i=0;i<5;i++){cin»x;insertlist(a,x,-l)；}cout«ninput2intnum:";cin»x;insertlist(a,x,1);cin»x;insertlist(a,x,1);looklist(a);cout«nupordersort:"；outputlist(a,l);cout«ndownordersort:"；outputlist(a,0);listb;initlist(b,ml);for(i=O;i<a.len;i-H-)insertlist(b,a.list[i],O);looklist(b);if(deletelist(a,x,l))cout«'*deletefront!M«endl;elsecout«Hdeletefale!"«endl;looklist(a);if{deletelist(a,x,-l))cout«"deleterear!H«endl;elsecout«Hdeletefale!*'«endl;looklist(a);cout«"inputadelnum:"；cin»x;if|deletelist(a,x,O))cout«'*deletesuccess!M«endl;elsecout«"deletefale!H«endl;looklist(a);算法三单链表操作1、目的会定义单链表的结点类型掌握对单链表的一些基本操作和具体函数的定义充分利用C或C++语言的特点，提高程序的可移植性2、要求编写对单链表的初始化、插入、删除、查找等算法。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试运行分析及功能。3、内容编写单链表：初始化单链表、清空单链表、求单链表的长度、判空、查找、插入、删除、线性表的有序输出等算法。参考程序如下：#include<iostream.h>#include<stdlib.h>typedefintelemtype;structInode{elemtypedata;Inode*next;)；voidinitlist(lnode*&hl){Inode*p=newInode;p->next=NULL;hl=p;hl->next=NULL;voidclearlist(Inode*&hl){Inode*p,*q;p=hl->next;while(p!=NULL){q=p->next;deletep;p=q;}hl->next=NULL;intlissize(lnode*hl){inti=0;Inode*p=hl->next;while(p!=NULL){i"；p=p->next;returni;}intlistempty(lnode*hl){returnhl->next=NULL;)elemtypegetelem(Inode*hl,inti){{cerr«"posisoutrange!"«endl;exit(1);)Inode*p=hl->next;intj=O;while(p!=NULL){j++；if(j=i)break;p=p->next;)ifi(p=NULL){cerr«nposisoutrange!H«endl;exit(l);)return(p->data);)voidinsertrear(Inode*hl,elemtypex){Inode*q=newInode;q->data=x;q->next=NULL;Inode*p=hl;while(p->next!=NULL)p=p->next;p->next=q;)voidlooklist(lnode*hl){Inode*p=hl->next;while(p!=NULL){cout«p->data«np=p->next;)cout«endl;)intfindlist(lnode*hl,elemtype&x){Inode*p=hl->next;while(p!=NULL)if(p->data=x){x=p->data;return1;)elsep=p->next;return0;voidinsertlist(lnode*hl,elemtypex,inti){{cerr«nposisoutrange!M«endl;exit(l);)Inode*p,*q;intj=O;P=hl;while(p->next!=NULL)if(j=i)break;p=p->next;}if(j==i){q=newInode;q->data=x;q->next=p->next;p->next=q;}else{cerr«Hposisoutrange!H«endl;exit(l);voiddeletelist(lnode*hl,inti){Inode*p=hl;intj=O;while(p->next!=NULL&&j<i-1){p=p->next;j++；}if(j>i-l||p->next=NULL){cerr«,'error!M«endl;exit(1);)Inode*q=p->next;p->next=q->next;deleteq;voidsortlist(Inode*hl,intk){Inode*head=newInode;head->next=NULL;head->data=hl->next->data;fbr(lnode*p=hl->next->next;p;p=p->next){Inode*q=newInode;q->data=p->data;Inode*cp=head;Inode*ap=NULL;while(cp){if(k=l){ifl(q->data<cp->data)break;else{ap=cp;cp=cp->next;}}else{ifi(q->data>cp->data)break;else{ap=cp;cp=cp->next;})}ifi[ap=NULL){q->next=head;head=q;}else{q->next=cp;ap->next=q;})Inode*r=newInode;r->next=head;head=r;looklist(head);clearlist(head);)voidmain(){Inode*hl;initlist(hl);inti;elemtypex;cout«ninputin5num:"；fbr(i=O；i<5;i++){cin»x;insertrear(hl,x);)cout«Hinput2num:";cin»x;insertlist(hl,x,1);cin»x;insertlist(hl,x,l);looklist(hl);sortlist(hl,l);sortlist(hl,0);算法四栈基本操作1、目的：掌握栈的存储表示方式和栈基本操作的实现方法2、要求：栈的基本操作实现方法，栈的应用3、内容：栈的实现栈的顺序存储。#include<stdio.h>#include<malloc.h>#include<conio.h>defineERROR0defineTRUE1defineFALSE0defineOK1defineEQUAL1//defineOVERFLOW-1defineSTACK_INIT_SIZE100defineSTACKINCREMENT10typedefintStatus;structSTU{charname[20];charstuno[10];intage;intscore;);typedefstructSTUSElemType;structSTACK{SElemType*base;SElemType*top;intstacksize;)；typedefstructSTACKSqStack;typedefstructSTACK*pSqstack;StatusInitStack(SqStack**S);StatusDestroyStack(SqStack*S);StatusClearStack(SqStack*S);StatusStackEmpty(SqStackS);intStackLength(SqStackS);StatusGetTop(SqStackS,SElemType*e);StatusPush(SqStack*S,SElemTypee);StatusPop(SqStack*S,SElemType*e);StatusStackTraverse(SqStackS,Status(*visit)());StatusInitStack(SqStack**S)((*S)=(SqStack*)malloc(sizeof(SqStack));(*S)->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S)->base)exit(OVERFLOW);(*S)->top=(*S)->base;(*S)->stacksize=STACK_INIT_SIZE;returnOK;StatusDestroyStack(SqStack*S)free(S->base);free(S);}StatusClearStack(SqStack*S){S->top=S->base;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;intStackLength(SqStackS)(一inti;SElemType*p;i=0;p=S.top;while(p!=S.base){p++;i++；StatusGetTop(SqStackS,SElemType*e)(if(S.top==S.base)returnERROR;*e=*(S.top-l);returnOK;}ifl(S->top-S->base>=S->stacksize)S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S->base)exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;)*/*(S->top++)=e;returnOK;)StatusPop(SqStack*S,SElemType*e)(if(S->top==S->base)returnERROR;*e=*-S->top;returnOK;}StatusStackPrintElem(SElemType*e){printfi[n%s%s%d%d\nM,e->name,e->stuno,e->age,e->score);}StatusStackTraverse(SqStackS,Status(*visit)())(while(S.top!=S.base)visit(—S.top);}main(){SElemTypee;SqStack*Sa;clrscr();printfifn\n\n SqStackDemoisrunning... \n\nH);printf(nFirstisPushfunction.\nn);InitStack(&Sa);strcpy(,nstu1")；strcpy(e.stuno,nl00001")；e.age=80;e.score=1000;printff'NowStackisEmpty.\nM);StackTraverse(*Sa,StackPrintElem);Push(Sa,e);printR”NowStackhasoneelement.\nM);StackTraverse(*Sa,StackPrintElem);strcpy(,nstu3n);strcpy(e.stuno,nl00002”)；e.age=80;e.score=1000;Push(Sa,e);printf(nNowStackhasanotherelement.\nn);StackTraverse(*Sa,StackPrintElem);prints"NowPopStack,thetopelemputintovariablee.\nn);Pop(Sa,&e);printftM%s\n%s\n%d\n%d\n,,,,e.stuno,e.age,e.score);print""Let'sseetheleftofStack'selem:\nn);StackTraverse(*Sa,StackPrintElem);getch();printf(n\n\n\nWelcomtovisit\n\nH);算法五表达式求值1、目的熟悉栈的定义和栈的基本操作熟悉每一种栈操作的函数实现熟悉把中缀算术表达式转换为后缀表达式的算法熟悉进行后缀表达式求值的算法2、要求编写对栈操作的函数(栈初始化、清空栈、入栈、出栈等)算法，若采用的是顺序栈存储结构入栈时要对栈满进行处理。注意类型定义。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试后的体会3、内容输入一个以@结尾的中缀算术表达式，转换成后缀算术表达式，进行计算并显示结果。参考程序如下：#include<iostream.h>#include<stdlib.h>#include<ctype.h>#include<PROCESS.H>#include<STRSTREAM.H>typedeffloatelemtype;structstack{elemtype*stack;shorttop;shortstackmaxsize;);staticvoidinitstack(stack&s,intms){s.stack=newelemtype[ms];if(!s.stack){cerr«,,memoryfull!M«endl;exit(l);)s.top=-l;s.stackmaxsize=ms;}staticvoidclearstack(stack&s){s.top=-l;}staticvoiddeletestack(stack&s){delete[]s.stack;s.top=-l;s.stackmaxsize=O;staticintstackempty(stack&s){returns.top==-l;}staticelemtypepeek(stack&s){if(s.top=-l){cerr«"stackempty!*'«endl;exit(l);)returns.stack[s.top];staticvoidpush(stack&s,elemtypeitim){ifi(s.top==s.stackmaxsize-1)cerr«Hstackovflw!H«endI;exit(1);)s.top++;s.stack[s.top]=itim;staticelemtypepop(stack&s)if{s.top==-l){cerr«Mstackempty!M«endl;exit(l);s.top—;returns.stack[s.top+l];staticintstackfull(stack&s){returns.top>==s.stackmaxsize-1;intprecedence(charop){switch(op){case'+1:case*-*:return1;case***:case'/1:return2;case'。：case*@*:default:return0;staticfloatcompute(char*str)typedeffloatelemtype;intsm=20;stacks;initstack(s,sm);istrstreamins(str);charch;floatx;ins»ch;while(ch!=,@,){switch(ch)(case'+':x=pop(s)+pop(s);break;case-1:x=pop(s);x=pop(s)-x;break;case*:x=pop(s)*pop(s);break;case'/':x=pop(s);if(x!=0)x=pop(s)/x;else{cerr«"divideby0!M«endl;exit(l);)break;default:ins.putback(ch);ins»x;}push(s,x);ins»ch;)// x=pop(s);// returnx;ifi(!stackempty(s)){X=pop(s);iR!stackempty(s)){cerr«Hexpressionerror!n«endl;exit(l);))else{cerr«Hstackisempty!H«endl;exit(l);)returnx;staticvoidchange(char*s1,char*s2){typedefcharelemtype;intms=20;stackr;initstack(r,ms);push(r；@');intij;i=0;j=0；charch=sl[i];while(ch!-@*){if(ch=-)ch=sl[-H-i];elseif(ch—(1){push(r,ch);ch=sl[-H-i];}elseifCch=7){while(peek(r)!=©s2[j++]=pop(r);pop(r);ch=sl[-H-i];elseif(ch=,+,||ch=,-,||ch=,*|||ch=7,){charw=peek(r);while(precedence(w)>=precedence(ch)){s2[j++]=w;pop(r)；w=peek(r);}push(r,ch);ch=sl[-H-i];)else{while(isdigit(ch)||ch—.*){s2[j-H-]=ch;ch=sl[-H-i];)S2[j++]=r；))ch=pop(r);while(ch!=,@,){if(ch=©{cerr«Mexpressionerror!n«endl;exit(1);}else{s2[j-H-]=ch;ch=pop(r);))S2Lj++]='@';s2U++]=W;voidmain()chara[50],b[50];cout«Minputin@end:H«endl;cin.getline(a,sizeofi(a));change(a,b);cout«Hduiyingdehouzhuibiaodashi:H«endl;cout«b«endl;cout«nqiuzhijieguoshi:H«compute(b)«endl;算法六队列操作1、目的熟悉队列的定义和队列的基本操作熟悉队列的顺序存储结构和链式存储结构函数实现，以便在实际问题背景下的灵活运用。掌握各种存储结构的队列类型定义2、要求编写对队列操作的函数（队列初始化、清空队列、入队、出队等）算法，若采用的是顺序存储结构入队时要对队满进行处理，注意链队操作处理（带附加表头结点还是不带附加表头结点）。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试后的体会3、内容建立一个队列，对该队列进行一系列（入队、出队等）操作后，体现出该队列的变化,注意循环队列的输出。参考程序如下：#include<iostream.h>#include<stdlib.h>constintmaxsize=50;typedefintelemtype;structqueue{elemtypequeue[maxsize];intfront,rear;}；voidinitqueue（queue&q）{q.front=q.rear=0;voidclearqueue(queue&q){q.front=q.rear=0;intqueueempty(queue&q)]returnq.front==q.rear;}elemtypeqfront(queue&q){ifi(q.front==q.rear){cerr«Mqueueisempty!n«en(il;exit(l);}returnq.queue[(q.front+l)%maxsize];}voidqinsert(queue&q,elemtypex){intk=(q.rear+1)%maxsize;ifi(k=q.front){cerr«nqueueoverflowe!**«endl;exit(l);}q.rear=k;q.queue[k]=x;elemtypeqdelete(queue&q)ifi(q.front==q.rear){cerr«”queueisempty!,,«endl;exit(l);}q.front=(q.front+l)%maxsize;returnq.queue[q.front];intqueuefull(queue&q)return(q.rear+-1)%maxsize==q.front;)intqueuesize(queue&q){return(q.rear-q.front)%maxsize;}voidlookqueue(queue&q){if(q.front==q.rear){cerr«,'queueisempty!n«endl;exit(l);)intk=(q.front+l)%maxsize;while(l){cout«q.queue[k]«M”；if(k=q.rear)break;k=(k+1)%maxsize;}cout«endl;}voidmain(){queueq;initqueue(q);for(inti=0;i<6;i++)iintx=rand()%100;inty=rand()%100;if(!queuefull(q)){qinsert(q,x)；cout«x«Minqueue,”；if(!queuefull(q)){qinsert(q,y);cout«y«Minqueue1,;)cout«endl;cout«"queuesizeis:n«queuesize(q)«endl;cout«qdelete(q)«noutqueuen«endl;cout«"queuesizeis:"«queuesize(q)«endl;}cout«endl;lookqueue(q);while(!queueempty(q)){cout«qdelete(q)«endl;cout«Hqueuesizeis:"«queuesize(q)«endl;算法七稀疏矩阵运算1、目的熟悉稀疏矩阵的定义和三元组表示及存储类型定义熟悉稀疏矩阵的顺序存储结构和每一种链式存储结构。掌握对稀疏矩阵的各种运及相应的算法描述2、要求编写对稀疏矩阵操作的函数（稀疏矩阵初始化、稀疏矩阵的输入、稀疏矩阵的输出、稀疏矩阵的转置等）算法。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试后的体会3、内容实对稀疏矩阵的转置，并显示结果。参考程序如下：#include<iostream.h>constintsmax=50;typedefintelemtype;structtriple{intij;elemtypev;structsmatrix{intm,n,t;triplesm[smax+l];voidinitmatrix(smatrix&M){M.m=M.n=0;M.t=0;)voidinputmatrix(smatrix&M,intm,intn){M.m=m;M.n=n;introw,col;elemtypeval;intk=0;cin»row»col»val;while(row!=0){k++;M.sm[k].i=row;M.sm[k].j=col;M.sm[k].v=val;cin»row»col»val;)M.t=k;)voidoutputmatrix(smatrix&M)(cout«'C；fbr(int{cout«V«M.sm[i].i«7;cout«M.sm[i].j«7;coutvvM.sm[i].vvv)W?；}ifi(M.t!=O){coutvv'('vvM.sm[M.t].ivv',';cout«M.sm[M.t].j«7;coutwM.sm[M.t].vw')';}cout«*),«endl;}smatrixtranspose(smatrix&M){smatrixs;initmatrix(s);intm,n,t;m=M.m;n=M.n;t=M.t;s.m=n;s.n=m;s.t=t;if(t==O)returns;intnum[smax+l];intcpot[smax-M];fbr(intcol=l;col<=n;col-H-)num[col]=0;for(intk=l;k<=t;k++)-H-num[M.sm[k].j];cpot[l]=l;fbr(col=2;col<=n;col+4-)cpot[col]=cpot[col-1]+num[col-l];fbr(intp=l;p<=t;p++){col=M.sm[p].j;intq=cpot[col];s.sm[q].i=M.sm[p].j;s.sm[q].j=M.sm[p].i;s.sm[q].v=M.sm[p].v;++cpot[col];returns;voidmain(){smatrixM;intm,n;initmatrix(M);cout«MinputM,N:M«endl;cin»m»n;inputmatrix(M,m,n);cout«Mm=,,«M.m«7;cout«Mn=H«M.n«7；cout«nt=n«M.t«endl;outputmatrix(M);cout«Mm=,,«M,m«7;cout«Mn=M«M.n«7;cout«Mt=M«M.t«endl;outputmatrix(transpose(M));算法八广义表操作1、目的熟悉广义表的定义和及存储类型定义熟悉广义表的链式存储结构。掌握广义表的各种运及相应的算法描述2、要求编写对广义表操作的函数（广义表初始化、广义表的长度、广义表的深度、广义表的建立、广义表的输出等）算法。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试后的体会3、内容首先建立一广义表的存储结构，接着输出该广义表，然后求出该广义表的长度、深度。参考程序如下：#include<iostream.h>#include<stdlib.h>typedefcharelemtype;structglnode{inttag;union{elemtypedata;glnode*sublist;}；glnode*next;)；intlenth(glnode*gl){if(gl!=NULL)return1+lenth(gl->next);elsereturn0;intdepth(glnode*gl)•!intmax=0;while(gl!=NULL){if(gl->tag=l){intdep=depth(g1->sublist);ifi(dep>max)max=dep;}gl=gl->next;}returnmax+1;voidcreate(glnode*&gl){charch;cin»ch;if(ch=W)gl=NULL;elseif(ch='C){gl=newglnode;gl->tag=l;create(gl->sublist);)else{gl=newglnode;gl->tag=0;gl->data=ch;)cin»ch;ifi(gl=NULL)jelseif(ch=7)create(gl->next);elseiR(ch=')')||(ch==';'))gI->next=NULL;)voidprint(glnode*&gl){if(gl->tag=l){coutv〈Cif(gl->sublist=NULL)coutvv'#';elseprint(gl->sublist);coutvv')';}elsecout«gl->data;ifi(gl->next!=NULL){cout«V;print(gl->next);voidmain(){glnode*g;create(g);print(g);cout«endl;cout«ngyblength:"«lenth(g->sublist)«endl;cout«ngybdepth:"«depth(g->sublist)«endl;算法九二叉树操作1、目的熟悉二叉树的结构和对二叉树的基本操作。掌握对二叉树的的每一种操作的实现。学会利用递归的方法编写对二叉树这种递归数据结构进行处理的算法2、要求编写对二叉树的每一种操作的实现的函数（二叉树初始化、二叉树的深度、二叉树的建立、二叉树的输出等）算法。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试后的体会3、实验内容首先定义二叉树的二叉链表存储结构结点的类型，接着建立一棵二叉树（可以采用广义表表示的输入法，也可以采用前根顺序输入法），然后对此二叉树进行操作。参考程序如下：#include<iostream.h>#include<STRSTREAM.H>typedefcharelemtype;structbtreenode{elemtypedata;btreenode*lchild;btreenode*rchild;voidinitbtree(btreenode*&bt){bt=NULL;}voidprecrttree(btreenode*&bt){charch;cin»ch;if(ch=T)bt=NULL;else{bt=newbtreenode;bt->data=ch;precrttree(bt->lchild);precrttree(bt->rchiId);voidcrtbtree(btreenode*&bt,char*a){charch;btreenode*s[20];inttop=-1;bt=NULL;btreenode*p;intk;istrstreamins(a);ins»ch;while(ch!='@'){switch(ch){case'C：top++;s[top]=p;k=l;break;case*),:top—;break;case*/:k=2;break;default:p=newbtreenode;p->data=ch;p->lchild=p->rchild=NULL;if(bt==NULL)bt=p;else{if(k=Ds[top]->lchild=p;elses[top]->rchild=p;)}ins»ch;intbtreeempty(btreenode*bt){returnbt==NULL;}voidpreorder(btreenode*bt){ifi(bt!=NULL){cout«bt->data«Tpreorder(bt->lchild);preorder(bt->rchild);voidinorder(btreenode*bt){if(bt!=NULL){inorder(bt->lchild);cout«bt->data«f\inorder(bt->rchild);voidpostorder(btreenode*bt){ifi[bt!=NULL){postorder(bt->lchild);postorder(bt->rchild);cout«bt->data«Tvoidlevorder(btreenode*bt){btreenode*q[30];intfront=0,rear=0;btreenode*p;iRbt!=NULL){rear=(rear+l)%30;q[rear]=bt;}while(front!=rear){front=(front+1)%30;p=q[front];cout«p->data«f*;if<p->lchild!=NULL){rear=(rear+l)%30;q[rear]=p->lchild;}ifl(p->rchild!=NULL){rear=(rear+1)%30;q[rear]=p->rchild;)))intbtreedepth(btreenode*bt)(if(bt==NULL)return0;else{intdepl=btreedepth(bt->lchild);intdep2=btreedepth(bt->rchild);ifi(depl>dep2)returndepl+1;elsereturndep2+l;intbtreecount(btreenode*bt){if(bt==NULL)return0;elsereturnbtreecount(bt->lchild)+btreecount(bt->rchild)+l;intbtreeleafcount(btreenode*bt){if(bt=NULL)return0;elseif(bt->lchild=NULL&&bt->rchild=NULL)return1;elsereturnbtreeleafcount(bt->lchild)+btreeleafcount(bt->rchild);)voidprintbtree(btreenode*bt){if(bt=NULL)return;else{cout«bt->data;if(bt->lchild!=NULL||bt->rchild!=NULL){cout«,(,；printbtree(bt->Ichild);ifl(bt->rchild!=NULL)cout«\';printbtree(bt->rchild);coutw')';voidclearbtree(btreenode*&bt){if(bt!=NULL){clearbtree(bt->lchild);clearbtree(bt->rchild);deletebt;bt=NULL;))voidmain(){btreenode*bt;initbtree(bt);charb[50];inttag;cout«H1.preordercreatebtree,,«endl;cout«n2.glistcreatebtreen«endl;cout«Hinputselecte1or2:H;cin»tag;ifi(tag=2)(cout«Hinput@endglist:"«endl;cin.getline(b,sizeofi(b));crtbtree(bt,b);}else{cout«ninputpretreeand'#':"vvendl;precrttree(bt);)printbtree(bt);cout«endl;cout«upreorder:M;preorder(bt);cout«endl;cout«"inorder:";inorder(bt);cout«endl;cout«Hpostorder:H;postorder(bt);cout«endl;cout«"levelorder:levorder(bt);cout«endl;cout«nbtreedepthis:";cout«btreedepth(bt)«endl;cout«nbtreenodenumis:";cout«btreecount(bt)«endl;cout«nbtreeleafnodenumis:";cout«btreeleafcount(bt)«endl;clearbtree(bt);算法十二叉排序树的操作1、目的熟悉二叉排序树的结构和二叉搜索树的定义。掌握对二叉排序树的每一种操作的含义和具体实现。会利用递归和非递归的两种方法方法编写对二叉排序树进行查找和插入元素处理的算法2、要求编写对二叉排序树的每一种操作的实现的函数（二叉搜索树初始化、二叉树的查找和插入元素、二叉搜索树删除元素、二叉树的输出等）算法。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试后的体会3、内容首先定义二叉排序树的二叉链表存储结构结点的类型，接着建立一棵二叉排序树，然后对此二叉排序树进行操作（查找和插入元素、二叉排序树删除元素）。参考程序如下：#include<iostream.h>#include<STRSTREAM.H>typedefintelemtype;structbstnode{elemtypedata;bstnode*lchild;bstnode*rchild;voidinitbtree（bstnode*&bst）{bst=NULL;}intbstreeempty(bstnode*bst){returnbst=NULL;}intfind(bstnode*bst,elemtype&x){if(bst=NULL)return0;elseifi(x=bst->data){x=bst->data;return1;}elseif(x<bst->data)returnfind(bst->lchild,x);elsereturnfind(bst->rchild,x);}intupdate(bstnode*bst,elemtypex){if(bst==NULL)return0;elseif{x=bst->data){bst->data=x;return1;}elseif(x<bst->data)returnupdate(bst->lchild,x);elsereturnupdate(bst->rchild,x);voidinsert(bstnode*&bst,elemtypex){if(bst=NULL){bstnode*p=newbstnode;p->data=x;p->lchild=p->rchild=NULL;bst=p;elseif(x<bst->data)insert(bst->lchild,x);elseinsert(bst->rchild,x)；)intdele(bstnode*&bst,elemtypex)(bstnode*t=bst,*s=NULL;while(t!=NULL){if(x=t->data)break;elseif(x<t->data){s=t;t=t->lchild;}else{s=t;t=t->lchild;})ifi(t==NULL)return0;if(t->lchild=NULL&&t->rchild=NULL){ifi(t==bst)bst=NULL;elseif(t=s->lchild)s->lchild=NULL;elses->rchild=NULL;deletet;}elseif(t->lchild==NULL||t->rchild==NULL){if(bst==t){if(t->lchild==NULL)bst=t->rchild;elsebst=t->lchild;)else{ifi(t=s->lchild&&t->lchild!=NULL)s->lchild=t->lchild;elseif(t=s->lchild&&t->rchild!=NULL)s->lchild=t->rchild;elseif(t=s->rchild&&t->lchild!=NULL)s->rchild=t->lchild;elseifi(t==s->rchild&&t->rchild!=NULL)s->rchild=t->rchild;}deletet;)elseif(t->lchild!=NULL&&t->rchild!=NULL){bstnode*p=t,*q=t->lchild;while(q->rchild!=NULL){p=q；q=q->rchild;)t->data=q->data;if(p=t)t->lchild=q->lchild;elsep->rchild=q->lchild;deleteq;)return1;)voidcreatebstree(bstnode*&bst,elemtypea[],intn){bst=NULL;fbr(inti=0;i<n;i++)insert(bst,a[i]);}voidinorder(bstnode*bst){if(bst!=NULL){inorder(bst->lchild);cout«bst->data«**;inorder(bst->rchild);intbstreedepth(bstnode*bst)if(bst=NULL)return0;else{intdepl=bstreedepth(bst->lchild);intdep2=bstreedepth(bst->rchild);if(depl>dep2)returndep1+1;elsereturndep2+l;intbstreecount(bstnode*bst){if<bst=NULL)return0;elsereturnbstreecount(bst->lchild)+bstreecount(bst->rchild)+1;intbstreeleafcount(bstnode*bst){if(bst=NULL)return0;elseif)(bst->lchild=NULL&&bst->rchild=NULL)return1;elsereturnbstreeleafcount(bst->lchild)+bstreeleafcount(bst->rchild);)voidprintbstree(bstnode*bst){if(bst=NULL)return;else{cout«bst->data;if(bst->lchild!=NULL||bst->rchild!=NULL){coutvv'C;printbstree(bst->lchild);if(bst->rchild!=NULL)COUtVV?；printbstree(bst->rchild);coutvv)；)})voidclearbstree(bstnode*&bst){if(bst!=NULL){clearbstree(bst->lchild);clearbstree(bst->rchild);deletebst;bst=NULL;voidmain(){elemtypea[10]={30,50,20,70,25,54,80,23,92,40);bstnode*bst=NULL;createbstree(bst,a,10);cout«Houtputbstree:n«endl;printbstree(bst);cout«endl;cout«ninorderlist:M«endl;inorder(bst);cout«endl;elemtypex;cout«ninputfindisx:”；cin»x;if(find(bst,x))cout«"ok!!!M«endl;elsecout«"fail!!!H«endl;insert(bst,36);dele(bst,30);dele(bst,20);cout«Hopendinorder:H«endl;inorder(bst);cout«endl;cout«nopendglist:M«endl;printbstree(bst);cout«endl;clearbstree(bst);算法十一图的操作1、目的掌握图的基本存储方法；掌握有关图的操作算法并用高级语言实现；熟练掌握图的两种搜索路径的遍历方法、拓扑排序；求最小生成树、关键路径、最短路径等方法。2、要求编写对图的遍历方法、拓扑排序、求最小生成树、关键路径、最短路径等算法。认真编写源程序，并进行调试，写出输入、输出结果写出上机调试运行分析及功能。3、内容图的遍历#include<dos.h>#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>defineMAXVERTEXNUM20〃图的最大顶点数defineMAXQSIZE30〃队列的最大容量enumBOOL{False,True};typedefstructArcNode{intadjvex; 〃该弧所指向的顶点的位置structArcNode*nextarc;〃指向下一条弧的指针ArcNode; //弧结点typedefstruct{ArcNode*AdjList[MAX_VERTEX_NUM];〃指向第一条依附该顶点的弧的指针intvexnum,arcnum; 〃图的当前顶点和弧数intGraphKind; //图的种类，0—无向图，1一有向图Graph;typedefstruct //队列结构{intelem[MAXQSIZE];〃数据域intfront; 〃队头指针intrear; 〃队尾指针}SqQueue;BOOLvisited[MAX_VERTEX_NUM];//全局变量——访问标志数组voidCreateGraph(Graph&); 〃生成图的邻接表voidDFSTraverse(Graph); 〃深度优先搜索遍历图voidDFS(Graph,int);voidBFSTraverse(Graph); 〃广度优先搜索遍历图voidInitial(SqQueue&);〃初始化一个队列BOOLQueueEmpty(SqQueue); 〃判断队列是否空BOOLEnQueue(SqQueue&,int); 〃将一个元素入队列BOOLDeQueue(SqQueue&,int&);〃将一个元素出队列intFirstAdjVex(Graph,int);〃求图中某一顶点的第一个邻接顶点intNextAdjVex(Graph,int,int);//求某一顶点的下一个邻接顶点voidmain(){GraphG;〃采用邻接表结构的图charj=y；textbackground(3);〃设定屏幕颜色textcolor(15);clrscr();// 程序解说 prints本程序将演示生成一个图，并对它进行遍历An)prints首先输入要生成的图的种类An")；printf("O一无向图，1--有向图\n");printfC之后输入图的顶点数和弧数。5格式：顶点数，弧数；例如:4,3\n");printf("接着输入各边(弧尾,弧头)An例如:\nl,2\nl,3\n2,4\n")；printff程序会生成一个图，并对它进行深度和广度遍历.\n")；printf("深度遍历:1->2・>4・>3\n广度遍历:l・>2・>3・>4\n")；while(j!=rN'&&j!-n,){printff请输入要生成的图的种类(0/1)：”)；scanf("％d”,&GGraphKind);〃输入图的种类printff请输入顶点数和弧数：,•);scanf(n%d,%dn,&G.vexnum,&Garcnum);〃输入图的顶点数和弧数CreateGraph(G); 〃生成邻接表结构的图DFSTraverse(G); //深度优先搜索遍历图BFSTraverse(G); 〃广度优先搜索遍历图printf(”图遍历完毕，继续进行吗?(Y/N)”)；scanff%c\&j);voidCreateGraph(Graph&G){〃构造邻接表结构的图Ginti;intstart,end;ArcNode*s;fbr(i=1;i<=Gvexnum;i++)GAdjList[i]=NULL;〃初始化指针数组fbr(i=l;i<=Garcnum;i++){scanfC%d,%d”,&start,&end);〃输入弧的起点和终点s=(ArcNode*)malloc(sizeofi(ArcNode));〃生成一个弧结点s->nextarc=GAdjList[start];〃插入到邻接表中s->adjvex=end;GAdjList[start]=s;if(G.GraphKind==O)〃若是无向图，再插入到终点的弧链中{s=(ArcNode*)malloc(sizeof(ArcNode));s->nextarc=G.AdjList[end];s->adjvex=start;G.AdjList[end]=s;voidDFSTraverse(GraphG){〃深度优先遍历图Ginti;printfi(',DFSTraverse:n);fbr(i=1;i<=Gvexnum;i++)visited[i]=False;〃访问标志数组初始化fbr(i=1;i〈=Gvexnum;i++)ifi[!visited[i])DFS(Qi);〃对尚未访问的顶点调用DFSprintfC\b\b\nM);}voidDFS(GraphG,inti){〃从第i个顶点出发递归地深度遍历图Gintw;visited[i]=True;〃访问第i个顶点fbr(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))if(!visited[w])DFS(Qw);〃对尚未访问的邻接顶点w调用DFSvoidBFSTraverse(GraphG){〃按广度优先非递归的遍历图G,使用辅助队列Q和访问标志数组visitedinti,u,w;SqQueueQ;printf("BFSTreverse:M);fbr(i=l;i<=Gvexnum;i-H-)visited[i]=False;〃访问标志数组初始化Initial(Q);〃初始化队列fbr(i=l;i<=Gvexnum;i+-»-)if(!visited[i]){visited[i]=True;〃访问顶点iprintf(M%d->w,i);EnQueue(Q,i); //将序号i入队列while(!QueueEmpty(Q))〃若队列不空，继续{DeQueue(Q,u); 〃将队头元素出队列并置为ufbr(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w])〃俞u欣尚未访问的邻接顶点w进行访问并入队列{visited[w]=True;printiV%d->”,w);EnQueue(Q,w);printff\b\b\nM);}intFirstAdjVex(GraphG,intv){〃在图G中寻找第v个顶点的第一个邻接顶点if(!GAdjList[v])return0;elseretum(GAdjList[v]->adjvex);intNextAdjVex(GraphG,intv,intu){〃在图G中寻找第v个顶点的相对于u的下一个邻接顶点ArcNode*p;p=G.AdjList[v];while(p->adjvex!=u)p=p・>nextarc;〃在顶点v的弧链中找到顶点uif(p->nextarc=NULL)return0; 〃若己是最后一个顶点，返回0elseretum(p->nextarc->adjvex);〃返回下一个邻接顶点的序号}voidInitial(SqQueue&Q){〃队列初始化Q.front=Q.rear=0;)BOOLQueueEmpty(SqQueueQ){〃判断队列是否己空，若空返回True,否则返回Falseifi(Q.front==Q.rear)returnTrue;elsereturnFalse;}BOOLEnQueue(SqQueue&Q,intch){〃入队列，成功返回True,失败返回Falseifi((Q.rear+1)%MAXQSIZE=Q.front)returnFalse;Q.elem[Q.rear]=ch;Q.rear=(Q.rear+1)%MAXQSIZE;returnTrue;BOOLDeQueue(SqQueue&Q,int&ch){〃出队列，成功返回True,并用ch返回该元素值，失败返回Falseifi(Q.front=Q.rear)returnFalse;ch=Q.elem[Q.front];Q.front=(Qfront+l)%MAXQSIZE;returnTrue; 〃成功出队列，返回True最小生成树 *#include<dos.h>#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#defineINFINITY30000 〃定义一个权值的最大值#defineMAX_VERTEX_NUM20〃图的最大顶