GVKun编程网logo

Lua数据结构 — TValue（一）（lua table数据结构）

20

如果您对Lua数据结构—TValue感兴趣，那么本文将是一篇不错的选择，我们将为您详在本文中，您将会了解到关于Lua数据结构—TValue的详细内容，我们还将为您解答一的相关问题，并且为您提供关于Ja

如果您对Lua数据结构 — TValue感兴趣，那么本文将是一篇不错的选择，我们将为您详在本文中，您将会了解到关于Lua数据结构 — TValue的详细内容，我们还将为您解答一的相关问题，并且为您提供关于Java数据结构和算法（一）——简介、java数据结构（一） 数组array、Java数据结构（一）：Vector、Java数据结构（一）：栈的有价值信息。

本文目录一览：

Lua数据结构 — TValue（一）（lua table数据结构）

Lua数据结构 — TValue（一）（lua table数据结构）

作者：罗日健

数据结构的设计，在一定程度上奠定了整个系统的设计，所以决定写一个对Lua主要数据结构的分析文章，本来打算写一篇就好了，但是每个数据类型其实都有点复杂，一篇的话篇幅太长，所以就拆开几篇来写了。

为什么是从TValue说起，TValue是实现Lua弱数据类型的主要数据结构，不但在脚本中的值使用了TValue，连Lua的实现中，很多数据结构也依赖于TValue，TValue一定程度上贯穿了整个Lua。先说一下Lua里面的数据类型:（lua.h :69）

从上面的定义中可以看到，Lua的值类型有9种，其中LUA_TNONE是用于判断这个变量是否等于为空使用的，这个是Lua内部使用的，后面再详细说明。现在来看Lua里面的TValue数据结构:（lobject.h 71-75）

在Lua里面，一个变量使用TValue这个类型来存储的，int tt就是上面宏的类型值（4个字节），而Value则是一个union（8个字节）。在这个union中，其实分工也十分明确:

在Value中，void* p、lua_Number n、int b都是不用回收的值类型，而GCObject* gc则都是需要回收的对象，下面是GCObject数据结构:（lstate.h 133-145）

GCObject也是一个union，存储了一个GCheader，这个GCHeader主要用于GC回收机制使用，GC回收机制超出了这次讨论话题，暂时先忽略。真正存储值的结构是TString、Udata、Closure等等，每个存储数据的结构都会有GCheader，接下来几篇文章将会开始逐个数据类型进行解释。

来自：http://blog.aliyun.com/761?spm=0.0.0.0.eS5aVm

Java数据结构和算法（一）——简介

Java数据结构和算法（一）——简介

、数据结构

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

1.数据结构的基本功能
　①、如何插入一条新的数据项
　②、如何寻找某一特定的数据项
　③、如何删除某一特定的数据项
　④、如何迭代的访问各个数据项，以便进行显示或其他操作

2.常用的数据结构

优缺点

二、算法

1. 算法的设计原则

  • ①、正确性：首先，算法应当满足以特定的“规则说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：

    • 一、程序语法错误。
    • 二、程序对于几组输入数据能够得出满足需要的结果。
    • 三、程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。
    • 四、程序对于一切合法的输入数据都能得到满足要求的结果。

PS：通常以第 三 层意义的正确性作为衡量一个算法是否合格的标准。

  • ②、可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。
  • ③、健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
  • ④、高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

java数据结构（一） 数组array

java数据结构（一） 数组array

数组最好写得支持泛型
public class Array<T> {

       #T是自己自定义的一个类型
          }

java不支持直接new一个泛型，必须先new一个Object，然后前面进行类型转换
data = (E[]) new Object[capacity]

动态数组：扩容部分
if size == length :
resize(2*data.length);

