計算機數(shù)據(jù)結(jié)構(gòu)與算法分析課內(nèi)實驗報告

1、數(shù)據(jù)結(jié)構(gòu)與算法分析課內(nèi)實驗小組成員：計算機 22 班：（2120505049）（2120505026）計算機 21 班：（2120505008）一、一元稀疏多項式計算器的實現(xiàn)程序源文件：#include iostreamusing namespaclass Link public:zhishu;td;double xishu;Link *next;Link(const double& elemval2, constzhishu = elemval; xishu = elemval2; next = nextval;Link(Link* p = NULL)next = p;Link(const

2、Link& p)zhishu = p.zhishu; xishu = p.xishu;if (p.next = NULL) next = NULL;elsenext = new Link(*p.next);& elemval, Link* nextval = NULL);class LList private:Link* head; Link* tail;Link* fence;t;t;void init()fence = tail = head = new Link;t =t = 0;void removeall()while (head != NULL)fence = head;head

3、= head-next; delete fence;public:LList()init();LList(const LList& p)t =t =t;t;head = new Link(*p.head);fence = head; for (; next()if (fence-next = NULL)tail = fence; break;i;xiangshu, zhishu; double xishu;p.getValue(xishu, zhishu); p.getXiangshu(xiangshu); setStart();for (i = 0; i next = new Link(it

4、em, item2, fence-next);if (tail = fence)tail = fence-next; t+;return true;bool append(const&);bool remove(double& it,& it2)if (fence-next = NULL)return false;it = fence-next-xishu;it2 = fence-next-zhishu; Link* ltemp = fence-next; fence-next = ltemp-next; if (tail = ltemp)tail = fence;dele temp; t-;

5、return true;void setStart()fence = head;t += t = 0;void setEnd()setStart();t;for (; fence-next != tail;)next();t = 1;t +=t - 1;/void prev(); bool next()if (fence-next != tail)fence = fence-next;t-; t+;return true;elsefence = fence-next;t-; t+;return false;leftLength()constreturnt;rightLength()constr

6、eturnt;bool setif ()t +t)return false;fence = head;t += t = 0;t;for (i = 0; i zhishu = it; return true;bool getXiangshu(& ti)constif (head = NULL)return false; ti = head-zhishu; return true;bool changeValue(double it,it2)if (fence = tail)return false;fence-next-xishu = it;fence-next-zhishu = it2; re

7、turn true;bool getValue(double& it,if (fence = tail)return false;it = fence-next-xishu;& it2)constit2 = fence-next-zhishu;return true;void pr()double value; value2;setStart();cout 項數(shù)： zhishu for (;)if (fence != head)cout +; getValue(value, value2);多項式：;cout ( value ) x next = tail)break; next();cout

8、 next = NULL)tail = fence; break;i;xiangshu, zhishu; double xishu;p.getValue(xishu, zhishu); p.getXiangshu(xiangshu); setStart();for (i = 0; i (xiangshu - zhishu - 1); i+) next();return *this;LList operator+(LList& it)xiangshu, xiangshu2;it.getXiangshu(xiangshu2); getXiangshu(xiangshu);if (xiangshu

9、xiangshu2)i;LList item;for (i = 0; i xiangshu2; i+)item.insert(1, 1);double xi, xi2; zhi, zhi2;setStart();it.setStart();item.setStart();for (i = 0; i (xiangshu2 - xiangshu); i+)it.next();item.next();for (;)it.getValue(xi2, zhi2); getValue(xi, zhi);item.changeValue(xi + xi2, zhi);if (next()it.next();

10、item.next();elseitem.setStart(); it.setStart();for (i = 0, it.getValue(xi2, zhi2); i (xiangshu2 - xiangshu); i+, item.next(), it.next(), it.getValue(xi2, zhi2)item.changeValue(xi2, zhi2); return item;elsei;LList item;for (i = 0; i xiangshu; i+)item.insert(1, 1);double xi, xi2; zhi, zhi2;setStart();i

11、t.setStart();item.setStart();for (i = 0; i (xiangshu - xiangshu2); i+)next();item.next();for (;)it.getValue(xi2, zhi2); getValue(xi, zhi);item.changeValue(xi + xi2, zhi); if (next()it.next();item.next();elseitem.setStart();setStart();for (i = 0, getValue(xi, zhi); i (xiangshu - xiangshu2); i+, item.

12、next(),next(), getValue(xi, zhi)item.changeValue(xi, zhi);return item;LList operator-(LList& it)xiangshu, xiangshu2;it.getXiangshu(xiangshu2); getXiangshu(xiangshu);if (xiangshu xiangshu2)i;LList item;for (i = 0; i xiangshu2; i+)item.insert(1, 1);double xi, xi2; zhi, zhi2;setStart();it.setStart();it

13、em.setStart();for (i = 0; i (xiangshu2 - xiangshu); i+)it.next();item.next();for (;)it.getValue(xi2, zhi2); getValue(xi, zhi);item.changeValue(xi - xi2, zhi); if (next()it.next();item.next();elseitem.setStart();it.setStart();for (i = 0, it.getValue(xi2, zhi2); i (xiangshu2 - xiangshu); i+, item.next

14、(), it.next(), it.getValue(xi2, zhi2)item.changeValue(-xi2, zhi2); return item;elsei;LList item;for (i = 0; i xiangshu; i+)item.insert(1, 1);double xi, xi2; zhi, zhi2;setStart();it.setStart();item.setStart();for (i = 0; i (xiangshu - xiangshu2); i+)next();item.next();for (;)it.getValue(xi2, zhi2); g

15、etValue(xi, zhi);item.changeValue(xi - xi2, zhi); if (next()it.next();item.next();elseitem.setStart();setStart();for (i = 0, getValue(xi, zhi); i (xiangshu - xiangshu2); i+, item.next(),next(), getValue(xi, zhi)item.changeValue(xi, zhi);return item;bool getY(double& it)setStart();if (fence = NULL)re

16、turn false; double xishu;zhishu, i; double x, y; y = 1; it = 0;cout 請輸入 X 值 x;for (;)getValue(xishu, zhishu); for (i = 0; i zhishu; i+)y = y*x; y = y*xishu; it = it + y;if (next()y=1; elsecout Y=; setStart(); for (;)if (fence != head)cout +; getValue(xishu, zhishu);cout ( xishu ) x next = tail)break

17、;next();cout = it m2)return m1;else return m2;main()LList duoxiangshi1;LList duoxiangshi2; LList duoxiangshi3;n, xiangshu, xiangshu2;cout 請輸入多項式 A endl;cout 請輸入多項式 A 的項數(shù)（包括系數(shù)為零的項） n;xiangshu = n;duoxiangshi1.setXiangs);cout 請輸入每一項的系數(shù)，由指數(shù)為零項的系數(shù)開始依指數(shù)升序輸入，注意系數(shù)為零項的系數(shù)請輸入 0，不能省略不輸 endl;i, k;for (i = 0; i

18、k; duoxiangshi1.insert(k, i);duoxiangshi1.pr();cout 請輸入多項式B endl;cout 請輸入多項式B 的項數(shù)（包括系數(shù)為零的項） n;xiangshu2 = n;duoxiangshi2.setXiangs);cout 請輸入每一項的系數(shù)，由指數(shù)為零項的系數(shù)開始依指數(shù)升序輸入，注意系數(shù)為零項的系數(shù)請輸入 0，不能省略不輸 endl;for (i = 0; i k; duoxiangshi2.insert(k, i);duoxiangshi2.pr();for (i = 0; i max(xiangshu, xiangshu2); i+) d

19、uoxiangshi3.insert(1, 1);for (;)cout nnnnn 請選擇相應(yīng)操作：n 若計算 A+B，請輸入 1n 若計算 A-B，請輸入2n 若計算 B-A，請輸入請輸入5 h; switch (h)case 1:duoxiangshi1.pr endl;duoxiangshi33n 若要計算多項式的值，請輸入4n 若要結(jié)束操作，(); cout + endl; duoxiangshi2.pr(); cout =duoxiangshi1+duoxiangshi2;duoxiangshi3.setXiangshu(max(xiangshu, xiangshu2); duox

20、iangshi3.pr(); break;case 2:duoxiangshi1.pr(); cout - endl; duoxiangshi2.pr(); cout endl;= duoxiangshi3=duoxiangshi1-duoxiangshi2;duoxiangshi3.setXiangshu(max(xiangshu, xiangshu2); duoxiangshi3.pr(); break;case 3:duoxiangshi2.pr(); cout - endl; duoxiangshi1.pr(); cout endl;= duoxiangshi3=duoxiangshi

21、2-duoxiangshi1;duoxiangshi3.setXiangshu(max(xiangshu, xiangshu2); duoxiangshi3.pr (); break;case 4:char q; double w; cout 計算多項式A 還是多項式 B？ q; if (q = A)duoxiangshi1.getY(w); else if (q = B)duoxiangshi2.getY(w); else cout 輸入錯誤，請重新輸入命令 endl; break;case 5:break;if (h = 5)break;return 0;實驗結(jié)果：二、八皇后問題程序設(shè)計：

22、利用二維數(shù)組 vis2直接判斷當前嘗試的皇后所在的列和兩個對角線是否已有其他皇后。如果沒有其他皇后，則進行程序代碼：#includen=8,vis320,C10,tot;，由此可以設(shè)計出方案。void search(i,j;cur)if(cur=n)for(j=0;jn;j+) coutCj ; coutendl; tot+;else for(i=0;in;i+)if(!vis0i&!vis1cur+i&!vis2cur-i+n)/判斷每一行每一列每一斜行是否已有皇后Ccur=i;vis0i=vis1cur+i=vis2cur-i+n=1; search(cur+1);vis0i=vis1cu

23、r+i=vis2cur-i+n=0;main()search(0);couttotn; return 0;運行結(jié)果：三、背包問題程序設(shè)計：可通過遞歸算法實現(xiàn)，每次加入一個物體，用總體積減去加入的物體體積，若體積小于零，則退出；若等于零，則輸出方案。程序代碼：#include #include #include using namespatd;constMAX_N = 30;t, n, wMAX_N;bool choiceMAX_N;void pr() sicnum = 0;cout Solution No. +num : endl;for (i = 1; i = n; +i)if (choic

24、ei) cout wi ( i )t; /體積（）cout endl;void DFS(x,last) if (last 0) return;if (x = n + 1) if (last = 0) pr(); return;choicex = false; DFS(x + 1, last); choicex = true;DFS(x + 1, last - wx);main() cout t;cout n;cout Input the sizes of the items:n;for (i = 1; i wi;memset(choice, 0, sizeof choice);DFS(1, t

25、);return 0;運行結(jié)果：四、學(xué)生成績分析#include #include #include #define maxsize1 100 /學(xué)生名字的最大字苻/ #define maxsize2 10/學(xué)生的最大個數(shù)*/typedef structnumber; /*學(xué)號*/char namemaxsize1; /*/pro5; /*1 為 數(shù)學(xué)的成績，2 為 英語的成績，3 為電腦的成績，4 為平均成績*/node;typedef structnode stumaxsize2; /*存放學(xué)生成績*/ num; /*存放學(xué)生人數(shù)*/md;md creat() /*創(chuàng)建學(xué)生信息*/md a

26、; i;prf(enter 學(xué)生人數(shù) ON.:);scanf(%d,&a.num); for(i=1;i=a.num;i+)prf(enter %d 號學(xué)生信息:,i); scanf(%d%s,&a.stui.number,&);prf(enter %d 數(shù)，電腦成績:,i);scanf(%d%d%d,&1,&2,&3);return a;void disp(md a)/*輸出學(xué)生信息*/i;for(i=1;i=a.num;i+)prf(學(xué)號名字:%s,數(shù)學(xué):%d,英語:%d,電:%d,腦 :%d,average

27、:%dn,a.stui.number,,1,2,3,a. 4);void sort(md a,m) /*排序函數(shù)*/i,j;node temp;for(i=0;ia.num;i+)/*起泡法從小到大排序*/ for(j=0;ja.stuj+1.prom)temp=a.stuj;a.stuj=a.stuj+1;a.stuj+1=temp; disp(a);void fun1(md a)/*按學(xué)生的功課排序*/select,i;for(i=1;i=a.num;i+)/*求每個學(xué)生的平均成績*/a.st

28、4=(1+2+3)/3;doprf(1.數(shù)學(xué)成績排序n);f(2.英語成績排序n);f(3.電腦成績排序n);f(4.average n);f(5.return n);f(enter select(1-5):);prpr pr prprscanf(%d,&select);if(select!=5)sort(a,select); else return;while(1);void fun2(md a)/*按各們功課平均成績排序*/select,i,al;doprf(1.數(shù)學(xué)平均n);prf(2.英語平均n);prf(3.電腦

29、平均n);prf(4.return n);prf(enter select(1-4):); scanf(%d,&select);if(select=4)return; elseal=0;for(i=1;ia.num;i+)al+=select;prf(平均成績:%dn,al/a.num);while(1);void find_nu(md a,b)/*按學(xué)號查找學(xué)生信息*/i;for(i=1;i=a.num;i+)if(a.stui.number=b)prf(名字:%s,數(shù)學(xué):%d,英語:%d,電腦:%dn,,1,

30、2,3); return;void find_na(md a,char ch)/*按名字查找學(xué)生信息*/i;for(i=1;i=a.num;i+)if(!strcmp(,ch)prf(學(xué)號:%d,數(shù)學(xué):%d,英語:%d,電腦:%dn,a.stui.number,1,2,3); return;void fun3(md a)/*學(xué)生信息查找函數(shù)*/x,select;chardoaxsize1;prf(1.按學(xué)號查找n);prf(2.按名字查找n);prf(3.returnn);prf(enter

31、select(1-3):); scanf(%d,&select);if(select=3)return;else if(select=1)/*按學(xué)號查找*/prf(enter 學(xué)號:n);scanf(%d,&x); find_nu(a,x);elseprf(enter 名字:n);/*按名字查找*/ gets(ch);find_na(a,ch);while(1);void main()md h;select; h=creat(); doprf(1.排序n);prf(2.class_平均 en); prf(3.查找n);prf(4.exitn);prf(enter select(1-4):);

32、scanf(%d,&select);if(select=4)prf(OK! n); exit(0);if(select=1)fun1(h);else if(select=2)fun2(h); else if(select=3)fun3(h);while(1);實驗結(jié)果：五：迷宮問題程序代碼如下： #include #include #include #include #define MAXSTACK 500using namespatd;typedef structx;y;m,n; count=0; start,end;maze100100;dir42=-1,0,1,0,0,-1,0,1;bo

33、ol isFind(x,y)if(end.x=x&end.y=y) return true;elsereturn false;void pr()system(CLS);for(i=0;i10;i+)for(j=0;j10;j+)switazeij)case 0: prcase 1: prcase 2: prf( ); break;f(#); break;f(.); break;coutendl;Sleep(100);void dfs(prx,y)();/打印目前的狀態(tài)if(isFind(x,y)count+;coutnow it find count roadendl;/如果找到目標結(jié)尾點，就讓方法計數(shù)器 count+；for(i=0;i4;i+)/利用方向數(shù)組進行四個方向的探索p=x+diri0;q=