数据结构与算法课程设计 (2).doc

数据结构与算法课程设计目录第一部分：课程设计题目要求第二部分：设计内容及结果展示第三部分：设计体会计算机科学系2011年数据结构与算法课程设计题目1.用单链表构造并实现多项式加、减法程序；并完成下列算式：f1(x) = 5x4+3x3-2x2+7x+1f2(x) = 5x3-10x2+2x-202.实现二叉树深度优先周游非递归前序和中序算法，并且自我构造一颗二叉树进行验证。3.实现图的邻接表表示程序，在此基础上，实现图的深度（dfs）和广度优先算法（bfs），并且用一个实例进行验证。4.编制一个演示内部排序算法比较的程序。采用快速排序、希尔排序和堆排序进行比较对输入的数字序列进行排序。a.输入：排序方法选择，由键盘或文件输入待排序表的表长。b. 输出：在不同输入情况下和不同排序方法关键字参加的比较次数和关键字的移动次数，列表显示。5.编写一个串类完成：两个字符串的连接、字符串的复制、字符串的比较 、求字符串长度、取子串、串的替换等六个基本函数。同时，以实例验证各个函数的功能。设计内容及结果展示1.用单链表构造并实现多项式加、减法程序；并完成下列算式：f1(x) = 5x4+3x3-2x2+7x+1f2(x) = 5x3-10x2+2x-20（）算法void creatlist(list &l,int n) list p; l=new link; l-next=null; coutplease input ntype for link:endl; for (int i=0;ip-signp-time; p-next=l-next; l-next=p; void display (list l) link* p=l-next; while(p!=null) coutsignnext; void playadd(list a,list b) list p,q,r,s; int x; p=a-next;q=b-next; s=a; while(p!=null)&(q!=null) if(p-timetime) r=q-next; q-next=p; s-next=q; s=q;q=r; else if(p-timeq-time) s=p; p=p-next; else x=p-sign+q-sign; if(x!=0) p-sign=x; s=p; else s-next=p-next; free(p); p=s-next; r=q; q=q-next; free(r); if(q!=null) s-next=q; free(b); 运行结果：2.实现二叉树深度优先周游非递归前序和中序算法，并且自我构造一颗二叉树进行验证。（）算法void init() memset(node,-1,sizeof(node); memset(built,0,sizeof(built); error=false;void build_binary_tree(int n) cout请按层序依次输入每一个结点及其左儿子，右儿子的数据域的值。若该结点没有左儿子，右儿子，则相应地输入-1; for(i=1;ifather_dataleft_child_dataright_child_data; if(father_data=-1) error=1; return;if(i=1) built1=true; nodei.data=father_data; if(left_child_data!=-1) nodei.left=idx=left(i); nodeidx.data=left_child_data;if(right_child_data!=-1) nodei.right=idx=right(i); nodeidx.data=right_child_data;elsefor(j=2;j=maxn) error=true; return;builtj=true;builtj=true;if(left_child_data!=-1) nodej.left=idx=left(j); nodeidx.data=left_child_data;if(right_child_data!=-1) nodej.right=idx=right(j); nodeidx.data=right_child_data;void pretraversal(int i) top=0; while(top|i!=-1) if(i!=-1) printf(%d ,nodei.data); stacktop+.num=i; i=nodei.left;else i=stack-top.num; i=nodei.right;void intraversal(int i) top=0; while(top|i!=-1) if(i!=-1) stacktop+.num=i; i=nodei.left; else i=stack-top.num; printf(%d ,nodei.data);i=nodei.right;运行结果：3.实现图的邻接表表示程序，在此基础上，实现图的深度（dfs）和广度优先算法（bfs），并且用一个实例进行验证。（）算法：void iniqueue(linkqueue&q)q.rear=q.front=new qnode;q.front-next=null;void enqueue(linkqueue&q,int e) queueptr p=new qnode;p-data=e;p-next=null;q.rear-next=p;q.rear=p;bool dequeue(linkqueue&q,int&e)queueptr p;if(q.front=q.rear)return error;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;delete(p);return ok;bool queueempty(linkqueue q)if(q.rear=q.front)return 1;elsereturn 0;int locatevex(algraph&g,char v)int i=0;while(ig.vexnum)&(g.verticesi.data!=v)i+;if(ig.vexnum)return i;elsereturn -1;bool createdg(algraph&g)coutg.vexnum;coutg.arcnum;cout请输入各顶点的信息endl;for(int i=0;ig.verticesi.data;g.verticesi.firstarc=null;for(int k=1;k=g.arcnum;k+) char v1,v2;coutv1v2;int i=locatevex(g,v1);int j=locatevex(g,v2);if(i0|jadjvex=j;if(g.verticesi.firstarc=null)|(g.verticesi.firstarc-adjvexj) p-nextarc=g.verticesi.firstarc;g.verticesi.firstarc=p;else arcnode *q;q=g.verticesi.firstarc;while(q-nextarc&(q-nextarc-adjvexnextarc;p-nextarc=q-nextarc;q-nextarc=p;return ok;bool visitedmax;void dfs(algraph&g,int v)visitedv=true;coutg.verticesv.dataadjvex) dfs(g,p-adjvex);p=p-nextarc;void dfstraverse(algraph&g)for(int m=0;mg.vexnum;m+) visitedm=false;for(int n=0;ng.vexnum;n+)if(!visitedn)dfs(g,n);void bfstraverse(algraph&g)for(int v=0;vg.vexnum;v+) visitedv=false;linkqueue q;iniqueue(q);for(int v=0;vg.vexnum;v+)if(!visitedv)visitedv=true;coutg.verticesv.dataadjvex)visitedp-adjvex=true;coutadjvex.dataadjvex);p=p-nextarc;运行结果：4.编制一个演示内部排序算法比较的程序。采用快速排序、希尔排序和堆排序进行比较对输入的数字序列进行排序。a.输入：排序方法选择，由键盘或文件输入待排序表的表长。b. 输出：在不同输入情况下和不同排序方法关键字参加的比较次数和关键字的移动次数，列表显示。（）算法：void swap(int *a,int *b)int temp;temp=*a;*a=*b;*b=temp;void quicksort(int k,int s,int t)int i,j;if(s=ki|i=t);do j-;while(!(ks=kj|j=s);if(i1)gap=gap/2;doflag=0;for(i=0;i=n-gap;i+)j=i+gap;if(kikj)temp=ki;ki=kj;kj=temp;flag=1;while(flag!=0);void printsort(int k,int len)int i;for(i=0;ilen;i+)printf(%d ,ki);printf(n);void sift(int*x,int n,int s) int t,k,j; t=*(x+s); k=s; j=2*k+1; while(jn) if(jn-1&*(x+j+1) j+; if(t=0;i-) sift(x,n,i); for(k=n-1;k=1;k-) t=*(x+0); *(x+0)=*(x+k); *(x+k)=t; sift(x,k,0); int main()int i,len,ran;int *a;int seldo;printf(输入数组的长度);scanf(%d,&len);a= (int *)malloc(sizeof(int)*len);srand( time(null) ); for(i=0;ilen;i+) ran=rand()%1000;ai=ran;printf(the orginal data arrayisn);for(i=0;ib)cout前者比后者长endl;if(ab)cout后者比前者长endl;if(a=b)for(int e=0;ea;e+)if(temp1.se!=temp2.se)cout两个字符串不相同endl;return; cout两个字符串相同endl;friend void replace(string temp1,string temp2)char *p;int i;p=&temp1.s0;temp1.s=temp2.s;temp2=p;i=temp1.size;temp1.size=temp2.size;temp2.size=i;void copy(string temp) char *p=new chartemp.size+1; s=&p0; int i=0; while(temp.si!=0) si=temp.si; i+; size=temp.size;void print()cout字符串是：;for(int i=0;isize;i+)coutsi;coutendl字符串的长度是：size=size) cout取点位置错误left)n=left;p=new charn+1;q=&spos-1;for(i=0;in;i+)pi=qi;pn+1=0;s=p;size=n;return true;string connect(string temp1,string temp2) int a,b; delete s; size=temp1.size+temp2.size; a=temp1.size; b=temp2.size; char *p=new chara+b+1; s=&p0; int i=0; while(temp1.si!=0) si=temp1.si; i+; int e=0; while(temp2.se!=0) int c=a+e; sc=temp2.se; e+; sa+b+1=0; ;int main()for(;)int n;cout1 比较字符串 endl; cout2 替换字符串 endl; cout3 取字符串的子串 endl; cout4 求输入字符串的长度 endl; cout5 字符串的复制endl; cout6 连接endl; cout0 退出 n;switch(n)case 1:char str120;char str220;coutstr1;coutstr2;string a(str1),b(str2);compare(a,b);break;case 2:char *p=new char20;char *q=new char20;coutp;coutq;string a(p),b(q);replace(a,b);cout替换后：;a.print();b.print();break;case 3: coutstr;int pos,n;coutpos;coutn;string c(str);c.substring(pos,n);cout抽取的字串为：;c.print();break;case 4:char str520;coutstr5;string e(str5);cout输入字符串的长度是：e.length();break;case 5:char str620,str720;coutstr6; coutstr7; string f(str6),g(str7); cout将后者复制给前者，结果为：; f.copy(g);f.print();b