文档介绍：
一、基本概念:
数据(Data):信息的载体,能够被计算机识别、存储和加工处理的物理符号。包括文本类型的数据(如:字母、数字、汉字)和多媒体类型的数据(如:声音、动画、图像)。
数据元素(Data Element):是数据的基本单位,有时也称为元素、结点、顶点、记录,可以有若干个数据项(字段、域、属性)组成。
数据结构(Data Structure):指的是数据之间的相互关系,即数据的组织形式。其包括三个部分:
1、逻辑结构:数据元素之间的逻辑关系
2、存储结构:数据元素及其关系在计算机存储器内的表示。
3、数据的运算(算法):即对数据施加的操作
数据的逻辑结构有两大类:
1、线性结构:
特征是:若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点最多只有一个直接前趋和一个直接后继。
例:一维数组、链表、栈、队列、串
2、非线性结构:
特征是:一个结点可能有多个直接前趋和直接后继。
例:多维数组、广义表、树、图
数据的存储结构有以下基本存储方法:
1、顺序存储方法:
该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,一般通过数组来实现的。
2、链接存储方法:
该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。
3、索引存储方法:
该方法通常是在存储结点信息的同时,还建立附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是:关键字,地址。
4、散列存储方法:
该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址,通过散列函数实现。例:除余法散列函数、相乘取整法散列函数
算法的基本特征:
1、可行性(Effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。
2、确定性(Definiteness):算法中的每一个步骤都必须有明确的定义,不允许出现歧义性。
3、有穷性(Finiteness):算法必须在有限时间内做完,即必须在执行有限个步骤之后终止。
时间复杂度:该算法执行的时间耗费,它是该算法所求解问题规模n的函数。
空间复杂度:该算法执行时所耗费的存储空间,它也是问题规模n的函数。
二、线性表:
线性表(Linear List):是由n(n>=0)个数据元素(结点)a1,a2,a3,······,an组成的有限序列。对于非空的线性表,有且仅有一个开始结点a1,它没有直接前趋;有且仅有一个终端结点
an,它没有直接后继;其余的结点有且仅有一个直接前趋结点和一个直接后继结点。
线性表的存储结构:
1、顺序存储(Sequential List):将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里,用这种方法存储的线性表称为顺序表。
2、链式存储(Linked List):逻辑上相邻的结点,物理上也相邻,存储单元可以是连续的,也可以是不连续的,在存储每个结点值的同时,还存储指向其后继结点的地址,用这种方法存储的线性表称为链表。
常见的运算有:
表的初始化、求表的长度、取表中的第i个结点、查找结点、插入新的结点、删除结点。
顺序表和链表的比较:
1、基于空间的考虑:
A、顺序表的存储空间是静态分配的,而链表的存储空间是动态分配的。
B、顺序表占的存储空间必须是连续的,而链表占的存储空间可以是连续的,也可是不连续的
C、顺序表存储密度为1,而链表中的每个结点,除了数据域外,还要额外的设置指针域,存储密度小于1
2、基于时间的考虑:
A、在链表中的任何位置上进行插入和删除,只需要修改指针,而顺序表中平均将要移动近一半的结点。
B、顺序表是随机存取结构,它的存取时间为O(1),而链表需从头结点顺着链扫描链表。
总之,当线性表的长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表作为存储结构;当线性表的长度变化较大,难以估计其存储规模时,以采用链表作为存储结构为好。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;对于频繁进行插入和删除的线性表,宜采用链表做存储结构。
例:关于线性表的描述中,错误的是( )
A、线性表是线性结构 B、线性表的顺序存储结构,必须占用一片连续的存储单元
C、线性表是单链表 D、线性表的链式存储结构,不必占用一片连续的存储单元
用数组表示线性表的优点是( )
A、便于插入和删除操作 B、便于随机存取
C、可以动态地分配存储空间 D、不需要占用一片连续的存储空间
三、栈:
栈(Stack):是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top