《数据结构》各章节复习范围.docVIP

第1章 绪论 1.数据结构的定义 数据－＞数据元素 －＞数据项 数据结构是指数据以及相互之间的联系。包括： （1）数据的逻辑结构。 （2）数据的存储结构（物理结构）。 （3）施加在该数据上的运算。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。 数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。 逻辑结构主要有两大类： （1）线性结构 （2）非线性结构： 1）树形结构 2）图形结构 存储结构分为如下四种： （1）顺序存储方法 （2）链式存储方法 （3）索引存储方法 （4）散列存储方法 2.抽象数据类型 抽象数据类型（Abstract Data Type简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。 3.什么是算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列 。 算法的五个重要的特性 ： （1）有穷性 （2）确定性 （3）可行性 （4）有输入 （5）有输出 4.算法分析 (1)算法的时间复杂度：是指其基本运算在算法中重复执行的次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作： T(n)=O(f(n)) 记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。 (2)算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度 。 对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。 第2章 线性表 1.线性表的定义 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。 1.线性表的顺序存储结构—顺序表 typedef struct { ElemType elem[MaxSize]; /*存放顺序表元素*/ int length; /*存放顺序表的长度*/ } SqList; 顺序表基本运算的实现 插入数据元素算法：元素移动的次数不仅与表长n有关 ；插入一个元素时所需移动元素的平均次数 n／2。平均时间复杂度为O(n)。 删除数据元素算法:元素移动的次数也与表长n有关 。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。 【例2.1】 设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。 void Insert(SqList A,ElemType x) { int i=0,j; while (iA.length AS.elem[i]x) i++; for (j=A.length-1;j=i;j--) A.elem[j+1]=A.elem[j]; A.elem[i]=x; A.length++; } 2.线性表的链式存储结构—链表 定义单链表结点类型: typedef struct LNode { ElemType data; struct LNode *next; /*指向后继结点*/ } LinkList; 定义双链表结点类型: typedef struct DNode { ElemType data; struct DNode *prior; /*指向前驱结点*/ struct DNode *next; /*指向后继结点*/ } DLinkList; （1）单链表基本运算的实现 重点：头插法建表和尾插法建表算法，它是很多算法设计的基础。 【例2.1】 设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点的hc单链表存放，编写一个就地算法，将其拆分为两个线性表，使得： A={a1,a2,…,an}，C={b1,b2,…,bn} void fun(LinkList *hc, LinkList *ha,LinkList *hb) { LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的头结点利用hc的头结点*/ ra=ha; /*ra始终指向h