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

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

1、第1章绪论1.数据结构的定义数据－＞数据元素－＞数据项数据结构是指数据以及相互之间的联系。包括：（1）数据的逻辑结构。（2）数据的存储结构（物理结构）。（3）施加在该数据上的运算。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。逻辑结构主要有两大类：（1）线性结构（2）非线性结构：1）树形结构2）图形结构存储结构分为如下四种：（1）顺序存储方法（2）链式存储方

2、法（3）索引存储方法（4）散列存储方法2.抽象数据类型抽象数据类型（AbstractDataType简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。3.什么是算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的五个重要的特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出4.算法分析(1)算法的时间复杂度：是指其基本运算在算法中重复执行的次数。算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“

3、O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。(2)算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。第2章线性表1.线性表的定义线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。1.线性表的顺序存储结构—顺序表typedefstruct{ElemTypeelem[MaxSize];/*存放顺序表元素*/intlength;/*存放顺序表的长度*

4、/}SqList;顺序表基本运算的实现插入数据元素算法：元素移动的次数不仅与表长n有关；插入一个元素时所需移动元素的平均次数n／2。平均时间复杂度为O(n)。删除数据元素算法:元素移动的次数也与表长n有关。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。【例2.1】设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。voidInsert(SqList&A,ElemTypex){inti=0,j;while(i

5、=A.length-1;j>=i;j--)A.elem[j+1]=A.elem[j];A.elem[i]=x;A.length++;}2.线性表的链式存储结构—链表定义单链表结点类型:typedefstructLNode{ElemTypedata;structLNode*next;/*指向后继结点*/}LinkList;定义双链表结点类型:typedefstructDNode{ElemTypedata;structDNode*prior;/*指向前驱结点*/structDNode*next;/*指向后继结点*/}DLinkList;（1）单链表基本运算的实现重点：头插法

6、建表和尾插法建表算法，它是很多算法设计的基础。【例2.1】设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点的hc单链表存放，编写一个就地算法，将其拆分为两个线性表，使得：A={a1,a2,…,an}，C={b1,b2,…,bn}voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc;/*ha的头结点利用hc的头结点*/ra=ha;/*ra始终指向ha的末尾结点*/hb=(LinkList*)malloc(sizeof(LinkList));/

7、*创建hb头结点*/rb=hb;/*rb始终指向hb的末尾结点*/while(p!=NULL){ra->next=p;ra=p;/*将*p链到ha单链表未尾*/p=p->next;if(p!=NULL){rb->next=p;rb=p;/*将*p链到hb单链表未尾*/p=p->next;}}ra=rb=NULL;}/*两个尾结点的next域置空*/整个算法实际上是采用尾插法建表。（2）双链表基本运算的实现重点：插入和删除结点的算法。（3）循环链表基本运算的实现重点：判断最后一个结点。第3章栈和队列3.1栈1.栈的定义栈是一种只能在一端进行