0

章節

２．１到２．３小節。

理解與表達線性表的邏輯結構；

線性表的結構、結構與操作；

順序表的表示與實現；順序表應用；

重點

線性表概念、順序表定義運算與實現；

難點

無較難點；

作業或思考題

完成學習測試２，作業３.１

內容達成以下標準(考核點)：

????????理解實現順序表基本操作；

????????理解與實現相關概念；完成測試，滿８０分以上

作業3：順序表的基本操作

一、題目及分析

1.1題目

????????給一個隨機給定的十進?數轉換成八進制數和二進制數，并輸出它們；然后將兩個十進制數的八進制數和二進制數分別相加，輸出其和的八進制數和二進制數。

1.2分析題目完成目標與方案

????????題目要求實現將一個隨機給定的十進制數轉換成八進制和二進制，然后將兩個十進制數的八進制和二進制分別相加，并輸出其和的八進制和二進制。可以采用鏈表或順序表來進行存儲和操作。

????????對于將十進制數轉換成八進制和二進制，需要采用數學上的除法和取余運算。具體來說，連續對十進制數進行除以二或除以八的運算，每次將余數插入一個鏈表或數組中，直到商為0停止運算。最終鏈表或數組中存儲的數字就是所求。

????????對于將兩個十進制數的八進制和二進制分別相加的問題，需要先將兩個數分別轉換成對應的八進制和二進制，然后再按位相加。具體來說，可以從兩個數的最低位開始，依次將對應位置上的八進制或二進制數加起來，若和大于7或1則需要進位，最終得到的數組或鏈表就是所求的和。

????????可以定義一個節點類并在其中定義一個指向下一節點的指針，然后定義鏈表類和順序表類。鏈表類需要實現頭插入節點、打印鏈表、清空鏈表和將十進制數轉換成八進制或二進制等方法。順序表類需要實現將十進制數轉換成八進制和二進制、打印八進制和二進制、計算兩個十進制數的和以及打印兩個數的八進制和二進制等方法。

抽象成抽象數據類型（ADT）:

// 鏈表節點

class ListNode {

????private int data;

????private ListNode next;

????public void setData(int data) {

????????this.data = data;

????}

????public int getData() {

????????return data;

????}

????public ListNode getNext() {

????????return next;

????}

????public void setNext(ListNode next) {

????????this.next = next;

????}

}

// 鏈表

interface LinkedListADT {

????void insert(int data); // 在鏈表頭部插入節點

????void print(); // 打印鏈表中的所有節點數據

????void convertToOctal(); // 將十進制數轉換為八進制，并將結果存儲在鏈表中

????void convertToBinary(); // 將十進制數轉換為二進制，并將結果存儲在鏈表中

????void clear(); // 清空鏈表

}

// 順序表

interface SequenceListADT {

????void convertToOctal(); // 將十進制轉換為八進制

????void convertToBinary(); // 將十進制轉換為二進制

????void printOctal(); // 打印十進制數的八進制表示

????void printBinary(); // 打印十進制數的二進制表示

????void printBinaryAndOctal(); // 打印十進制數的八進制和二進制表示

????SequenceListADT add(SequenceListADT d); // 返回兩個對象的十進制數之和的新對象

}

二、順序表實現

2.1 ?SequenceList類代碼

package homework3_2;// 順序表方法相關類
public class SequenceList {private int decimal; // 十進制數private int[] octal = new int[100]; // 八進制數組private int octalBits = 0; // 八進制位數private int[] binary = new int[100]; // 二進制數組private int binaryBits = 0; // 二進制位數public SequenceList(int d) {decimal = d;}public SequenceList() {}// 將十進制轉換為八進制private void convertToOctal() {if (octalBits == 0) { // 只在第一次需要轉換時計算int p = decimal;int q = 0;int i = 0;while (p != 0) {q = p % 8;p = p / 8;octal[i] = q;i++;octalBits++;}}}// 將十進制轉換為二進制private void convertToBinary() {if (binaryBits == 0) { // 只在第一次需要轉換時計算int p = decimal;int q = 0;int i = 0;while (p != 0) {q = p % 2;p = p / 2;binary[i] = q;i++;binaryBits++;}}}// 打印十進制數的八進制表示public void printOctal() {this.convertToOctal();System.out.print(" ??" + decimal + "的八進制數為：");for (int i = octalBits - 1; i >= 0; i--) {System.out.print(octal[i]);}System.out.println("");}// 打印十進制數的二進制表示public void printBinary() {this.convertToBinary();System.out.print(" ??" + decimal + "的二進制數為：");// 跳過前導零int startIndex = binaryBits - 1;while (startIndex >= 0 && binary[startIndex] == 0) {startIndex--;}// 輸出非前導零部分for (int i = startIndex; i >= 0; i--) {System.out.print(binary[i]);}System.out.println("");}public void printBinaryAndOctal(){this.convertToBinary();this.convertToOctal();System.out.print(" ??" + decimal + "的二進制數為：");int startIndex = binaryBits - 1;while (startIndex >= 0 && binary[startIndex] == 0) {startIndex--;}for (int i = startIndex; i >= 0; i--) {System.out.print(binary[i]);}System.out.print(" ?????????");System.out.print(" ??" + decimal + "的八進制數為：");for (int i = octalBits - 1; i >= 0; i--) {System.out.print(octal[i]);}System.out.println("");}// 返回兩個對象的十進制數之和的新對象public SequenceList add(SequenceList d) {int sumDecimal = decimal + d.decimal;return new SequenceList(sumDecimal);}
}

2.3 Main類代碼

