package nodelist;
public class LinkNode {
public Object data;//节点内的数据对象
public LinkNode next;//对下一个节点的引用
}
package nodelist;
/**
* 用链表实现一个队列
* @author zr
*
*/
public class NodeList {
private LinkNode root;
private int size;
private int count=1;
LinkNode tem1=new LinkNode();//实例化一个节点tem1作为一个临时节点使用
public NodeList(LinkNode root){
this.root=root;
}
/**
* 向队列中加入一个元素
* @param obj 要向队列中加入的元素
*/
public void add(Object obj){
if(root==null){
root=new LinkNode();//实例化一个根节点
root.data=obj;
tem1=root;//将tem1指向根节点root
// System.out.println("if---tem1.data="+tem1.data);
}else{
// System.out.println("else---tem1.data="+tem1.data);
LinkNode tem=new LinkNode();//实例化一个节点tem
tem.data=obj;
//tem1=root;//注意:不能在此处将tem1指向root，否则，每次加入的新元素都加在了root后面
tem1.next=tem;//将tem1的下一个节点指向tem
tem1=tem;//将tem1指向tem
// System.out.println("tem1.data="+tem1.data);
// System.out.println("root.data="+root.data);
}
}
/**
* 获取链表指定位置的节点
* @param index 指定的位置
* @return
*/
public LinkNode get(int index){
LinkNode node=new LinkNode();
LinkNode tem=root;
while(count<index||count==index){
if(count==index){
node=tem;
}
count++;
tem1=tem.next;
tem=tem1;
}
return node;
}
/**
* 获得队列的长度
* @return 返回队列的长度
*/
public int size(){
// System.out.println("size---root.data="+root.data);
LinkNode tem=root;
while(tem!=null){
size++;
tem1=tem.next;
tem=tem1;
//System.out.println("tem.data="+tem.data);
}
// System.out.println("size="+size);
return size;
}
}
package nodelist;
import nodelist.LinkNode;
/**
* 测试用链表实现的队列
* @author zr
*
*/
public class Test {
private static LinkNode root;
/**
* @param args
*/
public static void main(String[] args) {
Test t=new Test();
NodeList nl=new NodeList(root);
nl.add("根节点");
nl.add("节点1");
nl.add("节点2");
nl.add("节点3");
nl.add("节点4");
root=nl.getRoot();
t.printLinkList(root);
int size=nl.size();
System.out.println("链表的长度为："+size);
LinkNode node=nl.get(4);
System.out.println("第4个节点的值为："+node.data);
}
/**
* 遍历一个链表
* @param lroot 链表的根节点
*/
public void printLinkList(LinkNode lroot){
if(lroot!=null){
System.out.println(lroot.data);
LinkNode tem=new LinkNode();
tem=lroot.next;
printLinkList(tem);
}
}
}
结果：
根节点
节点1
节点2
节点3
链表的长度为：4
第4个节点的值为：节点3
往队列中添加元素:
第一个节点进来时：
tem1=root;//将tem1指向根节点root，此时tem1和root指向的是同一个地址
第二个节点进来时：
tem1.next=tem;//将tem1的下一个节点指向tem,因为root和tem1指向的是同一个地址，所以root.next也指向了tem
tem1=tem;//将tem1指向tem,此时tem1和tem指向同一个地址（此时tem所指向的地址）
第三个节点进来时:
tem1.next=tem;//将tem1的下一个节点指向tem,由于此时的tem1和上一次的tem指向的是同一个地址，所以tem.next也指向了tem
tem1= tem;//将tem1指向tem,此时tem1和tem指向同一个地址（此时tem所指向的地址）
第四个节点进来时：
tem1.next=tem;//将tem1的下一个节点指向tem, 由于此时的tem1和上一次的tem指向的是同一个地址，所以tem.next也指向了tem
tem1=tem;//将tem1指向tem, 此时tem1和tem指向同一个地址（此时tem所指向的地址） 
上面向队列中添加元素只能在链表为空的情况下添加，通过以上分析，下面我们来完善一下add()方法，使得无论链表是否为空，我们都可以向队列中添加元素。
分析：
当链表不为空时；
上例是首先将tem1指向了root节点，然后如上所述添加了新的节点；在这里，我们可以把tem1指向最后一个节点，然后如上所述添加新的节点。
tem1=end;//将tem1指向end，此时tem1和end指向同一地址
tem1.next=tem;//将tem1.next指向了tem,由于上一步tem1和tem1指向了同一地址，所以tem1也指向了tem
tem1=tem;//将tem1指向tem,此时tem1和tem指向了同一地址
我们如何获取最后一个节点呢？
1、 先求出已有链表的长度index,所以我们需要写一个求链表长度的方法LinkListSize()；
2、 链表最后一个节点的位置就是index；
3、 然后我们要获得最后一个节点，所以我们需要一个获取链表上某一指定位置节点的方法get(int index);
关键代码如下：
/**
* 用链表实现一个队列
* @author zr
*
*/
public class NodeList {
private LinkNode root;
LinkNode tem1=new LinkNode();//实例化一个节点tem1作为一个临时节点使用
public NodeList(LinkNode root){
this.root=root;
}
/**
* 向队列中加入一个元素
* @param obj 要向队列中加入的元素
*/
public void add(Object obj){
if(root==null){
root=new LinkNode();//实例化一个根节点
root.data=obj;
}else{
LinkNode tem=new LinkNode();//实例化一个节点tem
tem.data=obj;
int index=LinkListSize();//获得链表的长度
tem1=get(index);//获得链表的最后一个节点
//tem1=root;//注意:不能在此处将tem1指向root，否则，每次加入的新元素都加在了root后面
tem1.next=tem;//将tem1的下一个节点指向tem
tem1=tem;//将tem1指向tem
}
}
/**
* 当链表不为空时，向队列中加入元素
* @param obj
* @return 返回链表根节点
*/
public LinkNode add1(Object obj){
int index=LinkListSize();
LinkNode end=get(index);
System.out.println("end.data="+end.data);
LinkNode tem=new LinkNode();
tem.data=obj;
tem1=end;//将tem1指向end
tem1.next=tem;
tem1=tem;
System.out.println("tem1.data="+tem1.data);
return root;
}
/**
* 获取链表指定位置的节点
* @param index 指定的位置
* @return
*/
public LinkNode get(int index){
int count=1;
LinkNode node=new LinkNode();
LinkNode tem=new LinkNode();
LinkNode tem1=new LinkNode();
tem=root;
while(count<index||count==index){
if(count==index){
node=tem;
}
count++;
tem1=tem.next;
tem=tem1;
}
return node;
}
/**
* 获得队列的长度
* @return 返回队列的长度
*/
public int LinkListSize(){
int size = 0;
LinkNode tem=new LinkNode();
LinkNode tem2=new LinkNode();
tem2=root;
while(tem2!=null){
tem=tem2.next;
tem2=tem;
size++;
}
return size;
}
}
/**
* 测试用链表实现的队列
* @author zr
*
*/
public class Test {
private static LinkNode root,root2;
/**
* @param args
*/
public static void main(String[] args) {
Test t=new Test();
System.out.println("当链表为空时开始添加");
NodeList nl=new NodeList(root);
nl.add("根节点");
nl.add("节点1");
nl.add("节点2");
nl.add("节点3");
nl.add("节点4");
root=nl.getRoot();
System.out.println("打印出链表：");
t.printLinkList(root);
int size=nl.LinkListSize();
System.out.println("链表的长度为："+size);
LinkNode node=nl.get(4);
System.out.println("第4个节点的值为："+node.data);
System.out.println();
System.out.println("当链表不为空时开始添加");
root2=t.createLinkList();
NodeList nl2=new NodeList(root2);
nl2.add("节点5");
nl2.add("节点6");
System.out.println("打印出链表：");
root2=nl.getRoot();
t.printLinkList(root2);
int size2=nl2.LinkListSize();
System.out.println("链表的长度为："+size2);
LinkNode node2=nl2.get(7);
System.out.println("第7个节点的值为："+node2.data);
}
/**
* 创建一个链表
* @return 返回链表的根节点
*/
public LinkNode createLinkList(){
root=new LinkNode();
LinkNode n1=new LinkNode();
LinkNode n2=new LinkNode();
LinkNode n3=new LinkNode();
LinkNode n4=new LinkNode();
root.data="根节点";
root.next=n1;
n1.data="节点1";
n1.next=n2;
n2.data="节点2";
n2.next=n3;
n3.data="节点3";
n3.next=n4;
n4.data="节点4";
return root;
}
/**
* 遍历一个链表
* @param lroot 链表的根节点
*/
public void printLinkList(LinkNode lroot){
if(lroot!=null){
System.out.println(lroot.data);
LinkNode tem=new LinkNode();
tem=lroot.next;
printLinkList(tem);
}
}
}
结果为：
当链表为空时开始添加
打印出链表：
根节点
节点1
节点2
节点3
节点4
链表的长度为：5
第4个节点的值为：节点3
当链表不为空时开始添加
打印出链表：
根节点
节点1
节点2
节点3
节点4
节点5
节点6
链表的长度为：7
第7个节点的值为：节点6
相关推荐
用链表实现队列
用链表实现队列
本程序是用链表作为基类，队列类、栈类作为派生类，使用了虚函数，和对象指针
利用数组和链表实现队列的基本操作，如入队，出队，读出队首元素
用循环链表实现队列操作 讲解详细 通过多次编译 可以运行的
定义了一个队列的类，包括建立队、入队、出队、打印队列、访问队首队尾的成员函数。
链表队列的实现 链表队列的具体增删改查实现 是一种单链表实现
c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现,c++链表队列的实现
用链表实现栈和队列的操作，使链表操作更加成熟，熟练栈和队列的机制
链表 链表_使用Python基于链表实现队列数据结构
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点（哨兵） protected DLNode trailer;//指向尾节点（哨兵） protected ...
用链表和队列实现了归并排序，用MinGW实现，进行了大量数据实验，和通过数组实现相比比较省空间但是不省时间。
编译环境为Vs2010，单链表实现队列的出队和入队操作。
1. 编写程序 Node.h 实现例 9-5 的节点类，并...3. 编写程序 queue.h，用链表实现队列（或栈）类。在测试程序 lab9_3.cpp 中声明一个 整型队列（或栈）对象，插入 5 个整数，压入队列（或栈），再依次取出并显示出来。
数据结构 基于链表实现的优先队列 Cpp文件
这是一个双链表去实现队列的列子，里面用到了指针的东西， 还有NODE的东西
使用链表实现的队列 对应于数据机构与算法分析（c++版）第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
嵌入式常用数据结构-链表、队列、堆栈、可删除key值链表、优先级队列，消息队列
严蔚敏版数据结构的链表，队列，和栈的代码（c）实现
队列关于数组与链表的实现， linux c语言