数据结构中用数组或者链表实现线性表
发布网友
发布时间：2022-04-20 00:34
共2个回答
热心网友
时间：2022-04-23 18:58
1）自己实现线性表之顺序表
思路：
1. 顺序表因为采用顺序存储形式，所以内部使用数组来存储数据
2.因为存储的具体对象类型不一定，所以采用泛型操作
3.数组操作优点：
1.通过指针快速定位到下表，查询快速
缺点：
1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据
2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）
具体实现代码如下：
/**
* 自己用数组实现的线性表
*/
public class ArrayList< E> {
Object[] data = null;// 用来保存此队列中内容的数组
int current;// 保存当前为第几个元素的指标
int capacity;// 表示数组大小的指标
/**
* 如果初始化时，未声明大小，则默认为10
*/
public ArrayList() {
this(10);
}
/**
* 初始化线性表，并且声明保存内容的数组大小
* @param initalSize
*/
public ArrayList(int initalSize) {
if (initalSize < 0) {
throw new RuntimeException("数组大小错误:" + initalSize);
} else {
this.data = new Object[initalSize];
this.current = 0;
capacity = initalSize;
}
}
/**
* 添加元素的方法 添加前，先确认是否已经满了
* @param e
* @return
*/
public boolean add(E e) {
ensureCapacity(current);// 确认容量
this.data[current] = e;
current++;
return true;
}
/**
* 确认系统当前容量是否满足需要,如果满足，则不执行操作 如果不满足，增加容量
* @param cur 当前个数
*/
private void ensureCapacity(int cur) {
if (cur == capacity) {
// 如果达到容量极限，增加10的容量，复制当前数组
this.capacity = this.capacity + 10;
Object[] newdata = new Object[capacity];
for (int i = 0; i < cur; i++) {
newdata[i] = this.data[i];
}
this.data = newdata;
}
}
/**
* 得到指定下标的数据
* @param index
* @return
*/
public E get(int index) {
validateIndex(index);
return (E) this.data[index];
}
/**
* 返回当前队列大小
* @return
*/
public int size() {
return this.current;
}
/**
* 更改指定下标元素的数据为e
* @param index
* @param e
* @return
*/
public boolean set(int index, E e) {
validateIndex(index);
this.data[index] = e;
return true;
}
/**
* 验证当前下标是否合法，如果不合法，抛出运行时异常
* @param index 下标
*/
private void validateIndex(int index) {
if (index < 0 || index > current) {
throw new RuntimeException("数组index错误：" + index);
}
}
/**
* 在指定下标位置处插入数据e
* @param index 下标
* @param e 需要插入的数据
* @return
*/
public boolean insert(int index, E e) {
ensureCapacity(current);// 确认容量
validateIndex(index);
Object[] tem = new Object[capacity];// 用一个临时数组作为备份
//开始备份数组
for (int i = 0; i < current; i++) {
if (i < index) {
tem[i] = this.data[i];
}else if(i==index){
tem[i]=e;
}else if(i>index){
tem[i]=this.data[i-1];
}
}
this.data=tem;
current++;
return true;
}
}
（2）自己实现线性表之链表
思路：1.链表采用链式存储结构，在内部只需要将一个一个结点链接起来。（每个结点中有关于此结点下一个结点的引用）
链表操作优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可
缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表
实现代码如下：
/**
* 自己用链式存储实现的线性表
*/
public class LinkedList< E> {
private Node< E> header = null;// 头结点
int size = 0;// 表示链表大小的指标
public LinkedList() {
this.header = new Node< E>();
}
public boolean add(E e) {
if (size == 0) {
header.e = e;
} else {
// 根据需要添加的内容，封装为结点
Node< E> newNode = new Node< E>(e);
// 得到当前最后一个结点
Node< E> last = getNode(size-1);
// 在最后一个结点后加上新结点
last.addNext(newNode);
}
size++;// 当前大小自增加1
return true;
}
//在index位置后插入元素
public boolean insert(int index, E e) {
Node< E> newNode = new Node< E>(e);
// 得到index处的结点
Node< E> cNode = getNode(index);
newNode.next = cNode.next;
cNode.next = newNode;
size++;
return true;
}
/**
* 遍历当前链表，取得当前索引对应的元素
*
* @return
*/
private Node< E> getNode(int index) {
// 先判断索引正确性
if (index > size || index < 0) {
throw new RuntimeException("索引值有错：" + index);
}
Node< E> tem = new Node< E>();
tem = header;
int count = 0;
while (count != index) {
tem = tem.next;
count++;
}
return tem;
}
/**
* 根据索引，取得该索引下的数据
*
* @param index
* @return
*/
public E get(int index) {
// 先判断索引正确性
if (index >= size || index < 0) {
throw new RuntimeException("索引值有错：" + index);
}
Node< E> tem = new Node< E>();
tem = header;
int count = 0;
while (count != index) {
tem = tem.next;
count++;
}
E e = tem.e;
return e;
}
public int size() {
return size;
}
/**
* 设置index处结点的值
*
* @param x
* @param e
* @return
*/
public boolean set(int index, E e) {
// 先判断索引正确性
if (index > size || index < 0) {
throw new RuntimeException("索引值有错：" + index);
}
Node< E> newNode = new Node< E>(e);
// 得到index处的结点
Node< E> cNode = getNode(index);
cNode.e = e;
return true;
}
/**
* 用来存放数据的结点型内部类
*/
class Node< E> {
private E e;// 结点中存放的数据
Node() {
}
Node(E e) {
this.e = e;
}
Node next;// 用来指向该结点的下一个结点
// 在此结点后加一个结点
void addNext(Node< E> node) {
next = node;
}
}
}
（3）自己实现线性表之栈
栈是限定仅允许在表的同一端（通常为“表尾”）进行插入或删除操作的线性表。
允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)
特点：后进先出 (LIFO)或，先进后出（FILO）
因为栈是限定线的线性表，所以，我们可以调用前面两种线性表，只需要对出栈和入栈操作进行设定即可
具体实现代码
/**
* 自己用数组实现的栈
*/
public class ArrayStack< E> {
private ArrayList< E> list=new ArrayList< E>();//用来保存数据线性表
private int size;//表示当前栈元素个数
/**
* 入栈操作
* @param e
*/
public void push(E e){
list.add(e);
size++;
}
/**
* 出栈操作
* @return
*/
public E pop(){
E e= (E)list.get(size-1);
size--;
return e;
}
}
至于用链表实现栈，则只需要把保存数据的顺序表改成链表即可，此处就不给出代码了
(4)自己实现线性表之队列
与栈类似
队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为队头(front)。
特点：先进先出 (FIFO)、后进后出 (LILO)
同理，我们也可以调用前面两种线性表，只需要对队列的入队和出队方式进行处理即可
/**
* 用数组实现的队列
*/
public class ArrayQueue< E> {
private ArrayList< E> list = new ArrayList< E>();// 用来保存数据的队列
private int size;// 表示当前元素个数
/**
* 入队
* @param e
*/
public void EnQueue(E e) {
list.add(e);
size++;
}
/**
* 出队
* @return
*/
public E DeQueue() {
if (size > 0) {
E e = list.get(0);
list.delete(0);
return e;
}else{
throw new RuntimeException("已经到达队列顶部");
}
}
}
(5)对比线性表和链式表
前面已经说过顺序表和链式表各自的特点，这里在重申一遍
数组操作
优点：1.通过指针快速定位到下标，查询快速
缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据
2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）
链表操作
优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可
缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。
改进：
链表中我们每次添加一个数据时，都需要遍历整个表，得到表尾，再在表尾添加，这是很不科学的 现改进如下：设立一个Node
类的成员变量last来指示表尾，这样每次添加时，就不需要再重新遍历得到表尾，改进后add()方法如下public boolean add(E e) {
if (size == 0) {
header.e = e;
} else {
// 根据需要添加的内容，封装为结点
Node< E> newNode = new Node< E>(e);
//在表尾添加元素
last.addNext(newNode);
//将表尾指向当前最后一个元素
last = newNode;
}
size++;// 当前大小自增加1
return true;
}
热心网友
时间：2022-04-23 20:16
你想做什么？你定义一个数组就是一个线性表 线性表的操作实际就是下标操作
