“数据结构”读书笔记

1、“数据结构”读书笔记示例：第2章线性表学习线索：逻辑结构-基本运算定义-存储结构-基本运算实现(复杂度分析-应用实例)1. 逻辑结构：是由n(n>0)个数据元素组成的有限序列。2. 基本运算定义：(P. 16)(1) lnit_List(L)，线性表初始化;(2) Length _ List (L)，求线性表的长度;(3) Get_ List (L, i)，取表元;(4) Locate_ List (L, x),按值查找；(5) lnsert_ List (L, x, i);插入操作;(6) Delete_ List (L, i)，删除操作。3. 存储结构：(1) 顺序表：把线性表的结点

2、按逻辑次序存放在一组地址连续的存储 单元里。顺序存储的结构体定义：typedef struct datatype dataMAXSIZE; /* 一维数组 子域 */ int last;/*表长度子域*/ SeqList;/*顺序存储的结构体类型 */4-1.顺序表的基本运算的实现 (算法及其复杂度分析、应用实例：顺序表 的划分、合并、比较大小)(2) 单链表：只有一个链域的链表称单链表。结点结构：Data (节点值)Next (后继结点地址)其中data是数据域，next是指针域链式存储的结构体定义：typedef struct lnode datatype data;/* 数据子域*/st

3、ruct lnode *next; /* 指针子域*/ LNode, *LinkList; /*链式存储的结点结构类型 */4-2.单链表的基本运算的实现 (算法及其复杂度分析、应用实例：链表逆置、归并)单链表的发展：循环链表、双向链表顺序表和链表的比较1)基于空间：2)基于时间：“数据结构”读书笔记(线性结构部分)第1章绪论1. 数据：信息的载体，能被计算机识别、存储和加工处理。2. 数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单 位。3. 数据结构：数据之间的相互关系，即数据的组织形式。它包括：(1) 数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，

4、独立于计算机；(2) 数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。(3) 数据的运算(基本操作)，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的 运算：检索/插入/删除/更新/排序。4. 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用 计算机语言的实现。5. 数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6. 抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了 信息隐藏。7. 抽象数据类型 ADT :是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作 对象(类

5、的实例)解决问题。8. 数据的逻辑结构，简称为数据结构，有：(1) 线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接 前趋和后继。(2) 非线性结构，一个结点可能有多个直接前趋和后继。9. 数据的存储结构有：(1) 顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。(2) 链接存储，结点间的逻辑关系由附加指针字段表示。(3) 索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。(4) 散列存储，按结点的关键字直接计算出存储地址。10. 评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间(辅助存 储空间)；易于理解、编码、调

6、试。11. 算法的时间复杂度 T(n):是该算法的时间耗费，是求解问题规模n的函数。记为 0(n)。时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)、线性阶0(n)、线性对数阶O(nlog2n)、平方阶 O(nA2)、立方阶0(n人3)、k次方阶0(nAk)、指数阶 0(2An)。12. 算法的空间复杂度 S(n)：是该算法的空间耗费，是求解问题规模n的函数。13. 算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。14. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。第2章线性表1. 线性表：是由n(n >个数据元素组成的

7、有限序列。2. 线性表的基本运算有：(1) InitList(L)，构造空表，即表的初始化;(2) ListLength(L)，求表的结点个数，即表长；(3) GetNode(L , i)，取表中第 i 个结点，要求 K i < ListLength(L)(4) LocateNode(L , x)查找L中值为x的结点并返回结点在 L中的位置，有多个x则返回首个， 没有则返回特殊值表示查找失败。(5) InsertList(L , x, i)在表的第i个位置插入值为 x的新结点，要求 K i < ListLength(L)+1(6) DeleteList(L , i)删除表的第i个位

8、置的结点，要求 K i < ListLength(L)3. 顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。4. 顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C ； 1 < i < n5顺序表上的基本运算(1)插入 void insertlist(seqlist *L， datatype x, int i)int j ；if(i<1|i>L->le ngth+1)error( “position error” )；if(L->le ngth>=listsize)error( “ overflow ”

9、)；for(j=L->length-1 ； j>=i-1 ； j-)L->dataj+1=L->dataj；结点后移L->datai-1=x ；L->le ngth+ ；在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。(2)删除void delete (seqlist *L， int i)int j ；if(i<1|i>L->le ngth)error( “position error” )；for(j=i ； j<=L->length_1 ； j+)L->dataj-1=L->dataj；结点前

10、移L->length-；在顺序表上删除要移动表的(n+1)/2结点，算法的平均时间复杂度为O(n)。6.单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，结点结构如下：Data (节点值)Next (后继结点地址)其中data是数据域，next是指针域(1) 建立单链表。时间复杂度为O(n)。加头结点的优点：1)链表第一个位置的操作无需特殊处理；2)将空表和非空表的处理统(2) 查找运算。时间复杂度为O(n)。1) 按序号查找。List node * get no de(li nklist head， int i)int j ；list node *p ；p=

