数据结构第02级

1、PAGE 数据结构教案 PAGE 63PAGE PAGE 63教学内容：概 论11基本概念和术语12学习数据结构的意义班 级：02级基本要求：熟悉各名字、术语的含义。掌握基本概念，特别是数据的逻辑结构、存储结构、数据结构三个概念以及三个概念之间的关系。重 点：逻辑结构、存储结构、数据结构三个概念以及三个概念之间的关系。难 点：逻辑结构概念的正确理解教学过程：第一章 概 论程序设计的实质是数据表示和数据处理。而这种表示和处理应通过一个渐进的过程逐步完成。数据结构课程主要讨论这个过程中的一些基本问题。以其中的设计阶级为核心，同时涉及编码阶段和分析阶段若干基本问题。本章主要介绍数据结构有关的基本概念

2、、基本思想、基本原理及实际背景。本章学习要点是：1、熟悉各名字、术语的含义，掌握基本概念，特别是数据的逻辑结构、存储结构、数据结构三个概念以及三个概念之间的关系，2、了解评价算法的主要标准3、掌握时间复杂度的估算方法11基本概念和术语数据：计算机加工处理的对象。数据元素：数据的基本单位。作为一个整体加以考虑和处理。数据项：不可分割的最小标识单位。数据、数据项、数据元素反映了数据组织的三个层次。在数据结构课程中，对一个问题主要讨论如下图表示的渐进过程。机外表示执行部分数学模型非形式算法机外表示处理要求 建模 求精在此要特别强调：在非数值总是上，数学模型不再是数学方程。给定一个问题，不仅要描述数据

3、，更重要的要描述元素间的关系，即：数学模型中体现的数据元素之间的邻接关系。逻辑关系：数据元素之间的关联方式或邻接关系。逻辑结构：数据逻辑关系的总体，即数据的组织形式。集合 无关系的关系线性结构 表树型结构 树网状结构 图依元素间关系的不同特性分类描述非数值计算问题的数学模型（逻辑结构）是诸如：表、树、图。注意： （1）、逻辑结构与数据元素本身的形式、内容无关。 （2）、逻辑结构与数据元素的相对位置无关。 （3）、逻辑结构与所包含的结点个数无关。存储结构：数据以及数据元素之间关系在计算机中和存储形成。存储数据涉及到以下二个方面：数据元素本身数据元素之间的关系（在本课程中只考虑语言上的实现）有四种

4、基本的存储结构：顺序存储方式链式存储方式索引存储方式散列存储方式12学习数据结构的意义举例1：电话号码的查询问题举例2：多叉路口交通灯的控制问题通过以上两个例子，说明解决一个总是的关键步骤是：选取合适的数据结构表示问题才能写出有效的算法。作业：Page10 的1、2、3教学内容：13算法的描述和分析班 级：计算机02级基本要求：1、了解评价算法的主要标准2、掌握时间复杂度的估算方法重 点：时间复杂度的含义难 点：时间复杂度的估算教学过程：13算法的描述和分析算法：求解给定问题所需的所有处理和处理规则的描述。描述工具：程序 伪语言算法 非形式算法本教材在授课时采用C语言来描述算法的实现。评价标准

5、：正确性 易读性时间效率空间效率 健壮性 高效性 随着输入量的增加时间、空间的增长速度事先分析算法：所选策略因素：问题的规模书写程序的语言系统环境编译程序所产生机器代码的质量机器指令的执行速度 对一个问题时间效率的衡量不需要精确值，只要反映求解同一问题的不同算法的计算量之间的差异。从以上因素分析得：算法运行的时间只依赖于问题的规模，它是问题规模的一个函数。计算量的估算方法：标准操作重复次数T（n）=标准操作重复执行的次数 （一般是问题规模的一个函数）T（n）算法的时间复杂性（度）O（T（n）时间复杂性的量级（级别）例1：x=x+1 O(1)for i=1 to n dofor j=1 to n

6、 dox=x+1 O(n2)for i=1 to n dox=x+1O(n) (a) (b) (c)4例16结论：给定一个问题，我们所关心的不是具体的数，而是T（n）n的变化趋势。常见的量级有：O（1）、O（log2n）、O（n2）、O（2n ）作业：Page11的1.7教学内容：第二章 线性表21线性表的逻辑结构22线性表的顺序实现班 级：计算机系02级基本要求：了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的不同方法得到不同的两种不同的存储结构。熟练掌握顺序存储结构的语言描述。熟练掌握线性表在顺序存储结构上实现基本运算。知道线性表的优点和不足。重 点：顺序存储结

7、构的语言描述 基本运算在顺序存储结构上实现难 点：机外表示到机内表示的描述（语言级的语言描述） 函数参数教学过程：第二章 线性表本章主要介绍线性结构和线性表的基本概念、线性表的两种常用的存储结构以及常见运算的实现。本章要点：1、了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的不同方法得到不同的两种不同的存储结构。2、熟练掌握顺这两种存储结构的语言描述。3、熟练掌握线性表在顺序存储结构、链式存储结构上基本运算的实现。4、掌握从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 21线性表的逻辑结构线性表的逻辑结构线性结构2、线性表的定义及逻辑特征

