精华内容
下载资源
问答
  • Java链表实现队列

    千次阅读 2019-11-17 20:05:20
    Java链表实现队列

    链表队列和循环队列的效率差别不大  


    public interface Queue<E> {
        int getSize();
        boolean isEmpty();
        // 入队
        void enqueue(E e);
        // 出队
        E dequeue();
        // 返回对首元素
        E getFront();
    }

     

    • 从tail删除元素不容易
    • 从head端删除元素,从tail端插入元素
    • 由于没有 dummyHead,要注意链表为空的情况

    public class LinkedListQueue<E> implements Queue<E> {
        private class Node {
            public E e;
            public Node next;
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
            public Node(E e) {
                this(e, null);
            }
            public Node() {
                this(null, null);
            }
            @Override
            public String toString() {
                return e.toString();
            }
        }
        private Node head, tail;
        private int size;
    
        public LinkedListQueue() {
            head = null;
            tail = null;
            size = 0;
        }
        @Override
        public int getSize() {
            return size;
        }
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
        @Override
        public void enqueue(E e) {
            //链表为空的时候
            if (tail == null) {
                tail = new Node(e);
                head = tail;
            } else {
                tail.next = new Node(e);
                tail = tail.next;
            }
            size++;
        }
    
        @Override
        public E dequeue() {
            if (isEmpty()){
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            Node retNode = head;
            head = head.next;
            retNode.next = null;
            //链表为空了
            if (head == null) {
                tail = null;
            }
            size--;
            return retNode.e;
        }
        @Override
        public E getFront() {
            if (isEmpty()) {
                throw new IllegalArgumentException("Queue is empty.");
            }
            return head.e;
        }
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Queue: front ");
            Node cur = head;
            while (cur != null) {
                //->
                res.append(cur + "<-");
                cur = cur.next;
            }
            res.append("NULL tail");
            return res.toString();
        }
    }
    //LinkedListQueue<Integer> queue = new LinkedListQueue<>();
    //for (int i = 0; i < 10; i++) {
    //    queue.enqueue(i);
    //    System.out.println(queue);
    //    if (i % 3 == 2) {
    //        queue.dequeue();
    //        System.out.println(queue);
    //    }
    //}

    Queue: front 0<-NULL tail
    Queue: front 0<-1<-NULL tail
    Queue: front 0<-1<-2<-NULL tail
    Queue: front 1<-2<-NULL tail
    Queue: front 1<-2<-3<-NULL tail
    Queue: front 1<-2<-3<-4<-NULL tail
    Queue: front 1<-2<-3<-4<-5<-NULL tail
    Queue: front 2<-3<-4<-5<-NULL tail
    Queue: front 2<-3<-4<-5<-6<-NULL tail
    Queue: front 2<-3<-4<-5<-6<-7<-NULL tail
    Queue: front 2<-3<-4<-5<-6<-7<-8<-NULL tail
    Queue: front 3<-4<-5<-6<-7<-8<-NULL tail
    Queue: front 3<-4<-5<-6<-7<-8<-9<-NULL tail

    展开全文
  • 双向链表实现栈和队列

    万次阅读 2021-02-05 14:31:34
    双向链表实现栈和队列前言1. 双向链表2. 栈 --》 双向链表 首部加 首部出 O(1)3. 队列 --》 双向链表 首部加 尾部出 O(1) 前言 栈 --》 双向链表 首部加 首部出 O(1) 队列 --》 双向链表 首部加 尾部出 O(1) 1. ...

    前言

    栈 --》 双向链表 首部加 首部出 O(1)
    队列 --》 双向链表 首部加 尾部出 O(1)

    1. 双向链表

    	public static class Node<T> {
    		public T value;
    		public Node<T> last;
    		public Node<T> next;
    
    		public Node(T data) {
    			value = data;
    		}
    	}
    
    	//双向链表
    	public static class DoubleEndsQueue<T> {
    		public Node<T> head;
    		public Node<T> tail;
    
    		public void addFromHead(T value) {
    			Node<T> cur = new Node<T>(value);
    			if (head == null) {
    				head = cur;
    				tail = cur;
    			} else {
    				cur.next = head;
    				head.last = cur;
    				head = cur;
    			}
    		}
    
    		public void addFromBottom(T value) {
    			Node<T> cur = new Node<T>(value);
    			if (head == null) {
    				head = cur;
    				tail = cur;
    			} else {
    				cur.last = tail;
    				tail.next = cur;
    				tail = cur;
    			}
    		}
    
    		public T popFromHead() {
    			if (head == null) {
    				return null;
    			}
    			Node<T> cur = head;
    			if (head == tail) {
    				head = null;
    				tail = null;
    			} else {
    				head = head.next;
    				cur.next = null;
    				head.last = null;
    			}
    			return cur.value;
    		}
    
    		public T popFromBottom() {
    			if (head == null) {
    				return null;
    			}
    			Node<T> cur = tail;
    			if (head == tail) {
    				head = null;
    				tail = null;
    			} else {
    				tail = tail.last;
    				tail.next = null;
    				cur.last = null;
    			}
    			return cur.value;
    		}
    
    		public boolean isEmpty() {
    			return head == null;
    		}
    
    	}
    

    2. 栈 --》 双向链表 首部加 首部出 O(1)

    public static class MyStack<T> {
    		private DoubleEndsQueue<T> queue;
    
    		public MyStack() {
    			queue = new DoubleEndsQueue<T>();
    		}
    
    		public void push(T value) {
    			queue.addFromHead(value);
    		}
    
    		public T pop() {
    			return queue.popFromHead();
    		}
    
    		public boolean isEmpty() {
    			return queue.isEmpty();
    		}
    
    	}
    

    3. 队列 --》 双向链表 首部加 尾部出 O(1)

    public static class MyQueue<T> {
    		private DoubleEndsQueue<T> queue;
    
    		public MyQueue() {
    			queue = new DoubleEndsQueue<T>();
    		}
    
    		public void push(T value) {
    			queue.addFromHead(value);
    		}
    
    		public T poll() {
    			return queue.popFromBottom();
    		}
    
    		public boolean isEmpty() {
    			return queue.isEmpty();
    		}
    
    	}
    
    
    展开全文
  • 链表实现队列

    千次阅读 2018-07-11 10:20:56
    所有的数据结构都可以大致分为两类,由连续单位构成或者由离散单位构成,具体到实体也就是数组实现或者链表实现。数组实现的数据结构方便查找和修改但不方便增删,链表实现的数据结构则刚好相反,适于增删却不便于...

        所有的数据结构都可以大致分为两类,由连续单位构成或者由离散单位构成,具体到实体也就是数组实现或者链表实现。数组实现的数据结构方便查找和修改但不方便增删,链表实现的数据结构则刚好相反,适于增删却不便于查找。
          今天我们用链表来实现队列。

          我们需要实现的功能无非增删查改,这也是一般的数据结构都会具备的功能。

        一、关于Myqueue
          我们为这个队列设置一个Node类型的头结点head,这个头结点并不放数据,仅仅存一个指针,这样会更便于后面的插入和删除操作。然后再定义一个Node型的结点cur来表示当前结点,以及定义一个int 型的size记录队列的长度。

       二、关于Node
          我想实现的只是一个简单的单向队列,所以仅仅包含数据域data和指向下一个结点的“指针”next(Java中没有指针,只是类似一个索引),并且定义一个构造方法。(如果想实现双向队列可以定义front,next两个指针)代码如下:
    public class Myqueque {
    	public Node head;  //头结点,不存数据
    	public Node cur;   //当前节点
    	public int size;   //队列长度
    
    	public class Node {
    		public Object data;
    
    		public Node next;
    
    		public Node(Object data) {
    			this.data = data;
    			
    		}
    	}
    

    增删查改
     增 :增添操作给的参数是新加入的数据
          1.我们先创建一个新的节点来接受数据。
           2. 然后按照表是否为空表分讨论,因为两种情况的head指针位置是不同的。若为空表,则把新节点当作表头即可,让head           和cur都指向它;若不是空表,创建节点后让cur指向它。  
            代码如下:
    // 增
    	public void Add(Object input) {
    		Node addnode = new Node(input);
    		if(head==null) {  //如果头结点不存在
    
    			head=addnode;
    			head.next=null;
                           cur=head;//移动当前节点到头节点
    
    		}
    		 else  { 
                            //头节点存在,移动当前节点的位置
                            cur.next=addnode;
    
    			cur=cur.next;
    
    		}
    		size++; //数组的大小++
    		
    }
    
    


    删:删除操作给的参数是希望删除的位置。

         删除前也要问自己一个问题:表是不是空的?如果空了删个鬼哦;

        如果删的是表头,移动头指针就好了;

       如果删的是中间,则需要改变一下中间被删除节点的前一个节点,让其next绕过希望删除的节点temp;如果是删除表尾,则直接让cur.next=null。但是其实这两种情况可以合并为temp.next=temp.next.next;

      

    	// 删
    	public void Delete(int index) {
    		//   Object retuNode;   如果希望取得想删除节点的值就创一个节点接收数据,最后返回。此处我不想返回它的值,可以自己灵活更改
    		if (size <= 0) //数组的size必须大于0
    			System.out.println("Error.");
    		else {
    			if(index==0){  //删头节点
    			//   retuNode=head.data;
    			   head=head.next;  //关键句
    					   
    			   }
    			else if (index > 0 && index <= size) { //删除中间或表尾
    				int count = 0;
    				Node temp=head;
    				while (count != index) {
                                    temp=temp.next;
    				count++;
    				}
    				retuNode=temp.next.data;
    				temp.next=temp.next.next;   //关键句
    				size--;
    			}  
    			else { //输入越界
    				System.out.println("No such node.");
    
    			}
    		}
    
    	}
    
    


     查:查找操作给的参数是被查找元素的位置index

           同样的,要考虑给的index是否合理,有没有越界;接下来定义一个节点temp接收数据,操作很简单了,不解释了  

    //查
    	public Object Search(int index) {
    		int count = 0;
    		Node temp=head;
    
    		if (index >= 0 && index < this.Size()) {
    			while (count<index) {
    				temp = temp.next;
    				count++;
    			}
    			return temp.data;
    		} else { //如果要找的index越界
    			System.out.println("No such node.");
    			return null;
    		}
    	}
    



    改:修改与查找十分相似,区别仅仅是参数除了修改的位置还多了个数据N,因为不知道N是什么类型的所以用Object;

             步骤就是先查找,再赋值。

    	// 改
    	public void Change(int index,Object N) {
    		int count = 1;
    		Node temp=head;
    
    		if (index >= 0 && index <= this.Size()) {
    			while (count != index) {
    				temp = temp.next;
    				count++;
    			}
    			temp.data=N;
    		//	System.out.println(temp.data+"hhhhhhhhh已修改");  //调试用的
    		} else {
    			System.out.println("No such node.");
    			
    		}
    	}
    


     好了现在队列创建好了,我们给它添加一个测试类看看对不对:

    public class Test {
    
    	public int number;
    	public String name;
    	
    	public Test(int num,String s){
    		number=num;
    		name=s;
    	}
    	
    	/*public String toString() {
    		
            return getClass().getName() +;
        }*/
    	
    	
    	public static void main(String[] args) {
    		Test t1=new Test(1,"hhhhh");
    		Test t2=new Test(2,"xxxxx");
    		Test t3=new Test(3,"eeeee");
    		Test t4=new Test(4,"aaaaa");
    		
    		Myqueque q=new Myqueque();
    		q.Add(t1);
    		q.Add(t2);
    		q.Add(t3);
    		q.Add(t4);
    		
    		Test test1=(Test)q.Search(0);
    	//	Test test2=(Test)q.Change(3,"这是被修改的");
    		System.out.println("sssssssssss+"+test1.number+":"+test1.name);
    		//System.out.println("333333333333333+"+test2.number+":"+test2.name);
    		q.Change(3,"这是被修改的");
    		
    		q.Delete(0);
    		Test ts4=(Test)q.Search(0);
    		System.out.println("shanchu"+ts4.number+":"+ts4.name);
    
    		
    		
    	
    		q.Change(3, "hahahhah");
    		
    	}
    
    }
    


     测试的结果我就不放截图了(哈哈哈。。。)你可以自己试试哦

    展开全文
  • 用Python实现链表:用单向链表实现栈(元素进栈) 用单向链表实现元素进栈大概分为以下几个步骤; 创建节点 用链表的头部插入/删除元素 元素进栈 1.创建节点 _Node类的构造函数是为了方便而...

    用单向链表实现元素进栈大概分为以下几个步骤;

    1. 创建节点

    2. 用链表的头部插入/删除元素

    3. 元素进栈

    1.创建节点

    _Node 类的构造函数是为了方便而设计,它允许为每个新创建的节点赋值。
    由于 python 没有指针,因此一般使用类的结构实现指向关系。

    例如:

    class TreeNode:
        # 类的结构包含了指向关系
       def __init__(self,x):
            self.val = x
            self.next = None
      
    # 创建实例
    l1 = TreeNode(0)
    l2 = TreeNode(1)
    l3 = TreeNode(2)
      
    # 引用表示指向关系
    l1.next = l2
    l2.next = l3
    

    运行结果如下:

    In [1]:l3
    Out[1]: <__main__.TreeNode at 0x24d3e274908>
        
    In [2]:l1.next.next
    Out[2]: <__main__.TreeNode at 0x24d3e274908>
        
    In [3]:l3.val
    Out[3]: 2
        
    In [4]:l1.next.next.val
    Out[4]: 2
    

    可以看出 l1.next.next 和 l3 指向同一个地址。

    用单向链表实现元素压栈中,创建的节点为轻量级节点 _Node,为此定义了一个 __slots__对象,这是因为 python 中的命名空间均代表内置 dict 类的一个实例,即将范围内识别的名称与相关联的对象映射起来,这会导致额外内存使用量。
    因此,这里使用__slots__声明,将所有实例成员分配给一个固定的字符串序列,利用一组元组来自动打包。

    class _Node:
    	# 赋值右边是一组元组
        __slot__='_element','_next'
    

    创建节点的代码如下:

    # 创建节点
    class _Node:
        __slot__='_element','_next'
            
        def __init__(self,element,next):
            self._element = element
            self._next = next
    

    2.在链表的头部插入/删除元素

    只有在链表头部才能实现常熟时间内的有效插入和删除元素。为避免每次返回栈的大小时,必须遍历整个列表,因此定义一个变量 _size 持续追踪当前元素的数量。

    def __init__(self):
        self._head = None
        self._size = 0
    

    3.元素压栈

    当栈顶插入新元素时,调用 _Node 类来完成链接结构的改变。

    def push(self,e):
        self._head = self._Node(e,self._head)
        self._size += 1
    

    每一个新元素进栈,将其赋予 _Node 类创建一个新节点,新节点的 _next 指针被设置为前一个栈顶的元素,头指针设置为新节点。即原栈顶后移,新元素成为栈顶。
    这里可以创建一个实例更直观地了解一下。

    #创建ls实例
    ls=LinkedStack()
    ls.push(1)
    ls.push(2)
    
    In [1]: ls._head._element
    Out[1]: 2
    
    In [2]:ls._head._next._element
    Out[2]: 1
    

    当第一次调用 ls.push(1) 的时候,栈顶为 1,当第二次调用 ls.push(2) 的时候, self._Node(e,self._head) 中 self._head 为 _element 为 1 的元素,调用 _Node 类的 self._next = next ,self._head 设置为 _next,实现原栈顶后移,同时 _head 设置为 2 的元素,新元素成为栈顶。

    完整代码如下

    class LinkedStack:
        
        # 创建节点
        class _Node:
            __slot__='_element','_next'
            
            def __init__(self,element,next):
                self._element = element
                self._next = next
            
        # 设置栈顶
        def __init__(self):
            self._head =None
            self._size = 0
            
        # 元素压栈
        def push(self,e):
            self._head = self._Node(e,self._head)
            self._size += 1
    
    
    
    ls=LinkedStack()
    
    ls.push(1)
    ls.push(2)
    
    展开全文
  • linux内核双链表实现快速排序

    千次阅读 2020-09-22 03:20:02
    C语言,linux内核双链表实现快速排序,主要涉及到内核链表的基础操作,基地址转换和内核链表两个任意结点互换的实现。
  • 链表实现堆栈

    千次阅读 2017-06-24 15:09:31
    堆栈数据一种后进先出的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。基本的堆栈操作是push和pop,push是把...堆栈很容易实现,可以用静态数组、动态数组、链表实现堆栈。本文介绍的是链表实现的堆栈。
  • 链表实现大数加法

    千次阅读 2017-05-16 21:12:35
    链表实现大数加法标签: 算法Description你的任务是完成一条能实现加法功能的单向链表,需要实现的函数在头文件已给出。 假如现在有 123 与 234 两个数字,那么他们在链表中的存储结构将会是 : 3->2->1与 4->3->2 ...
  • 链表实现多项式乘法

    2019-01-02 21:54:04
    链表实现多项式乘法。 详细设计 #include &lt;stdlib.h&gt; #include&lt;iostream&gt; using namespace std; typedef struct lnode{ int coef; //系数 int exp; // 指数 lnode *next; }lnode; ...
  • C语言链表实现

    千次阅读 2018-09-07 16:33:09
    链表实现带头结点的栈,入栈用头插法 环境codeblocks */ #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;stdbool.h&gt; typedef int ElemType; typedef struct Node...
  • 单向链表实现堆栈

    千次阅读 2017-04-29 21:58:11
    单向链表实现堆栈 要求: 1 使用C语言; 2 使用单向链表; 3 接口规范,通用性强; 解: 1 链表元素的类型确定 为了最终确定这两个函数的调用模型,你还需要知道进出堆栈的数据是属于哪种类型的。也就是说,...
  • 链表实现栈和队列

    千次阅读 2018-11-03 22:07:06
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;...在之前的博文中详细介绍了栈的数组方式实现和队列的数组方式实现学习了链表当然要再实现一波咯!... * 使用链表实现栈 * @author Mr.Hu * */ public class...
  • 数据结构-使用链表实现队列

    万次阅读 2020-01-18 22:13:34
    使用链表实现队列 目录结构 Queue接口 package LinkedListQueue; //队列 public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); //向队列中添加元素 E dequeue(); /...
  • STM32用链表实现多级菜单

    热门讨论 2012-10-02 11:23:15
    链表实现多级菜单,STM32彩屏显示多级菜单
  • 链表实现多项式相加

    千次阅读 2018-01-29 20:15:43
    使用链表实现多项式的相加,最终输出相加的多项式。默认链表的指数为递增。输入时依次输入系数和指数,以0 0 作为结束标志。 比如: 多项式A:1+2*x-4*x^4 多项式B:2-2*x+5^x^4 输入: 0 1 2 1 -4 4 0 0 ...
  • 用循环链表实现队列

    千次阅读 2019-01-02 16:13:53
    用循环链表实现队列 请编写程序用循环链表实现队列,设置一个指针指向队尾元素(注意不设置头指针),该队列具有如下五个接口功能,并编写主程序测试队列的各个接口,测试方法:将一串字符入队后再依次出队并输出出...
  • C语言链表实现学生管理系统

    千次阅读 多人点赞 2019-06-19 21:38:02
    C语言链表实现学生管理系统 #include "stdio.h" #include "stdlib.h" #include "string.h" struct Student { unsigned long ID; char Name[21]; float Score; }; struct Node { struct ...
  • 链表实现vector

    2017-03-07 17:53:04
    链表实现vector的一些功能,部分代码如下,以后还要修改,现在先做一个修正 // keshan.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include #include #define NULL 0 #define LEN sizeof...
  • Python中除了列表,还有链表这样的基础数据结构,之前我们都是介绍用列表实现栈、队列这样的数据结构的,接下来我们看一下用链表实现的栈和队列。 既然列表已经可以实现栈和队列了,那么链表又有什么存在的意义呢?...
  • python使用链表实现列表list

    千次阅读 2018-09-29 09:29:25
    在python中列表是使用链表实现的,下面使用单向链表实现List class List(): class Node(): def __init__(self,object_,next_node): self.object_=object_ self.next=next_node def __init__(self...
  • 使用链表实现队列

    千次阅读 2015-09-28 20:41:22
    使用链表实现队列和堆栈不一样的地方在于: 需要另外的一个指针指向队列尾部。 每次Push()在链表尾部进行。 每次Pop()则在链表头部进行。 同样,在查看队列头尾元素时(Front()、Back()),对队列进行判空操作 ...
  • python用链表实现队列

    2019-02-19 00:48:07
    class LNode: """节点的类""...用链表实现队列,因为列表尾部出列时间复杂度高,所以一般就是在尾部加个指针self.pEnd实现尾入头出(个人理解)""" def __i
  • C语言链表实现大数加法

    千次阅读 2018-12-18 16:17:46
    C语言链表实现大数加法 #include &amp;amp;lt;stdio.h&amp;amp;gt; #include &amp;amp;lt;stdlib.h&amp;amp;gt; #include &amp;amp;lt;string.h&amp;amp;gt; typedef struct list { ...
  • C语言使用链表实现学生信息管理系统 代码实现的功能: 1.插入学生信息 2.显示学生信息 3.删除学生信息 4.在指定位置插入学生信息 5.查找学生信息 代码内容: #include #include #include #define Max_...
  • 栈是基本的数据结构。其特点是添加和删除(访问)数据都在线性表的一端(头端)。数据访问遵循先进后出(FILO)的原则。栈一般用数组或者链表来实现。数组需要静态分配数据...本文用单向链表实现栈。程序用C++实现。
  • 链表实现堆栈和队列

    千次阅读 2018-09-06 00:28:51
    链表实现堆栈:栈的顶部即为链表头,实例变量first指向栈顶,当使用push()压入一个元素时会将该元素添加到表头,当使用pop()删除一个元素时会将该元素从表头删除,操作时间与元素个数无关。 Java代码如下: ...
  • 队列的链表实现

    千次阅读 2015-08-30 20:58:19
    摘要:(1)用链表实现队列,,基本数据结构.很简单。 (2)注意开始rear与front的位置关系.#include "stdafx.h" #include "malloc.h" #include "stdlib.h" typedef struct QueueRecord * queue; struct QueueRecord ...
  • 链表实现冒泡排序!

    千次阅读 2017-09-07 17:26:53
    那么如何用链表实现冒泡排序呢? 我们需要把数据存储在链表中,然后调用排序函数就可以了。但必须要注意链表与数组的不同点,链表没有下标,要想访问数据域必须通过节点来访问。 二、代码实现 #include #...
  • DS之链表实现就地逆置

    千次阅读 2015-05-08 21:11:42
    链表实现数据元素逆置是一个很常用的实例,在顺序表实现输入数据逆置那篇博客需要额外的一个逆置函数,在主函数中实现逆置还需要调用逆置函数。这一篇就全部用链表的知识来实现就地逆置并且输出逆置后的数据元素。 ...
  • Java版双向链表实现

    千次阅读 2015-10-07 18:28:46
    Java版双向链表实现  双向链表是每个结点有两个地址域的线性链表,两个地址域分别指向前结点和后结点,结果如下:  双链表结点(prev 前驱结点地址域;data 数据域;next 后继结点地址域) 1、双链表结点类 public ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,252
精华内容 36,100
关键字:

链表实现