實(shí)驗(yàn)一 線性表的操作

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告項(xiàng)目名稱 線性表的操作 專業(yè)班級(jí) 學(xué) 號(hào) 姓 名 實(shí)驗(yàn)成績(jī)：批閱教師：2013年 03 月 31 日實(shí)驗(yàn)一 線性表的操作 實(shí)驗(yàn)學(xué)時(shí)： 2 實(shí)驗(yàn)地點(diǎn)： 科教樓四樓 實(shí)驗(yàn)日期： 2013/3/20 1需求分析（1）程序設(shè)計(jì)的任務(wù)：A.應(yīng)用線性表的基本操作，插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算。B. 實(shí)現(xiàn)一元n次多項(xiàng)式的加法運(yùn)算(2)規(guī)定：輸入的形式和輸入值的范圍：長(zhǎng)整型數(shù)組0100輸出的形式：多項(xiàng)式形式輸出程序所能達(dá)到的功能：完成多項(xiàng)式的輸入、顯示；實(shí)現(xiàn)多項(xiàng)式的加法操作測(cè)試數(shù)據(jù)：A . 正確的輸入及其輸出結(jié)果： 分別輸入兩個(gè)多項(xiàng)式的系數(shù)和指數(shù)，

2、分別以0結(jié)束,例如3*x2，請(qǐng)輸入3 24 6 2 5 8 7 1 00第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入下一個(gè)7 0 3 4 6 8 25 1 00多項(xiàng)式輸入完畢請(qǐng)輸入你想要進(jìn)行的運(yùn)算，1代表+，2代表-26*x8 + 8*x7 + 4*x6 + 2*x5 + 3*x4 + 25*x + -6Process completed.B . 錯(cuò)誤的輸入及其輸出結(jié)果： 分別輸入兩個(gè)多項(xiàng)式的系數(shù)和指數(shù)，分別以0結(jié)束,例如3*x2，請(qǐng)輸入3 24 5 1 2 3 6 5 5 0第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入下一個(gè)8 4 1 0 3 4 6 9 7 00多項(xiàng)式輸入完畢2概要設(shè)計(jì)抽象數(shù)據(jù)類型的定義：public M

3、ultinomial1()主程序的流程： 定義類-à定義主函數(shù)-àà定義兩個(gè)線性表用來(lái)存儲(chǔ)多項(xiàng)式-àà提示用戶輸入多項(xiàng)式的系數(shù)與指數(shù)-àà將用戶輸入的多項(xiàng)式存入線性表-àà將兩個(gè)線性表的元素比較并存入同一個(gè)線性表以實(shí)現(xiàn)多項(xiàng)式相加減-à-à輸出多項(xiàng)式相加減后的結(jié)果各程序模塊之間的層次(調(diào)用)關(guān)系：在Alist、Blist、Clist對(duì)堆申請(qǐng)空間時(shí)調(diào)用LinkList()函數(shù)，將多項(xiàng)式存入Alist、Blist中調(diào)用Add()函數(shù)，講Alist、Blist兩個(gè)線性表比較、排序并存入Clis

4、t中調(diào)用Sort()函數(shù)。3詳細(xì)設(shè)計(jì)偽碼算法：構(gòu)建鏈表：int newindex, newfactor; Scanner scanner = new Scanner(System.in); LinkedList Alist = new LinkedList(); LinkedList Blist = new LinkedList(); LinkedList Clist = new LinkedList(); Node pNew;第一個(gè)多項(xiàng)式：System.out.println("請(qǐng)輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)，例如2*x2，請(qǐng)輸入2 2，以0 0表示結(jié)束"); newfa

5、ctor = 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(); 第二個(gè)多項(xiàng)式：System.out.println("第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入第二個(gè)多項(xiàng)式"); newfactor = sca

6、nner.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("多項(xiàng)式輸入完畢");兩多項(xiàng)式相加：int Ai = 0, Bi = 0; Node pc; Node pa =

