北大数据结构课讲义

会计学1北大数据结构课讲义4.1

栈

栈的定义

栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈S=(a1,a2,…，an)

是按a1,a2,…，an次序进栈的，a1为栈底元素，an为栈顶元素。第1页/共65页栈与递归 递归可使问题及求解步骤的描述变得简洁而清晰。特别是对于复杂问题，用递归方法分析描述，比较自然，利于理解。递归包括递归步骤和终止出口。

递归问题转化为非递归往往要用栈来实现,把在递归中用到的变量入栈出栈,如书上【习题4-4】之9,10第2页/共65页4.7

队列

队列是一种先进先出（FIFO）线性表。只允许在其一端删除元素，即队头（front），只允许在其另一端插入元素，即队尾（rear）。第3页/共65页图4-10顺序队列的插入和删除操作第4页/共65页……01234……

M-2M-101234M-1M-2::

循环队列

把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列。入队时需先修改入队指针（队尾指针）

rear==(rear+1)%QueueMaxSize出队时需要修改队头指针front==(front+1)%QueueMaxSize第5页/共65页

初始时,队列为空,有

front=0rear=0测试队列为空的条件是

front=rear1Mabcdfrontrearad约定

rear指出实际队尾元素所在的位置,front指出实际队头元素所在位置的前一个位置.第6页/共65页

队列的静态数组一般是循环使用的。 为了判别队列满和队列空的指针状况，令front指向队首元素的前一个位置。 入队时需先修改入队指针（队尾指针）

rear==(rear+1)%QueueMaxSize

然后判断队列满的条件

(rear+1)%QueueMaxSize==front

最后将元素入队。 出队时先 判断队列空的条件

front==rear

然后修改队头指针

front==(front+1)%QueueMaxSize

最后将元素出队。第7页/共65页第8页/共65页在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素时间复杂度为：O(1)若存储队列的数组的长度为N，则队列长度（即所含元素个数）为:(N+rear-front)%N第9页/共65页（2）队列的链式存储结构

structLinkQueue{ LNode*front; LNode*rear; }; structLNode{ ElmeTypedata; LNode*next; };structLNode{ElemType data;//数据域

Lnode* next;//指针域

};

第10页/共65页第11页/共65页在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为：O(1)第12页/共65页4.4.4

队列运算的实现1.队列运算在顺序存储结构上的实现 （1）初始化队列

voidInitQueue(Queue&Q) { Q.MaxSize=10; Q.queue=newElemType[Q.MaxSiize]; Q.front=Q.rear=0; }

第13页/共65页

（2）将队列清空,并释放动态存储空间

voidClearQueue(Queue&Q) { if(Q.queue!=NULL)delete[]Q.queue; Q.front=Q.rear=0; Q.queue=NULL; Q.MaxSize=0; }

第14页/共65页（3）检查队列是否为空

intQueueEmpty(Queue&Q) { returnQ.front==Q.rear; }（4）读取队头元素//让front指针不是指向队首元素，而是指向它的前一个位置即：队首元素是队首指针front的下一个位置中的元素

ElemTypePeekQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"QueueisEmpty."<<endl; exit(1);} returnQ.queue[(Q.front+1)%QueueMaxSize]; }第15页/共65页（5）向队列插入新元素-1voidEnQueue(Queue&Q,constElemType&item){ intk=(Q.rear+1)%QueueMaxSize;//队尾的下一位置

if(k==Q.front){ cerr<<"Queueisoverflow."<<endl; exit(1); } Q.rear=k; Q.queue[k]=item;}入队时需先修改入队指针（队尾指针）

rear==(rear+1)%QueueMaxSize然后判断队列满的条件

