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）：使用链表来实现栈的操作，通过链表头部的插入和删除来模拟栈的入栈和出栈。
③可以在链表中增加尾指针，使得插入操作更高效。
④可以通过位运算来加快二进制转换的速度。使用位运算，而不是依赖除法和取余的方式。
⑤错误处理：
考虑在代码中添加错误处理机制，例如输入的十进制数为负数、输入非法字符等情况下给出相应的提示或处理方式。
