还剩49页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
线性结构树形结构图状结构集合结构int len nodetype*h/*返回单链表的长度*/int i=0;nodetypc*p=h;while p!=NULL p=p-next;i++；return i;nodetype findnodetype*h,int i/*返回第i个节点的指针*/{nodetype*p=h;int j=l;if ilenh||i=0return NULL;/*i上溢或下溢*/elsewhile p!二NULLj〈i/*查找第i个节点，并由p指向该节点*/j++；p=p-next;return p;nodetype*insnodetype*h,int i,elemtype x/*单链表head中第i个节点i〉=0之后插入一个data域为x的节点*/nodetype*p,*s;s=nodetype*malloc sizeofnodetype;/*创J立节点s*/s-data=x;s-next=NULL;if i=0/*i=0:s作为单链表的第一个节点*/s-next=h;h=s;elsep=findh,i;/*查找第i个节点，并由p指向该节点*/ifp!=NULLs-next=p-next;p-next=s;elseprintf〃输入的i值不正确\n〃;return h;nodetype*del nodetype*n,int i/*删除第i个节点*/nodetype*p=h,*s;int j=l;if i=l/*删除第一个节点*/h=h-next;freep;elsep=findh,i-1;/*查找第iT个节点，并由p指向该节点*/if p!=NULLp-next!=NULLs=p-next;/*s指向要删除的节点*/p-next=s-next;frees;elseprintf〃输入的i值不正确\n〃;return h;void disposenodetype*h/*释放单链表的所有节点占有的空间*/nodetype*pa=h,*pb;ifpa!=NULLpb=pa-next;if pb=NULL/*只有一个节点的情况*/free pa;elsewhilepb!=NULL/*有两个及两个以上的节点的情况*/freepa;pa=pb;pb=pb-next;free pa;/*试写一算法，对单链表实现就地逆置*/ftinclude^slink.cpp〃#includemalloc.hnodetype*invert nodetype*h/*实现单链表逆置*/nodetype*p,*q,*r;iflenh=1printf〃逆置的单链表至少有2个节点\n〃;return NULL;}elseP二h;q=p-next;while q!=NULLr=q-next;q-next=p;P=q；q=r;h-next=NULL;h=p;return h;void mainnodetype*head;head二create;disphead;head=inverthead;disphead;/*运行结果建立一个单链表输入第1节点data域值1输入第2节点data域值2输入第1节点data域值3输入第1节点data域值4输入第1节点data域值5输入第1节点data域值0输出一个单链表12345输出一个单链表54321*//*设线性表A=a a,,B=b],b2,…,bj,试写一个按以下规则合并A,B为线性表C的算法，即使得C=b2a bi,•••,a^,b,b i,•••,b当m=ri时，C=a b•••,a,b,a i,•••,a^当mn时线性表A,B和C均以单链表做存储结构，b nra+B bh nnn+且C表利用A表和B表中的结点空间构成注意单链表的长度值m和n均未显示存储*/#include〃slink.cpp〃nodetype^combine nodetype*ha,nodetype*hbnodetype*hc=ha,*pa=ha,*pb=hb,*q,*r;if lenpa!=lenpbprintf〃两个单链表长度不同\n〃;return NULL;while pa!=NULL q=pa-next;r=pb-next;pa-next=pb;pb-next=q;pa二q；pb=r;return he;void mainnodetype*heada,*headb,*headc;heada=create;headb=create;headc=combineheada,headb;dispheadc;#include/zslink.cpp〃nodetype*connect nodetype*hl,nodetype*h2nodetype*pa=hl,*pb=h2,*h3,*pc;h3=nodetype*malloc sizeofnodetype;/*创立哨兵*/pc=h3;/*pc总是指向生成的新单链表的最后一个节点*/whilepa!=NULLpb!=NULLif pa-datcipb-datapc-next=pa;pc=pa;pa=pa-next;elseifpa-datapb-datapc-next=pb;pc=pb;pb=pb-next;else/*pa-data=pb-data的情况*/pc-next=pa;pc=pa;pa=pa-next;pb=pb-next;if pa!=NULL pc-next=pa;/*hl单链表还有节点时*/if pb!=NULL pc-next=pb;/*h2单链表还有节点时*/pc二h3;/*删除哨兵*/h3=h3-next;free pc;return h3;void mainnodetype*headl,*head2,*head3;headl=create;head2=create;dispheadl;disphead2;head3=connectheadl,head2;disphead3;#includestdio.h#includemalloc.htypedef struct dnodeint data;structdnode*link;}dlist;dlist*xordlist*pl,dlist*p2/*在C/C++中异或运算符不能对地址进行异或运算，所以先将地址值转换为长整形，然后进行异或运算，再将结果强制转换成地址这是本函数的功能*/int addl,add2,add3;addl=longpl;add2=longp2;add3=addl add2;returndlist*add3;dlist*createdlist**eint i=l,x;dlist*head,*s,*pre;printf〃创立一个双链表以0结束D\n〃；while1printf C输入第%d节点值〃,i;scanf〃%d〃,x;if x=0/*生成最后一个节点的link值后退出循环*/pre-link=xorr,NULL;/*将s-link置为前后节点地址之异或*/*e=pre;break;s=dlist*mallocsizeof dlist;/*创立一个节点*/s-data=x;if i=l/*是第一个节点的情况*/pre=head=s;r=NULL;/*r为当前节点的前一个节点*/else pre-link=xor r,s;/*将s-link置为前后节点地址之异或*/r=pre;pre=s;i++；return head;void orderdlist*h,dlist*edlist*pre=NULL,*prel,*p二h;printf〃遍历节点序列〃；ifh==NULLprintf〃空表\n〃;elsewhil ep!=e/*遍历最后一节点前的所有节点*/printf，z%d〃,p-data;prel=p;p=xor pre,p-link;/*为下一个节点的地址*/pre=prel;printf，z%d”,e-data;printf〃\n〃；void maindlist*h,*e;int i;h二createe;printf〃从左向右〃；orderh,e;printf〃从右向左〃；order e,h;/*运行结果创立一个双链表以0结束输入第1节点值3输入第1节点值5输入第1节点值:8输入第1节点值:2输入第1节点值:6输入第1节点值0从左向右遍历节点序列35826从右向左遍历节点序列62853*/第三章栈和队列实现栈根本算法的头文件stack.cpp为#inuludesldio.h#define MaxLen20/*顺序栈存放的最多元素个数为Maxlen-1*/typedef charelemtype;typedef structsqstackelemtype data[MaxLen];int top;}stack;void initstack*st/*初始化栈st*/st-top=0;int pushstack*st,elemtype x/*入栈*/if st-top==MaxLen-lprintf〃栈溢出\n〃;return0;elsest-top++;st-data[st-top]=x;return1;int pop stack*st,elemtype*x/*退栈*/ifst-top==0printf〃栈下溢出\n〃；return0;else*x=st-data[st-top];st-top一;return1;int emptystack*st/*判断栈空*/ifst-top==0return1;elsereturn0;int gettopstack*st,elemtype*x/*获取栈顶元素*/if st-top==0printf（〃栈下溢出\n〃）;return0;else*x=st-data[st-top];return1;void dispstack*st/*输出栈的所有元素*/int i;fori=st-top;i0;i一printf z，%d z，,st-data[i];printf〃\n〃;/*练习
3.19*//*假设一个算术表达式中可以包含三种括号，圆括号〃和、方括号[和和花括号”{〃和“}〃,且这三种括号可按任意的次序嵌套使用如:.・[・・{・・}・・[・・]..].・[・・]・・・・・・.编写判别给定表达式中所含括号是否正确配对出现的算法表达式已存入数据元素为字符的顺序表中*//*输入{a+[b+c+d+e]+f}*/#include，zstack.cpp〃#includemalloc.hint correctchar*strstack st;char x;int i,ok=l;initst;for i=0;str[i]!=,\0J;i++switchstr[i]case，C:pushst,;break;case，[’:pushst,,[;break;case{:pushst,{;break;case:if!pop st,xx=二ok=0;break;case]:if!popst,xx==,ok-0;break;case}:if!popst,xx=二{ok=0;break;if!ok break;ifemptystok return1;else return0;}void mainchar*str;str=char*malloclOO*sizcofchar;printf/zstr:〃；scanf〃%s〃，str;ifcorrectstrprintf〃表达式括号匹配\n〃；elseprintf〃表达式括号不匹配\n〃;getchO;}#includestdio.httdefine MaxLen100int transchar str[],char exp[]int st[MaxLen];/*作为栈使用*/char ch;int i二0,t=0,top=T;/*t作为exp的下标，top作为st的下标，i作为str的下标*/whilech=str[i++]!=\0ifch=Och〈二9/*判断为数字*/exp[t]=ch;t++;while ch=str[i++]!=，\0,ch=，0，ch=9exp[t]=ch;t++;i—；exp[t]=#;t++;else ifch=二‘/*判断为左括号*/lop++;st[lop]-ch;else ifch=’/*判断为右括号*/while st[top]!=以下数据结构算法由C语言编译，并在TC上运行通过，其中，扩展名为〃.CPP〃的为头文件，运行时只需将头文件与相应算法连接即可第一章绪论（预备知识）/*试写一算法，自大至小输出顺序读入的三个整数X,Y和Z的值*/ttinclude stdio.hvoid swapint*x,int*y,int*z{int t;if*x〈*y t二*x;*x=*y产y=t;if*y*z t=*y;*y=*z;*z=t;if*x〈*y t二*x;*x二*y;*y=t;inainO{int a,b,c;scanf z，%d,%d,%d〃,a,b,c;swap a,b,c;printf〃％d%d%d”,a,b,c;第二章线性表顺序表
1.实现顺序表根本算法的头文件sq.cpp为#includestdio.h#define MaxLen50/*顺序表中最多元素个数*/typedef intelemtype;typedef elemtypesqlist[MaxLen];int createsqlist A/*创立线形表*/int i,n;printf〃创立一个顺序表\n〃；printf〃输入元素个数〃；scanfn;fori=0;in;i++printf〃输入第%d个元素值:〃，i+1;scanf〃％d〃，A[i];return n;void dispsqlist A,int n/*输出一个顺序表*/int i;printf〃输出一个顺序表\n〃;if n==0printf空表”;for i=0;in;i++printf%d〃,A[i];exp[t]=st[top];top一一;t++;top——;else ifch=+||ch=,/*判断为加减号*/while top=0st[top]!=exp[t]=st[top];top一;t++;top++;st[top]=ch;else ifch==，||ch二二/while st[top]=二||st[top]==，/，exp[t]=st[top];top一一;t++;top++;st[top]=ch;while top=0exp[t]=st[top];t++;top一;exp[t]-\0J;return1;int compvaluechar exp[],int*nint st[MaxLen],d;/*作为栈使用*/char ch;int t=0,top=T;/*t作为exp的下标，top作为st的下标*/while ch=exp[t+l]!=\0ifch=Och«’9/*为数字字符时转换为数字*/{d=0;doId=10*d+ch-O;}while ch=exp[t++]!=#;top++;st[top]=d;/*数字进栈*/else/*为运算符时，计算并退栈*/switchch case+:st[top-1]=st[top-1]+st[top];break;case-:st[top-1]=st[top-1]-st[top];break;case，*:st[top-1]=st[top-1]*st[top];break;case/:if st[top]!=0st[top-l]=st[top-l]/st[top];elsereturn0;/*除错误*/break;top一;*n=st[top];return1;void mainchar str[MaxLen];/*存储原算术表达式*/charexp[MaxLen];/*存储转换成的波兰表达式*/int n;printf〃算术表达式〃式scanf〃％s〃,str;if transstr,exp==0printf〃原算术表达式不正确\n〃;else printf〃波兰表达式%d\n，z,exp;ifcompvalueexp,n==lprintf计算结果%d\n，z,n;elseprintf〃计算错误\n〃；AAckerman函数的定义如下Akmm,n=n+l m=0,akmm-l,1m!=0,n=0akmm-1,akmm,n-1m!=0,n!=01,写出递归算法；2o写出非递归算法；3o根据非递归算法，画出求akm2,l时栈的变化过程*/#includestdio.h#define MaxLen5000/*此数应足够大，因为m和n值的较小增长会引起函数值的极快增长，用的栈的空间也很大*/ini flini in,ifilnifm==0return n+1;elseifn==0return fl m-1,1;elsereturn flm-1,flm,n-1;int noint m,int nifm==0return1;else ifn==0return2;else return3;int f2intm,int nintst[MaxLcn]
[4],top=l,ml,nl;st[top]
[0]=nom,n;st[top]
[1]=0;/*初值0进栈*/st[top]
[2]=m;/*初值m进栈*/st[top]
[3]=n;/*初值n进栈*/do/*开始循环*/ifst[top][l]==0if st[top]
[0]==3top++;st[top][l]=0;st[top]
[2]=st[top-1]
[2];st[top]
[3]=st[top-1]
[3]-1;st[top]
[0]=nost[top]
[2],st[top]
[3];else ifst[top]
[0]==2top++;st[top][l]=0;st[top]
[2]=st[top-1]
[2]-l;st[top]
[3]=1;st[top]
[0]=nost[top]
[2],st[top]
[3];if st[top]
[0]==lst[top][l]=st[top]
[3]+l;if top=lst[top]
[1]!=0st[top-1]
[0]==2st[top-l][l]=st[top]
[1];top--;else iftop=lst[top]
[1]!=0st[top-1]
[0]==3nl=st[top]
[1];ml=st[top-1]
[2]-l;top—;st[top][l]=0;st[top]
[2]=ml;st[top]
[3]=nl;st[top]
[0]=nost[top]
[2],st[top]
[3];iftop=lst[top][l]!=0/*栈中已有一个元素，且已计算出值，则退出循环*/break;}whiletop=l;return st
[1]
[1];void mainint n,m;printfinput mn:〃；scanf〃%d96d〃，m,n;printf，zdigui c%d,%d=%d\n，/,m,n,flm,n;printf feidigui c%d,%d=%d\n，/,m,n,f2m,n;systempause;/*输入38回车diguic3,8=2045feidigui c3,8=2045*//*假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点注意不设头指针，试编写相应的队列初始化、入队列和出队列的算法*/#includestdio.h#define MaxSize6typedef charqueue[MaxSize];int rear=0,len=0;/*队列初态*/int enqueue queue qu,char x iflen=二MaxSize/*队满，上溢出*/return0;else rear=rear+l%MaxSize;qu[rear]=x;len++;/*队列长度增1*/return1;int dequeue queuequ,char*xint front;if len=0/*队列为空时下溢出*/return0;elseIfront=rear-len+1+MaxSize%MaxSize;*x=qu[front];len-;/*队列长度减1*/return1;void mainchar x;queuequ;printf，za入队\n;enqueue qu,a;printf，zb入队\n〃;enqueue qu,b;printf c入队\n〃；enqueue qu,c;printf〃出队一次:〃;dequeuequ,x;printf〃枇\n〃,x;printf d入队\n〃;enqueue qu,d;printf，ze入队\n〃；enqueue qu,e;printf〃出对一次〃;dequeuequ,x;printf/，%c\n，/,x;printf z，f入队\n〃；enqueuequ,f;printf，zg入队\n〃;enqueue qu,g;printf〃出队一次〃;dequeuequ,x;printf C，%c\n，z,x;printf〃余下元素出列〃；whilelen0dequeuequ,x;printf，z%c〃，x;printf〃\n〃;systempause;/*假设称正读和反读都相同的字符序列为“回文〃，例如abba和abcba是回文，abcde和ababab则不是回文试写一个算法判别读入的一个以为结束符的字符序列是否是回文”.*/#includestdio.h#includemalloc.h#define MaxLen100typedef struct node chardata;struct node*next;}cnode;cnode*createchar s[]int i=0;cnode*h,*p,*r;whiles[i]!=\0p=cnode*mallocsizeofcnode;p-data=s[i];p-next=NULL;ifi==0h=p;r=h;/*r始终指向最后一个结点*/else{r-next=p;r=p;i++；return h;int judgecnode*h charst[MaxLen];int lop-0;cnode*p=h;while p!=NULL st[top]=p-data;top++;p=p-next;P=h;whilep!=NULLtop—;ifp-data==st[top]p=p-next;elsebreak;ifp=NULLreturn1;elsereturn0;void main{char str[MaxLen];cnode*h;printf〃输入一个字符序列〃；scanf〃%s〃，str;h二create str;if judgeh==lprintf〃%s是回文〃，str;elseprintf〃%s不是回文〃，str;getchO;第四章串实现串根本运算的头文件string.cpp为#includestdio.h#includestring.h#define MaxLen20typedef strcutchar ch[MaxLen];int len;}strtype;void create strtype*s,char str[]/*将普通字符串赋给串*/{slrcpys^ch,sir;s-len=strlen str;int lengthstrtype*s/*求串长度*/return s-len;void copystrtype*sl,strtype*s2/*串的复制*/int i;fori=0;isl-len;i++s2-ch[i]=sl-ch[i];s2-len=sl-len;s2-ch[s2-len]=\0;/*添加字符串结束符*/strtypr subsstrtype*s,int pos,int n/*求子串*/int i;strtype sub;if pos+n-llength si/*参数不正确*/sub.len=0;else!for i=pos-l;ipos+n-l;i++sub.ch[i-pos+l]=s-ch[i];sub.len=n;sub.ch[sub.len]二\0;return sub;int concatstrtype*s,strtype*t/*连接两个串*/int i;ifs-1en+t-1enMaxLenreturn0;for i=0;it-len;i++s-ch[i+s-len]=t-ch[i];s-len=s-len+t-len;s-ch[s-len]=，\0J;return1;int insstrtype*s,strtype*t,int i/*插入一个子串*/int j;ifs-len+t-lenMaxLenreturn0;for j=s-len-l;j=i-l;j—/*i之后的所有元素后移t-len个位置*/s-ch[j+t-len]=s-ch[j];for j=0;jt-len;j++s-ch[j+i-l]=t-ch[j];s-len=s-len+t-len;s-ch[s-len]=，\0，;return1;int delstrtype*s,int pos,int n/*删除一个子串*/int i;ifpos+ns-lenfor i=pos+nT;is-len;i++s-ch[i-n]=s-ch[i];s-len=s-len-n;s-ch[s-len]=，\0，;return1;void dispstrtype*s/*输出串*/ifs-len==0printf〃空串\n〃;elseprintf〃%d\n〃，s-ch;#includestdio.h#include，zstring.cpp〃strtype replacestrtype*sl,int i,int j,strtype*s2strtype s;int n,k;ifi+j-l=sl-lenfor n=0;n〈iT;n++/*把si的前i-1个字符赋给s*/s.ch[n]=sl-ch[n];for n=0;n〈s2-ch[n]/*连接s2串*/
5.ch[i+n-l]=s2-ch[n];
5.1en=i+s2-len-l;for n=s.len,k=i+j-l;ksl-len;n++,k++/*连接si的位置i及之后的字符*/
5.chEn]=sl-ch[k];s.len=n;s.ch[s.len]=\0;elses.ch
[0]=，\0，;s.len=0;return s;void mainstrtypes,si,s2,s3,s4,s5,s6;creates,〃xyz+*〃；printf〃s=〃;disps;sl=subss,7,1/s2=subss,3,1;/*s2=〃y*/s3=subss,6,1;/*s3=+*/s4=replace s,3,1,s3;s5=replaces4,6,1,sl;s6=replace s5,7,1,s2;printf〃t=〃；disps6;#includestdio.h#include/zstring.cpp〃int indexstrtype*sl,strtype*s2int i=0,j,k;while isl-lenj=0；ifsl-ch[i]==s2ch[j]k=i+1;j++;whileksl-lenjs2-lensl-ch[k]==s2-chEj]k++;j++;if j==s2-len/*s2中止时找到了子串*/break;else i++;else i++;if isl-lenreturn T;elsereturn i+1;void dclallstrtype*sl,strtype*s2printf〃\n〃；int inssqlist A,int n,int i,elemtype x/*在顺序表第i个元素前插入一个元素x,若i=0,则新元素作为第一个元素,若i=l,则插入在最后*/int j;ifi0||in printfi值下溢或上溢\n〃;else forj=n-l;j=i;j—A[j+l]=A[j];/*将第i个元素及其后的元素后移*/A[i]=x;n++;/*顺序表长度加1*/return n;int delsqlist A,int n,int i/*在顺序表中删除第i个元素*/int j;if i=01|in printf〃i值下溢或上溢\n〃；else forj=i-l;jn;j++;/*将第i个元素之后的元素前移覆盖n—;/*顺序表长度减1*/return n;int findsqlist A,int n,elemtype x/*在一个有n个元素的顺序表A中查找元素值为x的元素*/int i=0;whi1ei=nA[i]!=xi++;ifin return1;else return0;练习
2.11:/*设顺序表va中的数据元素递增有序试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性*/#include〃sq.cpp〃ini insertsqlist A,int n,eleinlype x/*顺序表A的长度为n*/int i,j;ifx=A[n-l]A[n]=x;/*若x大于最后的元素，则将其插入到最后*/elseint n;n=indexsi,s2;while n=0delsi,n,lengths2;n=indexsi,s2;diapsl;void mainstrtypesi,s2;charstr[MaxLen];printf〃字符串〃；gets str;createsl,str;printf子串〃；getsstr;creates2,str;delallsl,s2;第五章数组与广义表实现广义表根本运算的头文件list.cpp如下#includestdio.h#includestring.h#includemalloc.h^define MaxLen100typedef struct node/*定义广义表结构*/int tag;/*只取0原子节点或1表节点*/struct node*1ink;/*后继节点*/unionchar data;structnode*slist;/*子表*/}val;}gnode;void disastrchars[],char hstr口/*本函数为辅助建立广义表的函数从字符串s中取出第一个，之前的子串赋给hstr,并使s成为删除子串hstr和，之后的剩余串若串s中没有字符，，则操作后的hstr为操作前的s,而操作后的s为空串*/int i=0,j=0,k=0,r=0;char rstr[MaxLen];whiles[i]s[i]!=，,||kelse if s[i]==，k--；if s[i]||s[i]==，khstr[j]=s[i];i++；j++；hstr[j]=\0;ifs[i]==，,，i++;whiles[i]rstr[r]=s[i];r++;i++;rstr[r]=，\0;strcpys,rstr;gnode*createchar s[]/*从字符串表示创立广义表*/gnode*p,*q,*r,*gh;char subs[MaxLen],hstr[MaxLen];int len;len=strlens;if!strcmps,〃〃/*空表的情况*/gh=NULL;elseif1en==1/*原子的情况*/gh=gnode malloc sizeofgnode;/*建立一个新节点*/gh-tag=0;/*构造原子节点*/gh-val.data=*s;gh-link=NULL;else/*子表的情况*/gh=gnode*malloc sizeofgnode;/*建立一个新节点*/gh-tag=l;P=gh；s++;/*除掉前面的一个*/strncpysubs,s,len-2;subs[ler2]=\0;dodisastr subs,hstr;/*将subs分为表头和表尾*/r=crcatehstr;p-val.slist=r;q二P；len=strlensubs;iflen0p=gnode*mallocsizeofgnode;p-tag=l;q-link=p;}whilelen0;q-link=NULL;returngh;void dispgnode*h/*以字符串方式输出广义表*/gnode*p,*q;printf〃〃;ifhdop=h-val.slist;q=h-link;while qp!p-tag/*为原子且有后继节点的情况*/printf，z%d〃,p-val.data;p=q-val.slist;q=q-link;ifP!P-tag/*为原子之后继节点的情况*/printf级d〃,p-val.data;break;else/*为子表的情况*/if!pprintf〃〃;else dispp;if qprintf〃,〃；h二q;}whileh;printf〃〃;int locategnode*p,char x/*判断x是否在广义表中*/int find=O;ifp!=NULL if!p-tagp-val.data==x return1;else ifp-tagfind二locatep-val.slist,x;iffindreturn1;elsereturnlocate p-link,x;elsereturn0;}/*复制广义表*/Sinclude^list.cpp〃void gcopegnode*p,gnode*q if p二NULL;q=NULL;else q=gnode*malloc sizeofgnode;/*仓位一个节点*/q-tag=p-tag;if p-tag=0q-val.data=p-val.data;/*原子节点直接复制*/else gcopyp-val.slist,q-val.slist;gcopyp-link,q-link;}void maingnode*p,*q;charstr[MaxLen];prinll〃输入广义表表达式〃；scanf〃%s〃，str;p=create str;printf〃原来的广义表〃；dispp;gcopy p,q;printf〃\n复制的广义表”表dispq;printf〃\n〃;/*判别广义表是否相等的递归算法*/#include，zlist.cpp〃int samegnode*p,gnode*q int flag=l;ifp!=NULLq!=NULL ifp-tag==0p-tag!=0ifp-val.data!=q-val.dataflag=0;else ifp-tag==l,q-tag==lflag=samep-val.slist,q-val.slist;else flag=0;ifflagflag=samep-link,q-link;else ifp二二NULLq!二NULLflag=0;ifp!=NULLq=二NULL flag=l;}return flag;void maingnode e,*gl,*g2,*g3;gl二create〃a,b,c,d,e,f〃；g2=create〃a,b,c,d,e,f〃;g3=create〃a,b,c,d,e,f〃;printf〃广义表gl:〃；dispgl;printf〃\n〃;printf〃广义表g2:〃；dispg2;printf〃\n〃；printf〃广义表g3:〃；dispg3;printf〃\n〃；printf/zgl与g2:〃;printf samegl,g2=0〃不同〃〃相同〃;printf〃\n〃;printf，zgl与g3:〃;printf samegl,g3=0”不同〃〃相同〃;/*逆置广义表*/#include，zlist.cpp〃void reversegnode*p,gnodc*q gnode*r,*s,*t,*b;ifp=NULLq=NULL;else if p-tag=0/*为原子的情况*/s=gnode*mallocsizeof gnode;/*复制该原子节点*/s-tag=0;s-val.slist=NULL;s-val.data=p-val.data;q二s;else/*为表的情况*/reversep-val.slist,s;/*处理表头*/ifp-link!=NULL reversep-link,t；/*产生表尾的逆置广义表t*/b=gnode mal1oc sizeofgnode;/*给表头加上一个子表节点*/b-tag=l;b-link=NULL;b-val.slist=s;q=t;r=t;whiler-link!=NULL/*找到第一层的最后一个节点*/r=r-link;r-li nk=b;/*连接*/else/*p-link=NULL*/q二gnode*malloc sizeofgnode;/*创立表头节点q*/q=tag=l;q-link=NULL;q-val.slist=s;void maingnode*gl,*g2;gl二create〃a,b,c,d,e〃;printf〃广义表gl:〃；dispgl;printf〃\n〃；reversegl,g2;printf〃由gl逆置为g2\n〃;printf〃广义表gl:〃；dispg2;printf〃\n〃;/*删除x项*/#include，zlist.cpp〃void delallgnode*p,charx,gnode*q gnode*s,*t;ifp=NULLq=NULL;elsei f3-tag=0/*为原子节点的情况*/if p-val.data!=xq=gnode mal1ocsizeof gnode;/*复制到原子节点*/q-tag=0;q-val.data=p-val.data;q-link=NULL;elseq二NULL;/*返回空表*/elsedelal1p-val.slist,x,s；/*删除线性表头中的x得到s*/i[s=NULL/*新表的表头为空的情况*/p=p-link;ifp!=NULLdelall p-val.slist,x,t;/*从表尾的表头产生t*/q=gnode*mallocsizeofgnode;/*创立整个新表的表头节点q*/q-tag=l;q-link=NULL;q-val.slistr；/5^^t作为新表表头*/ifp-link!二NULL/*若还有后继元素，删除x后作为新表表尾*/delallp-link,x,t;q-link=t;else q=NULL;/*返回全表*/elsedelall p-link,x,t;/*删除表尾中的x得到t*/q=gnode*mallocsizeofgnode;/*创立整个新表的表头节点q*/q-tag=l;q-val.slist=s;q-link=t;void maingnode*gl,*g2;gl二create〃a,b,a,d,a〃;ifgl=NULLprintf〃gl:NULL\n〃;printf〃广义表gl:%dz，,dispgl;printf〃\n〃；delallgl,,a,g2;printf〃从gl中删除a，得到g2\n〃;printf〃广义表g2:%d\n/z,dispg2;printf〃\n〃;第六章树和二叉树实现树的根本运算的头文件tree.cpp为#includestdio.h#includemalloc.hSdcfinc MaxSize100#define MaxWidth40typedef charelemtype;typedef structnode elemtype data;structnode*left,bright;}BTree;/*定义二叉树类型*/void dispstackBTree*stack口，int top;void creatreeBTree*b,char*str/*根据嵌套括号表示法的字符串*str生成链接存储的二叉树*/{BTree*stack[MaxSize],*p;int top=T,k,j=0;/*top为栈指针，k指定是在左还是右孩子,j为str指针*/charch;b=NULL;ch=str[j];while ch!=，\0{switchch{case C:top++;stack[top]=p;k=l;break;/*为左节点*/case V:top--;break;case:k=2;break;/*为右节点*/default:p=BTree mallocsizeofBTree;p-data=ch;p-left=p-right=NULL;i fb二二NULL/*根节点*/b=p;else switchkcase1:stack[top]-left=p;break;case2:stack[top]-right=p;break;}j++；ch=str[j];}}void disptreeBTree*b/*以凹入表表示法输出一棵二叉树*/BTree*stack[MaxSize],*p;int level[MaxSize]
[2],top,n,i,width=4;char type;ifb!=NULL{lop-1;stack[top]=b;/*根节点入栈*/level[top]
[0]=width;level[top][l]=2;/*2表示是根*/while top0p二stack[top];/*退栈并凹入显示该节点值*/n=level[top]
[0];switchlevel[top]
[1]case0:type=O;break;/*左节点之前输出0*/case1:type=1;break;/*右节点之前输出1*/case2:type二r;break;/*根节点之前输出r*/}fori=l;i〈=n;i++/*其中n为输出的空格数，字符以右对齐显示*/printf，z〃；printf〃%d%dp-data,type;fori=n+l;i=MaxWidth;i+=2printf〃一〃；printf〃\n〃；top—;ifp-right!=NULL{/*将右子树根节点入栈*/top++;stack[top]=p-right;level[top]
[0]=n+width;/*输出空格数增加width*/level[top]
[1]=1;}/*表示是右子树*/ifp-left!=NULL top++;/*将左子树根节点入栈*/stack[top]=p-left;level[top]
[0]=n+width;/*输出空格数增加width*/level[top][l]=0;/*0表示是左子树*/void printreeBTree*b/*以嵌套括号表示法输出一棵二叉树*/ifb!=NULLprintf，z%d/z,b-data;ifb-left!=NULL||b-right!=NULL printf〃〃;prinlreeb-leri;/*递归处理左子树*/ifb-right!=NULLprintf〃，〃;printreeb-right;/*递归处理右子树*/printf〃〃；i=0;whilexA[i]i++;/*查找插入位置i*/forj=n;j=i;j—A[j+l]=A[j];/*移出插入x的位置*/A[i]=x;return n+1;/*顺序表长度增1*/}void mainsqlist A;int n;n=create A;dispA,n;n=insert A,n,10;/*插入元素10*/dispA,n;getchO;/*运行结果创立一个顺序表输入元素个数3输入第1个元素值6输入第1个元素值9输入第1个元素值14输出一个顺序表6914输出一个顺序表691014*//*设A=由,…,和B=b,…,b均为顺序表，A，和B，分别为A和B中除去最大共同前缀后的子表例如，A=x,y,y,z,x,z,B=x,y,y,z,y,x,x,z,则两者中最大的共同前缀为x,y,y,z,在两表中除去最大的共同前缀后的子表分别为A，二x,z和B=y,x,x,zo若A=B=空表，则人=8;若A=空表，B!二空表，或者两者均不为空表，且A的首元小于B，的首元，则人力；否则AB试写一个比较A,B大小的算法请注意在算法中，不要破坏原表A和B,并且，也不一定先求得A，和B才能进行比较*/#include〃sq.cpp〃int compsqlistA,int na,sqlist B,int nb{int i=0,j=0;wh i1e inajnbA[i++]==B[j++];/*比较相同局部*/i一；j-；ifi==naj==nb return0;/*a=b*/ifi==naj!=nb return-ifi!=naj==nb returnl;/*ab*/ifA[i]B[j]return1;void preorderBTree*b/*先序遍历的递归算法*/ifb!=NULLprintf/z%d z，,b-data;preorderb-left;preorder b-right;BTree*find BTree*b,elemtype x/*采用先序遍历查找值为x的节点*/BTree*p;ifb==NULLreturn NULL;elseifb-data==xreturn b;else p=findb-left,x;ifp!=NULLreturn p;elsereturn findb-right,x;void inorderBTree*b/*中序遍历的递归算法*/ifb!=NULLinorder b-left;printf z，%d〃，b-data;inorder b-right;void postorderBTree*b/*后序遍历的递归算法*/ifb!=NULLpostorder b-left;postorderb-right;printf z，%d”,—ata;int treedepthBTree*b/*求二叉树的深度*/int leftdep,rightdep;if b=NULL/*空树的深度=0*/return0;else leftdep=treedepthb-left;rightdep=treedepth b-right;if leftdeprightdepreturnleftdep+1;elsereturnrightdep+1;/*判断二叉数是否相似*/Sinclude^btree.cpp〃int linkBTree*bl,BTree*b2int likel,like2;ifbl==NULLb2==NULLreturn1;elseifbl二二NULL||b2二二NULLreturn0;else like1=1ikebl-left,b2-〉left;like2=likebl-right,b2-right;returnlikellike2;void mainBTree*b,*p,*q;creatreeb,〃abc,de,f,g〃；creatreep,〃abc,de,f,g;creatree q,〃a b,d e,g〃；prinlf〃b嵌套表示法〃；printreeb;printf〃\n〃;printfp嵌套表示法〃；printreep;printf〃\n〃;printf〃q嵌套表示法〃；printreeq;printf〃\n〃;printf〃b与q:〃；printf likeb,p==1〃相似〃〃不相似〃;printf〃\n〃；printf〃b与q:〃；printf likeb,q==l〃相似〃〃不相似〃；printf〃\n〃；/*先序遍历的非递归算法*/#includez，btree.cpp〃void porderBTree*b{BTree*stack[MaxSize],*p;int top;ifb!=NULLtop=1/*根节点入栈*/stack[top]=b;whi letop0/*栈不空时循环*/{p=stack[top];top一;printf〃%d〃,p-data;ifp-right!=NULL/*右孩子入栈*/top++;stack[top]=p-left;void mainBTree*b;creatree b,〃a bc,d e,f,g〃;printf〃嵌套表示法:〃；printree b;printf〃\n先序遍历〃；porder b;printf〃\n〃；/*后序遍历的非递归算法*/#include，zbtree.cpp〃void psorderBTree*tBTree*stack[MaxSize];BTree*p;int flag,top=T;/*栈指针置初值*/dowhilet/*将t的所有子节点入栈*/top++;stack[top]=t;t=t-left;p二NULL;/*p指向当前节点的前一个已访问的节点*/flag=l;/*设置t的访问标记为已访问过*/while top!=-lflagt二stack[top];/*取出当前的栈顶元素*/ift-right=二p/*右子树不存在或已被访问,访问之*/printf C%d”,t-data;/*访问t*/top一;P=t;/*p指向已被访问的节点*/elseIt=t-right;/*t指向右子树*/flag=0;*设置未被访问的标记*/}whiletop!=-l;void mainBTree*b;creatreeb,〃abc,de,f,g3;printf〃嵌套表示法〃;printreeb;printf〃\n后序遍历〃；psorder b;prinLf〃\n〃;/*编写递归算法，计算二叉树中叶子节点的数目*/includez，btree.cpp〃int nodesBTree*bint numl,num2;ifb==NULLreturn0;else ifb-left==NULLb-right==NULL return1;elsenuml=nodesb-left;num2=nodesb-right;returnnuml+num2+l;void mainBTree*b;creatreeb,〃abc,de,f,g〃；printf〃b嵌套表示法〃;printreeb;printf〃\n〃；printf b节点个数:%d〃，nodes b;printf〃\n〃;/*交换左右子树*/#include/zbtree.cpp〃BTree*swapBTree*bBTree*t,*tl,*t2;ifb二二NULLt=NULL;elset=BTree*mallocsizeof BTree;/*复制一个根节点*/t-data=b-data;tInswapb-left;t2=swapb-right;t-left=t2;t-right=tl;return t;void mainBTree*b,*p;creatreeb,〃abc,de,f,g，z;printf〃b嵌套括号表示法〃；printreeb;printf〃\n〃；p=swapb;printf〃p嵌套括号表示法〃；printreep;printf〃\n〃;/*删除以x为节点的子树，并释放相应的空间*/#includez，btree.cpp〃void disposeBTree*b ifb!=NULLdispose b-left;dispose b-right;freeb;BTree*tree BTree*r,elemtype x/*将x插入到二叉排序树r中*/ifr==NULL r=BTree*mallocsizeofBTree;r-data=x;r-left=r-right=NULL;else!ifxr-datatree r-left,x;elsetree r-right,x;return r;void delBTree*t,elemtype x/*删除以x为根的子树*/BTree*p=t,*q;/*q保存P的父节点*/intflag;/*flag指出p是q的左节点0还是右节点1*/i ft-data=x/*删除整个树*/t=NULL;elsedoifxp-data q二P；p=p-right;flag=l;else ifxp-data q=p;p=p-left;flag=0;}while p-data!=x;switchflagcase0:q-left=NULL;disposep;break;case1:q-right=NULL;disposep;break;void mainBTree*root=NULL;int i=0;char a口二〃daefgbch”;whilea[i]!=\0/*循环创立一棵二叉排序树*/root=tree roor,a[i];i++；printf〃二叉排序树〃;printreeroot;printf〃\n〃；del root,f;printf〃删除后二叉排序树〃；printree root;printf〃\n〃;/*编写按层次顺序遍历二叉数的方法*/itinclude^btree.cpp〃void translevelBTree*belse return-1;void main{sqlistA,B;int na,nb,n;na=createA;nb=createB;n=comp A,na,B,nb;switchncase0:printf〃A=B\n〃；break;case1:printf〃AB\n〃；break;case T:printf〃A〈B\n〃；break;getchO;/*运行结果创立一个顺序表输入元素个数3输入第1个元素值2输入第1个元素值3输入第1个元素值5创立一个顺序表输入元素个数4输入第1个元素值2输入第1个元素值3输入第1个元素值4输入第1个元素值5比较结果AB/*删除A中第i个元素起的k个元素*/#include〃sq.cpp〃int delksqlistA,int*n,int i,int kint j;ifi0||i+k-l*nprinU〃i,k参数不正确\ii〃；return0;el sefor j=i+k-l;j*n;j++g.adjlist[i].firstarc=NULL;fork=0;ke;k++i=edge[k]
[0];j=edge[k]
[1];p=arcnode*mallocsizeofarcnode;/*创立边节点*/p-adjvex=j;p-nextarc=g.adjlist[i].firstarc;/*将p插入到adjlist[i]链表的前面*/g.adjlist[i].firstarc=p;return g;graph creatngO/*采用create原理,不需人机交互,直接返回类似图7的无向图*/int n=4,e=10,i,j,k;graph g;arcnode*p;int edge[]
[2]={{0,3},{3,0},{0,1},{1,0},{1,2},{2,1},{2,3},{3,2},{0,2},{2,0}};/*每一条边设置两遍*/g.vexnum=n;g.arcnum=e;fori=0;in;i++g.adjlist[i].vertex=i;g.adjlist[i].firstare=NULL;for k=0;ke;k++i=edge[k]
[0];j=edge[k]
[1];p=arcnode*mallocsizeofarcnode;/*创立边节点*/p-adjvex=j;p-nextarc=g.adjlist[i].firstarc;/*将P插入到adjlist[i]链表的前面*/g.adjlist[i].firstarc=p;return g;输出图及实现图广度、深度优先序列:#include/zgraph.cpp〃void maingraph g;int visited[Vnum],i,v;for i=0;iVnum;i++/*赋初值*/visited[i]=O;createg;/*建立图的有向图*/dispg;printf〃输入顶点〃；scanf〃96d〃，v;printf〃深度优先序列〃；dfsg,v,visited;printf〃\n〃；printf〃广度优先序列〃;bfs g,v;printf〃\n〃;/*运行结果:创立一个图:第1条顶点数4边（节点号从到3）边数6第2条边（节点号从到3）第3条边（节点号从到3）第4条边（节点号从0到3）第5条边（节点号从0到3）第6条边（节点号从到3）输出图（0,1）0,3（）1,21,02,3（）2,0输入顶点1深度优先序列:广度优先序列123*/Sinclude^graph.cpp〃int visited[Vnum],A[Vnum];void dfslgraph*g,int vi,int vj,int d{int v,i;arcnode*p;visited[vi]=l;d++;A[d]=vi;if vi==vj1=2/*条件1=2*/printfC一条路径〃；fori=0;i=d;i++printf%d,A[i];printf，z\n，z;p=g-adjlist[vi].firstarc;/*找vi的第一个邻接顶点*/while p!=NULLv=p-adjvex;/*v为vi的邻接顶点*/if visited[v]==O||v==vj/*若该顶点未标记访问，或为vj,则递归访问之*/dfsl g,v,vj,d;p=p-〉nextarc;/*找vi的下一个邻接顶点*/visited[vi]=O;/*取消访问标记，以使该顶点可重新使用*/d一;void cyclegraph*g,int vi,int ddfslg,vi,vi,d;void maingraphg;int i;g=creatdg;dispg;for i=0;iVnum;i++visited[i]=O;printf经过0的环:\n〃;cycle g,0,-1;/*运行结果输出图0,10,3b01,22,02,3经过0的环一条路径010一条路径0120第十章内部排序/*编写一个双向起泡的排序算法,即相邻两边向相反反向起泡*/#includestdio.h^define Max20/*最多记录个数*/typedef intelemtype;typedef elemtyperecs[Max];void bibubblerecs r,int nint门48=1;/*继续遍历时为1,已排序好不需遍历时为0*/int i=0,j;elemtype temp;while flag==l flag=0;for j=n-i-l;j=i+1;j—/*反向遍历找最小值*/ifr[j]r[j-l]flagn；/*能交换时，说明未排好序，需继续*/temp=r[j];r[j]=r[j-l];r[j-l]=temp;forj=i+l;jn-l;j++/*正向遍历找最大值*/ifr[j]r[j+l]flag=1;/*能交换时，说明未排好序，需继续*/temp=r[j];r[j]=r[j+l];r[j+l]=temp;i++；void mainrecs A={2,8,3,6,9,5,1,4,0,7};int n=10,i;printf〃双向冒泡排序\n排序前〃;fori=0;in;i++printf〃%d〃，A[i];printf〃\n〃；bibubbleA,n;printf，z排序后〃；fori=0;in;i++printf〃％d〃，A[i];prinlfCV;getch;/*运行结果双向冒泡排序排序前:2836957407排序后:0123456789A[j-k]=A[j];*n-=k;return1;void mainOsqlistA;int n,i,k;create A;dispA,n;printf〃输入i,k:〃;scanf〃96d%dz，,i,k;if dclkA,n,i,k==l dispA,n;getchO;/*运行结果创立一个顺序表输入元素个数5输入第1个元素值1输入第1个元素值2输入第1个元素值3输入第1个元素值4输入第1个元素值5输出一个顺序表12345输入I,k:22输出一个顺序表145*//*试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表a a,...,a逆置为4,b2n#include〃sq.cpp〃void invertsqlistA,int nintm=n/2,i;/*m为长度的一半即的\2]*/elemtype temp;fori=0;iin;i++/*将A[i]与A[n-i-1]进行交换*/temp=A[i];A[i]=A[n-i-l];A[n-i-l]=temp;void mainOsqlistA;intn;n=crcate A;dispA,n;invert A,n;dispA,n;/*运行结果创立一个顺序表输入元素个数4输入第1个元素值2输入第1个元素值6输入第1个元素值3输入第1个元素值1输出一个顺序表2631输出一个顺序表1362*//*假设有两个按元素值递增有序排列的线性表A和B,均以单链表做存储结构，请编写算法将A表和B表归并成一个按元素值递减有序即非递增有序，允许表中含有值相同的元素排列的线性表3并要求利用原表即A表和B表的结点空间构造C表*/#includez，sq.cpp〃int intersectsqlistA,int na,sqlist B,int nb,sqlist Cint i=na,j=nb,k=0;whilei=0j=0i—;elseifA[i-l]B[j-l]J—；else/*A[i-l]=B[j-l]*/C[k++]=A[i-l];i—；j—；}return k-l;void maifiOsqlistA,B,C;int na,nb,nc;na=createA;dispA,na;nb二create B;dispB,nb;nc=intersect A,na,B,nb,C;dispC,nc;/*习题
2.25*//*假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合即同一表中的元素值各不相同，现要求另开辟空间构成一个线性表C,其元素为A和B中元素的交集,且表C中的元素也依值递增有序排列.试对顺序表编写求C的算法*/#includez，sq.cpp〃int unionssqlistA,int na,sqlist B,int nb,sqlist Cint i=0,j=0,k=0;whileinajnbifA[i]B[j]C[k++]=A[i++];else ifA[i]BEj]C[k++]=B[j++];elseAA[i]=B[i]*/C[k++]=A[i];i++；j++；if i〈na/*A还有元素*/forj=i;jna;j++C[k++]=A[j];else ifj〈nb/*B还有元素*/fori=j;inb;i++C[k++]=B[i];return k;}void mainsqlistA,B,C;int na,nb,nc;na=createA;dispA,na;nb=createB;dispB,nb;nc=unions A,na,B,nb,C;dispC,nc;线性表
2.实现线性表根本算法的头文件为#includestdio.h#includemalloc.htypedef intelemtype;/*定义数据域的类型*/typcdef struct linknode/*定义节点类型*/elemtype data;structlinknode*next;}nodetype;nodetype create/*建立单链表，由用户输入各节点data域之值，以表示输入结束*/elemtyped;nodetype*h=NULL,*s,*t;inti=l;peintf〃建立一个单链表\n〃；while1printf z，输入第%d个节点data域值〃，i;scanf〃96d〃，d;if d==0break;/*以0表示输入结束*/i fi二二1/*建立第一个节点*/h=nodetype mallocsizeofnodetype;h-data=d;h-next=NULL;t=h;e1se/*建立其余节点*/s=nodetype mallocsizeofnodetype;s-data=d;s-next=NULL;t-next=s;t=s;/*始终指向生成的单链表的最后一个节点*/i++；}return h;void dispnodetype*h/*输出由h指向的单链表的所有data域之值*/nodetype*p=h;printf〃输出一个单链表:\n〃；ifp=NULL prints〃空表〃;while p!=NULL printfz，%d，z,p-data;p=p-next;。
个人认证
优秀文档
获得点赞 0
