实验一 线性表的操作.docx

1、实验一 线性表的操作数据结构实验报告项目名称 线性表的操作 专业班级 学 号 姓 名 实验成绩：批阅教师：2013年 03 月 31 日实验一 线性表的操作 实验学时： 2 实验地点： 科教楼四楼 实验日期： 2013/3/20 1需求分析（1）程序设计的任务：A.应用线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。B. 实现一元n次多项式的加法运算(2)规定：输入的形式和输入值的范围：长整型数组0100输出的形式：多项式形式输出程序所能达到的功能：完成多项式的输入、显示；实现多项式的加法操作测试数据：A . 正确的输入及其输出结果： 分别输入两个

2、多项式的系数和指数，分别以0结束,例如3*x2，请输入3 24 6 2 5 8 7 1 00第一个多项式输入完毕，请输入下一个7 0 3 4 6 8 25 1 00多项式输入完毕请输入你想要进行的运算，1代表+，2代表-26*x8 + 8*x7 + 4*x6 + 2*x5 + 3*x4 + 25*x + -6Process completed.B . 错误的输入及其输出结果： 分别输入两个多项式的系数和指数，分别以0结束,例如3*x2，请输入3 24 5 1 2 3 6 5 5 0第一个多项式输入完毕，请输入下一个8 4 1 0 3 4 6 9 7 00多项式输入完毕2概要设计抽象数据类型的定

3、义：public Multinomial1()主程序的流程： 定义类-定义主函数- 定义两个线性表用来存储多项式- 提示用户输入多项式的系数与指数- 将用户输入的多项式存入线性表- 将两个线性表的元素比较并存入同一个线性表以实现多项式相加减- -输出多项式相加减后的结果各程序模块之间的层次(调用)关系：在Alist、Blist、Clist对堆申请空间时调用LinkList()函数，将多项式存入Alist、Blist中调用Add()函数，讲Alist、Blist两个线性表比较、排序并存入Clist中调用Sort()函数。3详细设计伪码算法：构建链表：int newindex, newfactor

4、; Scanner scanner = new Scanner(System.in); LinkedList Alist = new LinkedList(); LinkedList Blist = new LinkedList(); LinkedList Clist = new LinkedList(); Node pNew;第一个多项式：System.out.println(请输入第一个多项式的系数和指数，例如2*x2，请输入2 2，以0 0表示结束); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); while (

5、newfactor != 0) pNew = new Node(); 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 =

6、 new Node(); pNew.factor = newfactor; pNew.index = newindex; Blist.Add(pNew); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); System.out.println(多项式输入完毕);两多项式相加： int Ai = 0, Bi = 0; Node pc; Node pa = Alist.head.next, pb = Blist.head.next; while (Ai Alist.size & Bi pb.index) pc = new No

7、de(); pc.index = pa.index; pc.factor = pa.factor; Clist.Add(pc); pc = pc.next; pa = pa.next; Ai+; Clist.size+; else if (pa.index pb.index) pc = new Node(); pc.index = pb.index; pc.factor = pb.factor; Clist.Add(pc); pc = pc.next; pb = pb.next; Bi+; Clist.size+; else if (pa.index = pb.index) if (pa.fa

8、ctor + pb.factor != 0) pc = new Node(); 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 Alist.size) pc = new Node(); pc.index = pa.index; pc.factor

9、 = pa.factor; Clist.Add(pc); pa = pa.next; pc = pc.next; Ai+; Clist.size+; while (Bi Blist.size) pc = new Node(); pc.index = pb.index; pc.factor = pb.factor; Clist.Add(pc); pb = pb.next; pc = pc.next; Bi+; Clist.size+; Node pc1 = Clist.head.next; for (int Ci = 0; pc1.next != null; Ci+) System.out.pr

10、int(pc1.factor+*x+pc1.index+ + ); pc1 = pc1.next; System.out.print(pc1.factor+*x+pc1.index); 函数和过程的调用关系图：4调试分析调试过程中遇到的问题是如何解决的：参考课本、和同学交流讨论、上网查询对设计与实现的回顾讨论和分析：算法的时空分析和改进设想：经验和体会：平时必须多写多看程序，多加练习，并在写代码之前构思好算法和流程。5用户使用说明操作步骤：A. Build fileB. Run fileC. 根据提示输入多项式的系数与指数（以空格分开各项）D. 然后EnterE. 运行结果就会实现两个多项式的

11、相加减6测试结果请输入第一个多项式的系数和指数，例如2*x2，请输入2 2，以0 0表示结束1 5 4 6 2 3 0 45 5 2 7 9 5 0第一个多项式输入完毕，请输入第二个多项式8 3 4 9 6 1 0 22 1 4 5 66 7 1 5 3 00多项式输入完毕1*x5 + 4*x6 + 2*x3 + 5*x2 + 7*x9 + 5*x0 + 8*x3 + 4*x9 + 6*x1Process completed.请输入第一个多项式的系数和指数，例如2*x2，请输入2 2，以0 0表示结束41 85 5 7 9 5 5 2 4 45 4 5 1 2 4 512 00第一个多项式输入