11、head；j=0 ；while(p-> next&&j<i)p=p->next ；指针下移j+ ；if(i=j)return p；elsereturn NULL ；2) 按值查找。List node * locate no de(l in klist head , datatype key) list node *p=head->n ext ；while(p&&p->data!=key)p=p->next;return p;(3 )插入运算。时间复杂度为0(n)。Void insertlist(linklist head ，

12、datatype x, int i)list node *p ；p=getnode(head，i-1)；if(p=NULL)；error( “position error” )；s=(list node *)malloc(sizeof(list no de)；s->data=x ；s->next=p->next ；p_>next=s ；(4) 删除运算。时间复杂度为 O( n)。Void deletelist(linklist head ， int i)list node *p ， *r ；p=getnode(head ，i-1)；if(p=NULL|p-> ne

13、xt=NULL)error( “position error” )；r=p->next ；p->next=r->next ；free?；7. 循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的 处理灵活方便。8. 空循环链表仅由一个自成循环的头结点表示。9很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1)，查找尾结点的时间是O(n);用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。10. 在结点中增加一个指针域，

14、prior|data|next。形成的链表中有两条不同方向的链称为双链表。1) 双链表的前插操作。时间复杂度为O(1)。Void dinsertbefore(dlistnode *p ， datatype x)dlist node *s=malloc(sizeof(dlist no de)；s->data=x ；s->prior=p->prior ；s_>next=p ；p->prior->next=s ；p->prior=s ;2) 双链表的删除操作。时间复杂度为0(1)。Void ddeletenode(dlistnode *p) p->pr

15、ior->next=p->next ； p->next->prior=p->prior ； free(p)；11. 顺序表和链表的比较1 )基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表 的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结 构。2) 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除 操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表 的首尾时采用尾指针表示的单循环链表。12. 存储密度=(结点数据本身所占的存储量

16、)/ (整个结点结构所占的存储总量)存储密度：顺序表 =1，链表<1。第3章栈和队列1. 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表(LIFO表)。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。2. 栈的基本运算有：1) initstack(s)，构造一个空栈；2) stackempty(s)，判栈空；3) stackfull(s)，判栈满；4) push(s, x)，进栈；5) pop (s)，退栈；6) stacktop(s)，取栈顶元素。3顺序栈：栈的顺序存储结构称顺序栈。4. 当栈满时，做进栈运算必定产生空间溢出，称"上溢”。当栈空时，做退栈

17、运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。5. 在顺序栈上的基本运算：1) 置空栈。Void initstack(seqstack *s)s->top=-1 ；2) 判栈空。int stackempty(seqstack *s)return s->top=-1 ；3) 判栈满。int stackfull(seqstack *s) return s->top=stacksize-1 ;4) 进栈。Void push(seqstack *s, datatype x)if(stackfull(s)error( “ stack over

18、flow ” );s->data+s->top=x ；5) 退栈。Datatype pop(seqstack *s)if(stackempty(s)error( “ stack underflow ” );return S->datas->top-;6) 取栈顶元素。Dtatatype stacktop(seqstack *s)if(stackempty(s)error( “ stack underflow ” );return S->datas->top;6. 链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。7. 链栈上的基本运算：1) 建栈。Voi

19、d initstack(linkstack *s)s->top=NULL ；2) 判栈空。Int stackempty (linkstack *s)return s->top=NULL ；3) 进栈。Void push(linkstack *s， datatype x)stack node *p=(stack node *)malloc(sizeof(stack no de)； p->data=x ；p_>next=s->top ；s->top=p ；4) 退栈。Datatype pop(linksatck *s)datatype x；stack node

