课件-数据结构

上堂课要点回顾栈栈的定义、特征*、抽象数据类型顺序栈类及实现SeqStack.h单链栈类及实现LinStack.h栈的应用*1、计算算术表达式的值第六次课阅读：，第133-153页（递归），第64-83页（队列）练习：作业53.2

栈的应用3、实现递归算法（运行时栈）P133~153多个函数的嵌套调用例：main()sub1(

) sub2(

) sub3(

)RSTTSR需要保存返回地址后调用先返回采用栈保存存：R，S，T取：T，S，R递归(recursive)函数——是自己（直接或间接地）调用自己的函数例2：2阶Fibonacci数列的递归定义n

0n

1Fib(n1)

Fib(n

2) n

10Fib(n)

1n

0n

Fact(n

1)

n

0Fact(n)

1例1：阶乘的递归定义递归示例：n!递归函数必须包含一个递归出口。递归调用部分所使用的参数值应比函数的参数值要小，以便重复调用能最终获得基本部分所提供的值。n

0n

Fact(n

1)

n

0Fact(n)

1long

fact(int

n)//使用循环迭代方法，计算n!的函数{

long

m=1;int

i;if(n>0)for(i=1;i<=n;i++)m=m*i;return

m;}//时间复杂度：O(n)long

Fact(int

n){

long

y;if

(n<0)

reurn

-1;if

(n==0)

return

1;else{

y=Fact(n-1);return

n*y;}}//时间复杂度：O(n)递归示例：2阶斐波那契数列递归函数必须包含一个递归出口。递归调用部分所使用的参数值应比函数的参数值要小，以便重复调用能最终获得基本部分所提供的值。n

1Fib(n

1)

Fib(n

2)

n

1Fib(n)

1int

fibonacci(int

n)0

n

0

{if(n==0)

return

0;if(n==1)

return

1;int

oneBack=1;int

twoBack=0;for(int

i=2;i<=n;i++){ int

current=oneBack+twoBack;twoBack=oneBack;oneBack=current;}returncurrent;}//时间复杂度：O(n)int

Fibonacci(int

n){ if(n==0)

return

0;if(n==1)

return

1;

return

Fibonacci(n-1)+Fibonacci(n-2);}//时间复杂度为O(2n)递归原理每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配

空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈——递归工作栈组织。局部变量返回地址参数活动记录框架递归工作记录main(

)4

ny=Fact(3)返回4*63

ny=Fact(2)返回3*2y=Fact(1)返回2*1y=Fact(0)Fact(4)2

n

1

n

0

n返回1递归调用子递归调用子递归调用子递归调用子程序Fact(3)

程序Fact(2)

程序Fact(1)

程序Fact(0)结果返回返回1*1结果返回结果返回结果返回结果返回int

Fact(int

n){

int

y;if

(n<0)

return

-1;if

(n==0) return

1;else{

y=Fact(n-1);return

n*y;}}void

main(

){

int

fn=Fact(4);cout<<fn;}main(

)4

ny=Fact(3)返回4*63

ny=Fact(2)返回3*2y=Fact(1)返回2*1返回1*1Fact(4)2

n

1

n

0

ny=Fact(0)

返回1结果返回结果返回结果返回结果返回结果返回ny

Fact434n

n234n1234y

Fact

y

Fact

y

Fact

ny

Fact011234ny

Factny

Fact3264ny

Fact4

6

24ny

Fact递归调用子递归调用子递归调用子递归调用子程序Fact(3)

程序Fact(2)

程序Fact(1)

程序Fact(0)ny

Fact11121223344适宜于用递归算法求解的问题的充分必要条件是：问题可借用类同自身的子问题进行描述；某一有限步的子问题（也称作本原问题）有直接的解存在。当一个问题存在上述两个基本要素时，该问题的递归算法的设计方法是：把对原问题的求解设计成包含有对子问题求解的形式；设计递归出口。3.3

队列队列（Queue）的基本概念定义：限定所有的操作在表的一端进行，而删除操作在表的另一端进行的线性表。a0

a1

…an-1队头队尾/入队a0,a1

,

…

,

an-1例：

删除/出队a0,a1

,

…

,

an-1特征：先进先出（InOut,

FIFO）3.3.2

队列的抽象数据类型ADT

Queue数据元素：ai，i=0,1,…,n-1

(n≥0)，类型为DataType结构：对所有的数据元素ai

(0≤i≤n-2)存在次序关系<ai，ai+1>, a0无前趋，an-1无后继。逻辑操作：设Q为Queue

型Initiate(Q)

//构造一个空队列Q。NotEmpty(Q)/*判断队列Q非空否，若Q非空，则返回1，否则返回0。*/入一值为xAppend(Q,x)

