数据结构的语言算法

1、数据结构的语言算法 以下数据结构算法由C语言编译，并在TC上运行通过，其中，扩展名为”.CPP”的为头文件，运行时只需将头文件与相应算法连接即可。第一章 绪论（预备知识）练习1.16/*试写一算法,自大至小输出顺序读入的三个整数X,Y和Z的值*/#include void swap(int *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; main()int a,b,c;scanf(%d,%d,%d,&a,&b,&c);swap(&a,&b

2、,&c);printf(%d %d %d,a,b,c);第二章 线性表1顺序表实现顺序表差不多算法的头文件sq.cpp为：#include#define MaxLen 50/*顺序表中最多元素个数*/typedef int elemtype;typedef elemtype sqlistMaxLen;int create(sqlist A)/*创建线形表*/ int i,n; printf(创建一个顺序表：n); printf(输入元素个数：); scanf(%d,&n); for(i=0;in;i+) printf(输入第%d个元素值:,i+1); scanf(%d,&Ai); return

3、 n;void disp(sqlist A,int n)/*输出一个顺序表*/ int i; printf(输出一个顺序表: n); if(n=0) printf(空表); for(i=0;in;i+) printf(%d ,Ai); printf(n);int ins(sqlist A,int n,int i,elemtype x)/*在顺序表第i个元素前插入一个元素x,若i=0,则新元素作为第一个元素,若i=1,则插入在最后*/ int j; if(in) printf(i值下溢或上溢n); else for(j=n-1;j=i;j-) Aj+1=Aj; /*将第i个元素及其后的元素后移*

4、/ Ai=x;n+;/*顺序表长度加1*/ return n;int del(sqlist A,int n,int i)/*在顺序表中删除第i个元素*/ int j; if(in) printf(i值下溢或上溢n); else for(j=i-1;jn;j+) Aj=Aj+1; /*将第i个元素之后的元素前移覆盖Ai*/ n-; /*顺序表长度减1*/ return n;int find(sqlist A,int n,elemtype x)/*在一个有n个元素的顺序表A中查找元素值为x的元素*/ int i=0; while(i=n&Ai!=x) i+; if(i=An-1) An=x; /*

5、若x大于最后的元素，则将其插入到最后*/ else i=0; while(xAi) i+;/*查找插入位置i*/ for(j=n;j=i;j-) Aj+1=Aj; /*移出插入x的位置*/ Ai=x; return (n+1);/*顺序表长度增1*/void main() sqlist A; int n; n=create(A); disp(A,n); n=insert(A,n,10);/*插入元素10*/ disp(A,n); getch();/*运行结果：创建一个顺序表 输入元素个数：3 输入第1个元素值：6输入第1个元素值：9输入第1个元素值：14输出一个顺序表6 9 14输出一个顺序表

6、6 9 10 14 */练习2.12/*设A=（a1,am）和B=(b1,bm)均为顺序表，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,z)。若A=B=空表，则A=B;若A=空表，B!=空表，或者两者均不为空表，且A的首元小于B的首元，则AB。试写一个比较A,B大小的算法（请注意：在算法中，不要破坏原表A和B，同时，也不一定先求得A和B才能进行比较）*/#includesq.cppint comp(

7、sqlist A,int na,sqlist B,int nb) int i=0,j=0;while(ina&jnb&Ai+=Bj+);/*比较相同部分*/i-;j-;if(i=na&j=nb) return 0;/*a=b*/if(i=na&j!=nb) return -1;/*ab*/if(AiBj)return 1;else return -1;void main() sqlist A,B;int na,nb,n;na=create(A);nb=create(B);n=comp(A,na,B,nb);switch(n)case 0:printf(A=Bn); break;case 1:p

