小结—链表与数组
数组连续存储
链表分散
1.链表分类
2.链表的组成
头节点-（引用）->中间节点-（引用）->尾节点
节点有两个部分组成：
1.数据域
存储数据
2.引用域
下一个节点的引用
3.链表的简单实现
node 节点
linkedlist 链表
4.数组的优点和缺点
定义一个数组的方式：
数据类型 [] 数组名 = new 数据类型[长度]; //[]表示数组
数据类型 [] 数组名 ={值,...};
数据类型 [] 数组名 ;
数组名 = new 数据类型[长度] ;
数组名 = new 数据类型[] {值,....};
数据类型 [] [] 数组名 = new 数据类型[行] [列];
数据类型 [] 数组名 ={{值,.}，{..}};
空指针异常
int [] array = new int [10];//可以赋值的是数字 不是对象
获取一维数组元素总数：数组名.length;
获取二维数组的行的列数：数组名[r].length;
获取二维数组的行数：数组名.length;
获取指定位置的数据：数组名[下标];
数组名[行下标][列下标];
缺点：
大小确定，不能根据数据总数的变化进行更改大小
设置节点
/*
* 节点类
*/
public class Node {
private Object data;//数据
private Node next;//引用域
public Object getdata()
{
return data;
}
public void setdata(Object data)
{
this.data=data;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next=next;
}
}
设置链表，功能为增加，删除，查找，修改
——参考了其他代码和注释
public class LinkedList {
private Node root;// 声明一个根节点
private Node tail;// 声明一个尾节点
private int size;// 声明记录链表中节点的个数
/**
* 添加节点的方法
*
* newnode要被添加的节点对象
*/
public void add(Node newnode) {
// 判断root是否为null，如果是，则表示此时第一次添加节点
if (root ==null) {
root = newnode;// 将新节点给根节点
tail = newnode;// 将新节点给尾节点
}
else {// 将新节点添加到尾节点之后。
tail.setNext(newnode);// 将新节点设置为尾节点的下一个节点
tail = newnode;// 将尾节点移动到新添加的节点上，此处表示是末尾节点。
}
size++;// 让计数器加1
}
/**
* 移除指定索引位置的数据
* 在指定位置处删除节点
* 返回移除的数据
*/
public Object removeindex(int index) {
Node node = root;//遍历的节点,从根节点开始遍历
Node removeNode;//要移除的节点
if (index == 0) {//如果要移除的是第一个节点
root = node.getNext();//将root的下一个节点设置为root
removeNode = node;//把原来的root赋给要移除的节点
} else {//如果要移除的是不是第一个节点
//找到要移除节点的前一个节点对象
for (int i = 0; i < index - 1; i++) {
node = node.getNext();
}
//判断要移除的节点是否是最后一个
if (index == size - 1) {
//将node的下一个节点赋给要移除的节点
removeNode = node.getNext();
//将node的下一个节点引用设置为null
node.setNext(null);
} else {//要移除的节点是在链表的中间
//将node的下一个节点赋给要移除的节点
removeNode = node.getNext();
//将removeNode下一个节点的引用赋给nextNode
Node nextNode = removeNode.getNext();
//将removeNode的下一个节点nextNode赋给node,保持链表不会中断
node.setNext(nextNode);
}
}
size--;
//返回要移除节点的数据域对象
return removeNode.getdata();
}
/**
* 获取指定索引位置节点的数据
*
* @param index指定的索引位置
*/
public Object getData(int index) {
if (index < 0 || index >= size)//如果索引位置超出范围
return null;
Node node = root;//定义用来遍历的节点
// 循环获取到指定索引位置的节点
for (int i = 0; i < index; i++) {
node = node.getNext();
}
// 返回指定索引位置的元素
return node.getdata();
}
/**
* 修改索引节点的数据
* @return
*/
public Object changedata(int index ,Object data)
{
if(index<0||index>=size)
return null;//如果索引位置超出范围，返回空
Node node=root;
for(int i=0;i<index;i++){
node=node.getNext();
}
node.setdata(data);//改变指定节点的数据
return node.getdata();//返回索引位置的数据
}
/**
* 移除指定的数据,根据对象的属性值来移除数据
* removedata为指定要移除的数据
* 返回移除的次数
*/
public int removeData(Object removedata){
Node node = root;//定义用来遍历的节点
int count=0;
int index;
Node removeNode;
//如果要移除的是头节点
if(root.getdata().equals(removedata))
{root=root.getNext();
count=1;
}
// 循环获取到指定索引位置的节点
for (int i = 0; i < size-2; i++) {
if(node.getNext().getdata().equals(removedata))//如果node的下一节点的数据就是要找的数据,现在node就是要移除数据的前一个指针
{
index=i+1;
count++;
removeNode = node.getNext();//removeNode就是要移除数据的节点
//获取要删除节点的下一个节点，定义为nextNode
Node nextNode = removeNode.getNext();
//将removeNode的下一个节点nextNode赋给node,这样要移除节点的前一个节点就跳过removeNode直接指向nextNode了
node.setNext(nextNode);
}
node = node.getNext();//获取下一节点
}
size=size-count;
return count;//返回移除指定数据的次数
}
/**
* 返回链表中节点总数
*
* @return 返回size属性
*/
public int size() {
return size;
}
/**
*在指定位置插入节点
*index为指定索引位置
*/
public void insert(int index,Object s)
{
if(index<0||index>size)
System.out.println("错误");
Node temp=root;//定义要遍历的节点，从根节点开始遍历
Node insertNode=new Node();//定义要添加的节点
insertNode.setdata(s);
for(int i=0;i<index-1;i++)//得到要原链表添加位置的前一个节点
{
temp=temp.getNext();
}
insertNode.setNext(temp.getNext());
temp.setNext(insertNode);//设置这个节点指向要插入的节点
size++;
}
}
————11.16
没有实现哈夫曼二叉树