计算机数据结构与算法分析课内实验报告

1、数据结构与算法分析课内实验小组成员：计算机 22 班：（2120505049）（2120505026）计算机 21 班：（2120505008）一、一元稀疏多项式计算器的实现程序源文件：#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 项数： 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 的项数（包括系数为零的项） n;xiangshu = n;duoxiangshi1.setXiangs);cout 请输入每一项的系数，由指数为零项的系数开始依指数升序输入，注意系数为零项的系数请输入 0，不能省略不输 endl;i, k;for (i = 0; i

18、k; duoxiangshi1.insert(k, i);duoxiangshi1.pr();cout 请输入多项式B endl;cout 请输入多项式B 的项数（包括系数为零的项） n;xiangshu2 = n;duoxiangshi2.setXiangs);cout 请输入每一项的系数，由指数为零项的系数开始依指数升序输入，注意系数为零项的系数请输入 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 请选择相应操作：n 若计算 A+B，请输入 1n 若计算 A-B，请输入2n 若计算 B-A，请输入请输入5 h; switch (h)case 1:duoxiangshi1.pr endl;duoxiangshi33n 若要计算多项式的值，请输入4n 若要结束操作，(); 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;实验结果：二、八皇后问题程序设计：

22、利用二维数组 vis2直接判断当前尝试的皇后所在的列和两个对角线是否已有其他皇后。如果没有其他皇后，则进行程序代码：#includen=8,vis320,C10,tot;，由此可以设计出方案。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;运行结果：三、背包问题程序设计：可通过递归算法实现，每次加入一个物体，用总体积减去加入的物体体积，若体积小于零，则退出；若等于零，则输出方案。程序代码：#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;运行结果：四、学生成绩分析#include #include #include #define maxsize1 100 /学生名字的最大字苻/ #define maxsize2 10/学生的最大个数*/typedef structnumber; /*学号*/char namemaxsize1; /*/pro5; /*1 为 数学的成绩，2 为 英语的成绩，3 为电脑的成绩，4 为平均成绩*/node;typedef structnode stumaxsize2; /*存放学生成绩*/ num; /*存放学生人数*/md;md creat() /*创建学生信息*/md a

26、; i;prf(enter 学生人数 ON.:);scanf(%d,&a.num); for(i=1;i=a.num;i+)prf(enter %d 号学生信息:,i); scanf(%d%s,&a.stui.number,&);prf(enter %d 数，电脑成绩:,i);scanf(%d%d%d,&1,&2,&3);return a;void disp(md a)/*输出学生信息*/i;for(i=1;i=a.num;i+)prf(学号名字:%s,数学:%d,英语:%d,电:%d,脑 :%d,average

27、:%dn,a.stui.number,,1,2,3,a. 4);void sort(md a,m) /*排序函数*/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)/*按学生的功课排序*/select,i;for(i=1;i=a.num;i+)/*求每个学生的平均成绩*/a.st

28、4=(1+2+3)/3;doprf(1.数学成绩排序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.数学平均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)/*按学号查找学生信息*/i;for(i=1;i=a.num;i+)if(a.stui.number=b)prf(名字:%s,数学:%d,英语:%d,电脑:%dn,,1,

30、2,3); return;void find_na(md a,char ch)/*按名字查找学生信息*/i;for(i=1;i=a.num;i+)if(!strcmp(,ch)prf(学号:%d,数学:%d,英语:%d,电脑:%dn,a.stui.number,1,2,3); return;void fun3(md a)/*学生信息查找函数*/x,select;chardoaxsize1;prf(1.按学号查找n);prf(2.按名字查找n);prf(3.returnn);prf(enter

31、select(1-3):); scanf(%d,&select);if(select=3)return;else if(select=1)/*按学号查找*/prf(enter 学号: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);实验结果：五：迷宫问题程序代码如下： #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)();/打印目前的状态if(isFind(x,y)count+;coutnow it find count roadendl;/如果找到目标结尾点，就让方法计数器 count+；for(i=0;i4;i+)/利用方向数组进行四个方向的探索p=x+diri0;q=