class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 94.5pt;">? 数据结构—数组和链表
?
?????一、数组是连续线性的结构，所储存的数据长度是不可更改的，不能对其进行插入，删除，修改的操作。
???? 身份证号的存储是数组，由于长度不够，从15位扩展到了18位。
???????????????
?
????????? 定义数组的四种方式：
????????????????? 1：数组类型[] 数组名= new 数组类型[长度]；
????????????????? 2：数组类型[] 数组名={值…};
????????????????? 3：数组类型[] 数组名=new 数组类型[]{值…}；
????????????????? 4：数组类型[] 数组名；
?????????????????????? 数组名= new 数组类型[长度]；
?
???? 二、链表的存储是离散的，它的长度在建成之后可以改变，并且可以对其进行删改的操作。
???? 链表是由节点组成的，节点包括数据域和引用域，数据域中存储数据，引用域内存储下一节点的地址，由引用使节点联系起来，实际存储的位置可以是分散的。
?
//定义一个节点类
public class Node<E> {
// 定义一个数据域
public E data;
// 定义一个引用域
public Node next;
public Node(E data) {
this.data = data;
}
public Node getnext() {
return next;
}
public void setnext(Node next) {
this.next = next;
}
??
???? 三、相较于数组，链表更多应用在灵活性的数据上，例如Q、电话号的存储
???????? 相较于链表，数组最大的优点是可以直接根据下标找到数据，查询更方便，而链表必须从头节点开 始一次查找。
?
???? 四、数组队列
???? 因为数组的长度一旦确定就不能改变，所以当我们要改变长度时，必须开辟一个新的存储空间，重新定义数组的长度，将原数组内容进行复制，并加入新的内容，这就形成了数组队列。
public class Array {
private Object[] a=new Object[0];
int size=0;
//添加数组
public void add(Object obj){
size++;
//创建一个长度+1的数组
Object [] a1=new Object[size];
if(size==0){
a1[0]=obj;
//原数组指向新的数组
a=a1;
}
//把原数组的内容复制给新数组
for(int i=0;i<size-1;i++){
a1[i]=a[i];
}
//把obj给新数组的最后一个位置
a1[size-1]=obj;
//原数组指向新的数组
a=a1;
}
//删除数组
public void remove(int index){
if(index>=0&&index<size){
size--;
//创建一个长度-1的数组
Object a2[]=new Object[size];
a[index-1]=0;
for(int i=0;i<index-1;i++){
//把要删除的位置前面的数组赋值到新的数组里
a2[i]=a[i];
}
for(int i=index;i<size;i++){
//把要删除的位置后面的数组赋值到新的数组里
a2[i]=a[i];
}
//将原来的数组指向新的数组
a=a2;
}
}
//得到数组元素的个数
public int getsize(){
return size;
}
//获取数组内容
public Object gets(int i){
if(i>=0&&i<getsize()){
Object obj=a[i];
return obj;
}
return null;
}
}
?
????? 五、链表的队列
????? 引用将节点建立联系，并可以进行节点的添加、删除、插入(待完成)等操作。
//定义一个链表类
public class LinkedNode<E> {
private Node root;// 头节点
private Node tail;// 尾节点
private int size = 0;// 记录节点总数的计数器
private int index;
private E data;
static Node node;
Node node1;
private static LinkedNode link;
// 添加节点的方法
public void add(Node node) {
// System.out.println("调用了add方法");
// Node node1 = new Node(data);
// 判断头节点为null
if (root == null) {
root = node;// 将新节点给头节点
tail = node;// 将新节点给尾节点
System.out.println("第一个节点" + node);
}
// 将新节点添加到尾节点的后面
else {
tail.setnext(node);// 将新节点设置为尾节点的下一节点
tail = node; // 将新添加的节点作为尾节点
System.out.println("新加节点" + node);
}
size++;
}
//移除指定索引位置的数据
public Node remove(int index) {
// 循环的节点
Node node = root;
// 移除的节点
Node removeNode;
if (index == 0) {
root = node.getnext();
removeNode = node;
} else {
for (int i = 0; i < index - 1; i++) {
node = node.getnext();
}
// 判断移除的节点是否是最后一个
if (index == size - 1) {
removeNode = node.getnext();
node.setnext(null);
} else {
// 将node的下一个节点赋给要移除的节点
removeNode = node.getnext();
Node nextNode = removeNode.getnext();
node.setnext(nextNode);
}
}
size--;
// 返回要删除节点的数据域对象
return removeNode;
}
// 获取指定索引位置节点的参数
public Node get(int index) {
if (index < 0 || index >= size){
return null;
}
Node node = root;
// 循环获取到指定位置的诗句
for (int i = 0; i < index; i++) {
node = node.getnext();
}
return node;
}
// 返回链表中节点总数
public int size() {
return size;
}
}
??
?
?
相关文章
