实验一 线性表的操作.docx
《实验一 线性表的操作.docx》由会员分享，可在线阅读，更多相关《实验一 线性表的操作.docx（26页珍藏版）》请在冰点文库上搜索。
实验一线性表的操作
《数据结构》
实验报告
项目名称线性表的操作
专业班级
学号
姓名
实验成绩：
批阅教师：
2013年03月31日
实验一线性表的操作
实验学时：
2实验地点：
科教楼四楼实验日期：
2013/3/20
1．需求分析
（1）程序设计的任务：
A.应用线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
B.实现一元n次多项式的加法运算
（2）规定：
输入的形式和输入值的范围：
长整型数组0——100
输出的形式：
多项式形式输出
程序所能达到的功能：
完成多项式的输入、显示；实现多项式的加法操作
测试数据：
A.正确的输入及其输出结果：
分别输入两个多项式的系数和指数，分别以0结束,例如3*x^2，请输入32
46258710
0
第一个多项式输入完毕，请输入下一个
70346825100
多项式输入完毕
请输入你想要进行的运算，1代表+，2代表-
2
6*x^8+8*x^7+4*x^6+2*x^5+3*x^4+25*x+-6
Processcompleted.
B.错误的输入及其输出结果：
分别输入两个多项式的系数和指数，分别以0结束,例如3*x^2，请输入32
451236550
第一个多项式输入完毕，请输入下一个
8410346970
0
多项式输入完毕
2．概要设计
抽象数据类型的定义：
publicMultinomial1（）
主程序的流程：
定义类--定义主函数---定义两个线性表用来存储多项式---提示用户输入多项式的系数与指数---将用户输入的多项式存入线性表---将两个线性表的元素比较并存入同一个线性表以实现多项式相加减---输出多项式相加减后的结果
各程序模块之间的层次（调用）关系：
在Alist、Blist、Clist对堆申请空间时调用LinkList（）函数，将多项式存入Alist、Blist中调用Add（）函数，讲Alist、Blist两个线性表比较、排序并存入Clist中调用Sort（）函数。
3．详细设计
伪码算法：
构建链表：
intnewindex,newfactor;
Scannerscanner=newScanner（System.in）;
LinkedListAlist=newLinkedList（）;
LinkedListBlist=newLinkedList（）;
LinkedListClist=newLinkedList（）;
NodepNew;
第一个多项式：
System.out.println（"请输入第一个多项式的系数和指数，例如2*x^2，请输入22，以00表示结束"）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
while（newfactor!
=0）
{
pNew=newNode（）;
pNew.factor=newfactor;
pNew.index=newindex;
Alist.Add（pNew）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
}
第二个多项式：
System.out.println（"第一个多项式输入完毕，请输入第二个多项式"）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
while（newfactor!
=0）
{
pNew=newNode（）;
pNew.factor=newfactor;
pNew.index=newindex;
Blist.Add（pNew）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
}
System.out.println（"多项式输入完毕"）;
两多项式相加：
intAi=0,Bi=0;
Nodepc;
Nodepa=Alist.head.next,pb=Blist.head.next;
while（Ai{
if（pa.index>pb.index）
{
pc=newNode（）;
pc.index=pa.index;
pc.factor=pa.factor;
Clist.Add（pc）;
pc=pc.next;
pa=pa.next;
Ai++;Clist.size++;
}
elseif（pa.index{
pc=newNode（）;
pc.index=pb.index;
pc.factor=pb.factor;
Clist.Add（pc）;
pc=pc.next;
pb=pb.next;
Bi++;Clist.size++;
}
elseif（pa.index==pb.index）
{
if（pa.factor+pb.factor!
=0）
{
pc=newNode（）;
pc.index=pa.index;
pc.factor=pa.factor+pb.factor;
Clist.Add（pc）;
pc=pc.next;
pa=pa.next;
pb=pb.next;
Clist.size++;Ai++;Bi++;
}
else
{
pa=pa.next;
pb=pb.next;
Ai++;Bi++;
}
}
}
多项式中未加的部分运算：
while（Ai{
pc=newNode（）;
pc.index=pa.index;
pc.factor=pa.factor;
Clist.Add（pc）;
pa=pa.next;
pc=pc.next;
Ai++;Clist.size++;
}
while（Bi{
pc=newNode（）;
pc.index=pb.index;
pc.factor=pb.factor;
Clist.Add（pc）;
pb=pb.next;
pc=pc.next;
Bi++;Clist.size++;
}
Nodepc1=Clist.head.next;
for（intCi=0;pc1.next!
=null;Ci++）
{
System.out.print（pc1.factor+"*x^"+pc1.index+"+"）;
pc1=pc1.next;
}
System.out.print（pc1.factor+"*x^"+pc1.index）;
}
}
函数和过程的调用关系图：
4．调试分析
调试过程中遇到的问题是如何解决的：
参考课本、和同学交流讨论、上网查询
对设计与实现的回顾讨论和分析：
算法的时空分析和改进设想：
经验和体会：
平时必须多写多看程序，多加练习，并在写代码之前构思好算法和流程。
5．用户使用说明
操作步骤：
A.Buildfile
B.Runfile
C.根据提示输入多项式的系数与指数（以空格分开各项）
D.然后Enter
E.运行结果就会实现两个多项式的相加减
6．测试结果
请输入第一个多项式的系数和指数，例如2*x^2，请输入22，以00表示结束
154623045527950
第一个多项式输入完毕，请输入第二个多项式
83496102214566715300
多项式输入完毕
1*x^5+4*x^6+2*x^3+5*x^2+7*x^9+5*x^0+8*x^3+4*x^9+6*x^1
Processcompleted.
请输入第一个多项式的系数和指数，例如2*x^2，请输入22，以00表示结束
4185579552445451245120
0
第一个多项式输入完毕，请输入第二个多项式
4635122593262652132556222356
00
000
多项式输入完毕
41*x^85+5*x^7+472*x^5+6*x^2+4*x^45+6*x^5+9*x^3+26*x^26+5*x^21+3*x^255+63*x^2+4*x^512+2*x^3+5*x^6
Processcompleted.
请输入第一个多项式的系数和指数，例如2*x^2，请输入22，以00表示结束
154641694911223503202532+000
Exceptioninthread"main"java.util.InputMismatchException
atjava.util.Scanner.throwFor（Scanner.java:
840）
atjava.util.Scanner.next（Scanner.java:
1461）
atjava.util.Scanner.nextInt（Scanner.java:
2091）
atjava.util.Scanner.nextInt（Scanner.java:
2050）
atMultinomial1.main（Multinomial1.java:
34）
Processcompleted.
7．附录
带注释的源程序代码:
链表：
publicclassNode{//定义Node类
publicintindex;//定义参数
publicintfactor;
publicNodelast;
publicNodenext;
}
publicclassLinkedList{//定义LinkedList类
publicLinkedList（）{
head=newNode（）;
head.last=null;
tail=head;
tail.next=null;
}
publicNodehead;
publicNodetail;
publicintsize=0;
publicvoidAdd（NodepNew）//实现线性表的插入
{
tail.next=pNew;
tail=pNew;
tail.next=null;
size++;
}
publicvoidSort（）//排序
{
Nodep=head.next;
for（inti=0;i{
if（p.index{
p.next.next.last=p;
p.last=p.next;
p.next=p.next.next;
p.last.next=p;
head.next=p.last;
}
else
p=p.next;
for（intj=1;j{
if（p.index{
p.next.next.last=p;
p.last=p.next;
p.next=p.next.next;
p.last.next=p;
}
else
p=p.next;
}
}
}
}
/**
*@（#）Multinomial1.java
*
*
*@author
*@version1.002013/3/19
*/
importjava.util.Scanner;
publicclassMultinomial1{//定义Multinomaill类
publicMultinomial1（）{
}
publicstaticvoidmain（String[]args）//主函数
{
intnewindex,newfactor;
Scannerscanner=newScanner（System.in）;//调用LinkedList（）函数
LinkedListAlist=newLinkedList（）;
LinkedListBlist=newLinkedList（）;
LinkedListClist=newLinkedList（）;
NodepNew;
System.out.println（"请输入第一个多项式的系数和指数，例如2*x^2，请输入22，以00表示结束"）;//照此输入多项式的系数与指数
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
while（newfactor!
=0）
{
pNew=newNode（）;
pNew.factor=newfactor;
pNew.index=newindex;
Alist.Add（pNew）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
}
System.out.println（"第一个多项式输入完毕，请输入第二个多项式"）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
while（newfactor!
=0）
{
pNew=newNode（）;
pNew.factor=newfactor;
pNew.index=newindex;
Blist.Add（pNew）;
newfactor=scanner.nextInt（）;
newindex=scanner.nextInt（）;
}
System.out.println（"多项式输入完毕"）;
intAi=0,Bi=0;
Nodepc;
Nodepa=Alist.head.next,pb=Blist.head.next;//实现两个多项式的相加减
while（Ai{
if（pa.index>pb.index）
{
pc=newNode（）;
pc.index=pa.index;
pc.factor=pa.factor;
Clist.Add（pc）;
pc=pc.next;
pa=pa.next;
Ai++;Clist.size++;
}
elseif（pa.index{
pc=newNode（）;
pc.index=pb.index;
pc.factor=pb.factor;
Clist.Add（pc）;
pc=pc.next;
pb=pb.next;
Bi++;Clist.size++;
}
elseif（pa.index==pb.index）
{
if（pa.factor+pb.factor!
=0）
{
pc=newNode（）;
pc.index=pa.index;
pc.factor=pa.factor+pb.factor;
Clist.Add（pc）;
pc=pc.next;
pa=pa.next;
pb=pb.next;
Clist.size++;Ai++;Bi++;
}
else
{
pa=pa.next;
pb=pb.next;
Ai++;Bi++;
}
}
}
while（Ai{
pc=newNode（）;
pc.index=pa.index;
pc.factor=pa.factor;
Clist.Add（pc）;
pa=pa.next;
pc=pc.next;
Ai++;Clist.size++;
}
while（Bi{
pc=newNode（）;
pc.index=pb.index;
pc.factor=pb.factor;
Clist.Add（pc）;
pb=pb.next;
pc=pc.next;
Bi++;Clist.size++;
}
Nodepc1=Clist.head.next;
for（intCi=0;pc1.next!
=null;Ci++）
{
System.out.print（pc1.factor+"*x^"+pc1.index+"+"）;
pc1=pc1.next;
}
System.out.print（pc1.factor+"*x^"+pc1.index）;
}
}
数组：
/**
*@（#）Multinomial.java
*
*
*@author
*@version1.002013/3/19
*/
importjava.util.Scanner;
publicclassMultinomial{
publicstaticvoidmain（String[]args）
{
intAsize=0,Bsize=0,Csize=0;
inttemp;
intoperator;
intAfactor[]=newint[100];
intAindex[]=newint[100];
intBfactor[]=newint[100];
intBindex[]=newint[100];
intCfactor[]=newint[100];
intCindex[]=newint[100];
Scannerscanner=newScanner（System.in）;
System.out.println（"分别输入两个多项式的系数和指数，分别以0结束,例如3*x^2，请输入32"）;
Afactor[Asize]=scanner.nextInt（）;
Aindex[Asize]=scanner.nextInt（）;Asize++;
while（Afactor[Asize]==0）
{
Afactor[Asize]=scanner.nextInt（）;
if（Afactor[Asize]==0）
{
System.out.println（"第一个多项式输入完毕，请输入下一个"）;
break;
}
Aindex[Asize]=scanner.nextInt（）;Asize++;
}
Bfactor[Bsize]=scanner.nextInt（）;
Bindex[Bsize]=scanner.nextInt（）;Bsize++;
while（Bfactor[Bsize]==0）
{
Bfactor[Bsize]=scanner.nextInt（）;
if（Bfactor[Bsize]==0）
{
System.out.println（"多项式输入完毕"）;
break;
}
Bindex[Bsize]=scanner.nextInt（）;Bsize++;
}
System.out.println（"请输入你想要进行的运算，1代表+，2代表-"）;
operator=scanner.nextInt（）;
for（intAi=0;Ai{
for（intAj=0;Aj{
if（Aindex[Aj]{
temp=Aindex[Aj+1];
Aindex[Aj+1]=Aindex[Aj];
Aindex[Aj]=temp;
temp=Afactor[Aj+1];
Afactor[Aj+1]=Afactor[Aj];
Afactor[Aj]=temp;
}
}
升级会员 