7、Alist.head.next, pb = Blist.head.next; while (Ai < Alist.size && Bi < Blist.size) if (pa.index > 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.i

8、ndex = 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.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.s

9、ize+; Ai+; Bi+; else pa = pa.next; pb = pb.next; Ai+; Bi+; 多項(xiàng)式中未加的部分運(yùn)算：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.

10、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.print(pc1.factor+"*x"+pc1.index+" + "); pc1 = pc1.next; System.out.print(pc1.factor+"*x"+pc1.index); 函數(shù)和過(guò)程的調(diào)用關(guān)系圖：4調(diào)試分析調(diào)試過(guò)程

11、中遇到的問(wèn)題是如何解決的：參考課本、和同學(xué)交流討論、上網(wǎng)查詢對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析：算法的時(shí)空分析和改進(jìn)設(shè)想：經(jīng)驗(yàn)和體會(huì)：平時(shí)必須多寫多看程序，多加練習(xí)，并在寫代碼之前構(gòu)思好算法和流程。5用戶使用說(shuō)明操作步驟：A.Build fileB.Run fileC.根據(jù)提示輸入多項(xiàng)式的系數(shù)與指數(shù)（以空格分開各項(xiàng)）D.然后EnterE.運(yùn)行結(jié)果就會(huì)實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加減6測(cè)試結(jié)果請(qǐng)輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)，例如2*x2，請(qǐng)輸入2 2，以0 0表示結(jié)束1 5 4 6 2 3 0 45 5 2 7 9 5 0第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入第二個(gè)多項(xiàng)式8 3 4 9 6 1 0 22 1 4 5 66

12、 7 1 5 3 00多項(xiàng)式輸入完畢1*x5 + 4*x6 + 2*x3 + 5*x2 + 7*x9 + 5*x0 + 8*x3 + 4*x9 + 6*x1Process completed.請(qǐng)輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)，例如2*x2，請(qǐng)輸入2 2，以0 0表示結(jié)束41 85 5 7 9 5 5 2 4 45 4 5 1 2 4 512 00第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入第二個(gè)多項(xiàng)式463 5 1 2 2 5 9 3 26 26 5 21 3 255 62 2 2 3 5 600 0 0 0 多項(xiàng)式輸入完畢41*x85 + 5*x7 + 472*x5 + 6*x2 + 4*x45 + 6*x5

13、 + 9*x3 + 26*x26 + 5*x21 + 3*x255 + 63*x2 + 4*x512 + 2*x3 + 5*x6Process completed. 請(qǐng)輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)，例如2*x2，請(qǐng)輸入2 2，以0 0表示結(jié)束15 4 6 4169 4 91 1 22 3 50 3 20 2 532 + 00 0at java.util.Scanner.throwFor(Scanner.java:840)at java.util.Scanner.next(Scanner.java:1461)at java.util.Scanner.nextInt(Scanner.java:20

14、91)at java.util.Scanner.nextInt(Scanner.java:2050)at Multinomial1.main(Multinomial1.java:34)Process completed.7附錄帶注釋的源程序代碼:鏈表：public class Node /定義Node類 public int index; /定義參數(shù) public int factor; public Node last; public Node next;public class LinkedList /定義LinkedList類 public LinkedList() head = new

15、 Node(); head.last = null; tail = head; tail.next = null; public Node head; public Node tail; public int size = 0; public void Add(Node pNew) /實(shí)現(xiàn)線性表的插入 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 <

16、 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; 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; /* * (#

17、)Multinomial1.java * * * author * version 1.00 2013/3/19 */import java.util.Scanner;public class Multinomial1 /定義Multinomaill類 public Multinomial1() public static void main(String args) /主函數(shù) int newindex, newfactor; Scanner scanner = new Scanner(System.in); /調(diào)用LinkedList()函數(shù) LinkedList Alist = new L

18、inkedList(); LinkedList Blist = new LinkedList(); LinkedList Clist = new LinkedList(); Node pNew; System.out.println("請(qǐng)輸入第一個(gè)多項(xiàng)式的系數(shù)和指數(shù)，例如2*x2，請(qǐng)輸入2 2，以0 0表示結(jié)束"); /照此輸入多項(xiàng)式的系數(shù)與指數(shù) newfactor = scanner.nextInt(); newindex = scanner.nextInt(); while (newfactor != 0) pNew = new Node(); pNew.factor

19、= newfactor; pNew.index = newindex; Alist.Add(pNew); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); System.out.println("第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入第二個(gè)多項(xiàng)式"); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); while (newfactor != 0) pNew = new Node(); pNew.factor = newfactor; pNew

