数据结构复习提纲（zxy_aaron）
第一章：1. 数据结构基本术语。
数据结构概念、组成，记录、数据项等。
数据：利用文字符号，数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
数据元素：表示一个事物的一组数据。
数据项：具有独立含义的最小标识单位。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据类型：一个值的集合和定义在这个值集上的一组操作的总称。
原子类型：不可在分的基本数据类型。
结构类型：由若干个类型组合而成，可以再分解。
抽象数据类型：指一个数学模型及该模型上定义的一组操作的集合。
数据结构：指相互之间存在一种或多种特定关系的数据元素的集合，主要研究的是数据的逻辑结构，物理结构及数据的运算。
2. 数据的逻辑结构和物理结构。
四种逻辑结构：集合结构：数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”。
线性结构：数据元素之间是一对一的关系。
树形结构：数据元素之间存在一种一对多的层次关系。
图形结构：数据元素是多对多的关系。
四种物理结构：顺序存储结构：数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构：数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
索引存储结构：
散列存储结构：
3. 算法的描述与分析。
有穷性，确定性，可行性，输入，输出。
第二章：4. 线性表的顺序存储的优缺点，基本操作的实现。
优点：按位置读取元素，随机读取，缺点：插入删除十分复杂（i的位置插入，移动元素n-i-1）
基本操作：只要掌握插入、删除、查找（写关键性**）
插入：int listinsert(sqlist *l,int i,datatype e)
l->data[i-1]=e
l->length++;
return ok;
删除：int listdelete(sqlist *l,int i,datatype *e)
l->length--;
return ok;
查找：int locateelem(sqlist *l, elemtype e)
int i=0;
while (ilength &&l->data[i]!=e) i++;
if (i>=l->length)
return 0;
elsereturn i+1;
5. 线性表的链式存储优缺点，基本操作的实现。
优点：插入删除方便，只要修改相应指针。
缺点：占用空间大，访问元素遍历复杂，不能随机访问，只能顺序访问。
基本操作：插入、删除、查找。
插入：int listinsert(linklist &l,int i,datatype e)
linklist p,s;
s = linklist)malloc(sizeof(node生成新结点。
s->data = e;
s->next = p->next;
p->next = s
return ok;
删除。int listdelete(linklist &l,int i,datatype *e)
int j;
linklist p,q
q = p->next;
p->next = q->next
*e = q->data
free(q
return ok;
查找。int locateelem(linklist l,datatype e)
int i=0;
linklist p=l->next;
while(p)
return ok;
第。三、四、五章：
6. 队列基本操作的实现（循环队列、链队）
循环队列：为了充分利用存储空间，把它变为收尾相连的环，最多maxsize-1个元素。
基本操作：是满还是空、怎么入队、出队，元素个数怎么求（理解）
顺序队列：空：
入队： =x;
出队： x=
链队：单链表的头是对头：front，他的尾指：rear
入队、出队分别是怎么做的，关键**。
入队：s->data=e;
s->next=null;
q->rear->next=s;
q->rear=s;
出队：p=q->front->next;
e=p->data;
q->front->next=p->next;
free(p);
7. 栈的基本操作的实现（顺序栈，链栈）
栈：顺序栈（数组实现、top变量栈顶下标）、链栈，它们入栈、出栈是怎样实现的。
顺序栈：入栈： s->top++;s->data[s->top]=e;
出栈：e=s->data[s->top]; s->top--;
链栈：入栈：int push(linkstack *s, int e)
linkstackptr s=(linkstackptr)malloc(sizeof(stacknode));
s->data=e;
s->next=s->top;
s->top=s
s->count++;
return ok;
出栈：int pop(linkstack *s, int *e)
linkstackptr p;
if(stackempty(*s))
return error;
*e=s->top->data;
p=s->top
s->top=s->top->next
free(p
s->count--;
return ok;
8. 二维数组元素的存储位置。
二维数组求中间元素地址（行优先存储），知道int a[0][0]—a[10][10],起始地址100,求a[2][3]存储位置100+（10*2+3）*4
第六章：9. 树的基本定义。
树的结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：b 结点是a 结点的孩子，则a结点是b 结点的双亲；
兄弟结点：同一双亲的孩子结点；
堂兄结点：同一层上结点；
祖先结点： 从根到该结点的所经分支上的所有结点。
子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙。
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层。
结点的度：结点子树的个数。
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；
森林；互不相交的树集合；森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。
10. 二叉树的特性。
五个特性：i层最多结点2i-1个；深度h至多含2h-1个结点；n0个叶子、n2个度为2的结点，则n0= n2+1；n个结点的完全二叉树深度为[log2n]+1（向下取整），完全二叉树编号关系：i=1,该结点是根结点。
否则(i>1),其双亲结点序号为i/2。
如果2i≤n,其左子结点的序号为2i。（如节点）
如果 2i>n,则i结点，无左子结点，显然也没右节点。
如果2i+1≤n，则序号为i的结点的右孩子结点的序号为 2i+1。
如果2i+1>n，则序号为i的结点无右孩子结点。(具体详见p123-p125)
11. 满二叉树、完全二叉树。
p12312. 二叉树的遍历及特点。
前序、中序、后序，遍历后的特点左中右等等。
先序遍历（dlr）
1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树；
中序遍历（dlr）
1）先序遍历左子树；
（2）访问根结点；
（3）先序遍历右子树；
后序遍历（dlr）
（1）先序遍历左子树；
（2）先序遍历右子树；
3）访问根结点；
根据前序、中序或中序、后序还原二叉树。
13. 哈夫曼树的构造过程及特点。
哈夫曼树构造，挑权值最小的然后构造一个根结点。
带权路径长度=叶子结点权值*路径（累加）
特点：带权路径长度最小，权值小的是叶子结点；两个结点构造一个根，所以有孩子必有两个孩子，没权值为1的结点即单分支结点（不存在度为1的结点）
14. 树、森林与二叉树的相互转换及特点。
树——>二叉树，左孩子右兄弟特点没有右子树。给一个二叉树还原为树。
树的遍历先根、后根遍历和二叉树先、中、后根遍历的对应关系。
森林——>二叉树：先把每棵树都转化成二叉树，然后把各树的根看成是兄弟关系（左右子树都有）
15. 二叉树递归算法的理解。
递归公式+终结的条件。
p129-p130二叉树遍历递归。
第七章：最小路径、关键路径不考。
16. 图的基本术语。
度、连通图/分量、强连通图/分量、生成树、最小生成树（p167-p169）
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...