20、*p=s->top ；if(stackempty(s)error( “ stack underflow ” );x=p->data;s->top=p->next;free(p);return x;5) 取栈顶元素。Datatype stacktop(linkstack *s)if(stackempty(s)error( “ stack is empty ” );return s->top->data;8. 队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称 为先进先出线性表，FIFO表。9. 队列的基本运算：1) initque

21、ue(q)，置空队；2) queueempty(q)，判队空；3) queuefull(q)，判队满；4) enqueue(q, x)，入队；5) dequeue(q)，出队；6) queuefront(q)，返回队头元素。10. 顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。11. 顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素 的空间无法利用，队尾指针超过向量空间的上界而不能入队。12. 为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queues

22、ize13. 循环队列的边界条件处理：由于无法用front=rear来判断队列的“空”和“满”。解决的方法有：1)另设一个布尔变量以区别队列的空和满；2) 少用一个元素，在入队前测试rear在循环意义下加1是否等于front ；3) 使用一个记数器记录元素总数。14. 循环队列的基本运算：1 )置队空。Void initqueue(cirqueue *q)q_>front=q->rear=0 ；q->count=0 ；2 )判队空。Int queueempty(cirqueue *q)return q->count=0 ；3 )判队满。Int queuefull(cir

23、queue *q)return q->count=queuesize ;4) 入队。Void enqueue(cirqueue *q , datatype x)if(queuefull(q)error( "queue overfolw ” );q->co un t+ ;q->dataq->rear=x ;q->rear=(q->rear+1)%queuesize ;5) 出队。Datatype dequeue(cirqueue *q)datatype temp；if(queueempty(q)error( " queue underflo

24、w ” );temp=q->dataq->front;q->count-;q->front=(q->front+1)%queuesize ;return temp;6) 取队头元素。Datatype queuefront(cirqueue *q)if(queueempty(q)error( " queue is empty ” );return q->dataq->front;15. 链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。16. 链队列的基本运算：1)建空队。Void initqueue(linkqueu

25、e *q)q_>fron t=q->rear=NULL ；2) 判队空。Int queueempty(linkqueue *q)return q->front=NULL&&q->rear=NULL；3) 入队。Void enqueue(linkqueue *q， datatype x)queue node *p=(queue node *)malloc(sizeof(queue no de)；p->data=x ；p->next=NULL ；if(queueempty(q)q_front=q->rear=p ；elseq->rea

26、r->next=p ;q->rear=p;4) 出队。Datatype dequeue(linkqueue *q)datatype x；queuenode *p ;if(queueempty(q)error( "queue is underflow ” );p=q->front ;x=p->data;q_>front=p->next ;if(q->rear=p) q->rear=NULL ;free(p);return x;5) 取队头元素。Datatype queuefront(linkqueue *q)if(queueempty(q

27、)error( " queue is empty ” );return q->front->data ;第4章字符串及线性结构的扩展字符串1. 串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；2. 空串：长度为零的串称空串；空白串：由一个或多个空格组成的串称空白串；子串：串中任意个连续字符组成的子序列称该串的子串；主串：包含子串的串称主串;子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；3. 空串是任意串的子串；任意串是自身的子串；串常量在程序中只能引用但不能改变其值；串变量取值可以改变；4. 串的基本运算1) int strlen(char

28、*s);求串长。2) char *strcpy(char * to， char * from);串复制。3) char *strcat(char * to， char * from);串联接。4) int strcmp(char *s1， char *s2);串比较。5) char *strchr(char *s， char c); 字符定位。5. 串的存储结构：(1) 串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：1) 静态存储分配的顺序串：直接用定长的字符数组定义，以“0”表示串值终结。#define maxstrsize 256typedef char seqstringm

29、axstrsize;seqstri ng s;不设终结符，用串长表示。Typedef structChar chmaxstrsize;Int length;seqstring ;以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。2) 动态存储分配的顺序串：简单定义：typedef char * string;复杂定义：typedef structchar *ch；int length ；hstring ；(2) 串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedef struct nodechar data；struct node *next ；l

30、inkstrnode ；typedef linkstrnode *linkstring ；linkstring s；将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义：#defi ne no desize 80typedef struct nodechar data no desize；struct node * next ；linkstrnode ；6. 串运算的实现(1) 顺序串上的子串定位运算。1) 子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。2) 朴素的串匹配算法。时间复杂度为O(nA2)。比较的字符总次数为(n-m+1)m。Int naiv

