数据结构知识点整理(清华大学出版社).pdf

第一章第一章 绪论绪论1.数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及其操作的定义和实现问题。2.逻辑结构：不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。通常说的数据结构即此义。分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多)形成一个树形数据结构，城市间据通路(多对多)形成图状结构，此外还有集合结构(除同属一个集合外，无其它关联)，共四类3.数据结构(数据元素及关系/结构)在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构。4.顺序存储结构：关系采取顺序映像表示，即借助元素在存储器中的位置上的”相邻”关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点:需事先分配一足够大空间，且插入删除结点需移动大量数据。链式存储结构：关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。5.度量指标：算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法的效率。6.时间复杂度：频度函数的增长率基本与函数中“关键项”(去掉低次项和常数项)的增长率相同，故可用“关键项”反映算法效率。假设关键项为 f(n)，用 T(n)=O(f(n)表示算法时间增长率与 f(n)增长率同阶。称 O(f(n)为算法的渐近时间复杂度，简称时间复杂度。f(n)的增长率为 f(n+1)/f(n)，如对复杂度为 O(n)的算法其运行时间随问题规模增长率为 1+1/n,复杂度为 O(1)的算法时间增长率为 1。7.按增长率由小至大的顺序排列下列各函数(2/3)n-2100-2n-n1/2-n-n2n-n3/2-2n-n!-nn第二章第二章 线性表线性表1.顺序表：借助元素在存储器中位置上的”相邻”关系表示数据元素间具有的关系，如此存储的线性表称为顺序表。顺序表优点是实现简单方便，可随机访问各元素；缺点是插入或删除元素时会引起大量的数据元素移动(表尾除外)；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常得不到充分利用。2.线性链表:采用链式存储结构的线性表对应一个链表。结点包含数据域和指针域两部分。链表名指向第一个结点(头指针)，尾结点指针域值为 NULL。链表优点是空间利用好,插入删除不移动数据,表头表尾操作快(改进的单链表),位置概念强；缺点是需要顺序访问各元素，位序概念弱。顺序表相关程序：#define LIST_INIT_SIZE 100 /#define LISTINCREMENT 10 /typedef *ElemType;typedef structElemType*elem;/存储空间基址 int length;/int listsize;/SqList；SqList La,Lb,Lc;Status InitList_Sq(SqList&L)/构造空线性表 L L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)if(L.elem=0)exit(OVERFLOW);L.length=0;/初始化表长为 0，“空”表 L.listsize=LIST_INIT_SIZE;/初始化存储容量 return(OK);/InitList_Sqvoid ListDelete(SqList&L,int i,ElemType&e)/在顺序表 L 中删除第个元素，用返回其值/i 的合法值是1，ListLength(L)if(iL.length)return ERROR;/删除位置不合理 ElemType*p=&L.elemi-1,*q=L.elem+L.length-1;e=*p;while(pq)*p=*(p+1);+p;/删除位置后元素左移 -L.length;return Ok;/ListDelete_SqStatus ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表 L 的第 i 个位置前插入元素 e,i 的合法值为1.L.length+1 if(iL.length+1)return ERROR;/插入不合法 if(L.length=L.listsize)/表满，增加存储容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;ElemType*q=&L.elemi-1,*p=&L.elemL.length-1;while(p=q)*(p+1)=*p;-p;/插入位置后的元素右移 *q=e;+L.length;return OK;/ListInsert_S线性表相关程序：typedef *ElemType;typedef struct LNode ElemType data;/数据域 struct LNode*next;/指针域LNode,*LinkList;/默认带头结点,需说明LNode node1;LinkList La；Status GetElem_L(LinkList L,int i,ElemType&e)/L 为带头结点的单链表的头指针。第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR LNode*p=L-next;/p 指向”第 1 个”结点，int j=1;/j 为指向结点的位序 while(p&jnext;+j;if(!p)return ERROR;/第 i 个元素不存在 e=p-data;/取第 i 个元素 return OK；Status ListInsert_L(LinkList&L,int i,ElemType e)/向链表 L 中第 i 个位置插入 eLNode*p=L;int j=0;/*p 始终指向第 j 个结点*/while(p&jnext;+j;/寻找第 i-1 个结点 if(!p)return ERROR;LNode*temp;temp=(LNode*)Malloc(sizeof(LNode);if(!temp)exit(OVERFLOW);temp-data=e;temp-next=p-next;p-next=temp;return(OK);/ListInsert_LStatus ListDelete_L(LinkList&L,int i,ElemType&e)LNode*p=L,*q;int j=0;/*p 始终指向第 j 个结点*/while(p&jnext;+j;/寻找第 i-1 个结点，j 最终为 i-1,除非到表尾 p 空if(!p|!p-next)return ERROR;/第 i 个或更前结点不存在q=p-next;e=q-data;p-next=q-next;free(q);return(OK);/ListDelete_LStatus CreateList_L(LinkList&L,int n)/逆位序输入 n 个元素的值，建立带头结点的单链表L。LNode *p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(int i=1;idata);p-next=L-next;L-next=p;/插入到表头/CreateList_L相关两表的归并void MergeList_Sq(SqList La,SqList Lb,Sqlist&Lc)/归并非降顺序表 La 与 Lb 构成非降顺序表 LcLc.listsize=Lc.length=La.length+Lb.length;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);If(!Lc.elem)exit(OVERFLOW);/存储分配失败ElemType*pa=La.elem,*pb=Lb.elem,*pc=Lc.elem;ElemType*pa_last=La.elem+La.listsize-1;ElemType*pb_last=Lb.elem+La.listsize-1;while(pa=pa_last&pb=pb_last)/归并 if(*pa=*pb)*pc+=*pa+;else *pc+=*pb+;while(papa_last)*pc+=*pa+;/插入 La 剩余段while(pbpb_last)*pc+=*pb+;/插入 Lb 剩余段/MergeList_SqStatus ListMerge_SortedL(SortedSqList La,SortedSqList Lb,SortedSqList&Lc)/将两个有序顺序表 La 与 Lb 归并为有序顺序表 Lcint la_len=ListLength_Sq(La);int lb_len=ListLength_Sq(Lb);int i=1,j=1,k=1;ElemType a,b;InitList_Sq(Lc);while(i=la_len&j=lb_len)/归并 GetElem_Sq(La,i,a);GetElem_Sq(Lb,j,b);if(ab)ListInsert_Sq(Lc,k+,a);+i;else ListInsert_Sq(Lc,k+,b);+j;while(i=la_len)/插入 La 的剩余元素 GetElem_Sq(La,i+,a);ListInsert_Sq(Lc,k+,a);while(j=lb_len)/插入 Lb 的剩余元素 GetElem_Sq(Lb,j+,b);ListInsert_Sq(Lc,k+,b);return OK;/复杂度 O(ListLength(La)+ListLength(Lb),因只在表尾插入)3.注意链表中 next 指针的应用，如插入，删除等操作各个元素的链接。4.顺序表的就地逆置思路：分别设两个指针 p 与 q 指向第一个和最后一个元素，当 pq 时*p 与*q 互换，之后+p,-q。单链表的就地逆置思路：令指针 p 指向首元结点,头结点断开,将 p 所指结点插入到表头后,p 后移,直至 p 为空Status ListInverse_Sq(SqList&L)/顺序表就地逆置 ElemType*p,*q;ElemType e;p=L.elem;q=L.elem+L.length-1;while(pnext;L-next=NULL;while(p!=NULL)q=p-next;/令令 q 指向指向 p 的后继结点，以便以的后继结点，以便以后后 p 后移接下来两句将后移接下来两句将 p 所指向节点插入到头结点后所指向节点插入到头结点后 p-next=L-next;L-next=p;p=q;/q 后移后移 return OK;有序顺序表插入Status ListInsert_SortedSq(SqList&L,ElemType e)/在非降顺序表 L 中插入元素 e,使得 L 中各元素仍然非降。注意插入位置据 e 求得/思路：从最后一个元素开始，只要它比待插入元素大就后移。条件不成立时退出循环，将 e 插入当前位置后即可。顺序表插入操作莫忘表满的处理。只要是顺序表的插入操作就需要判断是否表满，对于链表则无此要求if(L.length=L.listsize)/表满，增加存储容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;/下面从最后一个元素开始，只要大于 e 就后移，最后插入当前位置后 p=L.elem+L.length-1;while(p=L.elem&*pe)*(p+1)=*p;-p;*(p+1)=e;+L.length;/表长加 1 return OK;5.循环链表、双向链表、双向循环链表的特点和基本操作。主要是插入删除的相关指针操作。/-线性表的双向(循环)链表存储结构-typedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;Status ListInsert_DuL(DuLinkList&L,int i,ElemType&e)/在带头结点的双向链表 L 的第 i 个位置插入 e,1i表长+1 DuLNode*p=L;int j=0;while(jnext;+j;if(!p)return ERROR;s=(DuLNode*)malloc(sizeof(DuLNode);if(!s)exit(OVERFLOW);s-data=e;s-prior=p;s-next=p-next;/记记:注意分析指针改变注意分析指针改变 p-next-prior=s;p-next=s;/次序对结果的影响次序对结果的影响 return OK;另外看下多项式的相关课件，老师复习提纲上有写这方面的代码。第三章第三章 栈和队列栈和队列1.栈(Stack)是定义在线性结构上的抽象数据类型，其操作类似线性表操作，但元素的插入、删除和访问都必须在表的一端进行，为形象起见，称允许操作端为栈顶(Top)，另一端为栈底(base)，注意 Top 指向待插入位置。特性:Last In First Out 后进先出/总是访问最近插入的一个/按插入顺序倒着访问。#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef?SElemType;/栈元素类型typedef struct SElemType*base;/栈底指针 SElemType*top;/栈顶指针 int stacksize;/栈容量 SqStackStatus InitStack(SqStack&S)/构造空栈 S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败 S.top=S.base;/空栈 S.stacksize=STACK_INIT_SIZE;return(OK);/InitStack 复杂度”O(1)”Status DestroyStack(SqStack&S)/销毁栈 S free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;/复杂度 O(1)Status ClearStack(SqStack&S)/置 S 为空栈 S.top=S.base;return OK;/复杂度 O(1)Status Push(SqStack&S,SElemType e)/插入 e 为栈顶元素 if(S.top-S.base=S.stacksize)/判断栈满/栈满则应重新分配空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=(S.base+S.stacksize);/使得 S.top 重新指向栈顶,因 realloc S.stacksize+=STACKINCREMENT;*S.top+=e;/top 指向待插入位置 return(OK);/Push,复杂度 O(1)Status Pop(SqStack&S,SElemType&e)/若栈不空则栈顶元素出栈并用 e 带回其值 if(S.top=S.base)return ERROR;/判断栈空判断栈空 e=*(-S.top);/栈顶元素为*(S.top-1)return OK;/复杂度 O(1)Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;else return FALSE;int StackLength(SqStack S)return(S.top-S.base);Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.top-1);/注意 top 指向待插入位置 return OK;栈的遍历一直没用到，可以自己找找课件看。2.队列类似线性表和栈,也是定义在线性结构上的 ADT,与线性表和栈的区别在于，元素的插入和删除分别在表的两端进行。类似日常生活中排队,允许插入的一端为队尾(rear),允许删除端称队头(front)。特性:First In First Out先进先出，如操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟。#define*QElemType typedef struct QNode QElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;/链队列Status InitQueue(LinkQueue&Q)/构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;/莫忘！return OK;/时间复杂度 O(1)Status DestroyQueue(LinkQueue&Q)/销毁队列 Q，此处不同于教材,先清空元素结点，后释放头结点 QueuePtr p=Q.front-next;while(p)/依次释放首元素至最后一个元素Q.front-next=p-next;free(p);p=Q.front-next;free(Q.front);Q.front=NULL;Q.rear=NULL;return OK;/去掉下划线部分为置空操作,复杂度 O(n)Status EnQueue(LinkQueue&Q,QElemType e)/插入元素 e 为 Q 的新的队尾元素 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;/莫忘！Q.rear-next=p;Q.rear=p;return OK;/复杂度 O(1)Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除 Q 的队头元素，用 e 返回其“值”if(Q.front=Q.rear)return ERROR;/空队列 QueuePtr p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;/只 1 个结点时改尾指针 free(p);return OK;/复杂度 O(1)3.循环队列#define MAXQSIZE 100 /最大队列长度typedef struct QElemType *base;/动态分配存储空间 int front;/头指针,队列不空则指向队列头元素 int rear;/尾指针,指向待插入元素位置 SqQueue;Status InitQueue(SqQueue&Q)/构造一个空队列 Q Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败 Q.front=Q.rear=0;return OK;/复杂度 O(1)Status DestroyQueue(SqQueue&Q)/销毁队列 Qfree(Q.base);Q.front=Q.rear=0;return OK;/时间复杂度 O(1)，比链队列快Status ClearQueue(SqQueue&Q)/将队列 Q 置空 Q.front=Q.rear=0;/只要想等即可 return OK;/复杂度 O(1)比链队列快Status EnQueue(SqQueue&Q,QElemType e)/插入元素 e 为 Q 的新的队尾元素,无法插入(已满)则返回 ERROR if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/判断循环队列满的条件判断循环队列满的条件 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;/加便可能越界加便可能越界,故取余故取余 return OK;/时间复杂度 O(1)Status DeQueue(SqQueue&Q,ElemType&e)/队列不空则删除队头元素,用 e 带回其值并返 OK;否则返 ERROR if(Q.rear=Q.front)return ERROR;/判断循环队列空 e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;/加就可能越界,故取余 return OK;/时间复杂度 O(1)int QueueLength(SqQueue Q)/返回队长return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;/减可能为负/时间复杂度 O(1)，比链队列快，可修改链队列定义Status QueueEmpty(SqQueue Q)/判断队列空 if(Q.rear=Q.front)return TRUE;else return FALSE;/O(1)Status GetHead(SqQueue Q,QElemType&e)if(Q.rear=Q.front)return ERROR;e=Q.baseQ.front;return OK;/O(1)若要修改对头元素的值可新设 SetHead(&Q,e)4.证明：若借助栈由输入序列 12n 得到的输出序列为 p1p2pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在 ijk 使 pjpkpi。思路：假设 pjpkpi往证 ijk 不成立。进一步假设 jj,从而 ijn，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子，否则，编号为 2i+1 的结点为其右孩子右孩子结点。4.含 n 个结点的树中，只有度为 k 的分支结点和度为 0 的叶子结点,试求该树含有的叶子结点数提示:n0+nk=n;e=knk=k(n-n0)=n-1故：n0=(nk-n+1)/k5.二叉树是度不大于 2 的有序树(每个结点最多两棵子树,子树有左右之分)。6.满二叉树：设深度为 k,含 2k-1 个结点的二叉树。结点数达最大。7.完全二叉树：设树中含 n 个结点,它们和满二叉树中编号为 1 至 n 的结点位置上一一对应(编号规则为由上到下，从左到右）。相比满二叉树仅少“最后的”若干个，不能少中间的。完全二叉树特点：(1)叶子结点出现在最后2 层或多或 1 层。(2)对于任意结点，若其右分支下的子孙的最大层次为 L,则左分支下的子孙的最大层次为 L 或L+1。8.二叉树顺序存储：将二叉树映射到完全二叉树上，不存在的结点以空标记，之后用地址连续的存储单元(一维数组)依次自上而下、自左而右存储完全二叉树上的各元素.(将一般二叉树以完全二叉树形式存储),最坏情况下k 个结点需 2k-1 个单元。但适合完全二叉树的存储，操作简单方便。9.二叉树链表存储：二叉链表包含内容，左孩子及右孩子的指针。三叉链表多了一个指向双亲结点的指针。typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree T;typedef struct TriTNode struct TriTNode *parent;TElemType data;struct TriTNode *lchild,*rchild;TriTNode,*TriTre10.先(根)序遍历：树非空则访问根结点,后递归地先序遍历其左子树；再递归地先序遍历其右子树；空则无操作。中(根)序遍历：树非空则递归地中序遍历根左子树；后访问根结点,再递归地中序遍历右子树；空则无操作。后(根)序遍历：树非空则递归地后序遍历根右子树；后递归地后序遍历右子树，再访问根结点；空则无操作层次遍历：由上到下,由左到右，不宜递归typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree T;/typedef int TElemType;Status CreateBiTree(BiTree&T)/递归创建二叉树 TElemType e;scanf(%d,&e);if(e=0)T=NULL;else T=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(OVERFLOW);T-data=e;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;/若元素为字符型则输入时不可随意加空格Status DestroyBiTree(BiTree&T)/二叉链表的后序递归销毁 if(!T)return OK;else DestroyBiTree(T-lchild);DestroyBiTree(T-rchild);free(T);T=NULL;/不可丢！return OK;Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)/先序遍历，先序输出函数只要把(*visit)换为输出函数 if(T)if(*visit)(T-data)if(PreOrderTraverse(T-lchild,(*visit)if(PreOrderTraverse(T-rchild,(*visit)return OK return ERROR;else return OK;int TreeDepth(BiTree T)/递归法求树的深度。思路：如果树为空树则深度为0，否则，先递归计算出左子树的深度，再计算出右子树的深度，最后，树的深度为两子树深度的最大值加 1if(T=NULL)d=0;elsed1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchild);if(d1d2)d=d1+1;else d=d2+1;return d;/其余操作类似实现，务必掌握int NodeCount(BiTree T)/递归求结点数，若二叉树为空树则节点数为 0，否则先递归求左子树和右子树的节点数，整棵树的节点数是左右子树节点数之和再加 1 if(T=NULL)return 0;else return1+NodeCount(T-lchild)+NodeCount(T-rchild);int LeafCount(BiTree T)/求叶子数，思路：若二叉树为空树则叶子节点数为0，若二叉树只含有一个节点则叶子数为 1，否则先递归求左子树和右子树的叶节点数，整棵树的节点数是左右子树叶节点数之和。if(T=NULL)return 0;else if(T-lchild=NULL&T-rchild=NULL)return 1;else return LeafCount(T-lchild)+LeafCount(T-rchild);Status ExchangeBiTree(BiTree&T)/二叉树用二叉链表存储,左右互换BiTNode*temp;if(T=NULL)return OK;else temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;ExchangeBiTree(T-lchild);ExchangeBiTree(T-rchild);return OK;11.由遍历序列确定二叉树：先序序列+中序序列：先序序列中第 1 个元素 X 为根，中序序列中唯有遍历完 X 的左子树后方访问 X，故 X 之前的 abc必构成 X 的左子树，X 之后的 def必构成 X 的右子树。对于子树类似处理，第 1 个在先序序列中出现的元素 Y 为该左子树的根，中序序列中 Y 左侧的元素构成 Y 的左子树，右侧构成右子树，依此类推，最终可定。中序序列+后序序列：后序序列中最后一个元素为根，中序序列中该结点前的元素为左子树，后的元素为右子树。对于左/右子树，最后一个在后序序列中出现的元素为子树的根结点，再看中序序列，依此类推。先序输出+后序输出不能确定。如 AB 和 BA。12.二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，若结点有左子树，则其lchild 域指示其左孩子，否则令 lchild 域指示其前驱；若结点有右子树，则其 rchild 域指示其右孩子，否则令rchild 域指示其后继。为了避免混淆，增加两个标志位 LTag 与 RTag：其为 0 是表示域指向孩子，为 1 时表示指向其前驱或者后继。（详细见课本 P132）13.二叉树的线索化：设一棵二叉树有 n 个结点，则有 n-1 条边(指针连线)，而 n 个结点共有 2n 个指针域(Lchild和 Rchild)，显然有 n+1 个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。增设头结点，左标记为 Link，左指针指根结点，右标记为 Thread，右指针指向最后被访问的结点，树空则均指向头结点。又称双向线索链表，先写出遍历序列，后添加头结点，再据序列增加线索即可。用这种结点结构构成的二叉树的存储结构；叫做线索链表；指向结点前驱和后继的指针叫做线索；按照某种次序遍历，加上线索的二叉树称之为线索二叉树。14.树的双亲表示法：以一组连续空间存储结点，各结点附设指示器指示其双亲结点的位置(数据域+双亲下标域)。线索化 双亲表示法15.树的孩子表示法：结点中为其每个孩子附设一个指针。具体定义时各结点指针的个数可取最大，也可根据各自的度不同而不同。前者同构，实现简单；后者需动态开辟指针域，实现复杂但空间省。16.孩子双亲表示法：链式存储与顺序存储结合,将各结点存储在一个数组中,每个数组元素附加一指针域指向结点的孩子形成的链表。若经常进行访问双亲结点的操作则可向数组元素追加双亲位置域。孩子双亲表示法 孩子兄弟表示法17.树的孩子兄弟表示法（二叉链表存储）：链式存储,每个结点包括数据域和两个指针域，左指针指向第一个孩子结点，右指针指向兄弟结点.又称二叉链表存储法。（表示法能画出来应该就可以，各个存储结构应该不会考吧，有兴趣的自己找找书 P135）18.森林的孩子兄弟表示法（二叉链表存储）：单颗树的二叉链表存储结构中根结点的右指针必为空，若要存储多颗树组成的森林，可将后一颗树的根结点看成前一颗树根结点的兄弟，即将后一颗树对应的二叉链表拼接到前一颗树根结点的右指针上，这称为森林的孩子兄弟表示法或二叉链表存储法。19.树、森林与二叉树的转换：以二叉链表存储结构为转换依据，将左右指针所指结点理解为左右孩子结点则得到二叉树；将左指针所指结点理解为孩子,右指针所指结点理解为当前结点的兄弟则得树或森林。20.树采用二叉链表存储，对树进行遍历即对二叉链表进行遍历。先序遍历二叉链表（先根结点后左子树再右子树），对应到树上是“先根，后自左到右递归遍历各子树”，称为树的先根序遍历。对二叉链表进行中序遍历(先左子树中根再右子树)对应到树上是“先从左到右各子树，后根”，称为树的后根序遍历。21.森林采用二叉链表存储(孩子兄弟表示法)，先序遍历二叉链表(先根结点后左子树再右子树)，对应到树上为“从左到右依次先根遍历各颗树”，称为森林的先序遍历。森林采用二叉链表存储(孩子兄弟表示法)，对二叉链表“先左子树中根再右子树”中序遍历，对应到森林为“从左到右依次后根遍历各颗树”，称为森林的中序遍历。22.由树的先根和后根遍历序列确定树：方法一(间接法，借助二叉链表)：树的先根序列对应二叉链表的先序序列、后根序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的树。方法二(直接法，根据先根后根)：先根序列中第 1 个 X 一定是整颗树的根结点，而后根序列中唯有遍历完 X 的所有子树后方访问 X，故 X 必然出现在最后；先根序列中第二个顶点必然是第一个子树的根结点，后根序列中该结点前的结点为此子树中各结点；除去第一颗子树中的结点后，先根序列中第一个结点必为第二颗子树的根结点，而后根序列中此结点前的结点构成第二颗子树，以此类推，最终可确定。23.由森林的先序和中序遍历序列确定森林：方法一(间接法，借助二叉链表):森林的先序序列对应二叉链表的先序序列、中序序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的森林方法二(直接法，根据先根后根)：先序序列中第 1 个 X 一定是第一颗树的根结点,而中序序列中在遍历完第一颗树的最后访问 X,故中序序列中 X 之前的结点构成森林的第一颗树，这些结点在先序和中序序列中的出现次序即为第一颗树的先根序列和后根序列，根据树的确定方法可得第一颗树；除去第一颗树的结点后，先序序列中余下的第一个结点为第二颗树的根结点，中序序列中该结点前结点的构成第二颗树,依次类推，最终可得森林。24.最优二叉树树：设二叉树具有 n 个带权值的叶子结点，从根结点到各个叶子结点的路径长度与对应叶子结点权值的乘积之和叫做二叉树的“带权”路径长度，对于一组带有确定权植的叶子结点，带权路径长度最小的二叉树称为最优二叉树(如Huffman树)。25.如何构造赫夫曼树赫夫曼算法：(1)创建 n 个根结点，权值 w1,w2,.,wn，得森林T1,T2,.,Tn；(2)在森林中选取根结点权值最小的两棵二叉树归并为新二叉树，新二叉树根结点权值为两权值之和；(3)将新二叉树加入森林，同时忽略被归并的两棵二叉树，(4)重复（2）和（3，至森林只有一棵二叉树。该二叉树就是哈夫曼树。26.度为 2 的树与二叉树的区别：前者至少一结点度为 2，且为无序树；后者度主要不超过 2 即可，且为有序树。第七章第七章 图图1.定义：临界点，度，入度，出度等见 P158。2.若无向图 G 中任意两个顶点之间都有路径相通，则称此图为连通图。如能找到一条含全部顶点的路径则说明是连通图。无向图中的极大连通子图称作此图的连通分量。极大指顶点尽量多,顶点连同其关联的边构成连通分量。图本身连通则连通分量唯一，是自身。3.有向图中若任意两顶点间都存在一条有向路径，则称此有向图为强连通图。有向图的极大强连通子图称作它的强连通分量。4.连通图的一个含有全部顶点的子图，如果连通且极小，则它必是一颗树(边数为 n-1)，称该树为原连通图的生成树。破圈法可得生成树。树是含边数最小的连通图(n-1)，图中若边少于 n-1 则必不连通；