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

《数据结构与算法课程设计 .doc》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计 .doc（24页珍藏版）》请在三一办公上搜索。

1、数据结构与算法课程设计目录第一部分：课程设计题目要求第二部分：设计内容及结果展示第三部分：设计体会计算机科学系2011年数据结构与算法课程设计题目1.用单链表构造并实现多项式加、减法程序；并完成下列算式：f1(x) = 5x4+3x3-2x2+7x+1f2(x) = 5x3-10x2+2x-202.实现二叉树深度优先周游非递归前序和中序算法，并且自我构造一颗二叉树进行验证。3.实现图的邻接表表示程序，在此基础上，实现图的深度（DFS）和广度优先算法（BFS），并且用一个实例进行验证。4.编制一个演示内部排序算法比较的程序。采用快速排序、希尔排序和堆排序进行比较对输入的数字序列进行排序。A.输入

2、：排序方法选择，由键盘或文件输入待排序表的表长。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; coutp

3、lease 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;

4、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)

5、; 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_

6、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=righ

7、t_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=no

8、dei.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.rea

9、r)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 Creat

10、eDG(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.vertic

11、esi.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(

12、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

13、=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;dof

14、lag=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=

15、*(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

16、)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(

17、temp.si!=0)待添加的隐藏文字内容2 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.s

18、ize+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 字符串的复制en

19、dl; 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(

20、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();break;case 6: char a20,b20; cout请输入字符串：a; cout请输入字符串：b; String A(

21、a),B(b),C; C.Connect(A,B); cout拼接后：; C.Print(); break; case 0:return -1;coutendl;coutendl;system(pause);return 0;运行结果：心得体会： 在完成任务的过程中，我们遇到了很多的困难，题目设计的很有针对性，做完后对我们数据结构和算法方面有了很大的提升，在王老师和同学们的帮助下，我们组团结合作，完成了所有五道题的任务，虽然还有些地方需要改进，但是这是我们四个人在上一周的努力结晶，我们很高兴有这次机会完成这项任务，通过课设我们逐步建立起了自己的信心，并对数据结构这门课程有了新的认识，对我们今后的发展有很大帮助。 特别感谢王老师的指导，在思路上给了我们很大的启发，让我们了解到怎么样才是最有效的办法。经过一个学期的学习和王老师指导下，我们所有人的编程能力有了很大的提升。 本次课设我们虽然完成了所有的任务，但我们还是发现了自己的不足，平时学习过于浮躁导致知识不够扎实，一些细节不够注意使得我们花了很长时间在修改低级错误上。另外，我们的程序还有些瑕疵，譬如第四题，我们可以再加一个时间函数比较不同的排序方法的时间代价。在今后的学习当中我们定将更加严格的要求自己，努力提高自己的编程能力。总之，这次课设我们付出很多，收获更大，再一次感谢王老师的指导，和同学们的帮助。 计算机一班 排版：