8、rintf(ABn); break;case -1:printf(AB*/练习2.16/*删除A中第i个元素起的k个元素*/#includesq.cppint delk(sqlist A,int *n,int i,int k)int j;if(i*n)printf(i,k参数不正确n);return 0;elsefor(j=i+k-1;j*n;j+)Aj-k=Aj;(*n)-=k;return 1;void main()sqlist A;int n,i,k;n=create(A);disp(A,n);printf(输入i,k:);scanf(%d %d,&i,&k);if(delk(A,&n,

9、i,k)=1)disp(A,n); getch(); /*运行结果：创建一个顺序表 输入元素个数：5输入第1个元素值：1输入第1个元素值：2输入第1个元素值：3输入第1个元素值：4输入第1个元素值：5输出一个顺序表1 2 3 4 5输入I,k:2 2输出一个顺序表1 4 5 */ 练习2.21/*试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,.,an)逆置为(an,an-1,.,a1).*/#includesq.cppvoid invert(sqlist A,int n) int m=n/2,i; /*m为长度的一半即n2*/ elemtype temp; for

10、(i=0;i=0&j=0)if(Ai-1Bj-1)i-;elseif(Ai-1Bj-1)j-;else/*Ai-1=Bj-1*/Ck+=Ai-1;i-;j-;return k-1;void main()sqlist A,B,C;int na,nb,nc;na=create(A);disp(A,na);nb=create(B);disp(B,nb);nc=intersect(A,na,B,nb,C);disp(C,nc);/*习题2.25*/*假设以两个元素依值递增有序排列的线性表A和B分不表示两个集合(即同一表中的元素值各不相同),现要求另开发空间构成一个线性表C,其元素为A和B中元素的交集,

11、且表C中的元素也依值递增有序排列.试对顺序表编写求C的算法*/#includesq.cppint unions(sqlist A,int na,sqlist B,int nb,sqlist C)int i=0,j=0,k=0;while(ina&jnb)if(AiBj)Ck+=Bj+;else/*Ai=Bi*/Ck+=Ai;i+;j+;if(ina)/*A还有元素*/for(j=i;jna;j+)Ck+=Aj;else if(jnb)/*B还有元素*/for(i=j;inb;i+)Ck+=Bi;return k;void main()sqlist A,B,C;int na,nb,nc;na=c

12、reate(A);disp(A,na);nb=create(B);disp(B,nb);nc=unions(A,na,B,nb,C);disp(C,nc);2. 线性表实现线性表差不多算法的头文件slink.cpp为：#include#includetypedef int elemtype;/*定义数据域的类型*/typedef struct linknode/*定义节点类型*/ elemtype data; struct linknode *next;nodetype;nodetype *create()/*建立单链表，由用户输入各节点data域之值，以0表示输入结束*/ elemtype