31、estrmatch(seqstring t，seqstring p)int i，j，k ；int m=p.length ；int n=t.length ；for(i=0 ； i<=n-m ； i+)j=0 ； k=i ；while(j< m&&t.chk=p.chj)j+ ； k+ ；if (j=m) return i；return -；(2) 链串上的子串定位运算。时间复杂度为O(nA2)。比较的字符总次数为(n-m+1) m。Linkstrnode * lilnkstrmatch(linkstring T, linkstring P)linkstrnode *s

32、hift , *t, *p ；shift=T ;t=shift; p=P;while(t&&p)if(t_>data=p_>data)t=t->next ;p=p->next;elseshift=shift->next ;t=shift ；p=P；if(p=NULL)return shift;elsereturn NULL ;数组和广义表1. 多维数组：一般用顺序存储的方式表示数组。2. 常用方式有：1)行优先顺序，将数组元素按行向量排列；2)列优先顺序，将数组元素按列向量排列。3. 计算地址的函数：LOC(Aij)=LOC(Ac1c2)+(i-c

33、1)*(d2-c2+1)+j-c2)*d4矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。(1) 对称矩阵：在一个 n阶的方阵A中，元素满足 Aij=Aji 0<=i，j<=n-1 ;称为对称矩阵。元素的总数为：n(n+1)/2 ；设：I=i或j中大的一个数；J=i或j中小的一个数；则：k=l*(l+1)/2+J ；地址计算：LOC(Aij)=LOC(sak)=LOC(sa0)+k*d= LOC(sa0)+ (I*(I+1)/2+J)*d(2) 三角矩阵：以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c;下三角的主对角线上元素均为常

34、数c。元素总数为：(n(n+1)/2)+1 ；以行优先顺序存放的Aij与SAk的关系：上三角阵：k=i*(2 n-i+1)/2+j-i；下三角阵：k=i*(i+1)/2+j ；(3) 对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为零。|i-j|>(k-1)/2以行优先顺序存放的Aij与SAk的关系：k=2i+j ； 5稀疏矩阵：当矩阵 A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。对其压缩的方法有顺序存储和链式存储。(1)三元组表：将表示稀疏矩阵的非零元素的三元组(行号、列号、值)按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存

35、储结构称为三元组表。其类型定义：#define maxsize 10000typedef int datatype ；typedef structint i ， j ；datatype v；trituplenode ;typedef structtrituple node datamaxsize;int m, n, t;tritupletable ;（2）带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三 元组表中的起始位置。类型定义：#define maxrow 100typedef structtritulpenode datamaxsize；int rowta

36、bmaxrow；int m， n,t；rtritulpetable ；6. 广义表：是线性表的推广，广义表是n个元素的有限序列，元素可以是原子或一个广义表,记为LS。7. 若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。8. 表的深度是指表展开后所含括号的层数。9. 把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；10. 允许结点共享的表称为再入表；11. 允许递归的表称为递归表；12. 相互关系：线性表纯表再入表递归表；13. 广义表的特殊运算：1）取表头head（LS） ； 2）取表尾tail（LS）。“数据结构”读书笔记（树、图、查找与排序）借

37、此抛砖引玉，希望同学们自己做得更好！第5章树结构1. 树：是n （n>0）个结点的有限集 T。T为空时称空树，否则满足：1）有且仅有一个特定的称为根的结点；2）其余结点可分为 m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。2. 树的表示方法：1）树形表示法；2）嵌套集合表示法；3 ）凹入表表示法；4）广义表表示法;3. 一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数；4. 度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点；5. 根结点称开始结点，根结点外的分支结点称内部结点；6. 树中某结点的子树的根称为该结点的孩子；该结点称为孩子的双

38、亲；7. 树中存在一个结点序列K1 , K2 ,Kn,使Ki为Ki+1的双亲，则称该结点序列为K1到Kn的路径或道路；8. 树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙；9. 结点的层数从根算起，若根的层数为1,则其余结点层数是其双亲结点层数加1;双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；10. 树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；11. 森林是m棵互不相交的树的集合。12. 二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称 为该根的左子树和右子树的二叉树组成。13. 二叉树不是树的特殊情况，