/*在队列Q的队的元素。*/Delete(Q)/*删除队列Q的队头元素，被删除的队头元素通过函数带回。*/GetFront(Q)//取队列Q的队头元素并由函数返回。约定队头指示器指向实际队头元素；队尾指示器指向实际队尾元素的下一个位置例如：MaxQueueSize-101n-1……frontrearna0a1…an-1…3.3.3

顺序队列顺序队列入队、出队时指针的变化情况：队空frontrear元素A、B、C入队后443rear322110front0CBA顺序队列入队、出队时指针的变化情况（续）：front43210rearEDA、B、C出队，队空43210rearfront元素D、E入队，队满F入队，“假溢出”CBA为解决“假溢出”现象，将队列设想成环形。3.3.4

顺序循环队列0frontDrear123E44front

32rear10EDF顺序循环队列入队、出队时指针的变化0frontDrear123E40frontDrear13E4FG2H0Dfrontrear123E4顺序循环队列入队、出队时指针的变化①入队描述：rear++；if

(rear==MaxQueueSize)rear=0；还可利用数学上的“模(%)运算”来实现上述过程：rear＝(rear+1)

%

MaxQueueSize

；②出队描述：front++；if

(front==MaxQueueSize)front=0；还可利用数学上的“模(%)运算”来实现上述过程：front＝(front+1)

%

MaxQueueSize；如何判队满、队空？01frontMaxQueueSize-1rear队空解决方法：设置计数器count，表示表长当count>0

&&

rear==

front

时，队满当count==0

时，队空front==rear队满？队空？MaxQueueSize-101front

rear队满顺序队列类定义：class

Se

ueue{private:DataType

data[MaxQueueSize];//顺序队列数组//队头指示器，指向实际队头元素位置*///队尾指示器，指向实际队尾元素的下一个位置*///当前表长intfront;int

rear;intcount;Public:ueue(void)

{front

=

rear

=

0;

count

=

0;};//构造函数Se~Se

ueue(void){};void

Append(const

DataType&

item);DataType

Delete(void);DataType

GetFront(void)const;//析构函数//入队列//出队列//取队头数据元素//非空否int

NotEmpty(void)

const

{return

count

!=

0;};};#define

MaxQueueSize

<队列允许存放的最大元素数>typedef

char

DataType;S

ueue.h文件实现顺序循环队列类【顺序循环队列的入队算法】void

Se ueue::Append(const

DataType&

item)//把数据元素item

队列作为当前的新队尾{if(count

>

0&&

front

==

rear){ cout<<"队列已满!"<<endl;data[rear]

=

item;exit(0);

}//把元素item加在队尾rear

=

(rear

+1)

%

MaxQueueSize;//队尾指示器加1count++;//计数器加1}【顺序循环队列的出队算法】DataType

Se

ueue::Delete(void)//把队头元素出队列，出队列元素由函数返回{if(count

==

0){ cout

<<

"队列已空!"

<<

endl;

exit(0);

}DataType

temp

=

data[front];front

=

(front

+

1)

%

MaxQueueSize;//保存原队头元素//队头指示器加1count--;return

temp;//计数器减1//返回原队头元素}【顺序循环队列的取队头算法】ueue::GetFront(

)

constDataType

Se{if(count

==

0){ cout<<“队列已空!"<<endl;exit(0);

}return

data[front]；}3.3.5

单链队列及其实现逻辑描述frontdata

next……队尾结点rear∧frontrear∧空链队列满足Q->front==Q->rear非空链队列：空链队列：删除队头位置结点位置a0an-1//定义类LinQueue<T>为友元//指针//数据元素{ friend

class

LinQueue<T>;private:QueueNode<T>

*next;T

data;public://构造函数

（不含头结点）QueueNode(const

T&

item,

QueueNode<T>

*ptrNext

=NULL)

:data(item),

next(ptrNext){}~QueueNode(){};//析构函数};链队列结点类定义template<class

T>

class

LinQueue;//前视定义,否则友元无法定义template<class

T>class

QueueNode//队头指针//队尾指针//计数器，表长public:LinQueue(void){front=rear=NULL;count

=

0;};//构造函数~LinQueue(void);//析构函数void

Append(const

T&

item);//入队列//出队列//取队头数据元素//非空否T

Delete(void);T

GetFront(void)

const;int

NotEmpty(void)

const{return

count

!=

0;};};链队列类定义template<class

T>class

