一、课程设计概述：
本次数据结构课程设计共完成五个题：一元稀疏多项式计算器、迷宫问题、成绩分析问题、图的基本操作与实现以及背包问题的求解
使用语言：C
编译环境：TC3.0
二、课程设计题目一
[实验内容]
一元稀疏多项式计算器
[问题描述]
设计一个一元稀疏多项式简单计算器。
[基本要求]
一元稀疏多项式简单计算器的基本功能是：
（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：n,c1,e1, c2,e2,,,,,,, c n,e n,其中n是多项式的项数，
c i,e i,分别是第i项的系数和指数，序列按指数降序排序；
（3）多项式a和b相加，建立多项式a+b；
（4）多项式a和b相减，建立多项式a-b；
（5）计算多项式在x处的值。
（6）计算器的仿真界面。（选做）
[概要设计]
-=ADT=-
Test1:主类，程序的启动
Item :项，表示多项式中的某一项
Ploynomial：多项式类
[存储结构]
Item属性：
private double c;//系数
private int e;//指数
Item方法：
public void setC(double c){//设置系数
}
public void setE(int e){ //设置指数
}
public double getC(){//获取系数
}
public int getE(){//获取指数
}
public double resultItem(double x){//在x处Item的值
}
private double fac(double x,int e){//求x的e次方,当e为整数时
}
Polynomial属性：
private LinList list;//单链表
Polynomial方法：
public Polynomial(){
}
public Polynomial(Item [] item)throws Exception{ //构造函数
}
private void initItem(Item [] item){//初始化Item数组，使其是按降序排序}
public int getItemNum(){//获取项数
}
public void print()throws Exception{//打印多项式不空行
}
public void println()throws Exception{//打印多项式空行
}
public LinList getLinList(){//获取单链表
}
public void printPolynomial()throws Exception{//只打印项数、系数和指数
}
public Polynomial add(Polynomial other)throws Exception{//多项式相加}
}
public Polynomial subtraction(Polynomial other)throws Exception{//多项式相减}
public double result(double x)throws Exception{
}
[详细设计]
Item类：
public class Item {
private double c;//系数
private int e;//指数
public Item(){}
public Item(double c,int e){
this.c=c;
this.e=e;
}
public void setC(double c){
this.c=c;
}
public void setE(int e){
this.e=e;
}
public double getC(){
return c;
}
public int getE(){
return e;
}
public double resultItem(double x){
return getC()*fac(x,getE());
}
private double fac(double x,int e){//求x的e次方,当e为整数时if(e==0) return 1;
return x*fac(x,e-1);
}
}
Polynomial类：
import java.util.*;
public class Polynomial{//多项式类
private LinList list;//单链表
public Polynomial(){
list=new LinList(0,null);
}
public Polynomial(Item [] item)throws Exception{ //构造函数int n=item.length;
list=new LinList(n,null);
if(n==0){
return;
}
initItem(item);
try{
for(int i=0;i list.insert(i,item[i]); }catch(Exception e){} } private void initItem(Item [] item){//初始化Item数组，使其是按降序排序int n=item.length; int max; for(int i=0;i max=i; for(int j=i+1;j if(item[j].getE()>item[max].getE()) max=j; if(max!=i){ Item temp=item[i]; item[i]=item[max]; item[max]=temp; } } } public int getItemNum(){//获取项数 Object temp=list.head.getElement(); int n=-1; if(temp instanceof Integer){ Integer i=(Integer)temp; n=i.intValue(); } return n; } public void print()throws Exception{//打印多项式不空行 int n=getItemNum(); // System.out.println(n); if(n==-1) return ; if(n==0){ System.out.print("0"); return; } boolean flag=true;//是不是输出第一项的标志 for(int i=0;i Item temp=(Item)list.getData(i); double c=temp.getC(); if(c==0) continue;//系数为0时不输出 if(flag && temp.getE()!=0 ){ System.out.print(c+"x^"+temp.getE()); } else if(flag && temp.getE()==0) System.out.print(temp.getC()); else { if(c>0) System.out.print("+"+c+"x^"+temp.getE()); else if(c<0) System.out.print(c+"x^"+temp.getE()); } flag=false; } } public void println()throws Exception{//打印多项式空行 print(); System.out.println(); } public LinList getLinList(){//获取单链表 return list; } public void printPolynomial()throws Exception{//只打印项数、系数和指数int n=getItemNum(); if(n==0) return ; System.out.print(n+","); for(int i=0;i Item item=(Item)this.getLinList().getData(i); if(i!=n-1){ System.out.print("c"+i+"="+item.getC()+", "+"e"+i+"="+item.getE()+", "); } else{ System.out.print("c"+i+"="+item.getC()+", "+"e"+i+"="+item.getE()); } } System.out.println(); } public Polynomial add(Polynomial other)throws Exception{//多项式相加 LinList otherList=other.getLinList(); int n1=getItemNum();//该多项式的项数 int n2=other.getItemNum();//另一个多项式的项数 if(n2==0) return this; if(n1==0) return other; Polynomial temp=new Polynomial(); int i=0,j=0; while (+i Item item=new Item(); Item item1=(Item)list.getData(i); Item item2=(Item)otherList.getData(j); double c1=item1.getC();//获得系数 double c2=item2.getC(); int e1=item1.getE();//获得指数 int e2=item2.getE(); if(e1==e2){//相等时 double c=c1+c2; item.setC(c); item.setE(e1); i++; j++; } else if(e1 item=item2; j++; } else { item=item1; i++; } try{ if(item.getC()==0)//当得到项的系数为0时就没有必要加入 continue; temp.getLinList().insert(temp.getLinList().size(),item); }catch(Exception e){} } //将没有参加比较的项加进去，注意比较之后有且只有一个有多余的项while(i Item item1=(Item)list.getData(i); try{ temp.getLinList().insert(temp.getLinList().size(),item1); }catch(Exception e){} i++; } while(j Item item1=(Item)otherList.getData(j); try{ temp.getLinList().insert(temp.getLinList().size(),item1); }catch(Exception e){} j++; } temp.getLinList().head.setElement(temp.getLinList().size());//设置项数 return temp; } public Polynomial subtraction(Polynomial other)throws Exception{//多项式相减int n=other.getItemNum(); if(n==0) return this; Polynomial temp=new Polynomial(); LinList l=temp.getLinList(); for(int i=0;i Item item =(Item)other.getLinList().getData(i); double c=-1*item.getC();//取反 l.insert(i,new Item(c,item.getE())); } l.head.setElement(n);//设置项数 return add(temp); } public double result(double x)throws Exception{ double sum=0; int n=getItemNum();//该多项式的项数 if(n==0) return 0; for(int i=0;i Item item=(Item)list.getData(i); sum+=item.resultItem(x); } return sum; } } Test1类： import java.io.*; import java.util.Scanner; public class Test1 { Scanner scanner =new Scanner(System.in); public static void main(String[] args)throws Exception{ Test1 test1=new Test1(); Scanner scanner1 =new Scanner(System.in); while(true){ System.out.println("请输入你要操作的系号：\n"+ "1)输出多项式\n"+ "2)多项式相加\n"+ "3)多项式相减\n"+ "4)计算多项式在x处的值\n"+ "5)退出"); String s=scanner1.next(); int t=-1; try{ t=Integer.parseInt(s); }catch(Exception e){} switch(t){ case 1:test1.printPolynomial();break; case 2:test1.add();break; case 3:test1.subtraction();break; case 4:test1.resultOfPolynomia();break; case 5:System.exit(0);break; default:System.out.println("你输入的操作有误，请重试\n");continue; } } } private void printPolynomial()throws Exception{//选择1时 System.out.println("请输入要输出的多项式的信息："); Item[] item=creatItemShuZu(); Polynomial p=new Polynomial(item); p.printPolynomial(); } private void add()throws Exception{//选择2时 System.out.println("请输入第一个多项式的信息："); Item[] item1=creatItemShuZu(); Polynomial p1=new Polynomial(item1); System.out.println("请输入第二个多项式的信息："); Item[] item2=creatItemShuZu(); Polynomial p2=new Polynomial(item2); Polynomial p=p1.add(p2); System.out.print("("); p1.print(); System.out.print(")+("); p2.print(); System.out.print(")="); p.print(); System.out.println(); } private void subtraction()throws Exception{//选择3时 System.out.println("请输入第一个多项式的信息："); Item[] item1=creatItemShuZu(); Polynomial p1=new Polynomial(item1); System.out.println("请输入第二个多项式的信息："); Item[] item2=creatItemShuZu(); Polynomial p2=new Polynomial(item2); Polynomial p=p1.subtraction(p2); System.out.print("("); p1.print(); System.out.print(")-("); p2.print(); System.out.print(")="); p.print(); System.out.println(); } private void resultOfPolynomia()throws Exception{//选择4时System.out.println("请输入要输出的多项式的信息："); Item[] item=creatItemShuZu(); Polynomial p=new Polynomial(item); System.out.println("请输入x="); double x=scanner.nextDouble(); System.out.println(p.result(x)); } private Item[] creatItemShuZu()throws Exception{//构造多项式数组System.out.print("项数n="); int n=scanner.nextInt(); double []c=new double[n]; int [] e=new int[n]; Item[] item=new Item[n]; System.out.print("请输入各项的系数："); for(int i=0;i c[i]=scanner.nextDouble(); System.out.print("请输入各项的指数："); for(int i=0;i e[i]=scanner.nextInt(); for(int i=0;i item[i]=new Item(c[i],e[i]); } return item; } } [调试分析] 本程序主要的操作对象是记录数组，使用的存储结构是结构体数组。另外还有对C语言中关于文件的操作，这是本程序中的一个重点也是难点，是此程序出现问题的主要原因之一： 问题一： 现象：输出的成绩不是正确的数字，而是一些类似于地址值的数字。 原因：程序中对各数组的下标操作不统一。因为程序要分别对三个科目的成绩进行统计，所以程序中就要有一个临时数组来存放成绩值，然而在将学科成绩存放在临时数组的过程中如果出现了下标不统一的情况，即在原记录数组中是1…n号元素存放数据,在临时数组中却是0…n-1号元素存放数据。就会引起程序的错误。解决的方法是将整个程序中相互有关的数组使用统一的下标存放数据，就可以避免这种问题。 问题二： 现象：这是一个关于文件操作的问题。在将记录存入文件以后再从文件中读取时就出现错误。 原因：在使用fwrite和fread命令的时候函数的参数没有写正确。fwrite和fread 命令的第一个参数是存储数据的首地址，如果没有地址没有正确，那么就不能正常地将数据存到文件中也不能正常地读取。 [运行结果及分析] 1. 初始界面： 2. 输出多项式测试： 输入数据： 输出结果： 3、多项式相加测试： 输入2后： 输入第一个多项式后： 输入第二个多项式后： 结果： 4、多项式相减与相加类似，这里就不举例。 5、计算多项式在x处的值测试：输入4后： 输完多项式和x的值后 结果： 三、课程设计题目二 2 迷宫问题 [问题描述] 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 [基本要求] （1）实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 （2）编写递归形式的算法，求得迷宫中所有可能的通路； （3）以方阵形式输出迷宫及其通路。（选做） [概要设计] public class InterSection{//路口类 //行列指定路口的位置 int row;//行下标 int col;//列下标 int w;//0和1分别表示迷宫中的通路和障碍 public InterSection(int r,int c,int w1){ } } Maze: public class Maze{ } public InterSection getFirstNeighbor(InterSection p){ //取路口point的第一个邻结点若不存在返回null 类似于图的下一个邻结点 //只要有一个路口的w值为那么这两个路口就不相通 } public InterSection getNext(InterSection p1,InterSection p2){//按顺时针获取的 } public boolean depthSearch(InterSection point)throws Exception{//递归 } public String answer(InterSection p)throws Exception{//非递归通过堆栈来实现} public void printMaze(){//打印迷宫 } } [详细设计] public class Maze{ InterSection[][] point;//路口的二维数组 InterSection exit;//出口的那个路口 int row;//迷宫的行数 int col;//迷宫的列数 boolean[][] visited; //构造迷宫 public Maze(int [][] p,int r,int c){//r行数c列数 row=r+1; col=c+1;
相关主题
文本预览