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