LinQueue{private:QueueNode<T>

*front;QueueNode<T>

*rear;int

count;【链队列的析构函数】template

<class

T>void

LinQueue<T>::~LinQueue

(

){ QueueNode<T>

*p,

*q;p=front;while(

p!=

NULL){

q=p;p=p->next;delete

q;

}count=0;front=NULL;rear=NULL;}链队列的运算（不结点）newnode∧itemfront…∧∧rearrear->next=newnode;rear=newnode;【链队列的入队算法】template

<class

T>void

LinQueue<T>::Append(const

T&

item)//把数据元素item

队列作为新队尾结点{/*构造新结点newNode，newNode的data域值为item，next域值为NULL*/QueueNode<T>*newNode=new

QueueNode<T>(item);if(rear!=NULL)

rear->next=newNode;//新结点链入rear

=

newNode;//队尾指针指向新队尾结点//若队头指针原先为空则置为指向新结点if(front

==

NULL)

front

=

newNode;count++;//计数器加1}链队列的删除运算（不结点）pfront∧…rearp=front->next;delete(front);front=p;p=NULL∧注意：∧frontrearif

(p==NULL)

rear=NULL;∧【链队列的出队算法】template

<class

T>

T

LinQueue<T>::Delete(void)//把队头结点删除并由函数返回{

if(count

==

0){ cout

<<"队列已空！"

<<endl;exit(0);

}QueueNode<T>*p=front->next;//p指向新的队头结点T

data=front->data;//保存原队头结点的data域值delete

front;front

=

p;//

原队头结点空间//front指向新的队头结点if(front==NULL)rear=NULL;//增加处理rear语句count--;return

data;//计数器减1//返回原队头结点的data域值}【链队列的取队头函数】template

<class

T>DataType

LinQueue<T>::GetFront

(){if(

count==0){ cout

<<"队列已空！"

<<endl;exit(0);

}return

front->data;}3.3.6

队列的应用1、回文问题（P80）以中间字符为基准两边字符完全相同的字符序列称之为回文，编写一个函数判断字符序列是否是回文。例如：A

B

B

AA

B

C

DE

D

C

B

AA

B

C

D

E

DC

A

BABCDEDCBA队列rear->front->ABCDEDCBA栈top->思想：1、自左向右扫描字符串，字符依次进栈S；入队列Q；2、当栈S非空且队列Q非空时，依次若S栈顶元素和Q队头元素相等，则S出栈；Q出队列；否则，输出不是回文，并退出3、输出字符串是回文，并退出算法：P82-83

：采用顺序循环队列。#include

"LinQueue.h"#include

"LinStack.h"void

HuiWen(char

str[]){ LinStack<char>

myStack;LinQueue<char>

myQueue;//求字符序列长度intn

=

strlen(str);for(int

i

=0;

i<n;

i++){

myQueue.Append(str[i]);myStack.Push(str[i]);}while(myQueue.NotEmpty()

&&

myStack.NotEmpty()

){ if(myQueue.Delete()

!=

myStack.Pop()){cout

<<

"不是回文!"

<<endl;

return;}}cout<<"是回文!"<<endl;}3.3.6

队列的应用操作系统中用到队列

1、对CPU的分配管理：进程排队、作业排队一般计算机只有一个CPU，采用一个就绪队列管理CPU的分配。

当多个进程需要CPU运行时，它的进程名就

入到就绪队列的队尾。CPU总是首先执行排在队头的进程。一个进程分配到CPU的一段时间执行完了，又将它 到队尾等待，CPU转而为执行下一个

队头进程。如此，按“先进先出”的原则一直进行下去，直到执行完的进程从队列中逐个删除掉。队列的应用操作系统中用到队列2、主机与外部设备之间通信由于外部设备传输速度远远低于主机传输速度，可以设定一个“输出数据队列缓冲区”

。当主机要输出数据时，将数据按块（例如每块512B）逐个添加到“队列缓冲区”的尾端，写满后就暂停输出，继而去做其它的事情。而外部设备则依其输出速度按照先进先出的原则依次从队首逐个取出数据块输出，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了输出的数据有完全相同的次序，

不致发生输出次序的

或数据的丢失，同时保证了主机的效率。队列的应用◆事件驱动模拟银行业务模拟每个来到的顾客发一个号码，如果哪个柜台空闲了，就叫号码最靠前的顾客来办理业务；如果同时几个柜台

空闲，就按照一种法则来决定这几个柜台叫号的顺序（最简单的是按柜台号码顺序）。这样，就能保证顾客按照先来后到的顺序接受服务——因为大家排在一个队里。航空客运订票系统对于预约客户 数据来说，由于要遵循先到先服务的原则，因此采用队列结构。由于预约人数无法预计，因此队列应以链表作为

结构。电梯模拟……补充题：设数据元素序列{a,b,c,d,e,f,g}的进队列操作和出队列操作可任意进行，请罗列出所有的出队列序列。已知K和max，要求输出K阶斐波那契序列前n+1项（

f0,f1,…,fn），其中fn<=max而fn+1>max（max为给定常数）。算法要求仅采用空间大小为K的数组实现。