13、d; nodetype *h=NULL,*s,*t; int i=1; peintf(建立一个单链表n); while(1) printf( 输入第%d个节点data域值:,i); scanf(%d,&d); if(d=0) break;/*以0表示输入结束*/ if(i=1)/*建立第一个节点*/ h=(nodetype *)malloc(sizeof(nodetype); h-data=d;h-next=NULL;t=h; else/*建立其余节点*/ s=(nodetype *)malloc(sizeof(nodetype); s-data=d;s-next=NULL;t-next=s;

14、 t=s;/*始终指向生成的单链表的最后一个节点*/ i+; return h;void disp(nodetype *h)/*输出由h指向的单链表的所有data域之值*/ nodetype *p=h; printf(输出一个单链表:n ); if(p=NULL) printf(空表); while (p!=NULL) printf(%d ,p-data); p=p-next; printf(n);int len(nodetype *h)/*返回单链表的长度*/ int i=0; nodetype *p=h; while(p!=NULL) p=p-next; i+; return i;node

15、type find(nodetype *h,int i)/*返回第i个节点的指针*/ nodetype *p=h; int j=1; if(ilen(h)|i=0) return NULL;/*i上溢或下溢*/ else while (p!=NULL&jnext; return p; nodetype *ins(nodetype *h,int i,elemtype x)/*单链表head中第i个节点(i=0)之后插入一个data域为x的节点*/ nodetype *p,*s; s=(nodetype *)malloc(sizeof(nodetype);/*创建节点s*/ s-data=x; s

16、-next=NULL; if(i=0)/*i=0:s作为单链表的第一个节点*/ s-next=h; h=s; else p=find(h,i);/*查找第i个节点，并由p指向该节点*/ if(p!=NULL) s-next=p-next; p-next=s; else printf(输入的i值不正确n); return h;nodetype *del(nodetype *n,int i)/*删除第i个节点*/ nodetype *p=h,*s; int j=1; if(i=1)/*删除第一个节点*/ h=h-next; free(p); else p=find(h,i-1);/*查找第i-1个

17、节点，并由p指向该节点*/ if(p!=NULL&p-next!=NULL) s=p-next;/*s指向要删除的节点*/ p-next=s-next; free(s); else printf(输入的i值不正确n); return h;void dispose(nodetype *h)/*释放单链表的所有节点占有的空间*/ nodetype *pa=h,*pb; if(pa!=NULL) pb=pa-next; if(pb=NULL)/*只有一个节点的情况*/ free(pa); else while(pb!=NULL)/*有两个及两个以上的节点的情况*/ free(pa); pa=pb;

18、pb=pb-next; free(pa); 练习2.22/*试写一算法，对单链表实现就地逆置*/#includeslink.cpp#includenodetype *invert(nodetype *h)/*实现单链表逆置*/nodetype *p,*q,*r;if(len(h)next;while(q!=NULL)r=q-next;q-next=p;p=q;q=r;h-next=NULL;h=p;return h;void main()nodetype *head;head=create();disp(head);head=invert(head);disp(head);/*运行结果建立一个

19、单链表 输入第1节点data域值：1输入第2节点data域值：2输入第1节点data域值：3输入第1节点data域值：4输入第1节点data域值：5输入第1节点data域值：0输出一个单链表1 2 3 4 5 输出一个单链表5 4 3 2 1 */练习2.23/*设线性表A=（a1,a2,am）,B=(b1,b2,bn),试写一个按下列规则合并A，B为线性表C的算法，即使得C=（a1,b1,am,bm,bm+1,bm） 当mn时。线性表A，B和C均以单链表做存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显示存储*/#includeslink.cppnodetyp

20、e *combine(nodetype *ha,nodetype *hb)nodetype *hc=ha,*pa=ha,*pb=hb,*q,*r;if(len(pa)!=len(pb)printf(两个单链表长度不同n);return NULL;while(pa!=NULL)q=pa-next;r=pb-next;pa-next=pb;pb-next=q;pa=q;pb=r;return(hc);void main()nodetype *heada,*headb,*headc;heada=create();headb=create();headc=combine(heada,headb);di

21、sp(headc);练习2.26#includeslink.cppnodetype *connect(nodetype *h1,nodetype *h2)nodetype *pa=h1,*pb=h2,*h3,*pc;h3=(nodetype *)malloc(sizeof(nodetype);/*创建哨兵*/pc=h3;/*pc总是指向生成的新单链表的最后一个节点*/while(pa!=NULL&pb!=NULL)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elseif(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-nex

22、t;else/*pa-data=pb-data的情况*/pc-next=pa;pc=pa;pa=pa-next;pb=pb-next;if(pa!=NULL) pc-next=pa;/*h1单链表还有节点时*/if(pb!=NULL) pc-next=pb;/*h2单链表还有节点时*/pc=h3;/*删除哨兵*/h3=h3-next;free(pc);return h3;void main()nodetype *head1,*head2,*head3;head1=create();head2=create();disp(head1);disp(head2);head3=connect(head

23、1,head2);disp(head3);练习2.34#include#includetypedef struct dnodeint data;struct dnode *link;dlist;dlist *xor(dlist *p1,dlist *p2)/*在c/c+中异或运算符不能对地址进行异或运算，因此先将地址值转换为长整形，然后进行异或运算，再将结果强制转换成地址。这是本函数的功能*/int add1,add2,add3;add1=(long)p1;add2=(long)p2;add3=add1add2;return(dlist *)add3;dlist *create(dlist *

24、e)int i=1,x;dlist *head,*r,*s,*pre;printf(创建一个双链表(以0结束)n);while(1)printf( 输入第%d节点值: ,i);scanf(%d,&x);if(x=0)/*生成最后一个节点的link值后退出循环*/pre-link=xor(r,NULL);/*将s-link置为前后节点地址之异或*/*e=pre;break;s=(dlist *)malloc(sizeof(dlist);/*创建一个节点*/s-data=x;if(i=1)/*是第一个节点的情况*/pre=head=s;r=NULL;/*r为当前节点的前一个节点*/elsepre-

25、link=xor(r,s);/*将s-link置为前后节点地址之异或*/r=pre;pre=s;i+;return head;void order(dlist *h,dlist *e)dlist *pre=NULL,*pre1,*p=h;printf(遍历节点序列: );if(h=NULL)printf(空表n);elsewhile(p!=e)/*遍历最后一节点前的所有节点*/printf(%d ,p-data);pre1=p;p=xor(pre,p-link);/*为下一个节点的地址*/pre=pre1;printf(%d ,e-data);printf(n);void main()dlis

26、t *h,*e;int i;h=create(&e);printf(从左向右);order(h,e);printf(从右向左);order(e,h);/*运行结果:创建一个双链表(以0结束) 输入第1节点值:3输入第1节点值:5输入第1节点值:8输入第1节点值:2输入第1节点值:6输入第1节点值:0从左向右遍历节点序列: 3 5 8 2 6 从右向左遍历节点序列: 6 2 8 5 3 */第三章 栈和队列实现栈差不多算法的头文件stack.cpp为：#include#define MaxLen 20/*顺序栈存放的最多元素个数为Maxlen-1*/typedef char elemtype;t

27、ypedef struct sqstackelemtype dataMaxLen;int top;stack;void init(stack *st)/*初始化栈st*/st-top=0;int push(stack *st,elemtype x)/*入栈*/if(st-top=MaxLen-1)printf(栈溢出n);return 0;elsest-top+;st-datast-top=x;return 1;int pop(stack *st,elemtype *x)/*退栈*/if(st-top=0)printf(栈下溢出n);return 0;else*x=st-datast-top;

28、st-top-;return 1;int empty(stack *st)/*推断栈空*/if(st-top=0)return 1;elsereturn 0;int gettop(stack *st,elemtype *x)/*猎取栈顶元素*/if(st-top=0)printf(栈下溢出n);return 0;else*x=st-datast-top;return 1;void disp(stack *st)/*输出栈的所有元素*/int i;for(i=st-top;i0;i-)printf(%d ,st-datai);printf(n);/*练习3.19*/*假设一个算术表达式中能够包含

29、三种括号，圆括号(和)、方括号和和花括号和,且这三种括号可按任意的次序嵌套使用(如:.(.).).编写判不给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中*/*输入：a+b+(c+d)+e+f*/#includestack.cpp#includeint correct(char *str)stack st;char x;int i,ok=1;init(&st);for(i=0;stri!=0;i+)switch(stri)case(:push(&st,();break;case:push(&st,);break;case:push(&st,);break;c

30、ase):if(!(pop(&st,&x)&x=()ok=0;break;case:if(!(pop(&st,&x)&x=)ok=0;break;case:if(!(pop(&st,&x)&x=)ok=0;break;if(!ok) break;if(empty(&st)&ok)return 1;elsereturn 0;void main()char *str;str=(char*)malloc(100*sizeof(char);printf(str: );scanf(%s,str);if(correct(str)printf(表达式括号匹配n);elseprintf(表达式括号不匹配n);

31、 getch();练习3.21#include#define MaxLen 100int trans(char str,char exp)int stMaxLen;/*作为栈使用*/char ch;int i=0,t=0,top=-1;/*t作为exp的下标，top作为st的下标，i作为str的下标*/while(ch=stri+)!=0)if(ch=0 & ch=0 & ch=0 & sttop!=()expt=sttop;top-;t+;top+;sttop=ch;else if(ch=*|ch=/)while (sttop=* | sttop=/)expt=sttop;top-;t+;t

32、op+;sttop=ch;while(top=0)expt=sttop;t+;top-;expt=0;return 1;int compvalue(char exp,int *n)int stMaxLen,d;/*作为栈使用*/char ch;int t=0,top=-1;/*t作为exp的下标，top作为st的下标*/while (ch=expt+1)!=0)if(ch=0 & ch=9)/*为数字字符时转换为数字*/d=0;dod=10*d+ch-0;while(ch=expt+)!=#);top+;sttop=d;/*数字进栈*/else /*为运算符时，计算并退栈*/switch(ch

33、)case+:sttop-1=sttop-1+sttop;break;case-:sttop-1=sttop-1-sttop;break;case*:sttop-1=sttop-1*sttop;break;case/:if(sttop!=0) sttop-1=sttop-1/sttop;elsereturn 0;/*除0错误*/break;top-;(*n)=sttop;return 1;void main()char strMaxLen;/*存储原算术表达式*/char expMaxLen;/*存储转换成的波兰表达式*/int n;printf(算术表达式: );scanf(%s,&str)

34、;if(trans(str,exp)=0)printf(原算术表达式不正确n);elseprintf(波兰表达式: %dn,exp);if(compvalue(exp,&n)=1)printf(计算结果: %dn,n);elseprintf(计算错误n);练习3.27/*已知Ackerman函数的定义如下：Akm(m,n)=n+1(m=0),akm(m-1,1)(m!=0,n=0) akm(m-1),akm(m,n-1)(m!=0,n!=0)1.写出递归算法；2。写出非递归算法；3。依照非递归算法，画出求akm(2,1)时栈的变化过程*/#include#define MaxLen 5000/

35、*此数应足够大，因为m和n值的较小增长会引起函数值的极快增长，用的栈的空间也专门大*/int f1(int m,int n)if(m=0)return n+1;elseif(n=0) return f1(m-1,1);elsereturn f1(m-1,f1(m,n-1);int no(int m,int n)if(m=0)return 1;else if(n=0)return 2;else return 3;int f2(int m,int n)int stMaxLen4,top=1,m1,n1;sttop0=no(m,n);sttop1=0;/*初值0进栈*/sttop2=m;/*初值m进

36、栈*/sttop3=n;/*初值n进栈*/do /*开始循环*/if(sttop1=0)if(sttop0=3)top+;sttop1=0;sttop2=sttop-12;sttop3=sttop-13-1;sttop0=no(sttop2,sttop3);else if(sttop0=2)top+;sttop1=0;sttop2=sttop-12-1;sttop3=1;sttop0=no(sttop2,sttop3);if(sttop0=1)sttop1=sttop3+1;if(top=1&sttop1!=0&sttop-10=2)sttop-11=sttop1;top-;else if(t

37、op=1&sttop1!=0&sttop-10=3)n1=sttop1;m1=sttop-12-1;top-;sttop1=0;sttop2=m1;sttop3=n1;sttop0=no(sttop2,sttop3);if(top=1&sttop1!=0)/*栈中已有一个元素，且已计算出值，则退出循环*/break;while(top=1);return (st11);void main()int n,m;printf(input m n:);scanf(%d %d,&m,&n);printf(digui c(%d,%d)=%dn,m,n,f1(m,n);printf(feidigui c(%

38、d,%d)=%dn,m,n,f2(m,n);system(pause);/*输入：3 8回车digui c(3,8)=2045feidigui c(3,8)=2045*/练习3.28/*假设以带头结点的循环链表表示队列，同时只设一个指针指向队尾结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法*/#include#define MaxSize 6typedef char queueMaxSize;int rear=0,len=0;/*队列初态*/int enqueue(queue qu,char x)if(len=MaxSize)/*队满，上溢出*/return 0;else

39、rear=(rear+1)%MaxSize;qurear=x;len+;/*队列长度增1*/return 1;int dequeue(queue qu,char *x)int front;if(len=0)/*队列为空时下溢出*/return 0;elsefront=(rear-len+1+MaxSize)%MaxSize;*x=qufront;len-;/*队列长度减1*/return 1;void main()char x;queue qu;printf(a入队n);enqueue(qu,a);printf(b入队n);enqueue(qu,b);printf(c入队n);enqueue(

40、qu,c);printf(出队一次:);dequeue(qu,&x);printf(%cn,x);printf(d入队n);enqueue(qu,d);printf(e入队n);enqueue(qu,e); printf(出对一次:);dequeue(qu,&x);printf(%cn,x);printf(f入队n);enqueue(qu,f);printf(g入队n);enqueue(qu,g);printf(出队一次:);dequeue(qu,&x);printf(%cn,x);printf(余下元素出列:);while(len0)dequeue(qu,&x);printf(%c ,x);

41、printf(n);system(pause);练习3.31/*假设称正读和反读都相同的字符序列为“回文”，例如：abba和abcba是回文，abcde和ababab则不是回文。试写一个算法判不读入的一个以为结束符的字符序列是否是回文.*/#include#include#define MaxLen 100typedef struct nodechar data;struct node *next;cnode;cnode *create(char s)int i=0;cnode *h,*p,*r;while(si!=0)p=(cnode *)malloc(sizeof(cnode);p-dat

42、a=si;p-next=NULL;if(i=0)h=p;r=h;/*r始终指向最后一个结点*/elser-next=p;r=p;i+;return h;int judge(cnode *h)char stMaxLen;int top=0;cnode *p=h;while (p!=NULL)sttop=p-data;top+;p=p-next;p=h;while(p!=NULL)top-;if(p-data=sttop)p=p-next;elsebreak;if(p=NULL)return 1;elsereturn 0;void main() char strMaxLen;cnode *h;pr

43、intf(输入一个字符序列：);scanf(%s,str);h=create(str);if(judge(h)=1)printf(%s是回文,str);elseprintf(%s不是回文,str);getch();第四章 串实现串差不多运算的头文件string.cpp为:#include#include#define MaxLen 20typedef strcutchar chMaxLen;int len;strtype;void create(strtype *s,char str)/*将一般字符串赋给串*/strcpy(s-ch,str);s-len=strlen(str);int len

44、gth(strtype *s)/*求串长度*/return s-len;void copy(strtype *s1,strtype *s2)/*串的复制*/int i;for(i=0;ilen;i+)s2-chi=s1-chi;s2-len=s1-len;s2-chs2-len=0;/*添加字符串结束符*/strtypr subs(strtype *s,int pos,int n)/*求子串*/int i;strtype sub;if(pos+n-1length(s1)/*参数不正确*/sub.len=0;elsefor(i=pos-1;ichi;sub.len=n;sub.chsub.len

45、=0;return sub;int concat(strtype *s,strtype *t)/*连接两个串*/int i;if(s-len+t-lenMaxLen)return 0;for(i=0;ilen;i+)s-chi+s-len=t-chi;s-len=s-len+t-len;s-chs-len=0;return 1;int ins(strtype *s,strtype *t,int i)/*插入一个子串*/int j;if(s-len+t-lenMaxLen)return 0;for(j=s-len-1;j=i-1;j-)/*i之后的所有元素后移t-len个位置*/s-chj+t-

46、len=s-chj;for(j=0;jlen;j+)s-chj+i-1=t-chj;s-len=s-len+t-len;s-chs-len=0;return 1;int del(strtype *s,int pos,int n)/*删除一个子串*/int i;if(pos+ns-len)for(i=pos+n-1;ilen;i+)s-chi-n=s-chi;s-len=s-len-n;s-chs-len=0;return 1;void disp(strtype *s)/*输出串*/if(s-len=0)printf(空串n);elseprintf(%dn,s-ch);练习4.6#include

47、#includestring.cppstrtype replace(strtype *s1,int i,int j,strtype *s2)strtype s;int n,k;if(i+j-1len)for(n=0;nchn;for(n=0;nchn)/*连接s2串*/s.chi+n-1=s2-chn;s.len=i+s2-len-1;for(n=s.len,k=i+j-1;klen;n+,k+)/*连接s1的位置i及之后的字符*/s.chn=s1-chk;s.len=n;s.chs.len=0;elses.ch0=0;s.len=0;return (s);void main()strtype

48、 s,s1,s2,s3,s4,s5,s6;create(&s, (xyz)+*);printf(s=);disp(&s);s1=subs(&s,7,1);/*s1=*/s2=subs(&s,3,1);/*s2=y*/s3=subs(&s,6,1);/*s3=+*/s4=replace(&s,3,1,&s3);s5=replace(&s4,6,1,&s1);s6=replace(&s5,7,1,&s2);printf(t=);disp(&s6);练习4.20#include#includestring.cppint index(strtype *s1,strtype *s2)int i=0,j,

49、k;while (ilen)j=0;if(s1-chi=s2chj)k=i+1;j+;while(klen & jlen & s1-chk=s2-chj)k+;j+;if(j=s2-len)/*s2中止时找到了子串*/break;else i+;else i+;if(is1-len)return -1;elsereturn (i+1);void delall(strtype *s1,strtype *s2)int n;n=index(s1,s2);while(n=0)del(s1,n,length(s2);n=index(s1,s2);diap(s1);void main()strtype s

50、1,s2;char strMaxLen;printf(字符串: );gets(str);create(&s1,str);printf(子串: );gets(str);create(&s2,str);delall(&s1,&s2);第五章 数组与广义表实现广义表差不多运算的头文件list.cpp如下:#include#include#include#define MaxLen 100typedef struct node/*定义广义表结构*/int tag;/*只取0（原子节点）或1（表节点）*/struct node *link;/*后继节点*/unionchar data;struct no

51、de *slist;/*子表*/val;gnode;void disastr(char s,char hstr)/*本函数为辅助建立广义表的函数从字符串s中取出第一个,之前的子串赋给hstr,并使s成为删除子串hstr和,之后的剩余串。若串s中没有字符,，则操作后的hstr为操作前的s,而操作后的s为空串*/int i=0,j=0,k=0,r=0;char rstrMaxLen;while(si&(si!=,|k)if(si=() k+;else if(si=) k-;if(si!=,|si=,&k)hstrj=si;i+;j+;hstrj=0;if(si=,) i+;while(si)rst

52、rr=si;r+;i+;rstrr=0;strcpy(s,rstr);gnode *create(char s)/*从字符串表示创建广义表*/gnode *p,*q,*r,*gh;char subsMaxLen,hstrMaxLen;int len;len=strlen(s);if(!strcmp(s,()/*空表的情况*/gh=NULL;elseif(len=1)/*原子的情况*/gh=(gnode *)malloc(sizeof(gnode);/*建立一个新节点*/gh-tag=0;/*构造原子节点*/gh-val.data=*s;gh-link=NULL;else/*子表的情况*/gh=

53、(gnode *)malloc(sizeof(gnode);/*建立一个新节点*/gh-tag=1;p=gh;s+;/*除掉前面的一个(*/strncpy(subs,s,len-2);subslen-2=0;dodisastr(subs,hstr);/*将subs分为表头和表尾*/r=create(hstr);p-val.slist=r;q=p;len=strlen(subs);if(len0)p=(gnode *)malloc(sizeof(gnode);p-tag=1;q-link=p;while(len0);q-link=NULL;return(gh);void disp(gnode *

54、h)/*以字符串方式输出广义表*/gnode *p,*q;printf();if(h)dop=h-val.slist;q=h-link;while(q&p&!p-tag)/*为原子且有后继节点的情况*/printf(%d ,p-val.data);p=q-val.slist;q=q-link;if(p&!p-tag)/*为原子之后继节点的情况*/printf(%d,p-val.data);break;else/*为子表的情况*/if(!p)printf();else disp(p);if(q)printf(,);h=q;while(h);printf();int locate(gnode *p

55、,char x)/*推断x是否在广义表中*/int find=0;if(p!=NULL)if(!p-tag&p-val.data=x)return(1);else if(p-tag)find=locate(p-val.slist,x);if(find)return(1);elsereturn(locate(p-link,x);elsereturn(0);练习5.31/*复制广义表*/#includelist.cppvoid gcope(gnode *p,gnode *q)if(p=NULL);q=NULL;elseq=(gnode *)malloc(sizeof(gnode);/*创建一个节点

56、*/q-tag=p-tag;if(p-tag=0)q-val.data=p-val.data;/*原子节点直接复制*/elsegcopy(p-val.slist,q-val.slist);gcopy(p-link,q-link);void main()gnode *p,*q;char strMaxLen;printf(输入广义表表达式: );scanf(%s,str);p=create(str);printf(原来的广义表: );disp(p);gcopy(p,q);printf(n复制的广义表: );disp(q);printf(n);练习5.32/*判不广义表是否相等的递归算法*/#inc

57、ludelist.cppint same(gnode *p,gnode *q)int flag=1;if(p!=NULL&q!=NULL)if(p-tag=0&p-tag!=0)if(p-val.data!=q-val.data)flag=0;else if(p-tag=1&q-tag=1)flag=same(p-val.slist,q-val.slist);else flag=0;if(flag)flag=same(p-link,q-link);elseif(p=NULL&q!=NULL)flag=0;if(p!=NULL&q=NULL)flag=1;return (flag);void m

58、ain()gnode e,*g1,*g2,*g3;g1=create(a,(b,c,d),e,(f);g2=create(a,(b,c,d),e,(f);g3=create(a,(b),(c,d),e,(f);printf(广义表g1: ); disp(g1);printf(n);printf(广义表g2: ); disp(g2);printf(n);printf(广义表g3: ); disp(g3);printf(n);printf(g1与g2:);printf(same(g1,g2)=0)?不同: 相同);printf(n);printf(g1与g3:);printf(same(g1,g3

59、)=0)?不同: 相同);练习5.34/*逆置广义表*/#includelist.cppvoid reverse(gnode *p,gnode *&q)gnode *r,*s,*t,*b;if(p=NULL)q=NULL;elseif(p-tag=0)/*为原子的情况*/s=(gnode *)malloc(sizeof(gnode);/*复制该原子节点*/s-tag=0;s-val.slist=NULL;s-val.data=p-val.data;q=s;else/*为表的情况*/reverse(p-val.slist,s);/*处理表头*/if(p-link!=NULL)reverse(p-

60、link,t);/*产生表尾的逆置广义表t*/b=(gnode *)malloc(sizeof(gnode);/*给表头加上一个子表节点*/b-tag=1;b-link=NULL;b-val.slist=s;q=t;r=t;while(r-link!=NULL)/*找到第一层的 最后一个节点*/r=r-link;r-link=b;/*连接*/else/*p-link=NULL*/q=(gnode *)malloc(sizeof(gnode);/*创建表头节点q*/ q=tag=1;q-link=NULL;q-val.slist=s;void main()gnode *g1,*g2;g1=cre