资源预览内容
第1页 / 共61页
第2页 / 共61页
第3页 / 共61页
第4页 / 共61页
第5页 / 共61页
第6页 / 共61页
第7页 / 共61页
第8页 / 共61页
第9页 / 共61页
第10页 / 共61页
亲,该文档总共61页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
.数据结构的语言算法以下数据结构算法由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,&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 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个元素与其后的元素后移*/ 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;/*若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 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(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;elsereturn -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:printf(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,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(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,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号