數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)目錄第一部分：課程設(shè)計(jì)題目要求第二部分：設(shè)計(jì)內(nèi)容及結(jié)果展示第三部分：設(shè)計(jì)體會(huì)計(jì)算機(jī)科學(xué)系2011年數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)題目1.用單鏈表構(gòu)造并實(shí)現(xiàn)多項(xiàng)式加、減法程序；并完成下列算式：f1(x) = 5x4+3x3-2x2+7x+1f2(x) = 5x3-10x2+2x-202.實(shí)現(xiàn)二叉樹(shù)深度優(yōu)先周游非遞歸前序和中序算法，并且自我構(gòu)造一顆二叉樹(shù)進(jìn)行驗(yàn)證。3.實(shí)現(xiàn)圖的鄰接表表示程序，在此基礎(chǔ)上，實(shí)現(xiàn)圖的深度（dfs）和廣度優(yōu)先算法（bfs），并且用一個(gè)實(shí)例進(jìn)行驗(yàn)證。4.編制一個(gè)演示內(nèi)部排序算法比較的程序。采用快速排序、希爾排序和堆排序進(jìn)行比較對(duì)輸入的數(shù)字序列進(jìn)行排序。a.輸入

2、：排序方法選擇，由鍵盤或文件輸入待排序表的表長(zhǎng)。b. 輸出：在不同輸入情況下和不同排序方法關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)，列表顯示。5.編寫一個(gè)串類完成：兩個(gè)字符串的連接、字符串的復(fù)制、字符串的比較 、求字符串長(zhǎng)度、取子串、串的替換等六個(gè)基本函數(shù)。同時(shí)，以實(shí)例驗(yàn)證各個(gè)函數(shù)的功能。設(shè)計(jì)內(nèi)容及結(jié)果展示1.用單鏈表構(gòu)造并實(shí)現(xiàn)多項(xiàng)式加、減法程序；并完成下列算式：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); 運(yùn)行結(jié)果：2.實(shí)現(xiàn)二叉樹(shù)深度優(yōu)先周游非遞歸前序和中序算法，并且自我構(gòu)造一顆二叉樹(shù)進(jìn)行驗(yàn)證。（）算法void init() memset(node,-1,sizeof(node); memset(built,0,sizeof(built)

5、; error=false;void build_binary_tree(int n) cout請(qǐng)按層序依次輸入每一個(gè)結(jié)點(diǎn)及其左兒子，右兒子的數(shù)據(jù)域的值。若該結(jié)點(diǎn)沒(méi)有左兒子，右兒子，則相應(yīng)地輸入-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;運(yùn)行結(jié)果：3.實(shí)現(xiàn)圖的鄰接表表示程序，在此基礎(chǔ)上，實(shí)現(xiàn)圖的深度（dfs）和廣度優(yōu)先算法（bfs），并且用一個(gè)實(shí)例進(jìn)行驗(yàn)證。（）算法：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請(qǐng)輸入各頂點(diǎn)的信息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;運(yùn)行結(jié)果：4.編制一個(gè)演示內(nèi)部排序算法比較的程序。采用快速排序、希爾排序和堆排序進(jìn)行比較對(duì)輸入的數(shù)字序列進(jìn)行排序。a.輸入：排序方法選擇，由鍵盤或文件輸入待排序表的表長(zhǎng)。b. 輸出：在不同輸入情況下和不同排序方法關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)，列表顯示。（）算法：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(輸入數(shù)組的長(zhǎng)度);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前者比后者長(zhǎng)endl;if(ab)cout后者比前者長(zhǎng)endl;if(a=b

16、)for(int e=0;ea;e+)if(temp1.se!=temp2.se)cout兩個(gè)字符串不相同endl;return; cout兩個(gè)字符串相同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) 待添加的隱藏文字內(nèi)容1 si=temp.si; i+; size=temp.size;void print()cout字符串是：;for(int i=0;isize;i+)coutsi;coutendl字符串的長(zhǎng)度是：size=size) cout取點(diǎn)位置錯(cuò)誤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.

18、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 求輸入字符串的長(zhǎng)度 endl; cout5 字符串的復(fù)制e

19、ndl; 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輸入字符串的長(zhǎng)度是：e.length();break;case 5:char str620,str720;coutstr6; coutstr7; string f(str6),g(str7); cout將后者復(fù)制給前者，結(jié)果為：; f.copy(g);f.print();