20、.index = newindex; Blist.Add(pNew); newfactor = scanner.nextInt(); newindex = scanner.nextInt(); System.out.println("多項(xiàng)式輸入完畢"); int Ai = 0, Bi = 0; Node pc; Node pa = Alist.head.next, pb = Blist.head.next; /實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加減 while (Ai < Alist.size && Bi < Blist.size) if (pa.index &

21、gt; 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; Clist.Add(pc); pc = pc.next; pb = pb.next; Bi+; Clist.size+; else if (

22、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 = pb.next; Ai+; Bi+; while (Ai < Alist.size) pc = new Node(); pc.inde

23、x = 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.size+; Node pc1 = Clist.head.next; for (int Ci = 0; pc1.next

24、 != null; Ci+) System.out.print(pc1.factor+"*x"+pc1.index+" + "); pc1 = pc1.next; System.out.print(pc1.factor+"*x"+pc1.index); 數(shù)組：/* * (#)Multinomial.java * * * author * version 1.00 2013/3/19 */import java.util.Scanner;public class Multinomial public static void main(S

25、tring 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.out.println("分別輸入兩個(gè)多

26、項(xiàng)式的系數(shù)和指數(shù)，分別以0結(jié)束,例如3*x2，請(qǐng)輸入3 2"); AfactorAsize = scanner.nextInt(); AindexAsize = scanner.nextInt(); Asize+; while (AfactorAsize = 0) AfactorAsize = scanner.nextInt(); if (AfactorAsize = 0) System.out.println("第一個(gè)多項(xiàng)式輸入完畢，請(qǐng)輸入下一個(gè)"); break; AindexAsize = scanner.nextInt(); Asize+; Bfactor

27、Bsize = scanner.nextInt(); BindexBsize = scanner.nextInt(); Bsize+; while (BfactorBsize = 0) BfactorBsize = scanner.nextInt(); if (BfactorBsize = 0) System.out.println("多項(xiàng)式輸入完畢"); break; BindexBsize = scanner.nextInt(); Bsize+; System.out.println("請(qǐng)輸入你想要進(jìn)行的運(yùn)算，1代表+，2代表-"); operato

28、r = 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; for (int Bi = 0; Bi < Bsize; Bi+) for (int Bj

29、 = 0; Bj < Bsize-Bi; Bj+) if (BindexBj < BindexBj+1) temp = BindexBj+1; BindexBj+1 = BindexBj; BindexBj = temp; temp = BfactorBj+1; BfactorBj+1 = BfactorBj; BfactorBj = temp; int Ak = 0, Bk = 0; if (operator = 1) for (; Ak < Asize && Bk < Bsize;) if (AindexAk > BindexBk) Cinde

30、xCsize = AindexAk; CfactorCsize = AfactorAk; Csize+; Ak+; else if (AindexAk < BindexBk) CindexCsize = BindexBk; CfactorCsize = BfactorBk; Csize+; Bk+; else if (AfactorAk + BfactorBk != 0) CindexCsize = AindexAk; CfactorCsize = AfactorAk + BfactorBk; Csize+; Ak+; Bk+; else if (operator = 2) for (;

31、 Ak < Asize && Bk < Bsize;) if (AindexAk > BindexBk) CindexCsize = AindexAk; CfactorCsize = AfactorAk; Csize+; Ak+; else if (AindexAk < BindexBk) CindexCsize = BindexBk; CfactorCsize = BfactorBk; Csize+; Bk+; else if (AfactorAk - BfactorBk != 0) CindexCsize = AindexAk; CfactorCsi

32、ze = AfactorAk - BfactorBk; Csize+; Ak+; Bk+; else System.out.println("輸入運(yùn)算符錯(cuò)誤"); while (Ak < Asize) CindexCsize = AindexAk; CfactorCsize = AfactorAk; Csize+; Ak+; while (Bk < Bsize) CindexCsize = BindexBk; CfactorCsize = BfactorBk; Csize+; Bk+; for (int Ci = 0; Ci < Csize-1; Ci+)

33、 if (CindexCi = 1) System.out.print(CfactorCi+"*x + "); else System.out.print(CfactorCi+"*x"+CindexCi+" + "); if (CindexCsize-1 = 0) System.out.print(CfactorCsize-1); else System.out.println(CfactorCsize-1+"*x"+CindexCsize-1); 百位數(shù)相加：/* * (#)Addition.java * * *

34、 author * version 1.00 2013/3/20 */import java.util.Scanner;public class Addition public Addition() public static void main(String args) int Anumber = new int 100; int Bnumber = new int 100; int Cnumber = new int 101; Cnumber0 = 0; int Asize = 0, Bsize = 0, Csize = 0; String str; Scanner scanner = new Scanner(System.in); System.out.println("請(qǐng)輸入第一個(gè)多項(xiàng)式，并以#結(jié)束"); str = scanner.nextLine(); int