(rear+1)%QueueMaxSize==front最后将元素入队。第16页/共65页（5）向队列插入新元素-2voidEnQueue(queue&Q,constElemType&item){ if((Q.rear+1)%QueueMaxSize==Q.front)

{//扩大2倍的存储空间

intk=sizeof(ElemType); Q.queue=(ElemType*)realloc(Q.queue, 2*Q.MaxSize*k); //把原队列尾部内容后移MaxSize个位置

if(Q.rear!=Q.MaxSize-1) 第17页/共65页{ for(inti=0;i<=q.rear;i++) Q.queur[i+Q.MaxSize]=Q.queur[i]; Q.rear+=Q.MaxSize; } Q.MaxSize=2*Q.MaxSize;

} //求出队尾的下一个位置

Q.rear=(Q.rear+1)%Q.MaxSize; //把item的值赋给新的队尾位置

Q.queue[Q.rear]=item;}入队时需先修改入队指针（队尾指针）

rear==(rear+1)%QueueMaxSize然后判断队列满的条件

(rear+1)%QueueMaxSize==front最后将元素入队。第18页/共65页（6）从队列中删除元素ElemTypeOutQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"Queueisempty."<<endl; exit(1); } Q.front=(Q.front+1)%QueueMaxSize;//队头指向下一位置

returnQ.queue[Q.front];}（7）检查队列是否已满intQueueFull(Queue&Q){ return(Q.rear+1)%QueueMaxSize==Q.front;}出队时先判断队列空的条件

front==rear然后修改队头指针

front==(front+1)%QueueMaxSize最后将元素出队。第19页/共65页

2.队列运算在链接存储结构上的实现（1）初始化链队voidInitQueue(LinkQueue&HQ){ HQ.front=HQ.rear=NULL;}（2）清空链队voidClearQueue(LinkQueue&HQ){ LNode*p=HQ.front; while(p!=NULL){ HQ.front=HQ.front->next; deletep; p=HQ.front; } HQ.rear=NULL;}structLNode{ElemType data;//数据域

Lnode* next;//指针域

};