8、数学定义：线性表是n（n0）个结点的有穷序列。即：a1、a2、a3ai、ai+1an其中：ai代表一个结点，i为ai在线性表中的位置序号。a1起始结点an终端结点ai为ai+1的直接前趋，ai+1为ai直接后继 n为线性表的长度，空表为0。特征：一个始点一个终点11的关系 要求：同一线性表中的所有元素具有相同的数据类型3、基本运算1）初始化initiate(l)2）求表长length(l)3）读表元get(l)4）定 位locate(l,x)5）插 入insert(l,x,i)6）删 除delete(l,i)要实现各种运算，首先要考虑线性表的存储结构。线性表常用的存储结构有：顺序存储方式形成顺

9、序表链式存储方式形成链表22线性表的顺序存储结构 线性表的顺序存储方式顺序表线性表的顺序存储又称顺序表。存储分配分配一块连续的区间 一个变量记表中的元素个数 语言描述： l.datatypedef struct node datatype datamaxsize;int length;sqlist; l.lengthsqlist l; l顺序表访问形式: 结构体变量形式 指针变量形式 l.datai 访问第i个结点 l-datai l.length 表长 i-last l.datal.length 访问最后一个元素 l-datal-length特点：（1）开辟一块连续的存储空间，逻辑上相邻物理

