数据结构（java语言描述）

布满荆棘的人生 2022-04-02 14:14 242阅读 0赞

数据结构（java语言描述）  
　　概念性描述与《数据结构实例教程》大同小异，具体参考：[http://www.cnblogs.com/bookwed/p/6763300.html。][http_www.cnblogs.com_bookwed_p_6763300.html]

概述  
基本概念及术语  
数据  
信息的载体，是对客观事物的符号表示，凡能输入到计算机中并被计算机程序处理的符号都可称为数据。  
数据元素  
是数据的基本单位，它在计算机处理和程序设计中通常作为独立个体。数据元素一般由一个或多个数据项组成，一个数据元素包含多个数据项时，常称为记录、结点等。数据项也称为域、字段、属性、表目、顶点。  
如数据库中的一行就是一个数据元素，每个字段又叫数据项。  
数据对象  
是具有相同特征的数据元素的集合，是数据的一个子集，如一个整型数组、一个字符串数组都是一个数组对象。  
数据结构  
简称DS（Data Structure），是数据及数据元素的组织形式。任何数据都不是彼此孤立的，通常把相关联的数据按照一定的逻辑关系组织起来，这样就形成了一个数据结构。  
数据结构包含两方面的内容，一是数据对象，二是数据对象中数据元素之间内在的关系，通常有四类基本形式：集合结构、线性结构、树型结构、图型结构或网状结构。  
集合结构：（参考：[http://www.cnblogs.com/bookwed/p/6763300.html）][http_www.cnblogs.com_bookwed_p_6763300.html 1]  
线性结构  
树型结构  
图型结构  
数据类型  
是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。每一种数据类型都有自身特点的一组操作方法，即运算规则。Java提供的基本数据类型有：byte、short、int、long、float、double、boolean、char。  
基本数据类型：在栈中可以直接分配内存；引用数据类型：数据的引用在栈中，但是它的对象在堆中。  
数据的逻辑结构  
从具体问题抽象出来的数学模型，与数据在计算机中的具体存储没有关系，独立于计算机，是数据本身所固有的属性。  
从逻辑上可以把数据结构分为线性结构和非线性结构。主要有：集合、线性、树和图形数据结构，其中集合、树、图都属于非线性结构。  
数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系集，它反映了D中各数据元素之间的前驱后继关系。通常记为R，即一个数据结构可以表示成二元组B=（D，R）。  
如一年四季可以表示成B1=（D1，R1），其中D1=\{春，夏，秋，冬\}，R1=\{<春，夏>,<夏，秋>,<秋，冬>\}；注意，<x,y>意为x和y之间存在“x领先于y”的次序关系。而(x,y)表示x和y之间没有次序上的关系。  
数据的物理结构  
又称存储结构，主要研究在计算机中如何表示和存储数据结构。分：顺序和链式两种，顺序存储的特点是数据元素在存储器的相对位置来体现数据元素相互间的逻辑关系，顺序存储结构通常用高级编程语言中的一维数组来描述或实现。  
链式存储结构是通过一组任意的存储单元来存储数据元素的，而这些存储单元可以是连续的，也可以是不连续的。  
在顺序存储结构的基础上，又可延伸出两种，即索引存储和散列存储。  
索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。  
散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时可以大大提高效率。  
面向对象的数据结构表示  
Java面向对象基础  
类的声明与实例化  
Java是面向对象的程序设计语言，类和对象是面向对象的核心。  
在java中，自定义一个类的实质是自定义一种数据类型。因此，必须将类实例化之后才能引用类中的成员变量和成员方法。所谓“实例化”就是使用类声明一个变量并通过new操作符以及构造器完成各成员变量的初始化。　　　　　  
类的成员的定义与使用  
类是数据以及数据的操作的封装体。类的成员详细描述了类的数据信息（成员变量）以及针对这些数据信息的操作方法（成员方法）。Java是面向对象的，方法不能独立存在，所有的方法都必须定义在类之中。  
类的成员在类的内部允许直接使用。但是，在类的外部引用类的成员通常必须使用对象名来引用，格式为：“对象.成员名”。  
抽象类  
在java中，类的成员方法用来完成类的成员变量的运算处理，因此通常拥有明确的可执行的语句代码。但是，当类表达的是抽象概念时，其运算也是抽象的，此时只能定义方法的格式，而无法写出语句代码。  
在java中，抽象类和抽象成员方法必须使用abstract来修饰。抽象方法不能有方法体。抽象类不能被实例化，无法使用new关键字来创建对象，但是抽象类可以作为父类被其他类继承。抽象类的子类必须实现抽象类的抽象成员方法。  
泛型类  
泛型就是一种包含了要运算处理的数据的类型尚不明确而临时使用类型参数来表示的一种自定义数据类型。  
泛型类在使用时必须明确指定各类型参数对应的实际数据类型，java编译器在编译代码时将根据所指定的实际数据类型自动替换对应的类型参数。  
使用Java语言描述数据结构的优势  
在Java中，使用类时必须先声明变量名（也称对象名），然后实例化，再引用类的成员。其中，实例化的本质是为对象分配足够的内存空间，以保存各数据成员的值。对象名代表对象的引用，可理解为对象所拥有的内存空间的首地址。因此，Java不使用指针就可以描述数据结构的前期后继关系。  
Java的泛型类定义了一个代码模板，专门针对暂时不确定的数据类型进行抽象描述和定义。  
算法的基本概念  
是指在有限的时间范围内，为解决某一问题而采取的方法和步骤的准确完整的描述，它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。  
一个算法的特征：  
有穷性  
确定性  
可行性  
输入  
输出  
算法效率的度量：  
正确性  
可读性  
健壮性  
运行时间  
占用空间  
算法效率分析  
时间复杂度（所需运行时间）和空间复杂度（所占存储空间）　　　　　　　　　　　　　　　　　　  
线性表  
线性表的逻辑结构  
概念  
是n个数据元素的有限序列，其元素可以是一个数、一个符号，也可以是由多个数据项组成的复合形式。  
线性表中的数据元素也可以由多个数据项组成。例如图书表中的一本书的基本信息，称为一条记录。通常，把含有大量记录的线性表称为文件。  
对于同一个线性表，其中的数据元素必须具有相同特性，也就是说，同一线性表中的数据元素必须属于同一种数据类型。  
在线性表中，数据元素之间的相对位置关系可以与数据元素的值有关，也可以无关。当有关时，称为有序线性表，即表中的元素按照其值的某种元素进行排列，否则，称为无序线性表。  
线性表的顺序表示和实现  
线性表的顺序表示  
即顺序表  
顺序表的实现  
通常用数组来描述顺序存储结构。对于线性表，可以用一维数组来实现。  
在顺序存储结构的线性表中插入或删除一个数据元素，其时间主要耗费在移动元素上。换句话说，移动元素的操作作为预估算法时间复杂度的基本操作，对于新增和删除操作，元素移动的次数不仅与表长有关，而且与插入和删除的位置有关。假定在任何位置上插入和删除元素都是等概率的，则插入和删除一个数据元素，平均约移动表中一半元素，算法add和remove的时间复杂度均为O(n)。  
　　  
线性表的链式表示和实现  
线性表的链式表示  
线性表的链式存储结构是用一组任意的存储单元来存放线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。  
对每个数据元素，除了存储本身的信息之外（数据域），还需存储一个指示其直接后继存放位置的指针（指针域）。这两部分信息组成数据元素的存储映像，称为结点。  
单链表  
含有n个元素的线性表通过每个结点的指针域链接成一个链表，又由于此链表的每个结点中只有一个指向后继的指针，所以称其为单链表或线性链表。  
循环链表  
特点是表中最后一个结点的指针域不再为空，而是指向表头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到链表中其他结点。  
循环链表的操作与单链表基本一致，差别仅在于算法中判断到达表尾的条件不是p或p.next是否为空，而是它们是否等于头指针。  
双向链表  
以上链表，只有一个指向其后继结点的指针域next，若已知某个结点，要找其前驱结点，则只能从表头指针出发。也就是说，找后继的时间复杂度为O(1)，而找前驱的时间复杂度为O(n)，如果希望找前驱的时间复杂度也为O(1)，则需付出空间的代价，在每个结点中再设一个指向前驱的指针域，由这种特点组成的链表称为双向链表。  
和单链表类似，双向链表也可以有循环表。  
栈和队列  
栈  
栈的定义及基本运算  
栈是限定仅在表尾进行插入和删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。  
独木桥，原路返回  
假设栈S=（a1,a2,…,an），则称a1为栈底元素，an为栈顶元素。栈中元素按a1，a2…an的顺序进栈，退栈从栈顶元素开始出栈。所以，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（LIFT,last in first out）的线性表。  
入栈和出栈是栈的两个主要操作，每一次进栈的元素总是称为当前的栈顶元素，而每一次出栈的元素总是当前的栈顶元素。所以栈顶的位置随元素的插入和删除而变化，为此需要一个称为栈顶指针的位置指示器来表示栈顶的当前位置。  
顺序栈  
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，把数组中下标为0的一端作为栈底。  
链栈  
栈的链式存储结构称为链栈。利用链表实现。链表中的每个数据元素由两部分信息组成，一部分存储数据元素信息，称为数据域；一部分存储后继存储位置的的信息，称为指针域。链栈在结构上是链表的形式，在操作定义上依然是栈的定义，栈中元素后进的先出，先进的后出，第一个入栈的是栈底元素，最后的是栈顶元素。  
对于链式栈，无栈满问题，空间可扩充，插入和删除仅在栈顶处执行，链式栈的栈顶在链头。

[http_www.cnblogs.com_bookwed_p_6763300.html]: http://www.cnblogs.com/bookwed/p/6763300.html%E3%80%82
[http_www.cnblogs.com_bookwed_p_6763300.html 1]: http://www.cnblogs.com/bookwed/p/6763300.html%EF%BC%89