数据结构 复习

《数据结构 复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最佳答案这是我们老师要求的重点，即考点。打印出来，背一下就行了，准过！第一章：绪论1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。数据项：是数据元素中有独立含义的、不可分割的最小标识单位。数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素

2、的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性：输入——算法有零个或多个输入数据。输出——算法有一个或多个输出数据，与输入数据有某种特定关系。有穷性——算法必须在执行又穷步之后结束。确定性——算法的每个步骤必须含义明确，无二义性。可行性——算法的每

3、步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。有穷性和可行性是算法最重要的两个特征。2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。2.3：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结高时间效率：算法的执行时间越短，时间效率越高。果。高空间效率：算法执行时占用的存储空间越少，空间效率越高。可读性：算法

4、的可读性有利于人们对算法的理解。2.4：度量算法的时间效率，时间复杂度，（课本39页）。2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：至少有一条初始定义是非递归的，如1！=1.由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n！。第二章：线性表1.1线性表：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作：LinearList=(a0,a1,a2,…an-1)其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长

5、度。若n=0，则LinearList为空表。若n>0，则a0没有前驱元素，an-1没有后继元素，ai（0

6、，元素地址是下标的线性函数。1.3：顺序表的插入和删除操作要移动数据元素。平均移动次数是属数据表长度的一半。（课本第50页）1.4：线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。它有两个域组成：数据域和地址域。通常成为节点。（课本第55页及56页）1.5单链表（课本56页）单链表的遍历：Nodep=head;while(p!=null){访问p节点；p=p.next;}单链表的插入和删除操作非常简便，只要改变节点间的链接关系，不需

7、移动数据元素。单链表的插入操作：1）：空表插入/头插入2)中间插入/尾插入if(head==null)Nodeq=newNode(x);{head=newNode(x);q.next=p.next;}else{p.next=q;Nodeq=newNode(x);中间插入或尾插入都不会改变单表q.next=head;的头指针head。head=q;}单链表的删除操作：头删除：head=head.next;中间/尾删除：if(p.next!=null){p.next=p.next.next;}循环单链表：如

8、果单链表最后一个节点的next链保存单链表的头指针head值，则该单链表成为环形结构，称为循环单链表。（课本67）若rear是单链表的尾指针，则执行（rear.next=head;）语句，使单链表成为一条循环单链表。当head.nex