12、完毕，请输入第二个多项式463 5 1 2 2 5 9 3 26 26 5 21 3 255 62 2 2 3 5 600 0 0 0 多项式输入完毕41*x85 + 5*x7 + 472*x5 + 6*x2 + 4*x45 + 6*x5 + 9*x3 + 26*x26 + 5*x21 + 3*x255 + 63*x2 + 4*x512 + 2*x3 + 5*x6Process completed. 请输入第一个多项式的系数和指数，例如2*x2，请输入2 2，以0 0表示结束15 4 6 4169 4 91 1 22 3 50 3 20 2 532 + 00 0Exception in thr

13、ead main java.util.InputMismatchException at java.util.Scanner.throwFor(Scanner.java:840) at java.util.Scanner.next(Scanner.java:1461) at java.util.Scanner.nextInt(Scanner.java:2091) at java.util.Scanner.nextInt(Scanner.java:2050) at Multinomial1.main(Multinomial1.java:34)Process completed.7附录带注释的源程

14、序代码:链表：public class Node /定义Node类 public int index; /定义参数 public int factor; public Node last; public Node next;public class LinkedList /定义LinkedList类 public LinkedList() head = new Node(); head.last = null; tail = head; tail.next = null; public Node head; public Node tail; public int size = 0; publ

15、ic void Add(Node pNew) /实现线性表的插入 tail.next = pNew; tail = pNew; tail.next = null; size+; public void Sort() /排序 Node p = head.next; for (int i = 0; i size; i+) if (p.index p.next.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;

16、 for (int j = 1; j size - i; j+) if (p.index p.next.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 * version 1.00 2013/3/19 */import java.util.Scanner;public class Multinomial1 /定义Multinomaill类 public Multi

17、nomial1() public static void main(String args) /主函数 int newindex, newfactor; Scanner scanner = new Scanner(System.in); /调用LinkedList()函数 LinkedList Alist = new LinkedList(); LinkedList Blist = new LinkedList(); LinkedList Clist = new LinkedList(); Node pNew; System.out.println(请输入第一个多项式的系数和指数，例如2*x2

18、，请输入2 2，以0 0表示结束); /照此输入多项式的系数与指数 newfactor = scanner.nextInt(); newindex = scanner.nextInt(); while (newfactor != 0) pNew = new Node(); pNew.factor = newfactor; pNew.index = newindex; Alist.Add(pNew); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); System.out.println(第一个多项式输入完毕，请输入第二个多

19、项式); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); while (newfactor != 0) pNew = new Node(); pNew.factor = newfactor; pNew.index = newindex; Blist.Add(pNew); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); System.out.println(多项式输入完毕); int Ai = 0, Bi = 0; Node pc; Node pa

20、= Alist.head.next, pb = Blist.head.next; /实现两个多项式的相加减 while (Ai Alist.size & Bi pb.index) pc = new Node(); pc.index = pa.index; pc.factor = pa.factor; Clist.Add(pc); pc = pc.next; pa = pa.next; Ai+; Clist.size+; else if (pa.index pb.index) pc = new Node(); pc.index = pb.index; pc.factor = pb.factor;

21、 Clist.Add(pc); pc = pc.next; pb = pb.next; Bi+; Clist.size+; else if (pa.index = pb.index) if (pa.factor + pb.factor != 0) pc = new Node(); 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 =

22、 pb.next; Ai+; Bi+; while (Ai Alist.size) pc = new Node(); pc.index = pa.index; pc.factor = pa.factor; Clist.Add(pc); pa = pa.next; pc = pc.next; Ai+; Clist.size+; while (Bi Blist.size) pc = new Node(); pc.index = pb.index; pc.factor = pb.factor; Clist.Add(pc); pb = pb.next; pc = pc.next; Bi+; Clist

23、.size+; Node pc1 = Clist.head.next; for (int Ci = 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 * version 1.00 2013/3/19 */import java.util.Scanner;public class Multinomial

24、public static void main(String args) int Asize = 0, Bsize = 0, Csize = 0; int temp; int operator; int Afactor = new int100; int Aindex = new int100; int Bfactor = new int100; int Bindex = new int100; int Cfactor = new int100; int Cindex = new int100; Scanner scanner = new Scanner(System.in); System.

25、out.println(分别输入两个多项式的系数和指数，分别以0结束,例如3*x2，请输入3 2); AfactorAsize = scanner.nextInt(); AindexAsize = scanner.nextInt(); Asize+; while (AfactorAsize = 0) AfactorAsize = scanner.nextInt(); if (AfactorAsize = 0) System.out.println(第一个多项式输入完毕，请输入下一个); break; AindexAsize = scanner.nextInt(); Asize+; Bfacto

26、rBsize = scanner.nextInt(); BindexBsize = scanner.nextInt(); Bsize+; while (BfactorBsize = 0) BfactorBsize = scanner.nextInt(); if (BfactorBsize = 0) System.out.println(多项式输入完毕); break; BindexBsize = scanner.nextInt(); Bsize+; System.out.println(请输入你想要进行的运算，1代表+，2代表-); operator = scanner.nextInt(); for (int Ai = 0; Ai Asize; Ai+) for (int Aj = 0; Aj Asize-Ai; Aj+) if (AindexAj AindexAj+1) temp = AindexAj+1; AindexAj+1 = AindexAj; AindexAj = temp; temp = AfactorAj+1; AfactorAj+1 = AfactorAj; AfactorAj = temp;