传智播客C和C++与数据结构基础讲义

精品范文模板 可修改删除撰写人：_日 期：_传智播客C和C+与数据结构基础讲义 传智扫地僧1、 数据结构概念1.1数据结构相关概念疑惑1、我学完了C语言，可是现在感觉还是写不出代码。2、为什么会有各种各样的程序存在？3、程序的本质是什么？程序是为了具体问题而存在的 程序需要围绕问题的解决进行设计同一个问题可以有多种解决方案如何追求程序的“性价比”？是否有可量化的方法判别程序的好坏？数据结构起源计算机从解决数值计算问题到解决生活中的问题现实生活中的问题涉及不同个体间的复杂联系需要在计算机程序中描述生活中个体间的联系数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系 不是研究复杂的算法数据结构中的基本概念数据 程序的操作对象，用于描述客观事物 (int a, int b,)数据的特点：可以输入到计算机可以被计算机程序处理数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等数据元素：组成数据的基本单位数据项：一个数据元素由若干数据项组成数据对象 性质相同的数据元素的集合 （比如：数组，链表） /友情提示，来自结构体课堂代码/声明一个结构体类型struct _MyTeacher /一种数据类型charname32;chartile32;intage;charaddr128;int main21()struct _MyTeacher t1; /数据元素struct _MyTeacher tArray30; /数据对象memset(&t1, 0, sizeof(t1);strcpy(t1.name, name); /数据项strcpy(t1.addr, addr); /数据项strcpy(t1.tile, addr); /数据项t1.age = 1;数据元素之间不是独立的，存在特定的关系，这些关系即结构数据结构指数据对象中数据元素之间的关系 如：数组中各个元素之间存在固定的线性关系 编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。基本概念总结：数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：数据的物理结构数据的运算1.2、算法1.2.1算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列 算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。1.2.2算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法=程序=数据结构+算法 总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据结构与算法相辅相成1.2.3算法特性输入算法具有0个或多个输入输出算法至少有1个或多个输出有穷性算法在有限的步骤之后会自动结束而不会无限循环确定性算法中的每一步都有确定的含义，不会出现二义性可行性算法的每一步都是可行的1.2.4算法效率的度量1、事后统计法比较不同算法对同一组输入数据的运行处理时间缺陷 为了获得不同算法的运行时间必须编写相应程序运行时间严重依赖硬件以及运行时的环境因素算法的测试数据的选取相当困难事后统计法虽然直观，但是实施困难且缺陷多算法效率的度量事前分析估算依据统计的方法对算法效率进行估算影响算法效率的主要因素算法采用的策略和方法问题的输入规模编译器所产生的代码计算机执行速度/算法最终编译成具体的计算机指令/每一个指令，在具体的计算机上运行速度固定/通过具体的n的步骤，就可以推导出算法的复杂度long sum1(int n) long ret = 0; int* array = (int*)malloc(n * sizeof(int); int i = 0; for(i=0; in; i+) arrayi = i + 1; for(i=0; in; i+) ret += arrayi; free(array); return ret; long sum2(int n) long ret = 0; int i = 0; for(i=1; i 0 ) ret = (1 + n) * n / 2; return ret;int main() printf(%dn, sum1(100); printf(%dn, sum2(100); printf(%dn, sum3(100); return 0;int func(int a, int len) int i = 0; int j = 0; int s = 0; for(i=0; ilen; i+) n for(j=0; jlen; j+) n s += i*j; /n*n return s; /n*n注意1：判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。注意2：在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。2、大O表示法算法效率严重依赖于操作(Operation)数量在判断时首先关注操作数量的最高次项操作数量的估算可以作为时间复杂度的估算O(5) = O(1)O(2n + 1) = O(2n) = O(n) O(n2+ n + 1) = O(n2)O(3n3+1) = O(3n3) = O(n3)常见时间复杂度关系3、算法的空间复杂度算法的空间复杂度通过计算算法的存储空间实现S(n) = O(f(n)其中，n为问题规模，f(n)为在问题规模为n时所占用存储空间的函数大O表示法同样适用于算法的空间复杂度当算法执行时所需要的空间是常数时，空间复杂度为O(1)空间与时间的策略多数情况下，算法执行时所用的时间更令人关注如果有必要，可以通过增加空间复杂度来降低时间复杂度同理，也可以通过增加时间复杂度来降低空间复杂度练习1：分析sum1 sum2 sum3函数的空间复杂度O(4n+12) O(8)=O(1) O(4)=O(1)总结：实现算法时，需要分析具体问题，对执行时间和空间的要求。练习2：时间换空间 /* 问题： 在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。 设计一个算法，找出出现次数最多的数字。*/方法1： 排序，然后找出出现次数最多的数字方法2：void search(int a, int len) int sp1000 = 0; int i = 0; int max = 0; for(i=0; ilen; i+) int index = ai - 1; spindex+; for(i=0; i1000; i+) if( max spi ) max = spi; for(i=0; i1000; i+) if( max = spi ) printf(%dn, i+1); int main() int array = 1, 1, 3, 4, 5, 6, 6, 6, 2, 3; search(array, sizeof(array)/sizeof(*array); return 0;把每个数字出现的次数的中间结果，缓存下来；在缓存的结果中求最大值。2、线性表2.1线性表基本概念线性表定义线性表(List)是零个或多个数据元素的集合 线性表中的数据元素之间是有顺序的线性表中的数据元素个数是有限的线性表中的数据元素的类型必须相同数学定义线性表是具有相同类型的 n（ 0）个数据元素的有限序列（a1, a2, , an）ai是表项，n 是表长度。性质a0为线性表的第一个元素，只有一个后继 an为线性表的最后一个元素，只有一个前驱除a0和an外的其它元素ai，既有前驱，又有后继线性表能够逐项访问和顺序存取练习下面的关系中可以用线性表描述的是A.班级中同学的友谊关系 N:NB.公司中的上下级关系 1:NC.冬天图书馆排队占座关系 D.花名册上名字之间的关系 1:1线性表的操作创建线性表销毁线性表清空线性表将元素插入线性表将元素从线性表中删除获取线性表中某个位置的元素获取线性表的长度线性表在程序中表现为一种特殊的数据类型线性表的操作在程序中的表现为一组函数C语言描述=线性表的设计与实现ADT抽象层 数据结构(C语言版).严蔚敏_吴伟民.扫描版.pdf p44页 人生财富库积累#ifndef _WBM_LIST_H_#define _WBM_LIST_H_typedef void List;typedef void ListNode;/创建并且返回一个空的线性表List* List_Create();/销毁一个线性表listvoid List_Destroy(List* list);/将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态void List_Clear(List* list);/返回一个线性表list中的所有元素个数int List_Length(List* list);/向一个线性表list的pos位置处插入新元素nodeint List_Insert(List* list, ListNode* node, int pos); /获取一个线性表list的pos位置处的元素ListNode* List_Get(List* list, int pos);/删除一个线性表list的pos位置处的元素 返回值为被删除的元素，NULL表示删除失败ListNode* List_Delete(List* list, int pos);#endif注意:int List_Insert(List* list, ListNode* node, int pos); (重点:分离思想) 2.2线性表的顺序存储结构2.2.1基本概念2.2.2设计与实现插入元素算法判断线性表是否合法判断插入位置是否合法把最后一个元素到插入位置的元素后移一个位置将新元素插入线性表长度加1获取元素操作判断线性表是否合法判断位置是否合法直接通过数组下标的方式获取元素删除元素算法判断线性表是否合法判断删除位置是否合法将元素取出将删除位置后的元素分别向前移动一个位置线性表长度减1链表顺序存储插入算法和删除算法2.2.3优点和缺点优点：无需为线性表中的逻辑关系增加额外的空间可以快速的获取表中合法位置的元素缺点：插入和删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量2.3线性表的链式存储2.3.1基本概念链式存储定义为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。表头结点链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息数据结点链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息尾结点链表中的最后一个数据结点，其下一元素指针为空，表示无后继。链表技术领域推演设计与实现链表链式存储_api实现分析在C语言中可以用结构体来定义链表中的指针域链表中的表头结点也可以用结构体实现带头结点、位置从0的单链表返回链表中第3个位置处，元素的值LinkListNode* LinkList_Get(LinkList* list, int pos) int i = 0;TLinkList *tList = (TLinkList *)list;LinkListNode *current = NULL;LinkListNode *ret = NULL;if (list=NULL |pos=tList-length)return NULL;current = (LinkListNode *)tList;for (i=0; inext;ret = current-next;return ret ;返回第三个位置的移动pos次以后，当前指针指向哪里？答案：指向位置2，所以需要返回 ret = current-next;备注：循环遍历时，遍历第1次，指向位置0遍历第2次，指向位置1遍历第3次，指向位置2遍历第n次，指向位置n-1;所以如果想返回位置n的元素的值，需要怎么做 ret = current-next;此问题是：指向头结点的指针移动n次 和 第n个元素之间的关系？删除元素重要技术场景图 链表链式存储_插入链表链式存储_删除2.3.3优点和缺点优点：无需一次性定制链表的容量 插入和删除操作无需移动数据元素缺点：数据元素必须保存后继元素的位置信息获取指定数据的元素操作需要顺序访问之前的元素2.4循环链表基本概念循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素循环链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos删除位置pos处的元素新增功能：游标的定义在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。循环链表新操作将游标重置指向链表中的第一个数据元素CircleListNode* CircleList_Reset(CircleList* list);获取当前游标指向的数据元素CircleListNode* CircleList_Current(CircleList* list);将游标移动指向到链表中的下一个数据元素CircleListNode* CircleList_Next(CircleList* list);直接指定删除链表中的某个数据元素 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); / 根据元素的值 删除 元素 pk根据元素的位置 删除 元素循环链表的应用2.4.2.1 证明循环链表打印两次。 约瑟夫问题求解约瑟夫问题-循环链表典型应用n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 m 个人，令其出列。然后再从下一 个人开始从 1 顺时针报数，报到第 m 个人，再令其出列，如此下去，求出列顺序。大话数据结构 3.16结尾：写书的人，也很累；临界点2.4.3设计与实现2.4.3.1循环链表插入元素的分析 1） 普通插入元素（和单链表是一样的）2） 尾插法（和单链表是一样的，单链表的写法支持尾插法；因：辅助指针向后跳length次，指向最后面那个元素） CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list);CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list);3） 头插法（要进行头插法，需要求出尾结点，和单链表不一样的地方，保证是循环链表）第一次插入元素时，让游标指向0号结点CircleList_Insert(list, (CircleListNode*)&v1, 0);CircleList_Insert(list, (CircleListNode*)&v1, 0);4)第一次插入元素2.4.3.2循环链表插入综合场景分析图2.4.3.3循环链表删除结点分析1、 删除普通结点2、 删除头结点（删除0号位置处元素），需要求出尾结点优点和缺点优点：功能强了。循环链表只是在单链表的基础上做了一个加强循环链表可以完全取代单链表的使用循环链表的Next和Current操作可以高效的遍历链表中的所有元素缺点：代码复杂度提高了大话数据结构 3.16结尾：写书的人，也很累；临界点2.5双向链表基本概念 请思考： 为什么需要双向链表？单链表的结点都只有一个指向下一个结点的指针单链表的数据元素无法直接访问其前驱元素逆序访问单链表中的元素是极其耗时的操作！len = LinkList_Length(list);for (i=len-1; len=0; i+) /O(n)LinkListNode *p = LinkList_Get(list, i); /O(n)/访问数据元素p中的元素/双向链表的定义在单链表的结点中增加一个指向其前驱的pre指针双向链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos删除位置pos处的元素设计与实现循环链表一般操作插入操作插入操作异常处理插入第一个元素异常处理在0号位置处插入元素；删除操作删除操作异常处理 双向链表的新操作获取当前游标指向的数据元素将游标重置指向链表中的第一个数据元素将游标移动指向到链表中的下一个数据元素将游标移动指向到链表中的上一个数据元素直接指定删除链表中的某个数据元素DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);DLinkListNode* DLinkList_Reset(DLinkList* list);DLinkListNode* DLinkList_Current(DLinkList* list);DLinkListNode* DLinkList_Next(DLinkList* list);DLinkListNode* DLinkList_Pre(DLinkList* list);/大家一定要注意：教科书不会告诉你 项目上如何用；哪些点是项目的重点；做一个企业级的财富库，完成你人生开发经验的积累，是我们的学习重点，要注意！双向链表重要技术场景循环链表插入结点技术场景循环链表删除结点技术场景2.5.3优点和缺点优点：双向链表在单链表的基础上增加了指向前驱的指针功能上双向链表可以完全取代单链表的使用双向链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素缺点：代码复杂3、栈tack和队列queue3.1栈stack 3.1.1Stack基本概念栈是一种 特殊的线性表 栈仅能在线性表的一端进行操作栈顶(Top)：允许操作的一端栈底(Bottom)：不允许操作的一端Stack的常用操作创建栈销毁栈清空栈进栈出栈获取栈顶元素获取栈的大小 C语言描述=栈的设计与实现 人生财富库积累#ifndef _MY_STACK_H_#define _MY_STACK_H_typedef void Stack;Stack* Stack_Create();void Stack_Destroy(Stack* stack);void Stack_Clear(Stack* stack);int Stack_Push(Stack* stack, void* item);void* Stack_Pop(Stack* stack);void* Stack_Top(Stack* stack);int Stack_Size(Stack* stack);#endif /_MY_STACK_H_栈模型和链表模型关系分析3.1.4栈的顺序存储设计与实现基本概念设计与实现头文件#ifndef _MY_SEQLIST_H_ #define _MY_SEQLIST_H_typedef void SeqList;typedef void SeqListNode;SeqList* SeqStack_Create(int capacity);void SeqStack _Destroy(SeqStack * list);void SeqStack _Clear(SeqStack * list);int SeqStack _Length(SeqStack * list);int SeqStack _Capacity(SeqStack * list);int SeqStack _Insert(SeqStack * list, SeqListNode* node, int pos);SeqListNode* SeqList_Get(SeqList* list, int pos);SeqListNode* SeqList_Delete(SeqList* list, int pos);#endif /_MY_SEQLIST_H_3.1.5栈的链式存储设计与实现基本概念设计与实现头文件#ifndef _MY_LINKSTACK_H_#define _MY_LINKSTACK_H_typedef void LinkStack;LinkStack* LinkStack_Create();void LinkStack_Destroy(LinkStack* stack);void LinkStack_Clear(LinkStack* stack);int LinkStack_Push(LinkStack* stack, void* item);void* LinkStack_Pop(LinkStack* stack);void* LinkStack_Top(LinkStack* stack);int LinkStack_Size(LinkStack* stack);#endif /_MY_LINKSTACK_H_3.1.6栈的应用案例1：就近匹配应用1：就近匹配 几乎所有的编译器都具有检测括号是否匹配的能力如何实现编译器中的符号成对检测？#include int main() int a44; int (*p)4; p = a0; return 0; 算法思路从第一个字符开始扫描当遇见普通字符时忽略，当遇见左符号时压入栈中当遇见右符号时从栈中弹出栈顶符号，并进行匹配匹配成功：继续读入下一个字符匹配失败：立即停止，并报错结束：成功: 所有字符扫描完毕，且栈为空失败：匹配失败或所有字符扫描完毕但栈非空当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性栈非常适合于需要“就近匹配”的场合计算机的本质工作就是做数学运算，那计算机可以读入字符串“9 + (3 - 1) * 5 + 8 / 2”并计算值吗？案例2：中缀表达式和后缀表达式应用2：中缀 后缀计算机的本质工作就是做数学运算，那计算机可以读入字符串“9 + (3 - 1) * 5 + 8 / 2”并计算值吗？后缀表达式 =？符合计算机运算波兰科学家在20世纪50年代提出了一种将运算符放在数字后面的后缀表达式对应的，我们习惯的数学表达式叫做中缀表达式=符合人类思考习惯实例：5 + 4= 5 4 + 1 + 2 * 3 = 1 2 3 * + 8 + ( 3 1 ) * 5 = 8 3 1 5 * + 中缀表达式符合人类的阅读和思维习惯后缀表达式符合计算机的“运算习惯”如何将中缀表达式转换成后缀表达式？中缀转后缀算法：遍历中缀表达式中的数字和符号对于数字：直接输出对于符号：左括号：进栈 运算符号：与栈顶符号进行优先级比较若栈顶符号优先级低：此符合进栈 （默认栈顶若是左括号，左括号优先级最低）若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈右括号：将栈顶符号弹出并输出，直到匹配左括号遍历结束：将栈中的所有符号弹出并输出中缀转后缀计算机是如何基于后缀表达式计算的？8 3 1 5 * + 遍历后缀表达式中的数字和符号对于数字：进栈对于符号：从栈中弹出右操作数从栈中弹出左操作数根据符号进行运算将运算结果压入栈中遍历结束：栈中的唯一数字为计算结果栈的神奇！ 中缀表达式是人习惯的表达方式后缀表达式是计算机喜欢的表达方式通过栈可以方便的将中缀形式变换为后缀形式中缀表达式的计算过程类似程序编译运行的过程 扩展：给你一个字符串，计算结果“1 + 2 * (66 / (2 * 3) + 7 )” 1字符串解析词法语法分析优先级分析 数据结构选型=栈还是树？3.2队列queuequeue基本概念队列是一种特殊的线性表 队列仅在线性表的两端进行操作队头(Front)：取出数据元素的一端队尾(Rear)：插入数据元素的一端队列不允许在中间部位进行操作！queue常用操作销毁队列清空队列进队列出队列获取队头元素获取队列的长度C语言描述=队列的设计与实现 人生财富库积累#ifndef _MY_QUEUE_H_#define _MY_QUEUE_H_typedef void Queue;Queue* Queue_Create();void Queue_Destroy(Queue* queue);void Queue_Clear(Queue* queue);int Queue_Append(Queue* queue, void* item);void* Queue_Retrieve(Queue* queue);void* Queue_Header(Queue* queue);int Queue_Length(Queue* queue);#endif /_MY_QUEUE_H_队列模型和链表模型关系分析队列的顺序存储设计与实现1基本概念队列也是一种特殊的线性表；可以用线性表顺序存储来模拟队列。2设计与实现#ifndef _MY_SEQQUEUE_H_#define _MY_SEQQUEUE_H_typedef void SeqQueue;SeqQueue* SeqQueue_Create(int capacity);void SeqQueue_Destroy(SeqQueue* queue);void SeqQueue_Clear(SeqQueue* queue);int SeqQueue_Append(SeqQueue* queue, void* item);void* SeqQueue_Retrieve(SeqQueue* queue);void* SeqQueue_Header(SeqQueue* queue);int SeqQueue_Length(SeqQueue* queue);int SeqQueue_Capacity(SeqQueue* queue);#endif /_MY_SEQQUEUE_H_队列的链式存储设计与实现1基本概念队列也是一种特殊的线性表；可以用线性表链式存储来模拟队列的链式存储。2设计与实现#ifndef _MY_LINKQUEUE_H_#define _MY_LINKQUEUE_H_typedef void LinkQueue;LinkQueue* LinkQueue_Create();void LinkQueue_Destroy(LinkQueue* queue);void LinkQueue_Clear(LinkQueue* queue);int LinkQueue_Append(LinkQueue* queue, void* item);void* LinkQueue_Retrieve(LinkQueue* queue);void* LinkQueue_Header(LinkQueue* queue);int LinkQueue_Length(LinkQueue* queue);#endif /_MY_LINKQUEUE_H_4、树专题 4.1树基本概念基础讲义：参考数据结构_树A.ppt参考数据结构_树B.ppt非线性结构，一个直接前驱，但可能有多个直接后继（1:n）树的定义1）具有递归性，即树中还有树2）m颗互不相交的集合根 叶子 森林有序树 无序树双亲 孩子 兄弟 堂兄弟 祖先 子孙结点 结点的度 结点的层次 终端结点 分支结点树的度 所有结点度中的最大值（Max各结点的度树的深度指所有结点中最大的层数（Max各结点的层次(或高度)4.2树的表示法图形表示法广义表表示法左孩子右兄弟表示法双亲孩子表示法4.3树的逻辑结构一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。广义表表示法左孩子右兄弟表示法4.4二叉树概念4.4.1基本概念二叉树的结构最简单，规律性最强可以证明，所有树都能转为唯一对应的二叉树，不失一般性定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成二叉树性质性质1: 在二叉树的第i层上至多有2i-1个结点（i0）性质2: 深度为k的二叉树至多有2k-1个结点（k0）性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。理解：（k-1层与满二叉树完全相同，第k层结点尽力靠左）数据结构数据：数据结构(C语言版).严蔚敏_吴伟民.扫描版.pdf p124 数据结构数据：数据结构(C语言版).严蔚敏_吴伟民.扫描版.pdf p127 性质4: 具有n个结点的完全二叉树的深度必为log2n1性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）二叉树的存储结构一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。答：一律转为完全二叉树！讨论：不是完全二叉树怎么办？方法很简单，将各层空缺处统统补上“虚结点”，其内容为空二、链式存储结构二叉树的表示二叉树表示法P127页/*typedef struct BiTNodeintdata; struct BiTNode *lchild, *rchild;BiTNode, *BiTree;*/struct BiTNodeintdata;struct BiTNode *lchild, *rchild;typedef struct BiTNode BiTNode;typedef struct BiTNode * BiTree;树的三叉链表表示/三叉链表typedef struct TriTNode int data;/左右孩子指针struct TriTNode *lchild, *rchild;struct TriTNode *parent;TriTNode, *TriTree;双亲链表法/双亲链表#define MAX_TREE_SIZE 100typedef struct BPTNodeint data;int parentPosition; /指向双亲的指针 /数组下标char LRTag; /左右孩子标志域BPTNode;typedef struct BPTreeBPTNode nodes100; /因为节点之间是分散的，需要把节点存储到数组中int num_node; /节点数目int root; /根结点的位置 /注意此域存储的是父亲节点在数组的下标BPTree;/用这个数据结构能表达出一颗树，为什么？4.4.3二叉树的遍历树的遍历本质剖析4.5二叉树编程实践基本操作typedef struct node int data; struct node *lchild,*rchild； NODE;NODE *root; DLR(NODE *root ) if (root) /非空二叉树 printf(“%d”,root-data); /访问DDLR(root-lchild); /递归遍历左子树DLR(root-rchild); /递归遍历右子树 中序遍历算法LDR(NODE *root) if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); 后序遍历算法LRD (NODE *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); 案例1：计算二叉树中叶子结点的数目int sum = 0; /全局变量DLR_CountLeafNum(NODE *root)/采用中序遍历的递归算法 if ( root) /非空二叉树条件，还可写成if(root !=NULL ) if(!root-lchild&!root-rchild) /是叶子结点则统计并打印 sum+; printf(%dn,root-data); DLR_CountLeafNum(root-lchild); /递归遍历左子树，直到叶子处； DLR_CountLeafNum(root-rchild);/递归遍历右子树，直到叶子处； return(0); 思想：1）求根结点左子树的叶子结点个数，累计到sum中，求根结点右子树的叶子结点个数累计到sum中。2）若左子树还是树，重复步骤1；若右子树还是树，重复步骤1。3）全局变量转成函数参数4）按照先序、中序、后序方式计算叶子结点，=三种遍历的本质思想强化：访问结点的路径都是一样的，计算结点的时机不同。案例2：求二叉树的深度思想：1）求根结点左子树高度，根结点右子树高度，比较的子树最大高度，再+1。2）若左子树还是树，重复步骤1；若右子树还是树，重复步骤1。案例3：完全Copy二叉树 思想：1）malloc新结点，2）拷贝左子树，拷贝右子树，让新结点连接左子树，右子树3）若左子树还是树，重复步骤1、2；若右子树还是树，重复步骤1、2。案例4：树的非递归遍历(中序遍历)中序 遍历的几种情况分析1：什么时候访问根、什么时候访问左子树、什么访问右子树 当左子树为空或者左子树已经访问完毕以后，再访问根 访问完毕根以后，再访问右子树。分析2：非递归遍历树，访问结点时，为什么是栈，而不是其他模型（比如说是队列）。 先走到的后访问、后走到的先访问，显然是栈结构分析3：结点所有路径情况步骤1：如果结点有左子树，该结点入栈；如果结点没有左子树，访问该结点；步骤2：如果结点有右子树，重复步骤1；如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1如果栈为空，表示遍历结束。 注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。分析4：有一个一直往左走入栈的操作，中序遍历的起点作业：自己编写堆栈函数原型，实现中序遍历非递归算法4.6二叉树的创建4.6.1中序和先序创建树1、根据中序遍历的结果能确定一棵树吗？中序遍历：结果为：“12345”，这个“12345”能确定一棵树吗？请思考，会有多少种形状。2、如何才能确定一棵树？结论：通过中序遍历和先序遍历可以确定一个树 通过中序遍历和后续遍历可以确定一个树通过先序遍历和后序遍历确定不了一个树。单独先序遍历：能求解根，但不能求解左子树什么时候结束、右子树什么时候开始。3、根据先序和中序结果画树算法1、通过先序遍历找到根结点A，再通过A在中序遍历的位置找出左子树，右子树2、在A的左子树中，找左子树的根结点（在先序中找），转步骤13、在A的右子树中，找右子树的根结点（在先序中找），转步骤1讲解：先序遍历结果：ADEBCF中序遍历结果：DEACFB练习：先序遍历结果：ABDHKECFIGJ中序遍历结果：HKDBEAIFCGJ4、学习算法可借助工具、动画光盘有2个；C+有1个4.6.2#号法创建树1、什么是#号法创建树#创建树，让树的每一个节点都变成度数为2的树先序遍历：124#3# 可以唯一确定一棵树吗，为什么？2 #创建树练习先序遍历：ABDH#K#E#CFI#G#J#,请画出树的形状#号法画出树关键点：要清楚的确定左子树什么结束，右子树什么时候开始。3、#号法编程实践利用前序遍历来建树（结点值陆续从键盘输入，用DLR为宜）Bintree createBTpre( ) Bintree T; char ch; scanf(“%c”,&ch); if(ch=#) T=NULL; else T=( Bintree )malloc(sizeof(BinTNode); T-data=ch; T-lchild=createBTpre(); T-rchild=createBTpre(); return T;/后序遍历销毁一个树void BiTree_Free(BiTNode* T)BiTNode *tmp = NULL;if (T!= NULL)if (T-rchild != NULL) BiTree_Free(T-rchild);if (T-lchild != NULL) BiTree_Free(T-lchild);if (T != NULL)free(T); T = NULL;4.7二叉线索树线索化概念1、前言普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若可将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。二叉线索树思想是干什么的？中序遍历这棵树=转换成链表访问2线索化思想结论：线索化过程就是在遍历过程（假设是中序遍历）中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。3线索化思想训练请将此树线索化。1）右空指针线索化：2）左空指针线索化3）总结线索化的实现1）线索化树结点typedef struct BiThrNode/* 二叉线索存储结点结构 */chardata;/* 结点数据 */struct BiThrNode *lchild, *rchild;/* 左右孩子指针 */intLTag;intRTag;/* 左右标志 */ BiThrNode, *BiThrTree;2）线索化思想分析线索化的本质：让前后结点，建立关系；1）两个辅助指针变量形成差值后：后继结点的左孩子指向前驱结点，前驱结点的右孩子指向后继结点。2）赋值指针变量和业务操作的逻辑关系4） 二叉树线索化树的遍历/* 中序遍历二叉线索树T(头结点)的非递归算法 */int InOrderTraverse_Thr(BiThrNode* T) BiThrNode* p;p = T-lchild; /* p指向根结点 */while (p != T) /* 空树或遍历结束时,p=T */while (p-LTag = Link)p = p-lchild;printf(%c , p-data);while (p-RTag=Thread & p-rchild!=T)p = p-rchild;printf(%c , p-data);p=p-rchild;return 0;4.8霍夫曼树4.8.1概念组建一个网络，耗费最小 WPL最小；这个方法是霍夫曼想出来的，称为霍夫曼树4.8.2霍夫曼树的构造对于文本”BADCADFEED”的传输而言，因为重复出现的只有”ABCDEF”这6个字符，因此可以用下面的方式编码：接收方可以根据每3个bit进行一次字符解码的方式还原文本信息。这样的编码方式需要30个bit位才能表示10个字符那么当传输一篇500个字符的情报时，需要15000个bit位在战争年代，这种编码方式对于情报的发送和接受是很低效且容易出错的。如何提高收发效率？要提高效率，必然要从编码方式的改进入手，要避免每个字符都占用相同的bit位准则：任一字符的编码都不是另一个字符编码的前缀！也就是说：每一个字符的编码路径，都不包含