数据结构课程设计报告

..编号课程设计题目1、一元稀疏多项式计算器2、模拟浏览器操作程序3、背包问题的求解4、八皇后问题二级学院计算机科学与工程学院专业计算机科学与技术班级2011级37-3班学生姓名XX学号XXXXXXXXXX指导教师XXXXX评阅教师时间一元稀疏多项式计算器[实验内容]一元稀疏多项式计算器。[问题描述]设计一个一元稀疏多项式简单计算器。[需求分析]其基本功能包括：〔1输入并建立多项式；〔2输出多项式,输出形式为整数序列为：n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数,ci,ei分别是第i项的系数和指数,序列按指数降序排序；〔3多项式a和b相减,建立多项a+b；〔4多项式a和b相减,建立多项式a-b；〔5计算多项式在x处的值；〔6计算器的仿真界面〔选做；[概要设计]-=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<>； 主函数}[存储结构]typedefstructnode /*定义多项式每一项*/{ inte; //e为指数 floatc; //c为系数 structnode*next; //next指向下一项}dnode;[流程图]1．dnode*creat<>//多项式的创建,即输入两个多项式hwhile<项数<MAXN>输入多项式的系数和指数p->next=h->next;h->next=p;继续输入returnh;2.voidsort<dnode*h>//采用冒泡法对链表每一项重新排序//while<p->next!=NULL> p=p->next;//寻找尾结点pi=p;指向最后一次交换的位置,初值为表尾while<pi!=h->next>//外层循环,比较趟数for<p=h->next;p!=pi;p=p->next>内层循环,前后两两相比swap<p,q>;pl=p;//调用交换函数pi=pl;3.dnode*operate<dnode*a,dnode*b>//稀疏多项式计算// while<p&&q>比较对应两项的指数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;[详细设计]源代码如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineNULL0typedefstructnode /*定义多项式每一项*/{ inte; //e为指数 floatc; //c为系数 structnode*next; //next指向下一项}dnode;dnode*creat<> /*用链表存放多项式*/{ //多项式的创建,即输入两个多项式 dnode*h,*p; inte,i,n; //n为多项式的项数 floatc; //c为多项式的系数 h=<dnode*>malloc<sizeof<dnode>>; //分配头节点 h->next=NULL; do//当n为0或小于1时,则重新输入 { printf<"请输入多项式的项数n:">; scanf<"%d",&n>; }while<n<1>; for<i=1;i<=n;i++> //输入各项的系数c和指数e { printf<"请输入第%d项的系数c和指数e:",i>; scanf<"%f%d",&c,&e>; p=<dnode*>malloc<sizeof<dnode>>; //创建新结点 p->c=c;p->e=e; //将值传给data域 p->next=h->next;//用头插法建立链表 h->next=p; } returnh; //返回头结点}voidswap<dnode*p,dnode*q> /*交换p,q指针所指的指数和系数*/{ 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; //寻找尾结点 pi=p;//pi指向最后一次交换的位置,初值为表尾 while<pi!=h->next> //结点数大于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>;//调用交换函数 pl=p; } } pi=pl; //pi指向前一个结点 }}dnode*operate<dnode*a,dnode*b>/*稀疏多项式计算*/{ intsel; floatx; dnode*p1,*p2,*p,*t; //t为结果链表的表头 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> //指数相同 { if<sel==1> x=p1->c+p2->c; //系数相加 else x=p1->c-p2->c; //系数相减 if<x!=0> { p=<dnode*>malloc<sizeof<dnode>>; p->e=p1->e; p->c=x; p->next=t->next;//利用头插法将p结点插入t中 t->next=p; } p1=p1->next; p2=p2->next; } elseif<p1->e>p2->e>//p1的指数大于p2的指数 { 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的指数小于p2的指数 { 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放在结果链表后面 t->next=p; } while<p2!=NULL> //p1为空,p2不为空时 { p=<dnode*>malloc<sizeof<dnode>>; p->e=p2->e; if<sel==2> //如果选择的是2,则将p2中剩余的项的系数取其相反数 p->c=<-1>*p2->c; else p->c=p2->c; p2=p2->next; p->next=t->next; //把p1放在结果链表后面 t->next=p; } returnt; //返回运算后的多项式的头结点}voidprn<dnode*h>//打印结果{ dnode*p; p=h->next; if<p==NULL>//如果多项式项数为0 { printf<"多项式项数为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++;}//指数小于0,进行除法 else{t*=x;i--;}//指数小于0,进行除法 } sum+=p->c*t; } returnsum;}voidmain<>{ intx; floatsum=0; dnode*a,*b,*c; a=creat<>; //第一个多项式 sort<a>; //排序 prn<a>; //打印结果 b=creat<>; //第二个多项式 sort<b>; //排序 prn<b>; //打印结果 c=operate<a,b>;//结果多项式 prn<c>; //打印 sum=qiuzhi<x,c>; printf<"多项式的值为：%.3f",sum>; printf<"\n">;}[运行结果及分析]〔1输入多项式：〔2输出多项式〔多项式格式为：c1x^e1+c2x^e2+…+cnx^en：〔3实现多项式a和b相加：〔4实现多项式a和b相减：计算多项式在x处的值：2、模拟浏览器操作程序[实验内容]模拟浏览器操作程序[问题描述]标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈,追踪可以后退和前进而能够到达的网页。在本题中,要求模拟实现这一功能。[需求分析]需要支持以下指令：BACK：将当前页推到"前进栈"的顶部。取出"后退栈"中顶端的页面,使它成为当前页。若"后退栈"是空的,忽略该命令。FORWARD：将当前页推到"后退栈"的顶部。取出"前进栈"中顶部的页面,使它成为当前页。如果"前进栈"是空的,忽略该命令。VISIT<url>：将当前页推到"后退栈"的顶部。使URL特指当前页。清空"前进栈"。QUIT：退出浏览器。假设浏览器首先加载的网页URL是：。[概要设计]-=ADT=-{typedefstructstacknodevoidpush<stacknode*top,stringe>//进栈stringpop<stacknode*top>//出栈voidInitStack<stacknode*top>//栈的初始化intgetempty<stacknode*top>intmain<>}[存储结构]typedefstructstacknode{ chardata[70]; structstacknode*next;}stacknode;[流程图][详细设计]源代码如下：#include<fstream>//C++文件输入输出流#include<string>//字符串操作#include<iostream>//C++标准输入输出#include<strstream>//实现将char[]转换成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<>库函数实现将string类型的e转换成char[]类型 q->next=top->next;//strcpy库函数实现将转换后的e.str<>复制到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转换成string类型的a,s是strstream的对象 s<<e;//这些都是C++封装好的,用法固定,没有什么为什么 stringa; s>>a; returna; }}voidInitStack<stacknode*top>//栈的初始化{ top->next=NULL;//初始化为一个带有头结点的链栈,头结点的数据域没有值}intgetempty<stacknode*top>//判断栈是否为空{ if<top->next==NULL> return1; else return0;}intmain<>{ stacknode*fls,*bls;//fls指向前进栈,bls指向后退栈 fls=<stacknode*>malloc<sizeof<stacknode>>;//分别开辟结点 bls=<stacknode*>malloc<sizeof<stacknode>>; InitStack<fls>;//分别初始化 InitStack<bls>;//用C++读取文件,代码比C语言要简单方便很多,但是效率稍低 ifstreamfin<"input.txt">;//C++的文件输入流,从硬盘读到内存,fin是自己定义的名字,可以随便更改成别的名字 ofstreamfout<"output.txt">;//C++的文件输出流,从内存写到硬盘,fout也是自己定义的名字,可以随便更改成别的名字 stringURL=":///";//将初始加载的网页赋值给URL,是string类型 stringdemand;/*关于为何使用string的说明：*/ cout<<"程序从input.txt文件读取测试数据"<<endl;/*C语言只提供了char类型来处理字符,对于字符串只能用字符数组,很不方便*/ cout<<"测试输出保存在output.txt文件中"<<endl;/*C++提供了string容器来处理字符串,在文件的读取中比较方便*/ while<!fin.eof<>>//如果没有读取到文件结尾,则执行循环 { fin>>demand;//先将第一个字符串读取到string类型的demand变量中,fin读取会忽略空格,遇空格停止 if<demand=="VISIT">//如果读到VISIT则执行题目要求的相应操作 { push<bls,URL>;//将当前页推到后退栈 fin>>URL;//将当前页推到后退栈后,接着读取VISIT后面的网址 fout<<URL<<endl;//将当前页输出到文件中 InitStack<fls>;//清空前进栈 } if<demand=="BACK">//如果独到BACK { if<getempty<bls>>//判断后退栈如果为空则输出Ignored到文件中 { fout<<"Ignored"<<endl; continue;//Ignored说明忽略这条命令,则结束本次循环 } push<fls,URL>;//否则将当前页推到前进栈 URL=pop<bls>;//取出后退栈中顶端的页面,使它成为当前页 fout<<URL<<endl;//将当前页写入到文件 } if<demand=="FORWARD">//如果独到FORWARD { if<getempty<fls>>//如果前进栈是空的,则输出Ignored到文件中 { fout<<"Ignored"<<endl; continue;//Ignored说明忽略这条命令,则结束本次循环 } push<bls,URL>;//否则将当前页推到后退栈 URL=pop<fls>;//取出前进栈中顶端的页面,使它成为当前页 fout<<URL<<endl;//将当前页写入到文件 } if<demand=="QUIT">//如果读到QUIT,则退出程序 exit<1>; } return0;}[运行结果及分析]运行程序界面：input与output文件截图：背包问题的求解[实验内容]背包问题的求解。[问题描述]假设有一个能装入总体积为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>。[概要设计]可利用回溯法的设计思想来解决背包问题。首先,将物品排成一列,然后,顺序选取物品装入背包,若已选取第i件物品后未满,则继续选取第i+1件,若该件物品"太大"不能装入,则弃之,继续选取下一件,直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包,则说明"刚刚"装入的物品"不合适",应将它取出"弃之一边",继续再从"它之后"的物品中选取,如此重复,直到求得满足条件的解,或者无解。由于回溯求解的规则是"后进先出",自然要用到"栈"。[存储结构]structstacks//定义一个顺序栈结构{intdata[size];inttop;}stack;[流程图]输入预期总体积T输入预期总体积T输入各物体体积输入各物体体积否否是输入是否为0结束是输入是否为0结束计算总体积sum计算总体积sum否sum是否等于T否sum是否等于T是是输出解输出解[详细设计]源代码如下：#include<stdio.h>#definesize100structstacks//定义一个顺序栈结构{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++;//继续试探之后的物品}while<!<stack.top==0&&k==number>>; if<c==0> printf<"所提供的物品不能将背包装满！\n">;}voidmain<>{intw[size];//存放物品intV;//背包所能承受的总体积inti=0;intj=1;intnumber;//可供选择装入物品的总个数ints=0;//可供选择装入物品的总体积printf<"请输入可供装入背包的物品的总个数：">;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>;}[运行结果及分析]〔1当提供的物品能将背包装满时：〔2当提供的物品不能将背包装满时：4、八皇后问题[实验内容]八皇后问题[问题描述]八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放8个皇后。若两个皇后位于同一行、同一列或同一对角线上,则称它们为互相攻击。在国际象棋中皇后是最强大的旗子,因为它的攻击范围最大。[需求分析]本题要求是：编程解决八皇后问题。在8*8棋盘上,放置8个皇后。要求使这8个皇后不能互相攻击,即每一横行、每一列、每一对角线上均只能放置一个皇后,求出所有可能的方案,输出这些方案,并统计方案总数。[概要设计]-=ADT=-{intfuzhi<> //为N赋值voidPrint<intN,intx[]>//将结果打印为矩阵intJudge<intk,intx[]>//判断是否在同一直、橫、斜线上有其它棋子voidbacktrack<intt,intN,intx[]>//将结果以矩阵形式展现出来voidjiemian<>voidmain<>}[存储结构]本题采用数组作为存储结构[流程图]数据初始化数据初始化从当前点当前方向开始,判断能否向前走结束程序向前走一步〔入栈是否已到达目标位置输出结果新位置作为当前点方向数加1方向数是否超界退回一步〔退栈是否已经回到起点能否否否是是是否[详细设计]源代码如下：#include<math.h> //用abs<>要调用的头文件#include<stdio.h>#include<string.h>#include<conio.h>//用getch<>要调用的头文件#include<stdlib.h>//要用system函数要调用的头文件intfuzhi<> //为N赋值{ intN; printf<"\n请输入N=">; scanf<"%d",&N>; returnN;}voidPrint<intN,intx[]>//将结果打印为矩阵{intMAX=N,sum=0; //sum用来统计有多少种可能 for<inti=0;i<MAX;i++> { for<intj=0;j<MAX;j++> if<j==x[i]> printf<"■">; else printf<"□">; printf<"\n">; } sum++; //打印一种情况统计一次 printf<"\n">;}intJudge<intk,intx[]>//判断是否在同一直、橫、斜线上有其它棋子{inti; f