第20页/共65页（3）判断链队是否为空intQueueEmpty(LinkQueue&HQ){ returnHQ.front==NULL;}（4）读取队首元素ElemTypePeekQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } returnHQ.front->data;}第21页/共65页（5）向链队中插入一个元素voidEnQueue(LinkQueue&HQ,constElemType&item){ LNode*newptr=newLNode; if(newptr==NULL){ cerr<<“Memoryalocationfailure."<<endl; exit(1); } newptr->data=item; newptr->next=NULL; if(HQ.rear==NULL) HQ.front=HQ.rear=newptr; elseHQ.rear=HQ.rear->next=newptr;}//不妨与书上P78的算法9(ppt4,算法9)：向单链表的末尾插入一个元素“相对照学习//思考与书上P137的算法2(ppt6,算法5)：向链栈中插入一个元素“的不同第22页/共65页（6）从队列中删除一个元素ElemTypeOutQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } ElemTypetemp=HQ.front->data; Lnode*p=HQ.front; HQ.front=p->next; if(HQ.front==NULL) HQ.rear=NULL; deletep; returntemp;}//不妨与书上P79的算法10(ppt4,算法12)：从单链表中删除表头元素“相对照学习//也可对照书上P137的算法3(ppt6,算法6)：从链栈中删除一个元素”第23页/共65页4.4.6

队列应用简介第一：解决主机与外设之间速度不匹配的问题如： 打印输出。设置一个打印数据缓冲区，用队列存储待输出的数据，解决主机与外设速度不匹配的问题。第二：解决多用户引起的资源竞争问题如： 多用户CPU资源竞争。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列第24页/共65页1.

熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.熟悉队列的含义，掌握基本概念、存储结构和运算的实现。本章学习要点第25页/共65页本章习题(第173－177页)(!!)4.1.1~4.1.4请独立完成该题4个问题(!!)4.2请独立完成该题(#)4.3课外思考该题(!)4.4.1~2,7能在书上程序的基础上编写程序实现(#)4.4.3~6,8~11有兴趣者课外思考第26页/共65页

书面回答,请以纸面形式上交课代表,要求整洁清楚，

时间期限:5月10日[格式提头:学号/序号/姓名/第四章]1、对于一个栈，如果输入项序列由A，B，C组成，给出全部可能和不可能的输出序列。2、设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a6,a7,a5,a8,a4,a2,a1，则栈S的容量至少应该是多少？（即至少应该容纳多少个元素？）3、设有算术表达式x+a*(y-b)-c/d，将其转换为后缀表达式。4、有字符串序列为3*-y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。（用X代表扫描字符串函数中顺序取一字符进栈的操作，S代表从栈中取出一个字符加入到新字符串尾的出栈操作。）例如，ABC变为BCA，则操作步骤为XXSXSS。5、假设Q[0..10]是一个线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（要求明确标出各元素在队列中的位置序号，头、尾指针）

(a)d,e,b,g,h入队

(b)d,e出队

(c)i,j,k,l,m入队

(d)b出队

(e)n,o,p入队课后作业第四章第27页/共65页约定:进栈X,出栈S4个元素依次进栈,任何时候都可以出栈,请写出所有可能的出栈序列XXXXSSSSXXXSXSSSXXXSSXSSXXXSSSXSXXSXXSSSXXSXSXSSXXSXSSXSXXSSXSXSXXSSXXSSXSXSXSXSXSXXXSSSXSXXSXSSXSXXSSXSXSXSXXSS方法提示第28页/共65页第五章树

5.1树的概念

5.2二叉树

5.3二叉树的遍历

5.4二叉树的其他运算

5.5树的存储结构和运算退出第29页/共65页校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂第30页/共65页(根目录)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………第31页/共65页例3第32页/共65页例4

au

ee

cn

edutsinghua

cspandabuaapku………………第33页/共65页一个数据元素:一个结点A数据元素(结点)之间的关系:分支AB第34页/共65页5.1树的概念

5.1.1

树的定义

树Tree：是由n0个结点组成的有穷集合以及结点之间关系组成的集合构成的结构。

递归的数据结构树的递归定义： （1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树； （2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m(m≥0)个互不相交的子集，每个子集也是一棵树，称为子树SubTree。第35页/共65页第36页/共65页tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r} ElemType是具有相同特性的数据元素。 关系r满足： （1）有且仅有一个结点没有前驱，这个结点即树根； （2）除树根外，其余结点有且仅有一个前驱； （3）包括根结点在内的所有结点都可以有任意个(含0个)后继。如上图：K={A，B，C，D，E，F，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}第37页/共65页JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树树(逻辑上)的特点1.有且仅有一个结点没有前驱结点,该结点为树的根结点。2.除了根结点外,每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。第38页/共65页

5.1.2

树的表示 树有五种表示方式： （1）树形表示， （2）二元组表示， （3）集合图表示， （4）凹入表表示， （5）广义表表示。第39页/共65页JIHGFEACXB1.

树形表示法

借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。第40页/共65页tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r}如上图：K={A，B，C，D，E，F，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}2.

二元组表示法

第41页/共65页第42页/共65页1.

结点的度：2.

树的度：3.

叶结点：4.

分支结点:5.

层次的定义:JIHGFEACXB该结点拥有的子树的数目。树中结点度的最大值。度为0的结点.度非0的结点.

根结点为第一层,若某结点在第i层,

则其孩子结点(若存在)为第i+1层.5.1.3树的基本术语第1层第2层第3层第43页/共65页7.

树林(森林):m0棵不相交的树组成的树的集合.8.

树的有序性:ABCDEABCDEFF6.

树的深度:树中结点所处的最大层次数.

若树中结点的子树的相对位置不能随意改变,则称该树为有序树，否则称该树为无序树。JIHGFEACXB有序树？无序树？深度为3的树第44页/共65页5.1.4

树的性质性质1

树中结点个数等于所有结点的度数加1。性质2

度为k的树中第i层上至多有ki-1个结点（i≥1）。性质3

深度为h的k叉树中至多有(kh-1)/(k-1)结点。

满k叉树：结点个数等于(kh-1)/(k-1)的k叉树。性质4

具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。JIHGFEACXB第45页/共65页5.2二叉树

5.2.1

二叉树的定义

二叉树为度为2的有序树。第46页/共65页

递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。 左孩子leftchild，左子树的根结点。 右孩子rightchild，右子树的根结点。第47页/共65页二叉树的基本形态：(空)根根左子树根右子树根左子树右子树

(a)空二叉树；

(b)仅有一个根结点的二叉树；

(c)右子树为空的二叉树；

(d)左右子树均非空的二叉树；

(e)左子树为空的二叉树。

第48页/共65页

1.度为2的树是二叉树。下面两种说法正确与否?应该怎样说才合适?

2.具有三个结点的树可以有以下五种形态:结论:子树有严格的左右之分的度为2的树是二叉树。

结论:具有三个结点的树只有两种形态。第49页/共65页两种特殊形态的二叉树

若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树

若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树第50页/共65页1.一棵非空二叉树的第i层最多有2i–1个结点(i1)。证明(采用归纳法)(1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有一个结点,即树的根结点.(2).假设对于第j层(1ji–1)结论也正确,即第j层最多有2j-1个结点.(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第i–1层的每个结点都有两棵非空子树,则第i层的结点数目达到最大.而第i–1层最多有2i–2个结点已由假设证明,于是,应有

22i–2=2i–1证毕.5.2.2二叉树的性质第51页/共65页2.

深度为h的非空二叉树最多有2h-1个结点.证明:

由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有

20+21+22+…+2i-1+…+2h-1=2h-1证毕.第52页/共65页3.

若非空二叉树有n0个叶结点,有n2个度为2的结点,

则n0=n2+1

证明:

设该二叉树有n1个度为1的结点,结点总数为n,有

n=n0+n1+n2

--------(1)

设二叉树的分支数目为B,有

B=n-1

--------(2)这些分支来自度于为1的结点与度度为2结点,即

B=n1+2n2

--------(3)联列关系(1),(2)与(3),可得到

n0=n2+1证毕.4.

具有n个结点的完全二叉树的深度h=log2n+1.证明:(略)推论：

n0=n2+2n3+3n4++(m-1)nm+1第53页/共65页5.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为i的结点具有以下性质:(1)若编号为i的结点有左孩子,则左孩子结点的编号为2i;

若编号为i的结点有右孩子,则右孩子结点的编号为2i+1.(2)除树根结点外,若一个结点的标号为i,则它的双亲结点的 编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,

它是双亲结点的左孩子,当i为奇数时,其双亲结点的编号 为(i-1)/2,它是双亲结点的右孩子.(3)若i≦|_n/2_|,即2i≦n,则编号为i的结点为分支结点,

否则为叶子结点.(4)若n为奇数,则每个分支结点都既有左孩子,又有右孩子;

若n为偶数,则编号最大的分支结点(编号为n/2)只有 左孩子,没有右孩子,其余分支结点左、右孩子都有.第54页/共65页12345678910n=10第55页/共65页换个说法5.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为i的结点具有以下性质:(1)当i=1,则编号为i的结点为二叉树的根结点;

若i>1,则编号为i的结点的双亲结点的编号为i/2.(2)若2i>n,则编号为i的结点无左子树;

若2in,则编号为i的结点的左子树的根的编号为2i.(3)若2i+1>n,则编号为i的结点无右子树;

若2i+1n,则编号为i的结点的右子树的根的编号为2i+1.第56页/共65页5.2.3

二叉树的抽象数据类型

ADTBinaryTree Data：存储类型BTreeType，用BT标识符表示

Operations：

voidInitBTree(BTreeType&BT); //初始化一棵二叉树，即置为空树

voidCreateBTree(BTreeType&BT,char*a); //根据字符串a建立一棵二叉树

intBTreeEmpty(BTreeTypeBT); //判断一棵二叉树是否为空树

voidTraverseBTree(BTreeTypeBT); //按照一定次序遍历二叉树

intBTreeDepth(BTreeTypeBT); //求一棵二叉树的深度

voidPrintBTree(BTreeTypeBT); //按照一种表示方法输出二叉树