王博华数据结构实验报告.doc

软件中外132王博华实验二 链表及其多项式相加Time Limit: 3000MSMemory Limit: 65536KTotal Submissions: 1127Accepted: 471Case Time Limit:1000MS Description通过有序对输入多项式的各个项，利用单链表存储该一元多项式，并建立的2个存储一元多项式的单链表，然后完成2个一元多项式的相加，并输出相加后的多项式。Input输入数据有多组，对于每组测试数据，第一行一个整数n，表示第一个多项式La的项数；接下来n行，每行表示多项式的一项，包含两个元素，表示系数和指数；接下来一个整数m，表示第二个多项式Lb的项数；接下来m行，每行表示多项式的一项，包含两个元素，表示系数和指数；两个多项式的输入都是按指数从小到大。（n,m=1000）OutputLa与Lb相加之后的多项式。按指数从小到大输出，每行一项，用空格把系数和指数分开。Sample Input31 22 33 434 32 54 6Sample Output1 26 33 42 54 6Source#include #include struct jiegou int shu,zhishu; struct jiegou *next; *a,*b,*c; void shuru() jiegou *p,*q; int i,j,n,m,c,d; scanf(%d,&n); p=a=(struct jiegou *)malloc(sizeof(jiegou); for(i=0;ishu=d; q-zhishu=c; p-next=q; p=q; p-next=NULL; scanf(%d,&n); p=b=(struct jiegou *)malloc(sizeof(jiegou); for(i=0;ishu=d; q-zhishu=c; p-next=q; p=q; p-next=NULL; void jifa() jiegou *p,*q; int e,d,i; p=c=(struct jiegou *)malloc(sizeof(jiegou); a=a-next; b=b-next; while(a!=NULL&b!=NULL) if(a-zhishu=b-zhishu) e=a-shu+b-shu; if(e!=0) q=(jiegou *)malloc(sizeof(jiegou); p-next=q; p=q; p-shu=e; p-zhishu=a-zhishu; b=b-next; a=a-next; else if(a-zhishuzhishu) q=(jiegou *)malloc(sizeof(jiegou); p-next=q; p=q; p-shu=a-shu; p-zhishu=a-zhishu; a=a-next; else q=(jiegou *)malloc(sizeof(jiegou); p-next=q; p=q; p-shu=b-shu; p-zhishu=b-zhishu; b=b-next; while(a) q=(jiegou *)malloc(sizeof(jiegou); p-next=q; p=q; p-shu=a-shu; p-zhishu=a-zhishu; a=a-next; while(b) q=(jiegou *)malloc(sizeof(jiegou); p-next=q; p=q; p-shu=b-shu; p-zhishu=b-zhishu; b=b-next; p-next=NULL; void shuchu() jiegou *p; p=c-next; while(p) printf(%d %dn,p-shu,p-zhishu); p=p-next; int main () shuru(); jifa(); shuchu(); 实验三 括号匹配判断算法Time Limit: 3000MSMemory Limit: 65536KTotal Submissions: 1025Accepted: 474Case Time Limit:1000MS Description假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 ( )均为不正确的格式。基于栈设计一个判断括号是否正确匹配的算法。Input输入数据有多组，每组测试数据一行，一个字符串，只包含 ， ，( ，) 。Output对于每组测试数据，若括号匹配输出yes 否则输出 no。Sample Input()()Sample OutputyesnoSource#include #include typedef struct snode char data; struct snode *next; snode,*linkstack; void initlinkstack(linkstack *); void linkstackpush(linkstack *,char); int linkstackpop(linkstack *); int linkstackgettop(linkstack,char *); void matching(char str); int main() char str8000; while(gets(str) matching(str); return 0; void linkstackpush(linkstack *ls,char e) linkstack p=(linkstack)malloc(sizeof(snode); p-data=e;p-next=*ls;*ls=p; int linkstackpop(linkstack *ls) linkstack p=*ls; if(*ls=NULL) return 0; (*ls)=(*ls)-next; free(p); return 1; int linkstackgettop(linkstack ls,char *e) if(ls=NULL) return 0; *e=ls-data;return 1; void initlinkstack(linkstack *ls) *ls=NULL; void matching(char str) linkstack s;int k,flag=1;char e; initlinkstack(&s); for(k=0;strk!=0&flag;k+) if(strk!=(&strk!=)&strk!=&strk!=&strk!=&strk!=) continue; switch(strk) case (:case :case :linkstackpush(&s,strk);break;case ): if(s!=NULL) linkstackgettop(s,&e); if(e=() linkstackpop(&s); else flag=0; else flag=0; break; case : if(s!=NULL) linkstackgettop(s,&e); if(e=) linkstackpop(&s); else flag=0; else flag=0; break; case : if(s!=NULL) linkstackgettop(s,&e); if(e=) linkstackpop(&s); else flag=0; else flag=0; break; if(flag=1&s=NULL) printf(yesn); else printf(non); 实验六 KMP算法Time Limit: 3000MSMemory Limit: 65536KTotal Submissions: 776Accepted: 383Case Time Limit:1000MS Description给定一个源串s和n个子串stri。判断stri是否是s的子串。Input输入数据有多组，对于每组测试数据第一行源串S（S长度小于100000），第二行一个整数n， 表示下面有n个查询，每行一个字符串str。Output若str是S的子串，输出 yes 否则输出 noSample Inputacmicpczjnuduzongfei3icpcduliuSample OutputyesyesnoHint因为串的长度比较长，超过256，因此本题的串不适合用定长顺序存储表示来存储串，SString的长度放在第一个元素，这个元素占一个字节，最大255.Source#include #include char a100001,b100001; int next100001; int main () int i,j,n,m,N,K,p; scanf(%s,a); scanf(%d%*c,&N); p=strlen(a); for(K=1;K=N;K+) scanf(%s,b+1); next0=strlen(b+1); i=1; next1=0; j=0; while(inext0) if(j=0|bi=bj) +i;+j; if(bi!=bj) nexti=j; else nexti=nextj; else j=nextj; i=0;j=1; while(j=next0&inext0) printf(yesn); else printf(non); 实验九 由先序遍历和中序遍历序列建立二叉树Time Limit: 3000MSMemory Limit: 65536KTotal Submissions: 451Accepted: 315Case Time Limit:1000MS Description按先序顺序和中序顺序输入二叉树的2个遍历序列，采用二叉链表建立该二叉树并用后序遍历顺序输出该二叉树的后序遍历序列。Input输入数据有多组，对于每组测试数据第一行输入二叉树的先序序列，第二行为中序序列。Output对于每组测试数据输出该二叉树的后序序列Sample Inputabdcef dbaecfSample OutputHintdbefcaSource#include #include #include typedef struct node char da; node *lcha,*rcha; *tree; tree fd; char xian1001,zhong1001; void PPP(int i,int j,int k,int m,tree &t) int s; t=(node*)malloc(sizeof(node); t-da=xiani; for(s=k;zhongs!=xiani;s+); if(s=k) t-lcha=NULL; else PPP(i+1,i+s-k,k,s-1,(t-lcha); if(s=m) t-rcha=NULL; else PPP(i+s-k+1,j,s+1,m,(t-rcha); void shuchu(node *t) /printf(%c,t-da); if(t-lcha) shuchu(t-lcha); if(t-rcha) shuchu(t-rcha); printf(%c,t-da); int main () int n; gets(xian+1); gets(zhong+1); n=strlen(xian+1); PPP(1,n,1,n,fd); shuchu(fd); printf(n); 实验十二 图的建立与遍历Time Limit: 3000MSMemory Limit: 65536KTotal Submissions: 796Accepted: 349Case Time Limit:1000MS Description按邻接矩阵的方法创建图，分别用深度优先和广度优先方法遍历图。Input输入的数据有多组对于每组测试数据第一行为图中点的个数n（0 n 100）与边的数量m(m =0)。接下来有m行，每行两个整数a,b(0 =a,b n)，代表这a,b这两个点之间是连通的。Output分别输出按照深度优先搜索与广度优先搜索方法遍历的结果，每个输出结果后面都有一空行。Sample Input3 05 30 10 41 3Sample Output0 1 20 1 20 1 3 4 20 1 4 3 2Source#include #include #define MAX 100 int visitedMAX;typedef struct int arcMAXMAX;int numVertexes,numEdges;MGraph;void creat(MGraph *G) int i,j,k; scanf(%d %d,&G-numVertexes,&G-numEdges); for(i=0;inumVertexes;i+)for(j=0;jnumVertexes;j+) G-arcij=0; for(k=0;knumEdges;k+) scanf(%d %d,&i,&j); G-arcij=G-arcji=1; void dfs(MGraph *G,int i) int j; visitedi = 1;printf(%d ,i);for(j=1;jnumVertexes;j+) if(G-arcij=1 & visitedj=0) dfs(G,j); void DFS(MGraph *G) int i; for(i=0;inumVertexes;i+) visitedi = 0; for(i=0;inumVertexes;i+) if(visitedi=0) dfs(G,i); printf(n); void BFS(MGraph *G)int i,j,k;for(i=0;inumVertexes;i+) visitedi = 0; for(k=0;knumVertexes;k+) int QMAX,front=0,rear=0;if(visitedk=0)printf(%d ,k);visitedk=1;rear=(rear+1)% MAX;i=k;Qrear=i;while(front!=rear) front=(front+1)%MAX;i=Qfront; for(j=0;jnumVertexes;j+)if(G-arcij=1 & !visitedj) printf(%d ,j);visitedj=1;rear=(rear+1)%MAX;Qrear=j;else continue;printf(n);int main() MGraph *Graph; Graph= (MGraph*)malloc(sizeof(MGraph);creat(Graph); DFS(Graph);BFS(Graph);printf(n);实验十八 BST树的构建与应用Time Limit: 3000MSMemory Limit: 65536KTotal Submissions: 330Accepted: 232Case Time Limit:1000MS Description实现BST查找及建立以及遍历算法，根据查询的数，建一颗BST树，初始树为空，重复的数不用插入树中。Input输入数据有多组。对于每组测试数据，第一行一个整数N,表示要查询的数的个数，第二行N个数，表示要查询的树。（100=N=10000）Output对于每组测试数据，输出两行，第一行为BST树中元素的个数第二行为BST树的先序序列Sample Input612 23 32 4 8 12Sample Output512 4 8 23 32Source#include#includestruct lispstruct lisp *l,*r;int data;*tree;int n;int m;void build(struct lisp *&p,int x)if(p=NULL)p=(struct lisp*)malloc(sizeof(struct lisp);p-data=x;p-l=NULL;p-r=NULL;m+;return;if(p-data=x