package homework3_2;public class Main {public static void main(String[] args) {//使用順序表實現System.out.println("1.使用順序表實現");SequenceList d1 = new SequenceList(36);SequenceList d2 = new SequenceList(64);SequenceList d3 = d2.add(d1);
/* ???????d1.printOctal();d1.printBinary();d2.printOctal();d2.printBinary();d3.printOctal();d3.printBinary();System.out.println();*/d1.printBinaryAndOctal();d2.printBinaryAndOctal();d3.printBinaryAndOctal();//使用鏈表實現System.out.println("2.使用鏈表實現");LinkedList ll1 = new LinkedList(36);LinkedList ll2 = new LinkedList(64);LinkedList ll3 = new LinkedList(ll1.decimal + ll2.decimal);ll1.print();ll2.print();ll3.print();}
}

2.4程序運行結果

三、鏈表實現

3.1 ?ListNode類代碼

package homework3_2;
// 鏈表節點類
public class ListNode {int data; // 存儲節點數據ListNode next; // 指向下一個節點的指針public ListNode(int data) {this.data = data;this.next = null; // 新節點的next指針初始化為null}
}

3.2 LinkedList類代碼

package homework3_2;// 鏈表類
public class LinkedList {private ListNode head; // 頭節點，鏈表的起點int decimal; // 十進制數，待轉換的數值public LinkedList(int d) {this.decimal = d;}// 在鏈表頭部插入節點public void insert(int data) {ListNode newNode = new ListNode(data); // 創建新節點newNode.next = head; // 將新節點的next指針指向當前頭節點head = newNode; // 更新頭節點為新節點}// 打印鏈表中的所有節點數據public void print() {this.convertToBinary();System.out.print(" ??" + decimal + "的二進制數為：");ListNode current = head; // 從頭節點開始遍歷while (current != null) {System.out.print(current.data + ""); // 打印當前節點的數據current = current.next; // 移動到下一個節點}System.out.println(); // 打印換行符this.convertToOctal();System.out.print(" ??" + decimal + "的八進制數為：");current = head; // 從頭節點開始遍歷while (current != null) {System.out.print(current.data + ""); // 打印當前節點的數據current = current.next; // 移動到下一個節點}System.out.println(); // 打印換行符}// 將十進制數轉換為八進制，并將結果存儲在鏈表中public void convertToOctal() {int number = decimal; // 獲取待轉換的十進制數clear(); // 清空鏈表while (number != 0) {int remainder = number % 8; // 計算余數insert(remainder); // 在鏈表頭部插入余數number /= 8; // 更新被除數為商}}// 將十進制數轉換為二進制，并將結果存儲在鏈表中public void convertToBinary() {int number = decimal; // 獲取待轉換的十進制數clear(); // 清空鏈表while (number != 0) {int remainder = number % 2; // 計算余數insert(remainder); // 在鏈表頭部插入余數number /= 2; // 更新被除數為商}}// 清空鏈表public void clear() {head = null;}}

3.3 Main類代碼

package homework3_2;public class Main {public static void main(String[] args) {//使用順序表實現System.out.println("1.使用順序表實現");SequenceList d1 = new SequenceList(36);SequenceList d2 = new SequenceList(64);SequenceList d3 = d2.add(d1);
/* ???????d1.printOctal();d1.printBinary();d2.printOctal();d2.printBinary();d3.printOctal();d3.printBinary();System.out.println();*/d1.printBinaryAndOctal();d2.printBinaryAndOctal();d3.printBinaryAndOctal();//使用鏈表實現System.out.println("2.使用鏈表實現");LinkedList ll1 = new LinkedList(36);LinkedList ll2 = new LinkedList(64);LinkedList ll3 = new LinkedList(ll1.decimal + ll2.decimal);ll1.print();ll2.print();ll3.print();}
}

3.4程序運行結果

四、結果與總結???????

4.1順序表實現

????????順序表使用數組來存儲八進制和二進制數的每一位，通過計算余數和商來完成十進制到八進制和二進制的轉換。優點是實現簡單，轉換后的結果可以直接按照倒序輸出；缺點是需要提前設置數組的大小，不夠靈活。

4.2鏈表實現

????????鏈表使用鏈式結構來存儲八進制和二進制數的每一位，通過在頭部插入節點的方式來實現反向存儲。優點是不需要提前設置數組大小，具有較好的靈活性；缺點是在打印結果時需要遍歷鏈表。

4.3總體

4.3.1優點

①通過順序表和鏈表兩種不同的數據結構實現了相同的功能，展示了不同數據結構的靈活性。

②代碼實現簡單明了，容易理解和使用。

4.3.2缺點

①順序表的缺點是需要提前設置數組的大小，如果超過了數組大小則無法繼續進行轉換。

②鏈表的缺點是在打印結果時需要遍歷鏈表，時間復雜度較高。

4.4改進方向

①動態數組:

????????可以考慮使用動態數組來解決順序表的大小限制問題。當順序表實現中遇到需要動態擴展數組大小的情況時，可以采用動態數組的方式來解決。通過設定一個初始大小，當數組容量不足時進行動態擴展，重新分配更大的空間，并將原有數據復制到新的數組中。

②棧的實現：

????????可以引入棧的概念，用來存儲轉換結果中的位數。順序棧（ArrayStack）：使用數組來實現棧的基本操作，包括入棧（push）、出棧（pop）和判斷棧空（isEmpty）等。鏈棧（LinkedStack）：使用鏈表來實現棧的操作，通過鏈表頭部的插入和刪除來模擬棧的入棧和出棧。

③可以在鏈表中增加尾指針，使得插入操作更高效。

④可以通過位運算來加快二進制轉換的速度。使用位運算，而不是依賴除法和取余的方式。

⑤錯誤處理：

????????考慮在代碼中添加錯誤處理機制，例如輸入的十進制數為負數、輸入非法字符等情況下給出相應的提示或處理方式。