10、上也相邻。(2）能随机存取:loc(ai)=loc(ai)+(i-1)*l 随机存取基本运算在顺序表上的实现1、插入基本思想：是指在表的第i个（1in+1）的位置上，插入一个新结点x，使长度为n的线性表（a1,a2,ai-1,ai,an）变成长度为n+1的线性表 （a1,a2,ai-1,x,ai,an）算法：（C语言算法略）判断i位置的合法性元素移动插入元素并修改表长注意：指针作为函数参数的特点，在此算法中结构体变量不能作为函数参数。 分析：基本操作元素的移动因为元素的移动次数与位序有关，所以讨论其平均移动次数。平均移动次数= 其中Pi=1/(n+1)为每个位置插入的概率在第i位插入元素移动的

11、次数为：n-i+1所以Eis=T(n)=n/2时间复杂性为O（T(n)）=O(n)结论：插入时元素的移动次数是表长的一半，效率较低。删除 基本思想：算法（C语言算法略）：判断i位置的合法性元素移动修改表长三种基本运算讲完后，我们可以看出顺序表有它的优点：逻辑上相邻物理上也相邻能随机存取但也有它的缺点：插、删效率较低要预留空间。为了克服顺序表的缺点，下面我们来学习线性表的另一种存储结构。教学内容：23 线性表的链式存储结构班 级：计算机系02级基本要求：掌握单链表的定义，区分：头指针、头结点、开始结点熟练掌握链式存储结构的语言描述。3、熟练掌握链表的建立。重 点：链式存储的语言描述、链表中结点的

12、访问难 点：链表中结点的访问教学过程：23线性表的链式存储实现 导入：顺序表的优、缺点，为了克服其缺点，引入链式存储基本思想：用一组任意的存储结点存放线性表的数据元素，每个存储结点不仅包含一个数据元素，还包含一组指针。每个指针指向一个与本结点有逻辑关系的结点，即用附加的指针表示逻辑关系。用链式方式存储的线性表为链表。线性表常见链式存储结构有单链表、循环链表和双链表。本节集中讨论单链表的组织方法以及线性表的基本运算在单链表上的实现。单链表1、定义：每个存储结点中附加一个指针指向其直接后继；最后一个结点的指针域为空；并且要有一个头指针指向第一个结点。因为只有一个指针，故称为单链表。W DBA如：

13、head3、访问形式：listnode *p; Pnew(P);p-data访问数据元素p-next后继元素的地址2、语言描述：A1）结点类型描述：typedef struct nodedatatype data; struct node *next;listnode; 2）头指针类型描述：typedef listnode* linklist;注意：为了操作方便，一般情况下在链表的最前面附加一个不存放任何信息的结点，称为头结点。 4、链表的建立 说明：为了操作实现方便，一般情况下在链表的第一个结点之前附加一个头结点称为头结点，而第一个元素结点称为首结点。 前插入建立 思想： 该方法从一个空表开

14、始，建立具有n个结点的链表，每个结点在链表的最前面插入。 算法： linklist creatlistF()linklist head;/head为头指针 listnode *s;/s为工作指针 head=NULL: for(i n) scanf(“”,&x); s=(listnode*)malloc(sizeof(listnode);/申请结点 s-data=x; s-next=head;/插入 head=s;/插入 return(head); 注意：链表中结点与输入的次序相反。 尾插入建立 思想：在一个具有表头结点的链表中，不断在链表的最后插入建立具有n个结点的链表。 算法：linklis

15、t creatlistR() linklist head=(linklist)malloc(sizeof(listnode);/申请头结点 listnode *s,*r;/s、r为工作指针 r=head; for() scanf();s=()malloc(); s-data=x; s-next=NULL; r-next=s; r=s;return(head);结论：对链表操作有两类指针，头指针和工作指针头指针标识整个链表，类型为linklist工作指针在链表中移动，访问当前结点，类型为listnode作业：Page30 的2.1教学内容：23 线性表的链式存储结构 基本运算的实现班 级：计算机

16、系02级基本要求：熟练掌握基本运算在单链表上的实现。重 点：基本运算的算法设计难 点：算法设计教学过程：23线性表的链式存储实现 前次课我们学习了单链表中的四个问题：单链表的定义、语言描述、访问形式、单链表的建立，这次课继续学习第五个问题。 5、基本运算在单链表上的实现 1)查找运算按序号查找 思想：线性表中按序号查找是一种常用的运算，在顺序表中可以按序号查找结点，即能随机存取，而在链表中,由于逻辑上相邻的结点并不是存储在物理上相邻的单元中,所以不能直接按序号查找,只能从头指针出发,顺链域next逐个往下搜索,直到找到第i个结点.查找结果返回结点地址（不成功时为空NULL） 算法： Listn

17、ode*getnode(linklist head,int i) /注意函数返回类型结点类型 p=head;/head为头指针，p为工作指针j=0;While(p-next!=NULL&jnext;j+;/此处涉及到链表中一种重要的操作扫描 if(i=j) return(p); else return(NULL); 按值查找分析（略） 算法：listnode* locatenode(linklist head,datatype x)/*求表head中第一个值等于x的结点,不存在这种点时返回NULL*/ p=head; while(p-next!=NULL&p-data!=x) p=p-next

18、;if(p-data=x) return(p);else return(NULL);2）插入运算insert(head,i,x) 思想：在链表中找第i-1个结点，若存在，则在第i-1之后插入第i个结点，否则“position error”. 算法：void insertlist(linklist* head,int i,datatype x) /*i-1结点*/ /带头结点p=head; j=0;while(p-next!=NULL&jnext;if(j=i-1) /若存在s=(lklist *)malloc(sizeof(struct node);s-data= x;s-next=p-nex

19、t; p-next=s;else error(“不存在第i个位置”)；算法分析：O（n）基本操作一指针移动。思 考：不带表头结点的插入、删除算法 3）删除算法（删第i个结点）思想：找第i-1个结点 若第i-1个结点并且第i个结点也存在，则将第i个结点 删除时只改变指针即可，不须移动元素。算法：void deletelist(linklist head,int i) /*在带表头的链表中删出不须返回头指针*/ listnode *p; p=getnode(head;i -1); /*调用前面getnode() */if (p!=NULL&p-next!=NULL) q=p-next;p-next

20、=q-nextfree(q);else error(“不在在该结点”)；return(head); 结论：链式存储在插入、删除时，不须元素移动，只须移动指针找指定的结点，之后改变指针，所以在插、删比较多的情况下，用链式存储效率较高。作业：Page30的2.2、 2.4、 2.8、2.11初始化linklist* init_ lklist（）linklist *head;head=(listnode *)malloc(sizeof(listnode);head-next=NULL;return(head);求表长主要操作：对链表进行全部扫描在算法中要用到两个指针，一个为头指针，另一个为工作指针。

21、p=head; j=0;while(p-next!=NULL)j+;p=p-next;教学内容：23 线性表的链式存储结构 其它链表 24 顺序表和链表的比较班 级：计算机系02级基本要求：熟练掌握基本运算在循环链表上的实现 （对比单链表来掌握）。 了解不同链表的使用场合掌握从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。重 点：循环链表基本运算的算法设计教学过程：循环链表定义：head head 区别： rear-next=head特点：从任一结点出发，能访问表中所有结点。 rear 另一种方式: 特点：访问链表两端的元素较方便尾结点：rear首结点：rear-ne

22、xt-next运算实现：求表长 p 插入 head 按序号查找 删除 定位注：将单链表中的所有判断: p-next!=NULL用p-next!=head替代整个链表的合并：单链：循环：p=head; p=head-next wjile(p-next!=NULL) head-next=avail; p-next=avail; avail=p; avail=head;双链表单链表缺点：找后继方便找前驱(n)struct dnode datatypt data; struct dnode *priur;struct dnode *next;dblklist;特点：对称结构（对称性）p-prior-n

23、ext=p=p-next-prior基本运算的实现：同单链表（求表长、按序号查找、定位）（插入、删除指针变化有别）删除操作：找第i个结点: while(p-next!=NULL&jnext; if(j= =i) 删除else error(“”);指针变化: p-prior-next=p-next; p-next-prior=p-prior; dispose (p);插入操作（在第i个结点之后插入）: q-prior=p; q-next=p-next; p-next-prior=q; p-next=q;24顺序表与链接表的比较顺序存贮顺序表线性表 链式存贮链表1、空间性能比较：存贮密度：结点数据

24、域占用量/分配给结点的整个空间 顺序表： 要预留、浪费、不易扩充、存贮密度高 链 表： 不须预留，易扩充、存贮密度低时间性能比较 时间复杂度 顺序表 单链表 定 位 O(n) O(n) 比较读表元 O(1) O(n) 扫描插 入 O(n)元素移动 O(n)指针移动删 除 O(n) 元素移动 O(n)指针移动结论：一般情况下，元素移动要比指针移动花费的时间多，所以若表中的元素插入、删除比较频繁的话，用链式存储较好，不则用顺序存储较好。根据实际问题的具体需要，对各方面的优缺综合平衡，选定适宜的实现方法。上机题 目：运动会记分系统班 级：计算机系02级问题描述： 参加运动会的N个学校（或系）编号为1

25、N。比赛分成m个男子项目和w个女子项目，项目编号分别1m和m+1m+w。每个项目取前三名，记分为5、3、1，写一统计程序产生名种成绩单和报表。基本要求：产生每个系的成绩单产生一总成绩表，包括：系名、男子团体总分、女子团体总分、团体总分存储结构要求用线性表的顺序存储。实验报告中要写出测试数据、错误分析以及收获。教学内容：第三章 栈和队列3.1 栈 栈的定义及基本运算 顺序栈 班 级：计算机系02级基本要求：掌握栈这种数据结构的特点，懂得在什么场合要用到栈。熟练掌握在顺序存储结构上实现栈的基本运算，特别注意栈空和栈满的条件。 重 点：栈的特点，如何使用栈教学过程： 第三章 栈和队列本章介绍栈、队列

26、的结构特性；在两种存储结构上如何实现栈和队列的基本运算，栈和队列在程序设计中的应用。本章要点：1、掌握栈和队列这两种数据结构的特点，懂得在什么场合应该利用哪种数据结构。 2、熟练掌握在两种存储结构上实现栈的基本运算，特别注意栈空和栈满的条件。 3、熟练掌握循环队列和链队的基本运算，特别队满和队空的描述方法。 31栈一、栈的定义栈是一种特殊的线性表，或者说是一种操作受限的线性表，限定插入和删除在表的一端进行的线性表为本栈。栈底:不允许插、删的一端。栈顶:允许插、删的一端。特点：先进后出（FILO）应用：计算机中的表达式求值。过程的嵌套调用。栈的基本运算初始化initstack(s) 进栈push

27、(s,x) 退栈 pop(s) 读栈顶 stacktop(s) 判栈空stackempty(s) 判栈满 stackfull(s) 常用的存储方式：顺序存储方式 链式存储方式二、栈的顺序实现顺序栈分配一块连续的空间存放线性表的元素附加指向变化栈顶的指针语言描述：typedef struct xxxx datatype datamaxsize; int top;seqstack;seqstack sq;栈空：top=-1下溢：正常现象、控制程序转移上溢：出错，应避免1、进栈void push(seqstack *s, int x)/*元素进顺序栈* if(s-top= =Maxsize) /判栈

28、满 printf(“ovetflovw”);exit(0);s-datas-top=x;/插入s-top+;/栈顶变化 注意：1)函数参数用指针，对栈中元素的访问形式s-datas-top 2)不用指针参数可以吗？2、退栈datatype pop(seqstack *s) /返回栈顶元素if (s-top= =-1)/判栈空printf(“undetflow”);exit(0); x=s-datas-top;/删除s-top-;/栈顶变化 return(x); 读栈顶元素datatype stacktop (sqstruct *s) if(s-top=-1) /判空 printf(“empty

29、”);exit(0); return(s-datas-top);/返回判空栈空、否则int stackemtpy(seqstack *s)if(s-top=-1) return(1);else return(0);判满介绍：多栈共享的情形作业：Page49的3.1、3.5的（1）教学内容：第三章 栈和队列3.1 栈 链栈班 级：计算机系02级基本要求：熟练掌握在链式存储结构上实现栈的基本运算。 重 点：链栈的各种操作教学过程：三、栈的链接实现链栈注意：不附加头结点1、语言描述：结点类型typedef struct node datatype data; struct node *next;st

30、acknode;头指针类型 typedef stacknode* linkstack;2、运算实现1）初始化栈linkstack initstack() linkstack p; p=NULL; return(p);main()h=initstack();2)进栈viod push(linkstack s,datatype x) p=(linkstack)malloc(sizeof(stacknode);p-data=x;p-next=s; p=s; return(p);3)退栈datatype pop(linkstack s) if(s!=NULL) printf(“underflow”);

31、exit(0); p=s; s=s-next; x=s-data;free(p); return(x);4)读元素datatype stacktop(linstack s) return(s-data);3、栈的应用1）栈与过程调用2）递归与栈递归满足的两个条件：问题逐步得到简化，但解决方法相同。终止条件float fact (int n) if(n=0& n=1)return(1);elsereturn(n*fact(n-1);main f(3) f(2) f(1) r s t 作业：Page49的3.2教学内容：3.2 队列 队列的定义及基本运算 顺序队班 级：计算机系02级基本要求：掌握

32、队列这种数据结构的特点，懂得在什么场合要用到队列。熟练掌握在循环队列的基本运算，特别注意队空和队满的条件。 重 点：队列的特点，如何使用队列难 点：循环队列循环的条件以及判空和判满的条件教学过程：32队列队列的基本概念1、队列的定义限定插入在表的一端，删除在表的另一端进行的线性表为队列。队头：允许删的一端队尾：允许插的一端特点：先进先出。2、基本运算：初始化initqueue(q)入队列 enqueue(q,x)出队列dequeue (q)读队头 getqueue(q)判队空 empty(q)二、队列的顺序实现分配一块连续区间指向队头、队尾的两个指针语言描述：#define M 100 typ

33、edet struct queue datatype qM; int front; int rear; seqqueue; sqqueue sq;约定：队尾指针指向真正的队尾元素。队头指针队头元素的前一个位置。问题：Sq.rear=m时，再入队，前方有空额假溢出。真溢出：sq.rear-sq.front=m解决办法： 将元素向排头方向移动浪费时间。将队列设想成一个循环队列。入队：sq.rear=(sq.rear+1)% M; sq.datasq.rear=x;出队：sq.rear=(sq.front+1)% M队满：sq.front=sq.rear 怎么区分 队空：sq.front=sq.re

34、ar方法（书中所采用）：设置一个计数器 count（sq.rear+1）% M=sq.front队满 浪费一个单元。语言描述：typedef structdatatype datam; int rear; int front; int count;cirqueue; 算法实现：1、入队列元素X加入cq中,注意判队列满的条件步骤：（1）判队满 （2）插入元素 （3）修改表长void enqueue(cirqueue *q,datatype x)if (q-count=m) /判队满printf(“overflow”);exit(0);q-rear=(q-rear+1)%M; /插入元素Xq-da

35、taq-rear=x; q-count+; /修改表长main().enqueue(&cq,x); 3、出队列 删除队头元素，并返回队头元素。 datatype dequeue(cirqueue *q) if (q-count=0) /判队空printf(“queue null”); exit(0);qfront=(qfront+1)%M; /删除队头元素q-count-; /修改表长return(q-dataq-front);4、读队头元素： datatype getqueue(cirqueue *q)return(qdate(qfront+1)%M);5、判空：int queueempty

36、(cirqueue *q)if(qcount=0) return(1); else return(0);判队满 （略） 总结：循环队列的引出：假溢出 循环的条件：q-front=(q-front+1)%m q-rear=(q-rear+1)%m 队空和队满的判断条件:q-count=0q-count=m作业：Page49的3.3教学内容：3.2 队列 链队列班 级：计算机系02级基本要求：熟练掌握在链式存储结构上实现队列的基本运算。 重 点：链队的各种操作难 点：算法中的参数教学过程：三、队列的链接实现： 注：附加头结点语言描述: Q.front Q.rearQ 结点类型描述typedef s

37、truet node datatype data; 0 struet node *next;queuenode;头、尾指针描述typedef struct queuenode *front; queuenode *rear; linkqueue; 头尾指针类型如左图。 运算实现：入队列void enqueue(linkqueue q,datatype x)p=(queuenode *)malloc(sizeof(queuenode);/申请结点pdata=x; pnext=NULL;rnext=p; /插入尾部r=p; /改变尾指针出队列判队空，返回队头元素的值 datatype dequeu

38、e (linkqueue Q) if (Q-rear=Q-front) /判队空 printf(“Queue NULL”);exit(0);s=Q-frontnext; /删除Q-frontnext=snext;if(snext= =NULL) /表中只有一个结点特殊处理Q-rear=Q-front;X=s-data; Q-front Q-rear 0free(s);return(x ) ; Q-rear S读队头元素 判队空作业：Page50的3.6、3.7、3.8、3.9教学内容： 第四章 串4.1 串及其运算 4.2 串的存储结构 班 级：计算机系02级基本要求： 了解串在计算机中的应用

39、熟悉串的各种基本运算的定义并能应用 理解串的各种存储结构 重 点：串的各种基本运算 教学过程： 第四章 串41串及其运算 串是一种特殊的线性表，它以字符为数据元素，以线性结构为逻辑结构的数据为字符串，即：“a1 a2 an”串一、串的基本概念串：由一个或多个字符组成的有穷序列空串：长度为串长：串中的字符个数。子串：一个串中任意个连续字符组成的子序列为该串的子串。主串：空串为任意串的子串，任意串为自身的子串。二、串的基本运算求串长（strlen）串复制（strcpy）串联接（strcat）串比较（strcmp）字符定位（strchr）42串的存储结构常用的存储结构 顺序存储方式链式存储方式1、串

40、的顺序存储顺序串静态存储方式的顺序串 typedef struct char chmaxsize; int length; seqstring; 动态存储方式的顺序串typedef structchar *ch; int length; hstring;2、串的链式存储链串由于串中元素的特殊性，用链式存储，结点的存储密度太小（元素只占一个字节）， 结点大小为所以，结点大小的选择结点大小1类型描述：struet cnode struct cnode char ch; char ch4;struct cnode *next; struct cnode *next; 作业：p58 4.1、4.2教学

41、内容： 第六章 树6.1 树的概念 6.2 二叉树 二叉树的定义 二叉树的性质 二叉树的存储结构班 级：计算机系02级基本要求： 1、了解树的定义及一些术语2、熟练掌握二叉树的定义及结构特性3、熟练掌握二叉树的各种存储结构的特点及适用范围重 点：掌握二叉树的定义、性质及存储特点教学过程：第六章 树 本章主要内容有：树的定义及术语；二叉树的定义、性质和存储结构；二叉树的遍历，二叉树和树之间的转换，二叉树的应用。学习要点：1、了解树的定义及一些术语2、熟练掌二叉树的定义及结构特性3、熟练掌握二叉树的各种存储结构的特点及适用范围4、遍历二叉树是二叉树各种运算的基础，要熟练掌握各种遍历的递归写法，了解

42、非递增归写法，同时注意栈的应用5、能简单运用遍历算法实现二叉树的其它运算6、熟练掌握树与二叉树之间的转换7、掌握二叉树的两种应用二叉排序树、哈夫曼树61树的基本概念特点：例1、根2、子树3、子树定义：树是n（n0）个结点的有各集合，其定义如下：有且仅有一个称根的结点；其佘结点分为m（m=0）个互不相交的非空集合T1，T2Tm,这些集合又是一棵树，称为根的子树。术语： 结点的度：子树数目。 叶子（终端结点）：度为0的结点。 分支点（非终端结点）：度大于0的结点。 树的度：所有结点度的最大值。 父结点（双亲）：结点的直接前趋为该结点的双亲（最多一个）。子结点（孩子）：结点的直接后继为该结点的孩子（

43、多个）；兄弟：父结点相同的的结点间互称兄弟。子孙：一棵树或子树上的任何结结点（除根外）称为根的子孙。祖先：B是A的子孙，则A为B的祖先。结点的层数：根层为1，则向下每层加1。树的高度（深度）：最大层数。结点数据元素。边元素间的关系。树的表示形式：树型表示法、嵌套集合表示法、凹入表示法树的基本运算：（略）62二叉树 另一种重要的树型结构二叉树的基本概念： 定义：结点的有穷集合，它或者为空、或者满足以下两个条件：1、有且仅有一个根结点；2、其佘分为两个互不相交的集合T1、T2，T1和T2又都是二叉树，分别称为左子树和右子树。区别：可以为空。右左子树不能颠倒。 二叉树的五种基本形态： 二、二叉树的性

44、质：性质1：第i（i=1）层上至多有21-1个结点。性质2：深度为K（K=1）的二叉树至少有2k-1个结点。性质3：任何二叉树,具有：n0=n2+1。满二叉树：深度为K具有2K-1个结点的二叉树。完全二树：结点从上下，从左右分配的二叉树。性质4：N个结点的完全二树深度为|logn|+1性质5：一棵二叉树按层编号，对编号i(11,双亲编号i/2;(2)、2*in，X无左孩子（且无右孩子）；否则左孩子的编为2i；(3)、若2*i+1n,X无右孩子；否则右孩子的编号为2*i+1。三、二叉树的存储结构 顺序存储、链式存储。二叉树的顺序存储适合于完全二叉树，对于一般二叉树要先进行完全化，然后存储。举例：

45、1、完全二叉树的情形2、一般二叉树的情形 特别注意完全化后，存储。 2、二叉树的链式存储结构二叉链表、三叉链表语言描述： typedef struct node datatype data; struet node *lchild,*rclild; bintnode; typedef bintnode * bintree; 举例：见图6.10 注意：根指针作业：Page97的6.1、6.3、6.4、6.6教学内容： 上机题 目：元素的逆序输出后依次出栈，观看元素的变化。目的掌握栈的各种基本操作。基本要求：1、利用栈实现 2、存储结构自选 3、实验报告重点要写实验收获 教学内容：6.3 二叉树的

46、遍历班 级：计算机系02级基本要求： 1、了解遍历是二叉树各种运算的基础 2、掌握二叉树的三种遍历方法、会写出各种遍历序列3、掌握三种遍历方法的递归算法重 点：二叉树的三种遍历方法 理解三种遍历的递归算法难 点：三种遍历的递归算法，关键是遍历过程中“栈”的状态教学过程：63二叉树的遍历叉树的遍历方法： 定义：指以一定规律走遍树中的每个结点，使每个结点被访问一次而且仅被访问一次。先根遍历（TLR）若二叉树为空，则退出；否则依次作如下操作： = 1 * GB3 、访问根结点 = 2 * GB3 、先根遍历右子树（递归） = 3 * GB3 、先根遍历右子树（递归） 举例：说明先根（TLR）的思想

47、（图略）算法：Void preorder(bintree r) if (r!=NULL) visit( r); /访问根结点preorder(rLchild);/ 先根遍历右子树（递归）preorder(rrchild);/ 先根遍历右子树（递归） 非递归写法：Void preorder(bitreptr *r)if (rNuLL) top=1; stacktop=r; wlile (top0) s=stacktop;top-;while (sNULL) do write(sdata); if (srchildNULL) stack(top+)=srchild; s=slchild 2、中根遍

48、历（LTR）若二叉树为空，则退出；否则依次作如下操作： = 1 * GB3 、中根遍历右子树（递归） = 2 * GB3 、访问根结点 = 3 * GB3 、中根遍历右子树（递归） 举例：说明中根（LTR）的思想3、后根遍历（LRT） 介词了以上三种遍历以后，我们考虑一个问题：给定一棵二叉树的TLR序列和LTR序列能否唯一确定一棵二叉树？给定LTR和LRT呢？给定TLR和LRT呢？作业：6.10、6.11、6.12 教学内容：6.5 树和林6.6 哈夫曼树及其应用班 级：计算机系02级基本要求： 1、了解树和林的遍历方法 2、掌握树与二叉树之间的相互转换3、了解树的各种存储方法4、了解哈夫曼树

49、的特性，掌握建立哈夫曼树和哈夫曼编码的方法重 点： 掌握树与二叉树之间的相互转换教学过程：65 树和林一、树、林与二叉树的关系：树 二叉树二叉树的存储形式较简单，便于操作。1）、树二叉树方法： = 1 * GB3 、兄弟之间连线 = 2 * GB3 、除最左孩子外取消双亲和其它孩子的连线 = 3 * GB3 、旋转 举例：（略） 特点：树转换为二叉树时，右子树为空 2）、二叉树-树 方法：自已总结 举例：（略）森林树的集合1）、林-二叉树关键：将各棵树的根看作为兄弟方法：每棵树都变为二叉树，然后各根以兄弟相连旋转。2）、二叉树-林首先从右子树判断此林由几棵树组成，然后将每棵转换成对应的二叉树二

50、、树的存储结构三种常用的存储结构：孩子链表表示法、孩子兄弟链表表示法、双亲表示法。孩子链表表示法基本思想：将每个结点的孩子建立一个链表（带头结点）为了便于存取，将所有表头结点作为一个向量。 语言描述：typedef struct datatype data; struct node *next;headnode;headnode Tn;孩子兄弟表示法：注意：与二叉树之间的关系。双亲表示表示：树的遍历先根遍历若树非空，则 = 1 * GB3 、访问根结点 = 2 * GB3 、依次先根遍历根的各子树后根遍历若树非空，则 = 1 * GB3 、后根遍历各子树 = 2 * GB3 、访问根结点层次遍

51、历 = 1 * GB3 、若树非空，访问根结点 = 2 * GB3 、若1i层上的结点已被访问，且第I+1层结点尚未访问，则从左右依次访问。67哈夫曼树一、名词路径：外外路径长度：加权外路径长度：WPL=Pi*Li;WPL平均比较次数 Pi概率 Li路径长度 哈夫曼树：WPL最小的二叉树 （）（）（） (a图) (b图)如下图：11 3 2 4 11 3*3+2*4*2+11=34 （3+2+4+11）*2=40结论：外路经长度最短的二叉树并非加权路经长度最短。问题：如何构造加权经长度最短的扩充二叉树（最佳二叉树）（哈夫曼树）二、哈夫曼算法思想：首先找出两个最小的要值W1和W2，求W1+W2，

52、设为W0然后对M-1权值W、W、W、WN来解这个问题，如此继续，直至所有的WI都成为外结点的权。例：权2、3、5、7、11、13、17三、哈夫曼树的应用在字符编号上的应用eg:D=S、R、P、O、T W=10、29、4、9、5电文：0001100101011100 作业：6.20、6.21 教学内容： 第七章 图 71图的定义和术语 讲前章的作业题班 级：02级基本要求：了解图的一些名词、概念重 点：一些重要概念：图的定义、分类、连通图、连通分量、强连通图、强连通图分量教学过程：第七章 图本章学习要点：1、弄清图的一些定义、概念2、熟悉图的两种存储结构3、掌握图的深度优先和广度优先遍历方法 4

53、、了解图的最小生成树、拓朴排序两种应用，并会产生最小生成树及拓朴序列71图的定义和术语图G是由两个集合V（G）和E（G）组成，记作：G=（V，E），其中：V（G）是顶点的非空有限集合E（G）是边的有穷集合，而边是顶点的无序对或有序对。无向图：边是顶点的无序对。有向图：边是顶点的有序对。举例：无向图G1的表示形式 （V1，V2）边有向图G2的表示形式 V1，V2孤若V1，V2是一条孤，则V1是孤的尾或初始点V2是孤的头或终端点无向图中边的最大数为n*(n-1)/2有向图是边的最大数为n*(n-1)相邻结点：若（V1，V2）或V1，V2E，则称V1，V2为相邻结点。相关联的边：有边（V1，V2），

54、则边为与结点V1，V2相关联的边。度：与该顶点相关联的边的数目。入度：以该顶点为头的孤的数目。出度：以该顶点为尾的孤的数目。边与各顶点度之间的关系 E=(d1+d2+dn)/2子图：图G=（V，E），G=（V，E），若V V，E E，并且E中的边所关联的结点都在V中，则G是G的子图。路径：VpVq之间存在一顶点序列（Vp，Vi1，Vi2，Vi3，Vin，Vq），并且相邻顶点 （Vp，Vi1）、（Vi2，Vi3）、（Vin，Vq）都在E中，称为从VpVq存在一条路径。 回路：Vp=Vq的路径。又称环。连通：对无向图，若从Vi到Vj有一条路径，则称Vi、Vj连通。连通图：若对任意结点之间都有路径，

55、则称图是连通图。连通分支：图的最大连通子图。 两个连通分支：V1、V2、V3、V4 V5、V6 生成树（连通图）：含全部顶点的一个极小连通子图。（边数最少，n-1）上次作业中的一些问题：1、6.4 2、6.103、6.204、6.21教学内容：72图的存储结构 邻接矩阵存储班 级：02级基本要求：1、掌握图的邻接矩阵存储，元素的存储、关系的存储 2、掌握图的建立、一些简单运算的实现重 点：采用邻接矩阵图的建立难 点：语言描述（元素、关系）教学过程：72图的存储结构 邻接矩阵表示法图有两种主要的存储结构 邻接表表示法一、邻接矩阵表示法1、基本思想：图中结点信息用一个向量来存储元素之间的关系用一个

56、二维数组来存储，二维数组定义如下： 设G=（V，E）是一个图，其中V具有n个结点。G的邻接矩阵是一个具有下述性质的n阶方阵： 1 若（vi,vjE）或E Aij= 0 反之 V1V2 V4 V3无向图G1例： 0 1 0 1 1 0 1 1 0 1 0 1 度 1 1 1 0 对称性 A1= V1 V2 V3 有向图G20 1 00 1 1 出度0 0 0 入度不对称A2=带权图： wij 若（vi,vjE）或EAij= 反之2、图的邻接矩阵建立算法类型描述如下：访问形式：graph gh;gh.vexs 存放顶点信息gh.arcs 存放关系typedef struct datatype ve

57、xsmax; int edgesmaxmax;Mgraph;算法：void createMgraph(Mgraph *G)/考虑为什么用指针作为函数参数int I,j,k,n,e; scanf(“%d,%d”,&n,&e); for(I=0;IversI=getchar(); For(I=0;In;I+) /矩阵初始化For(j=0;jedgesIj=0;For(k=0;kedgesIj=1; G-edgesjI=1; 思考：主函数如何调用上述函数？3、总结：( 1）对称性（2）空间复杂度O（n2）（3）判断两顶点是否有边相关联、结点的度、入度、出度易求 ID（Vi）=Aji （j=1，n）

58、OD（Vi）=Aij （j=1，n） TD（Vi）=Aij （j=1，n）（4）存储空间只与结点数有关，而与边数无关，当enext=ghi.link; /*在相应的链表中作前插操作 ghi.link=p; 思考：主函数如何调用上述函数？作业：7.2、7.3教学内容：73图的遍历74生成树和最小生成树76拓朴排序班 级：02级基本要求：1、掌握图的两种遍历方法 2、了解图的两种不同应用重 点：图的遍历序列、最小生成树的生成、拓朴序列难 点：遍历算法教学过程：73图的遍历遍历：按照一定的规则对图中的结点进行访问，而且每个结点仅被访问一次。方法： 深度优先遍历 广度优先遍历一、深度优先遍历1、基本思

59、想：给定一连通图，从图中某个结点V1出发，首先访问出发点V1，然后任选一个V1的未被访问过的邻接点V2，以V2为新的出发点继续进行深度优先遍历，直到图中所有结点都被访问过。（递归定义） 例： 访问序列：V1 V2 V4V8 V5 V6 V3 V7 不唯一若给定一种存储顺序，则计算机给出一种遍历序列。2、算法实现：存储选择：邻接表类型描述：为了操作方便，不考虑结点信息，只考虑结点编号。附加一标志位数组Markn，以标识未被访问过的结点。分析过程：（略）Void dfs(adj_list gh,int v)markv=1; visit(v); w=ghv-next; while(w!=NULL)

60、if(markw-data=0)dfs(gh,w-data); w=w-next; 二、广度优先遍历1、基本思想：给定一连通图，从图中某个结点V1出发，在访问了V1之后依次访问V1的所有邻接点；然后分别从这些邻接点出发按广度优先遍历图的其它结点，直到所有结点都被访问到。例：给定上图，其遍历序列：V1V2 V3 V4 V5 V6 V7V8 2、算法实现存储选择：邻接表类型描述：为了操作方便，不考虑结点信息，只考虑结点编号。附加一标志位数组Markn，以标识未被访问过的结点。为了顺序访问路径长度为2、3、的结点，需附设队列以存储已被访问过的结点。Void bfs(adj_list gh,int v