39、这是两种不同的数据结构；它与无序树和度为 2的有序树不同。14. 二叉树的性质：1） 二叉树第i层上的结点数最多为2A（ i-1）；2）深度为k的二叉树至多有2Ak-1个结点；3） 在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1 ；15. 满二叉树是一棵深度为k的且有2Ak-1个结点的二叉树；16. 完全二叉树是至多在最下两层上结点的度数可以小于2,并且最下层的结点集中在该层最左的位置的二叉树；17. 具有N个结点的完全二叉树的深度为log2N取整加1 ；18. 二叉树的存储结构（1）顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然

40、后依次存储在一个向量b0n中，b1n存放结点，b0存放结点总数。各个结点编号间的关系：1） i=1是根结点；i>1则双亲结点是i/2取整；2） 左孩子是2i,右孩子是2i+1 ;（要小于n）3）i> （n/2取整）的结点是叶子；4） 奇数没有右兄弟，左兄弟是i-1 ；5） 偶数没有左兄弟，右兄弟是i+1 ；(2) 链式存储结构结点的结构为：lchild|data|rchild ;相应的类型说明: typedef char data；typedef struct nodedatatype data；struct node *lchild , *rchild ；bintnode ；ty

41、pedef bintnode *bintree ；19. 在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表。20. 二叉链表由根指针唯一确定。在n个结点的二叉链表中有 2n个指针域，其中n+1个为空。21. 二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为0 （n）。22. 线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。23. 线索链表结点结构：lchild|ltag|data|rtag|rchi

42、ld ; ltag=O , Ichild 是指向左孩子的指针；ltag=1， Ichild是指向前趋的线索；rtag=0， rchild是指向右孩子的指针；rtag=1，rchild是指向后继的线索；24. 查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为0（ h）。线索对查找前序前趋和后序后继帮助不大。25. 遍历线索二叉树。时间复杂度为0 （n）。26. 树、森林与二叉树的转换（1）树、森林与二叉树的转换1）树与二叉树的转换：1所有兄弟间连线；2保留与长子的连线，去除其它连线。该二 叉树的根结点的右子树必为空。2 ）森林与二叉树的转换：1将所有树转换成二叉树；2将所有树根连线。（2

43、）二叉树与树、森林的转换。是以上的逆过程。27. 树的存储结构：使用链表结构（1） 双亲链表表示法：为每个结点设置一个pare nt指针，就可唯一表示任何一棵树。Dataware nt（2） 孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩 子结点序号。Data|firstchild 。（3） 孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。Leftmostchild|data|rightsibling28. 树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历 对应二叉树。29. 最优二叉树（哈夫曼树）：树的路径长度

44、是从树根到每一结点的路径长度之和。将树中的 结点赋予实数称为结点的权。30. 结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所 有叶子的带权路径长度之和。31. 带权路径长度最小的二叉树称最优二叉树（哈夫曼树）。32. 具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。33. 哈夫曼编码34. 对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称 前缀码。35. 符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；36. 使文件总长或平均码长最小的前缀码称最优前缀码37. 利用哈夫曼树求最

45、优前缀码，左为 0，右为1。编码平均码长最小；没有叶子是其它叶子的 祖先，不可能出现重复前缀。第6章图结构1. 图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；2. G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。3. 顶点n与边数e的关系：无向图的边数 e介于0n (n-1) /2之间，有n (n-1) 12条边的称无向完全图；有向图的边数e介于0n (n-1)之间，有n (n-1)条边的称有向完全图；4. 无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边

46、数。5图G (V , E)，如V '是V的子集，E'是E的子集，且E'中关联的顶点均在 V '中，贝U G ' (V' , E')是G的子图。6. 在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；7. 在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8. 在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9. 将图中每条边赋上权，则称带权图为网络。10. 图的存储结构：(1) 邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。 无向图是对称矩阵；有向图行是出

47、度，列是入度。(2) 邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表， adjvex|next,如要保存顶点信息加入 data；对所有顶点设立头结点， vertexfirstedge，并顺序存储在 一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。11. 邻接矩阵表示法与邻接表表示法的比较：1) 邻接矩阵是唯一的，邻接表不唯一；2) 存储稀疏图用邻接表，存储稠密图用邻接矩阵；3) 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4) 判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O (n);5) 求边数e,邻接矩阵耗时为 O

48、5人2),与e无关，邻接表的耗时为 O (e+n);12. 图的遍历：(1) 图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。对邻接表表示的图深度遍历称DFS，时间复杂度为 O (n+e)；对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O ( nA2 )；(2) 图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。对邻接表表示的图广度遍历称BFS，时间复杂度为 O (n+e)；对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O 5人2 )；13. 将没有回路的连通图定义为树称自由树。14. 生成树：连通图 G的一个子图若是一棵包含G中所

