【数据结构算法】数组、串和广义表

1、数据结构算法数据结构算法 Visual C+ 6.0程序集程序集 侯侯 识识 忠忠 等编著等编著 中国水利水电出版社中国水利水电出版社 第三章 数组、串和广义表 3、0 变长参数表的应用 / 变长参数表的应用VLArgument.cpp #include #include #include double average( int, .); void main() double w=36.5,x=21.5,y=1.9,z=10.1; coutVLArgument.cpp运行结果:n; coutsetiosflags(ios:fixed|ios:showpoint) setprecision(1)

2、w = wnx = x ny = ynz = zendl; coutsetprecision(3)The average of w and x is average(2,w,x) nThe average of w, x, and y is average(3,w,x,y) nThe average of w, x, y, and z is 单击此处运行程序 average(4,w,x,y,z)endl;cin.get(); double average(int i, .) double total=0; va_list ap; va_start( ap, i ); for(int j=1;j

3、size1(); ; /intarray.cpp /建立一维,二维数组的类实现 /数组下标从1开始,引用下标作下标越界检查 #include #include #include intarray.h void IntArray1:init(int n) if(n1) coutError dimension description; exit(1); size=n; data=new intsize; int delete data; exit(2); return datai-1;/IntArry1的下标从1开始 void IntArray1:ReArray(int si) if(si1) c

4、err长度无效!n;exit(1); if(si=size) return; int *newArray=new intsi; if(!newArray) cerr内存分配失败!n;exit(1); int n=(si=size)?si:size; int *souceP=data; int *destP=newArray; while(n-) *destP+=*souceP+; delete data; data=newArray; size=si; IntArray2:IntArray2(int m,int n) if(m1|n1) coutError dimension descript

5、ion; exit(1); size=m; data=new IntArray1size; for(int i=0;isize;i+) datai.init(n); IntArray1 delete data; exit(1); return datai-1;/IntArry2的下标从1开始 /建立一维,二维数组的类测试intarraym.cpp #include #include #include #include intarray.cpp void main() coutintarraym.cpp运行结果:n; int i,j; IntArray1 a(10); cout数组a长度=a.s

6、ize1()endl; srand(120); for(i=1;i=10;i+) ai=rand()%10; 单击此处运行程序 coutsetw(3)ai; coutendl; a.ReArray(12); cout重定义数组a长度=a.size1()endl; for(i=1;i=12;i+) ai=rand()%10; coutsetw(3)ai; coutendl; IntArray2 b(3,4); for(i=1;i=b.size1();i+) for(j=1;j=b.size2();j+) bij=rand()%12; cout二维数组b:n; for(i=1;i=b.size1(

7、);i+) for(j=1;j=b.size2();j+) coutsetw(4)bij; coutendl; coutendl;cin.get(); 3、2 稀疏矩阵的类定义与操作 /稀疏矩阵的类定义与操作xishu.h /假设非0元个数的最大值为100 #define MAXSIZE 100 /三元组顺序表 class TSMatrix; class Triple public: int ii,jj;/行号和列号 ElemType e; friend class TSMatrix; ; class TSMatrix public: /构造函数 TSMatrix( ) /构造函数 /创建一个

8、Mrow行,Mcol列且非零元个数为t的稀疏矩阵 TSMatrix(int Mrow,int Mcol,int t); /求稀疏矩阵的转置矩阵 void TrMatrix(TSMatrix /快速转置 void FastTrMatrix(TSMatrix /稀疏矩阵相乘 void mulmatrix(TSMatrix Triple dataMAXSIZE;/非0三元组表 int mu,nu,tu;/稀疏矩阵的行数、列数和非零元个数 ; /创建一个Mrow行,Mcol列且非零元个数为t的稀疏矩阵 TSMatrix:TSMatrix(int Mrow,int Mcol,int t) int m,n

9、,i,j,f0=0; if(t=0) exit(0); ElemType (*A)MCOL=new ElemTypeMROWMCOL; if(!A)cerr内存分配失败!n;exit(-1); for(i=0;iMrow;i+) for(j=0;jMcol;j+) Aij=0; srand(150); while(f0=0 if(Amn!=0) f0+; for(i=0;iMrow;i+) for(j=0;jMcol;j+) coutsetw(3)Aij; coutendl; /求稀疏矩阵的转置矩阵 void TSMatrix:TrMatrix(TSMatrix T.mu=nu;T.nu=mu

10、;T.tu=tu; if(T.tu) /如果T的非0元个数不为0 q=0; for(col=0;colnu;+col) for(p=0;ptu;+p) if(datap.jj=col) T.dataq.ii = datap.jj; T.dataq.jj = datap.ii; T.dataq.e = datap.e; +q; /快速转置 void TSMatrix:FastTrMatrix(TSMatrix T.mu=nu;T.nu=mu;T.tu=tu; if(T.tu) for(col=0;colnu;+col) numcol = 0; /先置M每列非0元个数均为0 for(t=0;ttu

11、;+t) +numdatat.jj; /求M中每一列非0元个数 cpot0=0; /M中第一列第一个非元在T中的序号为1 for(col=1;colnu;+col) cpotcol=cpotcol-1+numcol-1; /求M中第col列中第一个非0元在T中的序号 for(p=0;ptu;+p) col=datap.jj; /记下M中第p个元素的列号 q=cpotcol; /该列中第一个非0元在T中的序号 T.dataq.ii=datap.jj; T.dataq.jj=datap.ii; T.dataq.e=datap.e;/行、列交换,并赋值 +cpotcol; /该列下一个非0元序号=上

12、一个序号+1 /稀疏矩阵相乘 void TSMatrix: mulmatrix(TSMatrix if(nu!=b.mu) cerrerrorn; exit(0); if(tu*b.tu!=0) int *rowSize=new intb.mu; int *rowStart=new intb.mu+1; ElemType *temp=new ElemTypeb.nu; for(i=0;ib.mu;i+) rowSizei=0; for(i=0;ib.tu;i+) rowSizeb.datai.ii+; rowStart0=0; for(i=1;i=b.mu;i+) rowStarti=rowS

13、tarti-1+rowSizei-1; int current=0,lastInresult=-1; while(currenttu) rowA=datacurrent.ii; for(i=0;ib.nu;i+) tempi=0; while(currenttu for(i=rowStartcolA;irowStartcolA+1;i+) colB=b.datai.jj; tempcolB+=datacurrent.e*b.datai.e; current+; for(i=0;ib.nu;i+) if(tempi!=0) lastInresult+; c.datalastInresult.ii

14、=rowA; c.datalastInresult.jj=i; c.datalastInresult.e=tempi; c.mu=mu;c.nu=b.nu;c.tu=lastInresult+1; delete rowSize;delete rowStart;delete temp; /稀疏矩阵相关操作的测试xishuM.cpp #include #include #include #include typedef int ElemType; #define L 6 #define N 7 const int MROW=3; const int MCOL=4; #include xishu.h

15、 /三元组顺序表的输出 void print(TSMatrix a) cout i j en; for(int k=0;ka.tu;k+) coutsetw(4)a.datak.ii; coutsetw(4)a.datak.jj; coutsetw(4)a.datak.eendl; void main() coutxishuM.cpp运行结果:n; int bNL,i,j,k=0; int aLN=0,12,9,0,0,0,0,0,0,0,0,0,0,0,-3,0,0,0,0,14,0, 0,0,24,0,0,0,0,0,18,0,0,0,0,0,15,0,0,-7,0,0,0; TSMatr

16、ix a1,b1,c1; a1.mu=L;a1.nu=N;a1.tu=0; cout稀疏矩阵a1:n; for(i=0;iL;i+)/输出数组a1 for(j=0;jN;j+) coutsetw(3)aij; coutn; /创建三元组顺序表 for (i=0;iL;i+) for (j=0;jN;j+) if (aij!=0) a1.datak.ii=i; a1.datak.jj=j; a1.datak.e=aij; a1.tu+;k+; cout原三元组顺序表a1:n; print(a1); cout按任意键继续.n;getch(); a1.TrMatrix(c1); for (i=0;i

17、N;i+)/初始化数组 for (j=0;jL;j+) bij=0; for (k=0;kc1.tu;k+) bc1.datak.iic1.datak.jj=c1.datak.e; cout转置矩阵 c1:n; for (i=0;iN;i+) for (j=0;jL;j+) coutsetw(3)bij; coutn; cout转置矩阵三元组顺序表:n; print(c1); cout按任意键继续.n;getch(); a1.FastTrMatrix(b1); for (i=0;iN;i+)/initial array_b for (j=0;jL;j+) bij=0; for (k=0;kb1

18、.tu;k+) bb1.datak.iib1.datak.jj=b1.datak.e; cout转置矩阵 b1:n; for (i=0;iN;i+) for (j=0;jL;j+) coutsetw(3)bij; coutn; int p34=10,0,5,7,2,1,0,0,3,0,4,0; int w42=2,0,4,8,0,14,3,5; TSMatrix aa,bb,cc; aa.mu=3;aa.nu=4;aa.tu=0; bb.mu=4;bb.nu=2;bb.tu=0; /创建三元组顺序表 for (k=0,i=0;i3;i+) for (j=0;j4;j+) if (pij!=0)

19、 aa.datak.ii=i;aa.datak.jj=j; aa.datak.e=pij; aa.tu+;k+; 单击此处运行程序 /创建三元组顺序表 for (k=0,i=0;i4;i+) for (j=0;j2;j+) if (wij!=0) bb.datak.ii=i;bb.datak.jj=j; bb.datak.e=wij; bb.tu+;k+; aa.mulmatrix(bb,cc); cout乘积矩阵三元组顺序表:n; print(cc); cout创建的稀疏矩阵:n; TSMatrix ff(MROW,MCOL,4); cout按任意键结束!n;getch(); 3、3 十字链

20、表的定义与相关操作 /十字链表的定义与相关操作xishuM1.cpp #include #include #include typedef int ElemType; /十字链表 struct OLNode int ii,jj; /非0元的行和列下标 struct OLNode *right,*down; union ElemType e; struct OLNode *next;tag; ; /创建十字链表 struct OLNode *CreateOLSMat() int m,n,t,s,r,i,c,v; struct OLNode *h100,*p,*q; coutmnt; p=new

21、struct OLNode;if(!p) exit(-1); h0=p; p-ii=m; p-jj=n; s=mn?m:n; for(i=1;itag.next=p; p-ii=p-jj=0; p-down=p-right=p; hs-tag.next=h0; cout按任意次序输入行号r,列号c和非0元v:n; for(i=1;ircv; p=new struct OLNode;if(!p) exit(-1); p-ii=r; p-jj=c; p-tag.e=v; q=hr; while(q-right!=hr p-right=q-right; q-right=p; q=hc; while(

22、q-down!=hc p-down=q-down; q-down=p; return h0; void prmat(struct OLNode *hh) struct OLNode *p,*q; cout按行输出矩阵元素:n; cout行数=ii 列数=jjendl; couttag.next; while(p!=hh) q=p-right; while(p!=q) coutsetw(3)ii; coutsetw(3)jj; coutsetw(3)tag.eright; p=p-tag.next; void main() coutxishuM1.cpp运行结果:n; struct OLNode

23、 *dd; dd=CreateOLSMat(); prmat(dd); cin.get();cin.get(); 3、5 十字链表的定义与相关操作 /十字链表的类定义与相关操作xishuM2.cpp #include #include #include typedef int ElemType; class CrossList; class OLNode /十字链表 public: int ii,jj; /非0元的行和列下标 ElemType e; /该非0元所在的行表和列表的后继链域 OLNode *right,*down; friend class CrossList; ; typedef

24、 class OLNode *OLink; class CrossList public: OLink *rHead,*cHead; /行指针和列指针 int mu,nu,tu; /稀疏矩阵的行数、列数和非0元个数 /创建稀疏矩阵,用十字链表存储表示 void CreateOLSMatrix(); ; void CrossList:CreateOLSMatrix() int m,n,t,i,j,e,k,s; OLink p,q; coutmnt; mu=m;nu=n;tu=t; s=mn?m:n; rHead=new OLinks;if(!rHead) exit(-1); cHead=new

25、OLinks;if(!cHead) exit(-1); for(k=0;ks;k+) rHeadk=cHeadk=NULL; /初始化行列头指针指向空链表 coutije;i!=-1;cinije) p=new OLNode;if(!p) exit(-1); p-ii=i;p-jj=j;p-e=e; /生成结点 p-right=NULL;p-down=NULL; if(rHeadi=NULL) rHeadi=p; else /寻找在行表中的插入位置 for(q=rHeadi;(q-right) q-right=p; /完成插入 if(cHeadj=NULL) cHeadj=p; else /寻

26、找在列表中的插入位置 for(q=cHeadj;(q-down) q-down=p;/完成插入 cout按行输出矩阵元素:n; cout行数=mu 列数=nuendl; cout i j en; for(i=0,p=rHead0;itu;p=rHead+i) q=p; while(!(q=NULL) coutsetw(3)ii; coutsetw(3)jj; coutsetw(3)eright; 单击此处运行程序 /十字链表相关操作的测试 void main() coutxishuM2.cpp运行结果:n; CrossList dd; dd.CreateOLSMatrix(); cin.get

27、();cin.get(); 3、5 十字链表的定义与相关操作 /十字链表的定义与相关操作xishuM3.cpp #include #include #include typedef int ElemType; /十字链表 typedef struct OLNode int ii,jj; /非0元的行和列下标 ElemType e; /该非0元所在的行表和列表的后继链域 struct OLNode *right,*down; *OLink; typedef struct OLink *rHead,*cHead; /行指针和列指针 int mu,nu,tu; /稀疏矩阵的行数、列数和非0元个数 C

28、rossList; /创建稀疏矩阵M.用十字链表存储表示 void CreateOLSMatrix(CrossList OLink p,q; coutmnt; M.mu=m;M.nu=n;M.tu=t; s=mn?m:n; M.rHead=new OLinks;if(!M.rHead) exit(-1); M.cHead=new OLinks;if(!M.cHead) exit(-1); for(k=0;ks;k+) M.rHeadk=M.cHeadk=NULL; /初始化行列头指针指向空链表 coutije;i!=-1;cinije) p=new OLNode;if(!p) exit(-1)

29、; p-ii=i;p-jj=j;p-e=e; /生成结点 p-right=NULL;p-down=NULL; if(M.rHeadi=NULL) M.rHeadi=p; else /寻找在行表中的插入位置 for(q=M.rHeadi;(q-right) q-right=p; /完成插入 if(M.cHeadj=NULL) M.cHeadj=p; else /寻找在列表中的插入位置 for(q=M.cHeadj;(q-down) q-down=p;/完成插入 cout按行输出矩阵元素:n; cout行数=M.mu 列数=M.nuendl; cout i j en; for(i=0,p=M.rH

30、ead0;iM.tu;p=M.rHead+i) q=p; while(!(q=NULL) coutsetw(3)ii; coutsetw(3)jj; coutsetw(3)eright; 单击此处运行程序 void main() coutxishuM3.cpp运行结果:n; CrossList dd; CreateOLSMatrix(dd); cin.get();cin.get(); 3、6 十字链表的定义与相关操作 /十字链表的类定义与相关操作xishuM4.cpp #include #include #include typedef int ElemType; class OLNode/十

31、字链表 public: int ii,jj; /非0元的行和列下标 OLNode *right,*down; union ElemType e; OLNode *next;tag; OLNode *CreateOLSMat(); void prmat(OLNode *hh); ; /创建十字链表 OLNode *OLNode:CreateOLSMat() int m,n,t,s,r,i,c,v; OLNode *h100,*p,*q; coutmnt; p=new OLNode;if(!p) exit(-1); h0=p; p-ii=m; p-jj=n; s=mn?m:n; for(i=1;i

32、tag.next=p; p-ii=p-jj=0; p-down=p-right=p; hs-tag.next=h0; cout按任意次序输入行号r,列号c和非0元v:n; for(i=1;ircv; p=new OLNode;if(!p) exit(-1); p-ii=r; p-jj=c; p-tag.e=v; q=hr; while(q-right!=hr p-right=q-right; q-right=p; q=hc; while(q-down!=hc p-down=q-down; q-down=p; return h0; void OLNode:prmat(OLNode *hh) OL

33、Node *p,*q; cout按行输出矩阵元素:n; cout行数=ii 列数=jjendl; couttag.next; while(p!=hh) q=p-right; while(p!=q) coutsetw(3)ii; coutsetw(3)jj; coutsetw(3)tag.eright; p=p-tag.next; /十字链表相关操作的测试 void main() coutCreateOLSMat(); dd-prmat(tt); cin.get();cin.get(); 3、7 广义表的类定义和实现 /广义表的类定义guangyi.h #include #include #in

34、clude typedef enumINTGR,CH,LSTElemTag; class GList public: ElemTag utype; GList *first; union int intinfo; char charinfo; GList *hlink; ; /构造函数 GList() /返回由elem指示的表元素的值 GList /返回表元素elem的元素值的数据类型 int nodetype(GList *elem) return elem-utype; /将由elem指示的表元素的值修改为x GList /判断广义表是否相等的重载函数 int operator =(GLi

35、st /判断广义表是否相等 int equal(GList *s,GList *t); /返回由ls指示的广义表的第一个元素的值 GList /返回广义表除第一个元素以外其它元素组成的表 GList *Tail(); /返回广义表的第一个元素 GList *First(); /返回由elem指示的表元素的直接后继元素 GList *Next(GList *elem); /返回一个以x为头,由ls指示的广义表为尾的新表 GList *Addon(GList *ls,GList /由ls指示的广义表的复制 GList *Copy(GList *ls); /求由ls指示的非递归表的深度 int de

36、pth(GList * /判断广义表是否为空 bool GlistEmpty() return first=NULL; /将广义表的头元素重置为x void setHead(GList * /将elem2插到表中元素elem1后 void setNext(GList *elem1,GList *elem2); /将x定义为由ls指示的广义表的尾 void setTail(GList * /插入元素x作为由ls指示的广义表的第一元素 GList *InsertGL(GList * /删除广义表中含数x或结点x的操作 GList *delvalue(GList * /删除广义表中含数x或结点x的操

37、作 GList *delvalue(GList * /S是广义表的书写形式串,由S创建广义表GL GList *CreateGList(char * /建立广义表时调用的过程 int sever(char * /广义表的输出 void prtGlist(GList *h); ; /广义表的类实现guangyi.cpp /返回由elem指示的表元素的值 GList pitem-utype=elem-utype; if(elem-utype=LST) pitem-hlink=elem-hlink; if(elem-utype=INTGR) pitem-intinfo=elem-intinfo; i

38、f(elem-utype=CH pitem-first=elem-first; return *pitem; /将由elem指示的表元素的值修改为x GList if(x.utype=INTGR) elem-intinfo=elem-intinfo; if(x.utype=CH return *elem; /返回由ls指示的广义表的第一个元素的值 GList if(ls=NULL) coutfirst; temp=ls; if(ls-utype=INTGR) temp-intinfo=ls-intinfo; if(ls-utype=CH) temp-charinfo=ls-charinfo;

39、temp-first=ls; return *temp; /返回广义表除第一个元素以外其它元素组成的表 GList *GList:Tail() if(first=NULL) coutfirst; /返回广义表的第一个元素 GList *GList:First() if(hlink=NULL) return NULL; else return hlink; /返回由elem指示的表元素的直接后继元素 GList *GList:Next(GList *elem) if(elem-first=NULL) return NULL; else return elem-first; /插入元素x作为由ls

40、指示的广义表的第一元素 GList *GList:InsertGL(GList * else static GList *temp=new GList; temp-utype=x.utype; temp-first=ls-first; temp-intinfo=info; ls-hlink=temp; ls-first=temp; return ls; /返回一个以x为头,由ls指示的广义表为尾的新表 GList *GList:Addon(GList *ls,GList p-utype=x.utype; if(x.utype=INTGR) p-intinfo=info; i

41、f(x.utype=CH) p-charinfo=x.charinfo; p-first=Copy(ls); ls=p; return ls; /将广义表的头元素重置为x void GList:setHead(GList * temp-utype=x.utype; if(x.utype=INTGR) temp-intinfo=info; if(x.utype=CH temp-first=ls-first-first; ls-first=temp; ls-hlink=temp; /将elem2插到表中元素elem1后 void GList:setNext(GList *elem1,GL

42、ist *elem2) GList *temp; while(elem1-first!=NULL) temp=elem1-first; elem2-first=temp-first; delete temp; elem1-first=elem2; /将x定义为由ls指示的广义表的尾 void GList:setTail(GList * temp-utype=x.utype; if(x.utype=INTGR) temp-intinfo=info; if(x.utype=CH r=ls; while(!(r-charinfo!=)r=r-first; q=p-first; p-firs

43、t=temp; temp-first=q; /由ls指示的广义表的复制 GList *GList:Copy(GList *ls) static GList *gh,*q,*p=new GList; q=p; if(ls) do gh=new GList; p-utype=ls-utype; switch(ls-utype) case INTGR:p-intinfo=ls-intinfo;break; case CH:p-charinfo=ls-charinfo;break; case LST:p-hlink=ls-hlink;break; p-first=ls-first; ls=ls-fir

44、st; p=gh; while(ls-first!=NULL); p-first=NULL; return q; /求由ls指示的非递归表的深度 int GList:depth(GList * int m=0; if(temp-first=NULL) return 0; do if(temp-utype=LST) m+; temp=temp-first; while(temp!=NULL); return m; /判断广义表是否相等的重载函数 int GList:operator =(GList return k; /判断广义表是否相等 int GList:equal(GList *s,GLi

45、st *t) int x; if(s-first=NULL if(s-first=NULL else x=0; else if(s-first-utype=CH) if(s-first-charinfo=t-first-charinfo) x=1; else x=0; else x=equal(s-first-first,t-first-first); if(x) return equal(s-first,t-first); return 0; /删除广义表中含数x或结点x的操作 GList *GList:delvalue(GList * p=ls; while(ls!=NULL) p=ls-

46、first; while(p!=NULL delete p; p=r;break; if(p=r)ls-first=r;break; ls=ls-first; return q; /删除广义表中含数x或结点x的操作 GList *GList:delvalue(GList * p=ls; while(ls!=NULL) p=ls-first; while(p!=NULL delete p; p=r;break; if(p=r)ls-first=r;break; ls=ls-first; return q; /S是广义表的书写形式串,由S创建广义表GL GList *GList:CreateGLi

47、st(char * p=q=new GList; p-first=NULL; char *sub=new char30; char *hsub=new char30; for(int i=0;i30;i+) hsubi=subi=0; strncpy(sub,s,strlen(s); substrlen(s)=0; cout欲创建的广义表=sendl; cout广义表的长度=strlen(s)first=NULL; else do sever(sub,hsub); if(strlen(hsub)=1) if(48=hsub0 p-utype=INTGR;p-intinfo=atoi(hsub)

48、; p-first=r;p=r; else if(65=hsub0 p-utype=CH;p-charinfo=hsub0; p-first=r;p=r; else if(hsub0=() r=new GList;r-first=NULL; p-utype=LST;p-hlink=r; p-first=r;p=r; while(*sub!=0); p-first=NULL; return q; /建立广义表时调用的过程 int GList:sever(char *int i=0,k=0,j=0; int n=strlen(str1); static int m=1; if(m=1) while

49、(jn|k!=0) ch=str1j;j+;m+; if(ch=0) break; if(ch=() k+; else if(ch=) k-; if(k!=0) return 0; for(i=0;in;+i) ch=str1i; if(ch=0) break; if(ch=,) for(int i0=i;i01) strncpy(hstr1,str1,1); strncpy(str1,str1+1,n-1);str1n-1=0; return 1; else if(n=1) strncpy(hstr1,str1,1); str10=0;return 1; else return 0; /广义

50、表的输出 void GList:prtGlist(GList *h) GList *q,*p=h; if(h) do if(p-utype=INTGR) q=p-first; if(q-charinfo=)|q-first=NULL) coutintinfo; else coutintinfofirst; else if(p-utype=CH) q=p-first; if(q-charinfo=)|q-first=NULL) coutcharinfo; else coutcharinfofirst; else if(p-utype=LST) coutfirst; while(p-first!=

51、NULL); /广义表的相关操作的测试guangyiM.cpp #include #include #include #include #include guangyi.h #include guangyi.cpp static GList *GL,*GL1,*GL2,*GL3; static GList GU,GU1,GU2,GU3,GU4; void main() coutguangyiM.cpp运行结果:n; char *a=(A,(B),(3,5,7),(a,b),(C),D); char *b=(A,(B),(3,5),(a,b),7); char *c=(9,(B),(3,5),(

52、a,b); GU3.utype=INTGR;GU3.intinfo=9; GU3.first=GL2; GL=GU.CreateGList(a); cout返回的指针值GL=GLendl; cout创建后的广义表=; GU.prtGlist(GL); coutn广义表GL的深度=GU.depth(GL); GL=GU.delvalue(GL,5); coutn删除5后的广义表GL=;GU.prtGlist(GL); GL=GU.delvalue(GL,a); coutn删除a后的广义表GL=;GU.prtGlist(GL); coutn将GU3定义为由ls指示的广义表的尾:; GU.setTa

53、il(GL,GU3);GU.prtGlist(GL); coutn重置广义表的头元素后的广义表:; GU.setHead(GL,GU3);GU.prtGlist(GL); GL1=GU.Copy(GL); coutn复制后的广义表GL1=; GU.prtGlist(GL1); coutn广义表GU的第一个元素的值:n; GU2=GU.Head(GL1); coutGU2.utype=GU2.utype; if(GU2.utype=INTGR) cout,GU2.intinfo=GU2.intinfoendl; if(GU2.utype=CH) cout,GU2.charinfo=GU2.cha

54、rinfoendl; GU=GU.Info(GL1); cout广义表GU的第一个元素的值:n; coutGU.utype=utype=INTGR) cout,GU.intinfo=GU.intinfoutype=CH) cout,GU.charinfo=GU.charinfoendl; GL2=GU1.CreateGList(b); if(GU.operator =(GU1) cout广义表GU与GU1相等!n; else cout广义表GU与GU1不等!n; cout修改广义表GU1的表头后的广义表:; GL2=GU1.InsertGL(GL2,GU3); GU1.prtGlist(GL2

55、); GU1=*GL2; coutn广义表GU1除第一个元素以外其它元素组成的表:; GL2=GU1.Tail();cout(; GU1.prtGlist(GL2);coutendl; 单击此处运行程序 GL3=GU4.CreateGList(c); cout创建后的广义表=; GU4.prtGlist(GL3); coutn以GU3为头,由GL3指示的广义表为尾 的新表:; GU3.utype=CH;GU3.charinfo=F; GU3.first=NULL; GL3=GU4.Addon(GL3,GU3);cout(; GU4.prtGlist(GL3);cout); getch(); 3

56、、8 字符串的模式匹配 /字符串的模式匹配Findstr.cpp #include #include #include #include #include #define MAXSTRLEN 64 void GetNext(char TMAXSTRLEN,int (i=1;next1=j=0; while(i(int)T0) if(j=0|Ti=Tj) +i;+j;nexti=j; else j=nextj; for(j=1;j(int)T0;j+) printf(next%d=%-3d,j,nextj); if(j)%5=0) printf(n); coutendl; void GetNex

57、t(char TMAXSTRLEN,int (i=0;next0=-1; for(j=1;j=0) i=nexti; if(Tj=Ti+1) nextj=i+1; else nextj=-1; for(j=0;j=m;j+) printf(next%d=%-3d,j,nextj); if(j+1)%5=0) printf(n); coutendl; void GetNextVal(char TMAXSTRLEN,int (i=1;next1=j=0; while(i(int)T0) if(j=0|Ti=Tj) +i;+j; if(Ti!=Tj) nexti=j; else nexti=next

58、j; else j=nextj; for(i=1;i(int)T0;i+) printf(next%d=%-3d,i,nexti); if(i%5=0) coutendl; coutendl; int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (i=j=1; n=(int)S0;m=(int)T0; while(in|j=m) return i+1-m; else return 0; int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (i=pos;j=1; while(i(int)S0|j=(int

59、)T0) return i+1-(int)T0; else return 0; int IndexKMP(char SMAXSTRLEN,char TMAXSTRLEN,int (i=j=0; while(in+j; else if(j=0) i+; else j=nextj-1+1; if(jm) return -1; else return i-m+1; int IndexBF(char SMAXSTRLEN,char TMAXSTRLEN,int pos) int i,j;i=pos;j=1; while(i=S0 else return 0; void main() printf(Fi

60、ndstr.cpp运行结果:n); int Index,N,M,next64=0; char sMAXSTRLEN,tMAXSTRLEN; printf(GetNext-IndexKMP的结果:n); printf(输入主串s:);gets(s); printf(输入模式串t:);gets(t); N=strlen(s);M=strlen(t); printf(主串s长=%dn,N); printf( 模式串t长=%dn,M); GetNext(t,next,M); Index=IndexKMP(s,t,next,N,M); if(Index!=-1) printf(模式串在主串的位置从第%d