private void resize(int newcapacity) {

E[] newData = (E[]) new Object[newcapacity];
for(int i=0;i<size;i++) {
    newdata[i] = data[i];
    }
data  = newdata

复杂度震荡问题：本来removelast,和addlast操作，均摊的时间复杂度是O(n),但是如果操作到了需要扩容或缩容的元素，频繁的进行，removelast,然后又addlast，这样一直是O(n)
出现这样问题的原因呢：我们添加和删除时候的扩容太激进了，（too eager）,应该元素个数变成总容量1/4的时候，我们只缩容到容量的一半，而不是过于激进，直接缩容到1/4

Java数据结构（一）：Vector

Java数据结构（一）：Vector

1 Vector对象的创建

在使用Vector对象时，需要导入java包：java.util.Vector。

import java.util.Vector;


Vector的创建方式如下，尖括号中可以填写任何的类名（如果想使用基本数据类型，需要填入对应的包装类），该类便是Vector对象中各个元素的类型。

Vector<Integer> v = new Vector<Integer>(); //整型向量
Vector<Double> v = new Vector<Double>(); //双精浮点型向量

2 向Vector对象添加元素

可以使用add与addElement函数来添加元素，两者在使用上没有太大的区别。add的返回值是boolean类型，addElement的返回值是void类型。

Vector<Integer> v = new Vector<Integer>();
v.add(3);　　　　　　　　　　　　　　　　　　//add的返回值是boolean类型
v.add(5);
v.add(8);
v.addElement(10); 　　　　　　　　　　　　　//addElement的返回值是void类型
for(int e:v)System.out.print(e+" ");　　//遍历数组元素，输出： 3 5 8 10

3 读取和修改Vector中的元素

get：根据下标读取元素
set：根据下标修改元素

Vector<Integer> v = new Vector<Integer>();
v.add(3);
v.add(5);
v.add(8);
v.add(10);
for(int e:v)System.out.println(e);      //输出： 3 5 8 10 
System.out.println(v.get(2));　　　　　　 //v.get(2)为读取v中的第2个元素，因此输出：8
v.set(0,100);　　　　　　　　　　　　　　　　//修改第0个元素为100
v.set(3,200);　　　　　　　　　　　　　　　　//修改第3个元素为200
for(int e:v)System.out.println(e);　　  //输出： 100 5 8 200

4 移除Vector中的元素


remove：根据下标移除元素
clear：移除所有元素

Vector<Integer> v = new Vector<Integer>();
    v.add(3);
    v.add(5);
    v.add(8);
    v.add(10);
    v.remove(1); 　　　　　　　　　　　　　　　　　　//移除第1个元素"5"
    for(int e:v)System.out.print(e + " ");　　  //输出: 3 8 10
    v.clear();
    System.out.println("向量v的长度为" + v.size());//size()返回向量的长度，输出: 向量v的长度为0


5 遍历Vector中的元素


・下标遍历

Vector<Integer> v = new Vector<Integer>();
v.add(3);
v.add(5);
v.add(8);
v.add(10);
for(int i = 0 ;i<v.size();i++)System.out.print(v.get(i) + " ");//使用下标遍历，输出: 3 5 8 10

・foreach遍历

以上例子多次使用的就是这种方式

Vector<Integer> v = new Vector<Integer>();
v.add(3);
v.add(5);
v.add(8);
v.add(10);
for(int e:v)System.out.print(e + " ");//使用foreach风格遍历，输出: 3 5 8 10

 ・迭代器遍历

由于需要使用Iterator对像，所以需要导入下面的包

import java.util.Iterator;

 

Vector<Integer> v = new Vector<Integer>();
v.add(3);
v.add(5);
v.add(8);
v.add(10);
Iterator iterator = v.iterator();
while (iterator.hasNext()) {
 　　System.out.println(iterator.next());//输出: 3 5 8 10
}

 

6 查询搜索

contains与isEmpty函数

Vector<Integer> v = new Vector<Integer>();
v.add(3);
v.add(5);
v.add(8);
v.add(10);
System.out.println(v.contains(8));//因为向量v元素里包含"8"，所以输出:true
System.out.println(v.contains(7));//因为向量v元素里不包含"7"，所以输出:false
System.out.println(v.isEmpty());//因为向量v里元素个数不为0，所以输出:false
Vector<Integer> v1 = new Vector<Integer>();
System.out.println(v1.isEmpty());//因为向量v1里没有元素，所以输出:true

 

indexOf：从向量头（或指定下标）开始搜索,返回所遇到的第一个对象对应的下标，若不存在此对象,返回-1.
lastindexOf：从向量尾部（或指定下标）开始逆向搜索对象. 返回所遇到的第一个对象对应的下标，若不存在此对象,返回-1. 

Vector<Integer> v = new Vector<Integer>();
v.add(3);
v.add(5);
v.add(8);
v.add(5);
v.add(10);
System.out.println(v.indexOf(5));//第一个"5"的下标为1，所以输出: 1
System.out.println(v.indexOf(5,2));//从第2个元素开始搜索"5"，所以输出: 3
System.out.println(v.lastIndexOf(5));//从尾部开始逆向搜索"5"，所以输出: 3
System.out.println(v.lastIndexOf(5,2));//从第2个元素开始逆向搜索"5"，所以输出: 1

 

Java数据结构（一）：栈

Java数据结构（一）：栈

导言：栈和我们的现实当中的箱子是一样的，保持一个先进后出，后进先出的原则。比如我们往一个箱子堆积衣服，一件一件地放进去之后，过一段时间再回来拿。那么最先放进去的衣服肯定最后拿出来，最后放进去的衣服就会最先拿出来，或许可以类比于给老师提交作业，最先提交作业的同学老师总是最后批改。 因此在Java里面我们可以通过一个数组来模拟这个栈。

首先我们可以构建一个栈，然后在另外一个类当中对栈进行插入数据和移除数据的操作。

一.Mystack.java

/**
 * Created by lenovo on 2019/5/11.
 */
public class Mystack {
//底层实现是一个数组
    private  long[] arr;
    private int top;
//默认的构造方法
    public Mystack()
{
    arr=new long[10];
    top=-1;


}
//带参数的构造方法，参数为数组的初始化大小
    public Mystack(int maxsize)
    {
        arr=new long[maxsize];
        top=-1;
    }
//往栈里添加数据
    public void push(int value)
    {
        arr[++top]=value;

    }
    //移除数据
    public long pop()
    {
        return arr[top--];

    }
    //查看数据
    public long peek()

    {

        return arr[top];

    }
    //判断是否为空
    public boolean isEmpty()
    {
        return top == -1;
    }
//判断是否满了
    public  boolean isFull()
    {

        return top==arr.length-1;//因为top是从0开始的
    }

}

然后我们在一个类当中对这个栈进行操作即可。

二.TestMyStack.java

/**
 * Created by lenovo on 2019/5/11.
 */
public class TestMyStack {
    public static void main(String[] args) {
        Mystack ms=new Mystack(4);//竟然要在主函数里面进行调用才会管用，太神奇了
        ms.push(23);
        ms.push(12);
        ms.push(1);
        ms.push(90);
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());
        System.out.println(ms.peek());
        System.out.println(ms.peek());
        while(!ms.isEmpty())
        {
            System.out.println(ms.pop()+",");
        }
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());
    }

最后的输出结果为：

false
true
90
90
90,
1,
12,
23,
true
false

上面的代码很容易理解，我也就不多讲了。关键是要理解这种后进先出的数据结构是如何实现的。

我们今天的关于Lua数据结构 — TValue和一的分享就到这里，谢谢您的阅读，如果想了解更多关于Java数据结构和算法（一）——简介、java数据结构（一） 数组array、Java数据结构（一）：Vector、Java数据结构（一）：栈的相关信息，可以在本站进行搜索。

本文标签：

上一篇用lua实现ByteArray和ByteArrayVarint（lua string byte）

下一篇LuaJavaBridge - Lua 与 Java 互操作的简单解决方案（lua和java）

相关文章