..編號課程設(shè)計題目1、一元稀疏多項式計算器2、模擬瀏覽器操作程序3、背包問題的求解4、八皇后問題二級學院計算機科學與工程學院專業(yè)計算機科學與技術(shù)班級2011級37-3班學生姓名XX學號XXXXXXXXXX指導(dǎo)教師XXXXX評閱教師時間一元稀疏多項式計算器[實驗內(nèi)容]一元稀疏多項式計算器。[問題描述]設(shè)計一個一元稀疏多項式簡單計算器。[需求分析]其基本功能包括：〔1輸入并建立多項式；〔2輸出多項式,輸出形式為整數(shù)序列為：n,c1,e1,c2,e2,……,cn,en,其中n是多項式的項數(shù),ci,ei分別是第i項的系數(shù)和指數(shù),序列按指數(shù)降序排序；〔3多項式a和b相減,建立多項a+b；〔4多項式a和b相減,建立多項式a-b；〔5計算多項式在x處的值；〔6計算器的仿真界面〔選做；[概要設(shè)計]-=ADT=-{ voidinput<Jd*ha,Jd*hb>；//輸入兩個多項式voidsort<Jd*h>； //用冒泡排序法對一個多項式進行降序排序 voidsum<Jd*ha,Jd*hb>；//多項式求和 voidminus<Jd*ha,Jd*hb>；//多項式相減voidoutput<Jd*h>； //輸出多項式voidoperate<Jd*ha,Jd*hb>； //對多項式進行操作intqiuzhi<intx,Jd*ha>； //計算多項式在x處的值voidmain<>； 主函數(shù)}[存儲結(jié)構(gòu)]typedefstructnode /*定義多項式每一項*/{ inte; //e為指數(shù) floatc; //c為系數(shù) structnode*next; //next指向下一項}dnode;[流程圖]1．dnode*creat<>//多項式的創(chuàng)建,即輸入兩個多項式hwhile<項數(shù)<MAXN>輸入多項式的系數(shù)和指數(shù)p->next=h->next;h->next=p;繼續(xù)輸入returnh;2.voidsort<dnode*h>//采用冒泡法對鏈表每一項重新排序//while<p->next!=NULL> p=p->next;//尋找尾結(jié)點pi=p;指向最后一次交換的位置,初值為表尾while<pi!=h->next>//外層循環(huán),比較趟數(shù)for<p=h->next;p!=pi;p=p->next>內(nèi)層循環(huán),前后兩兩相比swap<p,q>;pl=p;//調(diào)用交換函數(shù)pi=pl;3.dnode*operate<dnode*a,dnode*b>//稀疏多項式計算// while<p&&q>比較對應(yīng)兩項的指數(shù)x=p->c+q->c;if<fabs<x><1e-5>p=p->next;q=q->next;if<x!=0>將和鏈接到新的鏈表中elseif<p->e>q->e>p鏈接到新的鏈表中,p后移,q不動elseif<p->e<q->e>p鏈接到新的鏈表中,q后移,p不動++c->c;if<q!=NULL>t->next=q;++c->c;if<p!=NULL>t->next=p;++c->c;4.floatqiuzhi<intx,dnode*h>//求多項式在x處的值 if<p==NULL>return0;while<p>if<p->e==0>sum+=p->c;elsesum+=<p->c>*<pow<x,p->e>>; p=p->next;returnsum;[詳細設(shè)計]源代碼如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineNULL0typedefstructnode /*定義多項式每一項*/{ inte; //e為指數(shù) floatc; //c為系數(shù) structnode*next; //next指向下一項}dnode;dnode*creat<> /*用鏈表存放多項式*/{ //多項式的創(chuàng)建,即輸入兩個多項式 dnode*h,*p; inte,i,n; //n為多項式的項數(shù) floatc; //c為多項式的系數(shù) h=<dnode*>malloc<sizeof<dnode>>; //分配頭節(jié)點 h->next=NULL; do//當n為0或小于1時,則重新輸入 { printf<"請輸入多項式的項數(shù)n:">; scanf<"%d",&n>; }while<n<1>; for<i=1;i<=n;i++> //輸入各項的系數(shù)c和指數(shù)e { printf<"請輸入第%d項的系數(shù)c和指數(shù)e:",i>; scanf<"%f%d",&c,&e>; p=<dnode*>malloc<sizeof<dnode>>; //創(chuàng)建新結(jié)點 p->c=c;p->e=e; //將值傳給data域 p->next=h->next;//用頭插法建立鏈表 h->next=p; } returnh; //返回頭結(jié)點}voidswap<dnode*p,dnode*q> /*交換p,q指針所指的指數(shù)和系數(shù)*/{ floatm;//中間變量 intn; //中間變量 n=p->e;//交換操作 p->e=q->e; q->e=n; m=p->c; p->c=q->c; q->c=m;}voidsort<dnode*h> /*采用冒泡法對鏈表每一項重新排序*/{ dnode*pi,*pl,*p,*q; p=h->next; //p此時指向第一項 while<p->next!=NULL> p=p->next; //尋找尾結(jié)點 pi=p;//pi指向最后一次交換的位置,初值為表尾 while<pi!=h->next> //結(jié)點數(shù)大于1時 { pl=h->next; //pl為中間變量,起傳遞地地址的作用 for<p=h->next;p!=pi;p=p->next> { q=p->next; if<p->e>q->e> { swap<p,q>;//調(diào)用交換函數(shù) pl=p; } } pi=pl; //pi指向前一個結(jié)點 }}dnode*operate<dnode*a,dnode*b>/*稀疏多項式計算*/{ intsel; floatx; dnode*p1,*p2,*p,*t; //t為結(jié)果鏈表的表頭 t=<dnode*>malloc<sizeof<dnode>>; t->next=NULL; printf<"--------------------------------------\n">; printf<"|請選擇運算方式:|\n">; printf<"|1、多項式相加|\n">; printf<"|2、多項式相減|\n">; printf<"|0、退出!|\n">; printf<"--------------------------------------\n">; printf<"請選擇:">; scanf<"%d",&sel>; p1=a->next; p2=b->next; while<p1&&p2> { if<p1->e==p2->e> //指數(shù)相同 { if<sel==1> x=p1->c+p2->c; //系數(shù)相加 else x=p1->c-p2->c; //系數(shù)相減 if<x!=0> { p=<dnode*>malloc<sizeof<dnode>>; p->e=p1->e; p->c=x; p->next=t->next;//利用頭插法將p結(jié)點插入t中 t->next=p; } p1=p1->next; p2=p2->next; } elseif<p1->e>p2->e>//p1的指數(shù)大于p2的指數(shù) { p=<dnode*>malloc<sizeof<dnode>>; p->e=p2->e; if<sel==1> p->c=p2->c; else p->c=<-1>*p2->c; p->next=t->next; t->next=p; p2=p2->next; } else //p1的指數(shù)小于p2的指數(shù) { p=<dnode*>malloc<sizeof<dnode>>; p->e=p1->e; p->c=p1->c; p->next=t->next; t->next=p; p1=p1->next; } } while<p1!=NULL> //p2為空,p1不為空時 { p=<dnode*>malloc<sizeof<dnode>>; p=p1; p1=p1->next; p->next=t->next; //把p1放在結(jié)果鏈表后面 t->next=p; } while<p2!=NULL> //p1為空,p2不為空時 { p=<dnode*>malloc<sizeof<dnode>>; p->e=p2->e; if<sel==2> //如果選擇的是2,則將p2中剩余的項的系數(shù)取其相反數(shù) p->c=<-1>*p2->c; else p->c=p2->c; p2=p2->next; p->next=t->next; //把p1放在結(jié)果鏈表后面 t->next=p; } returnt; //返回運算后的多項式的頭結(jié)點}voidprn<dnode*h>//打印結(jié)果{ dnode*p; p=h->next; if<p==NULL>//如果多項式項數(shù)為0 { printf<"多項式項數(shù)為0,退出!\n">; exit<0>; } printf<"生成的多項式如下：\n">; while<<p->next>!=NULL>//否則,則輸出 { printf<"%3.1fX^%d+",p->c,p->e>; p=p->next; } if<p->next==NULL> { printf<"%3.1fX^%d\n",p->c,p->e>; }}floatqiuzhi<intx,dnode*h>//求多項式在x處的值{ dnode*p; floatsum=0; inti,t; printf<"請輸入x的值：">; scanf<"%d",&x>; for<p=h->next;p;p=p->next> { t=1; for<i=p->e;i!=0;> { if<i<0>{t/=x;i++;}//指數(shù)小于0,進行除法 else{t*=x;i--;}//指數(shù)小于0,進行除法 } sum+=p->c*t; } returnsum;}voidmain<>{ intx; floatsum=0; dnode*a,*b,*c; a=creat<>; //第一個多項式 sort<a>; //排序 prn<a>; //打印結(jié)果 b=creat<>; //第二個多項式 sort<b>; //排序 prn<b>; //打印結(jié)果 c=operate<a,b>;//結(jié)果多項式 prn<c>; //打印 sum=qiuzhi<x,c>; printf<"多項式的值為：%.3f",sum>; printf<"\n">;}[運行結(jié)果及分析]〔1輸入多項式：〔2輸出多項式〔多項式格式為：c1x^e1+c2x^e2+…+cnx^en：〔3實現(xiàn)多項式a和b相加：〔4實現(xiàn)多項式a和b相減：計算多項式在x處的值：2、模擬瀏覽器操作程序[實驗內(nèi)容]模擬瀏覽器操作程序[問題描述]標準Web瀏覽器具有在最近訪問的網(wǎng)頁間后退和前進的功能。實現(xiàn)這些功能的一個方法是：使用兩個棧,追蹤可以后退和前進而能夠到達的網(wǎng)頁。在本題中,要求模擬實現(xiàn)這一功能。[需求分析]需要支持以下指令：BACK：將當前頁推到"前進棧"的頂部。取出"后退棧"中頂端的頁面,使它成為當前頁。若"后退棧"是空的,忽略該命令。FORWARD：將當前頁推到"后退棧"的頂部。取出"前進棧"中頂部的頁面,使它成為當前頁。如果"前進棧"是空的,忽略該命令。VISIT<url>：將當前頁推到"后退棧"的頂部。使URL特指當前頁。清空"前進棧"。QUIT：退出瀏覽器。假設(shè)瀏覽器首先加載的網(wǎng)頁URL是：。[概要設(shè)計]-=ADT=-{typedefstructstacknodevoidpush<stacknode*top,stringe>//進棧stringpop<stacknode*top>//出棧voidInitStack<stacknode*top>//棧的初始化intgetempty<stacknode*top>intmain<>}[存儲結(jié)構(gòu)]typedefstructstacknode{ chardata[70]; structstacknode*next;}stacknode;[流程圖][詳細設(shè)計]源代碼如下：#include<fstream>//C++文件輸入輸出流#include<string>//字符串操作#include<iostream>//C++標準輸入輸出#include<strstream>//實現(xiàn)將char[]轉(zhuǎn)換成string的功能頭文件usingnamespacestd;typedefstructstacknode{ chardata[70]; structstacknode*next;}stacknode;voidpush<stacknode*top,stringe>//進棧{ stacknode*q; q=<stacknode*>malloc<sizeof<stacknode>>; strcpy<q->data,e.c_str<>>;//e.c_str<>庫函數(shù)實現(xiàn)將string類型的e轉(zhuǎn)換成char[]類型 q->next=top->next;//strcpy庫函數(shù)實現(xiàn)將轉(zhuǎn)換后的e.str<>復(fù)制到q->data中 top->next=q;}stringpop<stacknode*top>//出棧{ stacknode*p; chare[70]; if<top->next==NULL> { returnNULL; } else { p=top->next; top->next=p->next; strcpy<e,p->data>; free<p>; strstreams;//將char[]類型的e轉(zhuǎn)換成string類型的a,s是strstream的對象 s<<e;//這些都是C++封裝好的,用法固定,沒有什么為什么 stringa; s>>a; returna; }}voidInitStack<stacknode*top>//棧的初始化{ top->next=NULL;//初始化為一個帶有頭結(jié)點的鏈棧,頭結(jié)點的數(shù)據(jù)域沒有值}intgetempty<stacknode*top>//判斷棧是否為空{(diào) if<top->next==NULL> return1; else return0;}intmain<>{ stacknode*fls,*bls;//fls指向前進棧,bls指向后退棧 fls=<stacknode*>malloc<sizeof<stacknode>>;//分別開辟結(jié)點 bls=<stacknode*>malloc<sizeof<stacknode>>; InitStack<fls>;//分別初始化 InitStack<bls>;//用C++讀取文件,代碼比C語言要簡單方便很多,但是效率稍低 ifstreamfin<"input.txt">;//C++的文件輸入流,從硬盤讀到內(nèi)存,fin是自己定義的名字,可以隨便更改成別的名字 ofstreamfout<"output.txt">;//C++的文件輸出流,從內(nèi)存寫到硬盤,fout也是自己定義的名字,可以隨便更改成別的名字 stringURL=":///";//將初始加載的網(wǎng)頁賦值給URL,是string類型 stringdemand;/*關(guān)于為何使用string的說明：*/ cout<<"程序從input.txt文件讀取測試數(shù)據(jù)"<<endl;/*C語言只提供了char類型來處理字符,對于字符串只能用字符數(shù)組,很不方便*/ cout<<"測試輸出保存在output.txt文件中"<<endl;/*C++提供了string容器來處理字符串,在文件的讀取中比較方便*/ while<!fin.eof<>>//如果沒有讀取到文件結(jié)尾,則執(zhí)行循環(huán) { fin>>demand;//先將第一個字符串讀取到string類型的demand變量中,fin讀取會忽略空格,遇空格停止 if<demand=="VISIT">//如果讀到VISIT則執(zhí)行題目要求的相應(yīng)操作 { push<bls,URL>;//將當前頁推到后退棧 fin>>URL;//將當前頁推到后退棧后,接著讀取VISIT后面的網(wǎng)址 fout<<URL<<endl;//將當前頁輸出到文件中 InitStack<fls>;//清空前進棧 } if<demand=="BACK">//如果獨到BACK { if<getempty<bls>>//判斷后退棧如果為空則輸出Ignored到文件中 { fout<<"Ignored"<<endl; continue;//Ignored說明忽略這條命令,則結(jié)束本次循環(huán) } push<fls,URL>;//否則將當前頁推到前進棧 URL=pop<bls>;//取出后退棧中頂端的頁面,使它成為當前頁 fout<<URL<<endl;//將當前頁寫入到文件 } if<demand=="FORWARD">//如果獨到FORWARD { if<getempty<fls>>//如果前進棧是空的,則輸出Ignored到文件中 { fout<<"Ignored"<<endl; continue;//Ignored說明忽略這條命令,則結(jié)束本次循環(huán) } push<bls,URL>;//否則將當前頁推到后退棧 URL=pop<fls>;//取出前進棧中頂端的頁面,使它成為當前頁 fout<<URL<<endl;//將當前頁寫入到文件 } if<demand=="QUIT">//如果讀到QUIT,則退出程序 exit<1>; } return0;}[運行結(jié)果及分析]運行程序界面：input與output文件截圖：背包問題的求解[實驗內(nèi)容]背包問題的求解。[問題描述]假設(shè)有一個能裝入總體積為T的背包和n件體積分別為w1,w2,…wn的物品,能否從n件物品中挑選若干件恰好裝滿背包,即使w1+w2+…+wm=T,要求找出所有滿足上述條件的解。例如：當T=10,各件物品的體積{1,8,4,3,5,2}時,可找到下列4組解： <1,4,3,2> <1,4,5> <8,2> <3,5,2>。[概要設(shè)計]可利用回溯法的設(shè)計思想來解決背包問題。首先,將物品排成一列,然后,順序選取物品裝入背包,若已選取第i件物品后未滿,則繼續(xù)選取第i+1件,若該件物品"太大"不能裝入,則棄之,繼續(xù)選取下一件,直至背包裝滿為止。如果在剩余的物品中找不到合適的物品以填滿背包,則說明"剛剛"裝入的物品"不合適",應(yīng)將它取出"棄之一邊",繼續(xù)再從"它之后"的物品中選取,如此重復(fù),直到求得滿足條件的解,或者無解。由于回溯求解的規(guī)則是"后進先出",自然要用到"棧"。[存儲結(jié)構(gòu)]structstacks//定義一個順序棧結(jié)構(gòu){intdata[size];inttop;}stack;[流程圖]輸入預(yù)期總體積T輸入預(yù)期總體積T輸入各物體體積輸入各物體體積否否是輸入是否為0結(jié)束是輸入是否為0結(jié)束計算總體積sum計算總體積sum否sum是否等于T否sum是否等于T是是輸出解輸出解[詳細設(shè)計]源代碼如下：#include<stdio.h>#definesize100structstacks//定義一個順序棧結(jié)構(gòu){intdata[size];inttop;}stack;voidbag<intV,intw[size],intnumber>//向背包中裝入物品{ inti=0,j=1,k=0,c=0;//c為背包裝滿與否的標志 stack.top=0;//將順序棧置空 do{while<V>0&&k<=number>{if<V>=w[k]>{stack.data[stack.top]=k;//將符合條件的物品的下標入棧stack.top++;//棧頂元素的位置后移V-=w[k];//計算背包的剩余體積}k++;}if<V==0>{printf<"第%d個符合條件的解：",j>;for<i=0;i<stack.top;i++>{printf<"%d",w[stack.data[i]]>;}j++;printf<"\n">; c=1;} k=stack.data[--stack.top];//彈棧 stack.data[stack.top]=0; V+=w[k]; k++;//繼續(xù)試探之后的物品}while<!<stack.top==0&&k==number>>; if<c==0> printf<"所提供的物品不能將背包裝滿！\n">;}voidmain<>{intw[size];//存放物品intV;//背包所能承受的總體積inti=0;intj=1;intnumber;//可供選擇裝入物品的總個數(shù)ints=0;//可供選擇裝入物品的總體積printf<"請輸入可供裝入背包的物品的總個數(shù)：">;scanf<"%d",&number>;printf<"\n請輸入各件物品的體積分別為：\n">;for<i=0;i<number;i++>scanf<"%d",&w[i]>;for<i=0;i<number;i++>//計算物品的總體積s=s+w[i];printf<"\n可供選擇的物品的總體s=%d\n",s>;printf<"\n請輸入背包的總體積：">;scanf<"%d",&V>;printf<"\n">; bag<V,w,number>;}[運行結(jié)果及分析]〔1當提供的物品能將背包裝滿時：〔2當提供的物品不能將背包裝滿時：4、八皇后問題[實驗內(nèi)容]八皇后問題[問題描述]八皇后問題是一個古老而著名的問題,是回溯算法的典型例題。該問題是十九世紀著名的數(shù)學家高斯1850年提出：在8×8格的國際象棋上擺放8個皇后。若兩個皇后位于同一行、同一列或同一對角線上,則稱它們?yōu)榛ハ喙?。在國際象棋中皇后是最強大的旗子,因為它的攻擊范圍最大。[需求分析]本題要求是：編程解決八皇后問題。在8*8棋盤上,放置8個皇后。要求使這8個皇后不能互相攻擊,即每一橫行、每一列、每一對角線上均只能放置一個皇后,求出所有可能的方案,輸出這些方案,并統(tǒng)計方案總數(shù)。[概要設(shè)計]-=ADT=-{intfuzhi<> //為N賦值voidPrint<intN,intx[]>//將結(jié)果打印為矩陣intJudge<intk,intx[]>//判斷是否在同一直、橫、斜線上有其它棋子voidbacktrack<intt,intN,intx[]>//將結(jié)果以矩陣形式展現(xiàn)出來voidjiemian<>voidmain<>}[存儲結(jié)構(gòu)]本題采用數(shù)組作為存儲結(jié)構(gòu)[流程圖]數(shù)據(jù)初始化數(shù)據(jù)初始化從當前點當前方向開始,判斷能否向前走結(jié)束程序向前走一步〔入棧是否已到達目標位置輸出結(jié)果新位置作為當前點方向數(shù)加1方向數(shù)是否超界退回一步〔退棧是否已經(jīng)回到起點能否否否是是是否[詳細設(shè)計]源代碼如下：#include<math.h> //用abs<>要調(diào)用的頭文件#include<stdio.h>#include<string.h>#include<conio.h>//用getch<>要調(diào)用的頭文件#include<stdlib.h>//要用system函數(shù)要調(diào)用的頭文件intfuzhi<> //為N賦值{ intN; printf<"\n請輸入N=">; scanf<"%d",&N>; returnN;}voidPrint<intN,intx[]>//將結(jié)果打印為矩陣{intMAX=N,sum=0; //sum用來統(tǒng)計有多少種可能 for<inti=0;i<MAX;i++> { for<intj=0;j<MAX;j++> if<j==x[i]> printf<"■">; else printf<"□">; printf<"\n">; } sum++; //打印一種情況統(tǒng)計一次 printf<"\n">;}intJudge<intk,intx[]>//判斷是否在同一直、橫、斜線上有其它棋子{inti; f