数据结构(Java)基本知识.doc

数据结构(JAVA)培训提纲
第一章绪论
1、概念
数据:是数据结构最基本的概念
数据元素:构成数据结构的基本单位
数据项:构成数据结构的最小单位
数据结构:某种联系的数据元素以及元素之间所构成的各种关系组成的集合。
数据的结构可以分为数据的逻辑结构和数据的物理结构
2、数据结构的三种基本结构
线性结构:数据元素之间一对一的线性关系
层次结构(树形结构):数据元素之间一对多的关系
网状结构(图形结构):数据元素之间多对多的关系
3、算法:完成某项任务或特定问题的求解步骤。算法和程序有区别,算法是解决问题的步骤分析,程序是实现算法的有效工具。
算法的基本特性:输入性、确定性、可执行性、输出型、有限性
算法的效率不仅仅包含算法的时间复杂度还有空间复杂度。
线性表
线性表:将多个具有相同类型的数据元素放在一起构成的有限序列的结构称为线性表。
A代表一个线性表
ai称为线性表的元素,i为元素下标,标示该元素在线性表中位置
线性表中N为表长,N》=0,当N=0时线性表为空
线性表式基于相邻元素之间的对应关系,将元素ai-1称为元素ai 的直接前驱,就有 ai+1为元素 ai的直接后继。
线性表的存储结构可分为顺序存储结构和链式存储结构。
线性表的常见操作有:建表(初始化)、求表长、查找、插入、删除等。
顺序表:线性表在顺序存储形式下构成的表
顺序形式:指一段连续的存储单元
优点:简化操作
缺点:不便于插入、删除。对空间效率不是最优
链表:也是一种有顺序的表,起内容可存储在一组任意的存储单元中,任意的存储单元,即这组存储单元可以连续也可以连续,
相关概念
结点:将表示数据元素和下一个元素位置的结构称为链表的结点。
头结点:若第一个结点只表示整个链表的起始位置,而无任何信息,称其为头结点。
尾结点:对于最后一个结点,后面无任何元素,其表示元素位置的地址“∧”表示,称为尾结点
链表的表示:链表中结点的表示必须要用到2个区域,其中一个存放数据元素自身的信息,称为数据域;另外一个存放下一个元素的地址或位置,以保证表的连续性,称为
指针域。
链表的分类
单链表:最常见的一种,从第一个元素到最后一个元素构成的链表。
循环链表:单链表中,最后一个元素如果它指向第一个元素位置,构成循环链表
双向链表:每元素可以向两个方向进行查找。包含两个指针域。
栈和队列
栈:特殊的线性表,其全部操作都被限制在表的固定一端进行。满足“后进先出”的顺序。
例如:利用一个堆栈,如果输入序列有ABC组成,试给出全部可能的输出序列.
解:输出的可能有5种,分别如下:
B C (A入A出,B入B出,C入C出)
C B (A入A出,B入C入,C出,B出)
A C (A入B入,B出,A出,C入,C出)
C A (A入B入,B出,C入C出,A出)
A B (A入B入C入,C出,A不可能先于B出来)此种不可能
B A (A入B入C入,C出B出A出)
顺序栈:顺序存储结构下的栈叫做顺序栈。
链式栈:链式存储结构下的栈叫做顺序栈
栈的常见操作:建立栈、元素进入栈