49、有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。15. 最小生成树：将权最小的生成树称最小生成树。(是无向图的算法)(1) 普里姆算法：1) 确定顶点 S、初始化候选边集 T0n-2 ； formvex|tovex|length2) 选权值最小的T与第1条记录交换；3) 从T1中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4) 选权值最小的T与第2条记录交换；5) 从T2中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6) 重复n-1次。学习好资料欢迎下载初始化时间是 0 （

50、n）,选轻边的循环执行 n-1-k次，调整轻边的循环执行n-2-k ;算法的时间复杂度为0 5人2），适合于稠密图。（2）克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2）取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3）重复e次。对边的排序时间是 0 （elog2e）;初始化时间为 O （n）;执行时间是 O （Iog2e）;算法的时间 复杂度为0（ elog2e），适合于稀疏图。16. 路径的开始顶点称源点，路径的最后一个顶点称终点；17. 单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；18. 单目标最短路径问题：将

51、图中每条边反向，转换为单源最短路径问题；19. 单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；20. 所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；21. 迪杰斯特拉算法：1）初始化顶点集 S，路径权集D，前趋集P；2）设置Ss为真，Ds为0；3）选取D最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复3） n-1次。算法的时间复杂度为 0（ nA2 ）。22. 拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足 弧尾在弧头之前。这样的线性序列称拓扑序列。（1） 无前趋的顶点优先：总是选择入度为0的结点输出并删

52、除该顶点的所有边。设置各个顶点入度时间是 0 （n+e），设置栈或队列的时间是 0 （n），算法时间复杂度为 0 （n+e）。（2） 无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。设置各个顶点出度时间是 0 （n+e），设置栈或队列的时间是 0（n ），算法时间复杂度为 0 （n+e）。 求得的是逆拓扑序列。第7章查找查找是以线性结构和非线性结构为基础，重点掌握查找的思想和方法。1. 查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静 态查找表。2. 衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平 均查找长度A

53、SL）.3. 线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。（1）顺序查找的算法基本思想：是从表的一端开始顺序扫描线性表，依次将扫描到的结点关键 字与给定值K比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。1）顺序查找方法可用链式存储结构和顺序存储结构实现。2）在顺序存储结构的顺序查找算法中所设的哨兵是为了简化循环的边界条件而引入的附加结点（元素），其作用是使for循环中省去判定防止下标越界的条件从而节省了比较的时间。3） 在等概率情况下，查找成功时其平均查找长度约为表长的一半（n+1） /2.查找失败的话 其平均查找长

54、度为 n+1.(2) 二分查找(又称折半查找)，它的算法思想：是对一有序表中的元素，从初始的查找区间 开始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，贝U查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。1) 二分查找在等概率的情况下查找成功的平均查找长度ASL为lg (n+1) -1，在查找失败 时所需比较的关键字个数不超过判定树的深度，最坏情况下查找成功的比较次数也不超过判定树的深度厂lg(n+1) n (不小于lg (n+1)的最小整数)2) 二分查找只适用于顺序存储结构而不能用链式存储结构实现。因为链

55、表无法进行随机访 问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二 分查找。(3) 分块查找(又称索引顺序查找)的基本思想：是将原表分成若干块，各块内部不一定有序， 但表中的块是”分块有序”的，并抽取各块中的最大关键字及其起始位置建立索引表。因为索引表是 有序的，分块查找就是先用二分查找或顺序查找确定待查结点在哪一块，然后在已确定的块中进行顺序查找(不能用二分查找，因为块内是无序的)。分块查找实际上是两次查找过程，它的算法效 率介与顺序查找和二分查找之间。4. 以上三种查找方法的比较如下表：查找算法存储结构优点缺点适用于顺序查找顺序结构链表结构算法简单且对表的结构无任何要求查找效率低 n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)二分查找顺序结构查找效率高关键字要有序且只能用顺序存储结构实现特别适用于一经建立就很少改动又经常需要查找的线性表分块查找顺序结构链表 在表中插入或删除记录时就只要在该记录所属块内操作，因为块内记录的存放是随意的， 所以插入和删除比较容易要增加一个辅助数组的存储空间，并要进行将初始表分块排序运算适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块