10092130138——张伟.doc

1800实现一个线性表:参照课本P5上的sq_delete函数，对一个n不超过1024的线性表进行删除操作#define M 1024#includeint main()int sq_delete(int list,int * p_n,int i);int aM,n,m;int i,q,k,p,l;scanf(%d,&n);m=n;for(i=0;in;i+)scanf(%d,&ai);scanf(%d,&q);while(q-)scanf(%d,&k);l=ak-1;p=sq_delete(a,&m,k-1);if(p=-1)printf(%dn,p);if(p=0)printf(%dn,l);return 0;int sq_delete(list,p_n,x)int list;int * p_n,x;int j;if(x=* p_n)return -1;for(j=x+1;j* p_n;j+)listj-1=listj;(* p_n)-;return 0;被调用函数：int sq_delete(list,p_n,x)线性表删除调试时间：2010-10-16 23:08:251801实现环形队列(MAXN不超过100001)，要求能够进行进队出队操作，参考课本P15页例程。#define N 100001#include#includechar aN20;int head=0;int tail=0;int main()int enq(char ch1);int deq(char * p);char b7,c20;int q,x;scanf(%dn,&q);while(q-)scanf(%s,&b);if(b0=e)scanf(%s,&c);enq(c);if(enq(c)=0)printf();else if(b0=d)x=deq(&ahead);if(x=-2)printf(-1n);else printf(%sn,adeq(&ahead);return 0;int enq(char ch1)tail=(tail+1)%N;if(tail=head)if(tail=0)tail =N-1;else tail-;return 1;strcpy(atail,ch1);return 0;int deq(char * p) int h;if(head=tail)return -2; h=head;head=(head+1)%N;* p=ahead0; return h;被调用函数：进队函数 int enq（char ch1）出对函数int deq（char * p）调试时间：2010-11-10 09:26:011803实现线性链表的创建于插入(插入到已有元素之后)includetypedef struct node int data; struct node * link; NODE;int main()NODE * creatlist(int n);void insert(NODE * phead,int a,int b);NODE * ahead,*p;int m,q;int x,y;scanf(%d,&m);ahead=creatlist(m);scanf(%d,&q);while(q-)scanf(%d%d,&x,&y);insert(ahead,x,y); for(p=ahead;(p-link)!=NULL;p=p-link) printf(%d ,p-data); printf(%dn,p-data); return 0;NODE * creatlist(int n)int i;NODE * head,* p0,* q;if(n=0)return(NULL);head=(NODE *)malloc(sizeof(NODE);p0=head;for(i=1;idata);q=(NODE *)malloc(sizeof(NODE);p0-link=q;p0=q;scanf(%d,&(p0-data);p0-link=NULL;return head;void insert(NODE * phead,int a,int b)NODE * p0,* q;q=(NODE *)malloc(sizeof(NODE);q-data=b;q-link=NULL;if(phead=NULL)phead=q;else p0=phead;while(p0-data!=a&p0-link!=NULL)p0=p0-link; q-link=p0-link; p0-link=q;被调用函数：线性表创建NODE * createlist（int n）和插入函数void insert（NODE * phead， int a，int b）调试时间：2010-11-30 20:35:301804实现字符串的strcat, strsub, strequ操作，参照课本P62例程#define N 1024#includechar aN;char cN;int main()int strlen(char s);int strcat(char s1,char s2);int strsub(char s1,int i,int j,char s2);int strequ(char s1,char s2);char b6;int d,e,n;gets(a);scanf(%dn,&n);while(n-)scanf(%s,&b);if(strequ(b,strcat)=1)scanf(%s,&c);strcat(a,c);printf(%sn,a);else if(strequ(b,strsub)=1)scanf(%d%d,&d,&e);if(dstrlen(a)printf(failn);elsestrsub(a,d,e,c); printf(%sn,c); else if(strequ(b,strequ)=1)scanf(%s,&c);if(strequ(a,c)=1)printf(yesn);else printf(non);return 0;int strlen(char s)int i;for(i=0;si!=0;i+);return i;int strcat(char s1,char s2)int i,j,k;if(i=strlen(s1)+(j=strlen(s2)=N)return 0;for(k=0;k=j;k+)s1i+k=s2k;return 1;int strsub(char s1,int i,int j,char s2)int m,k;if(i=(m=strlen(s1)return 0; if(jm)return 0;for(k=0;kj;k+)s2k=s1i+k;s2k=0;return 1;int strequ(char s1,char s2)int i=0;while(s1i=s2i&s1i!=0&s2i!=0)i+;if(s1i=0&s2i=0)return 1;else return 0;被调用函数：int strcat（char s1,char s2）int strsub(char s1,int I,int j,char s2) int strequ(char s1,char s2)调试时间：2010-10-28 23:35:251806实现选择排序define M 1023#includeint main()int aM;int n,i;int j,t;int k;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)k=i;for(j=i+1;jaj) k=j;t=ai;ai=ak;ak=t;if(i%(n-1)=0&i0)printf(%dn,ai);else printf(%d ,ai);return 0;调试时间：2010-10-19 12:14:101807实现快速排序#define M 20000#includeint main()void quick(int a,int low,int up);int n,k;int bM;scanf(%d,&n);for(k=0;kn;k+)scanf(%d,&bk);quick(b,0,n-1);for(k=0;kn-1;k+)printf(%d ,bk);printf(%dn,bk);return 0;void quick(a,low,up)int a;int low,up; int i,j; int t; if(lowup) i=low; j=up; t=alow; while(i!=j) while(it) j-; if(ij)ai+=aj; while(ij&ai=t) i+; if(ij)aj-=ai; ai=t; quick(a,low,i-1); quick(a,i+1,up); 被调用函数：void quick（int a,int low,int up）调试时间：2010-10-16 23:35:281808实现冒泡排序#define N 1024#includeint main()int aN;int n,i;int j,t;int m;scanf(%dn,&n);for(i=0;i0)j=0;for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t; j=i;n=j;for(i=0;im;i+)printf(%d ,ai); printf(%dn,ai);return 0;调试时间：2010-10-25 00:08:131809对于n个整数，找出第1小，第2小.第k小的整数#define N 1000000#includeint aN;int main() void quick(int b,int low,int up); int i,k; int n; scanf(%d%d,&n,&k); for(i=0;in;i+) scanf(%d,&ai); quick(a,0,n-1); for(i=0;ik-1;i+) printf(%d ,ai); printf(%dn,ai); system(pause); return 0;void quick(int b,int low,int up) int i,j; int t; if(lowup) i=low; j=up; t=blow; while(i!=j) while(it) j-; if(ij)bi+=bj; while(ij&bi=t) i+; if(ij)bj-=bi; bi=t; quick(b,low,i-1); quick(b,i+1,up); 被调用函数：viod quick（int b, int low int up）调试时间：2010-11-09 00:40:131810利用原稀疏矩阵的三元数组a，求转置矩阵的三元数组b，并将其规格化，即按行号递增，若行号相同则按照列号递增的顺序。参照课本P93.94例程include int g1000001,f1000001; int a10000013,b10000013;int main() int m,n; int i,j; int k,c; while(scanf(%d%d%d,&m,&n,&c)!=EOF) k=1; while(k0) for(i=0;in;i+) gi=0; for(i=1;i=c;i+) gai1+=1; f0=1; for(i=1;in;i+) fi=gi-1+fi-1; for(i=1;i=c;i+) j=fai1; bj0=ai1; bj1=ai0; bj2=ai2; fai1=j+1; for(i=1;i=c;i+) printf(%d %d %dn,bi0,bi1,bi2); system(pause); return 0; 调试时间：2010-11-17 18:53:121811根据树的层号表示建树，打印树的后序遍历序列。层号表示法参见课本P117#include#include#define M 26#define N 26struct node int lev; char data; struct node * childM; struct node * parent;typedef struct node NODE;typedef struct dnode int lev; char data; DNODE; int main()void levtree(DNODE a,int n);void aftree(NODE * root1);DNODE a0N;int n0,i;char c1,c2,c3,c4;scanf(%dn,&n0);for(i=0;ilev=a0.lev;root-data=a0.data; for(i=0;ichildi=NULL;root-parent=NULL;p=root;for(i=1;ilev=ai.lev;q-data=ai.data;for(j=0;jchildj=NULL;while(q-levlev)p=p-parent;q-parent=p;for(j=0;jchildj=NULL)p-childj=q;break;p=q;aftree(root);void aftree(NODE * root1) int ii;if(root1!=NULL) for(ii=0;iichildii);printf(%c,root1-data); 被调用函数：层次建立树void levtree(DNODE a,int n) 后序遍历树 void aftree(NODE * root)调试时间：2010-12-22 09:19:511812给定一个有根二叉树，规定连接两个节点的每条边长度是1，定义树的深度为根到叶子节点距离的最大值includeint main()int m=1,n=0;int i,j=0;int k,l;int x,y;int n1,n2=0;scanf(%d,&k);while(m!=0) n1=m;m=0;for(i=0;i0)m+;if(y0)m+;n2+;if(j=k)m=0;printf(%dn,n2);return 0;调试时间：2010-12-22 15:12:391814二叉树T中，如果非叶子结点都有两棵非空子树，那么称二叉树T是一棵完全二叉树。现在根据边的连接情况判断一棵树是否是完全二叉树。define N 1025#includeint main()int aN=0,n;int i,j;int x,y;int m;scanf(%d%d,&n,&j);m=n-1;while(m-) scanf(%d%d,&x,&y); ax=ax+1;ay=ay+1;if(aj=2|aj=0)aj=3;else aj=2;for(i=1;i=N) printf(yesn); return 0;调试时间：2010-12-15 16:20:481815我们大家都学习了Huffman算法，给出每一个点的权值，它可以求出一个具有最小加权外部路径的二叉树，也就是使造价 W(k1)*Lk1 + . + W(kn)*Lkn (树枝长度为根结点到叶结点边数)最小的二叉树。现在由你来完成这项工作#define N 10001#include#includetypedef struct nodeint data;struct node *lchild;struct node *rchild;struct node *parent;NODE;NODE *adrN;int main() NODE *creat(int a,int n);int n0,aN,m,i;int sum;NODE * root,* p;scanf(%d,&n0);for(i=0;in0;i+)scanf(%d,&ai);root=creat(a,n0);sum=0;for(i=0;iparent!=NULL) m+;p=p-parent; sum=sum+m*adri-data;printf(%dn,sum);return 0;NODE *creat(int a,int n)int n1,n2,i,j;int u,v,min1,min2;for(i=0;idata=ai;adri-lchild=NULL;adri-rchild=NULL;adri-parent=NULL;ai=-ai;for(i=n;i2*n-1;i+)min1=999999999;min2=999999999;n1=-1;n2=-1;for(j=0;j0)if(umin1)min2=min1;min1=u;n2=n1;n1=j;else if(uparent=NULL;adri-lchild=adrn1;adri-rchild=adrn2;adrn1-parent=adri;adrn2-parent=adri;ai=an1+an2;adri-data=ai;an1=-an1;an2=-an2;a2*n-2=-a2*n-2;return adr2*n-2;被调用函数：NODE * creat（int a,int n）调试时间：2010-12-26 12:57:401816如果无向图G每对顶点v和w都有从v到w的路径，那么称无向图G是连通的。现在给定一张无向图,判断它是否是连通的。#define N 1000001#include#includestruct lnode int ver;struct lnode * link;typedef struct lnode LNODE;typedef struct int ver1; int ver2;ENODE;LNODE * headN;ENODE eN;int vN=0;void createlist(head,n,e ,m)LNODE * headN;ENODE eN;int n,m;int i,u,v;LNODE * p;for(i=1;in;i+)headi=NULL;for(i=0;iver=v;p-link=headu;headu=p;p=(LNODE *)malloc(sizeof(LNODE);p-ver=u;p-link=headv;headv=p;void dfs(int k)LNODE * t;vk=1;t=headk;while(t!=NULL)if(vt-ver=0)dfs(t-ver);t=t-link;int main()int n1,m1;int x,y;scanf(%d%d,&n1,&m1);for(x=0;xm1;x+)scanf(%d%d,&ex.ver1,&ex.ver2);createlist(head,n1,e ,m1);dfs(1);for(x=1;xn1)printf(yesn);else printf(non);return 0;被调用的函数：void createlist(head,n,e ,m)，