浙江省计算机三级数据库复习资料讲解.docx

数据结构基础数据结构的基本概念及有关术语：数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。它可以是一个不可分割的原子项，也可以由多个数据项组成。数据类型是指一个类型和定义在这个类型上的操作集合。数据结构（data structure）指数据元素之间存在的关系数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被称为数据结构。根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图，其中树结构和图又称为非线性结构。P2数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。而数据的存储结构是逻辑结构在计算机内存中的实现，是依赖于计算机的。数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法分析主要包含时间代价和空间代价两个方面。时间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。空间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。算法的时间及空间复杂性度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。T(n)=O(f(n)) 度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。 S(n)=O(f(n)) 基本数据结构及其操作：线性表是由n(n=0)个类型相同的数据元素a0,a1,…,a(n-1)组成的有限序列。P36线性表的逻辑结构：其中，元素ai的数据类型可以是整数、浮点数、字符或类；n是线性表的元素个数，称为线性长度。若n=0,则为空表；若n0,ai(0in-1)有且仅有一个前驱元素a(i-1),没有后继元素a(i+1),a0没有前驱元素，a(n-1)没有后继元素线性表的存储结构（顺序存储、链式存储）线性表的顺序存储结构使用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。顺序存储的线性表也称为顺序表。线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。插入、删除操作单链表的插入操作：空表插入/头插入if(head==null) head=new NodeT(x,null); //空表插入else{ NodeTq= new NodeT(x,null); //头插入q.next=head;head=q;}中间插入/尾插入NodeTq= new NodeT(x,null); q.next=p.next;p.next=q;单链表的删除操作：头删除head = head.next;中间/尾删除if (p.next!=null)p.next = p.next.next;双链表的插入操作：q = new DLinkNode(x);q.prev = p.prev;q.next = p;p.prev.next = q;p.prev = q;双链表的删除操作：p.prev.next = p.next;if (p.next!=null) (p.next).prev = p.prev;数组是一种数据结构，数据元素具有相同的数据类型。数组逻辑结构与存储结构的关系：数组采用的是顺序存储结构，即使用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。所以数组的存储结构表现其存储结构。栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。允许操作的一段称为栈顶，不允许操作的一端称为栈底。栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的栈称为空栈。栈的插入和删除只允许在栈顶进行，每次入栈即成为当前栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈也称为后进先出表。逻辑结构存储结构采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链式栈。进栈、出栈操作：链式栈使