数据结构栈和队列.ppt

数据结构,教学目标,【知识目标】 掌握栈的定义及基本运算 掌握顺序栈、链栈基本运算的实现算法 掌握队列的定义及基本运算 掌握循环队列、链队列基本运算的实现算法 【能力目标】 具有恰当的选择栈或队列作为数据的逻辑结构，顺序栈（队列）、链栈（队列）作为数据的存储结构的能力 具有应用栈、队列解决实际问题的能力,引例描述数制转换,将十进制数F转换为B进制数。输入任意一个十进制数，可以是整数，也可以是小数，输出对应进制的数。,演示执行,一、栈的定义及基本操作 1.定义 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为出（退）栈。 通常插入、删除的这一端称为栈顶（Stack Top），由于元素的进栈和退栈，使得栈顶的位置经常是变动的，因此需要用一个整型量Top指示栈顶的位置，通常称Top 为栈顶指针；另一端称为栈底。当表中没有元素时称为空栈，即Top=-1。 栈为后进先出（Last In First Out）的线性表，简称为LIFO表。,3.1 栈,知识储备,2栈的基本运算 （1）置空栈：InitStack (S) 构造一个空栈S。 （2）判栈空：StackEmpty (S) 若S为空栈，则返回1，否则返回0。 （3）判栈满：StackFull (S) 若S为满栈，则返回1，否则返回0。 （4）进栈：Push(S，x) 若栈S不满，则将元素x插入S的栈顶。 （5）退栈：Pop (S) 若栈S非空，则将S的栈顶元素删去，并返回该元素。 （6）取栈顶元素：StackTop (S) 若栈S非空，则返回栈顶元素，但不改变栈的状态。,二、顺序栈及基本操作的实现 1顺序栈（Sequence Stack） 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 2顺序栈的描述 #define StackSize 100 /假定栈空间最多为100个元素 typedef char DataType;/假定栈元素的类型为字符类型 typedef struct DataType dataStackSize;/栈元素定义 int top;/栈指针定义 SeqStack; SeqStack *S;/栈定义,注意： 有元素x进栈时，需要先将S-top加1，然后再将元素进栈，即依次完成下列操作：+S-top;S-dataS- top=x;； 当栈顶元素做退栈操作后，需要将S-top减1，即完成操作：S-top-;； 条件S-top=StackSize-1表示栈满；S-top=-1表示栈空； 当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避免； 当栈空时，做退栈运算所产生的溢出现象称为下溢。,3顺序栈上基本运算的算法 （1）置栈空 （2）判栈空 如果栈S为空，则S-top=-1，此时应该返回1，而关系表达式S-top=-1的值为1；如果栈S为非空，则S-top!=-1，此时应该返回0，而关系表达式S-top=-1的值为0，因此，无论怎样只需返回S-top=-1的值。 （3）判栈满 与判栈空的道理相同，只需返回S-top=StackSize-1。 （4）进栈 （5）出栈 （6）取栈顶元素,（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）进栈 int Push(SeqStack *S,DataType x) /进栈 if (StackFull(S) puts(栈满); return 0; S-data+S-top=x; return 1; ,（5）出栈 int Pop(SeqStack *S, DataType *x) /出栈 if(StackEmpty(S) puts(栈空); return 0; *x=S-dataS-top-; return 1; ,（6）取栈顶元素 int StackTop(SeqStack *S, DataType *x) if(StackEmpty(S) puts(栈空); return 0; *x=S-dataS-top; return 1; ,【例3-1】元素a1，a2，a3，a4依次进入顺序栈，则下列不可能的出栈序列是 Aa4, a3, a2, a1Ba3, a2, a4, a1 Ca3, a4, a2, a1Da3, a1, a4, a2 分析：对于A，由于元素a1，a2，a3，a4依次进栈，而a4先出栈，说明a1，a2，a3已经入栈，所以出栈顺序只能是a4，a3，a2，a1，因此A是正确的出栈序列；对于B，C，D，由于都是a3先出栈，说明a1，a2已经入栈，所以a1，a2的相对位置一定是不变的，这就是a2一定在a1之前出栈，比较上述三个答案，只有D中的a1出现在a2的前面，这显然是错误的。因此，答案为D。,【课堂实践3-1】 设计一个选择菜单，根据用户的选择决定对顺序栈进行置空栈、进栈、退栈、取栈顶元素和退出程序的操作。,做 一 做,三、链栈及基本操作的实现 1链栈（Linked Stack） 栈的链式存储结构称为链栈，栈顶指针就是链表的头指针。 2链栈的描述 typedef char DataType;/假定栈元素的类型为字符类型 typedef struct stacknode /结点的描述 DataType data; struct stacknode *next; StackNode; typedef struct /栈的描述 StackNode *top; /栈顶指针 LinkStack;,注意： LinkStack结构类型的定义是为了方便在函数体中修改top指针本身； 若要记录栈中元素个数，可将元素个数属性作为LinkStack类型中的成员定义； 条件S-top= NULL表示空栈，链栈没有栈满的情况。 3链栈上基本运算的算法 （1）置栈空 （2）判栈空 （3）进栈 （4）出栈 （5）取栈顶元素,（1）置栈空 void InitStack(LinkStack *S) /将链栈置空 S-top=NULL; ,（2）判栈空 int StackEmpty(LinkStack *S) return S-top=NULL; ,（3）进栈 int Push(LinkStack *S,DataType x) /将元素x插入链栈头部 StackNode *p=(StackNode *)malloc(sizeof(StackNode); if(p=NULL) puts (内存申请不成功!);return 0; p-data=x; p-next=S-top;/将新结点*p插入链栈头部 S-top=p; /栈顶指针指向新结点 return 1; ,（4）出栈 int Pop(LinkStack *S, DataType *x) /出栈 StackNode *p=S-top;/保存栈顶指针 if(StackEmpty(S) puts(栈空); return 0; *x=p-data; /保存栈顶结点数据 S-top=p-next; /将栈顶结点从链上摘下 free(p); return 1; ,（5）取栈顶元素 int StackTop(LinkStack *S, DataType *x) /取栈顶元素 if(StackEmpty(S) puts(栈空); return 0; *x =S-top-data; return 1; ,【课堂实践3-2】 设计一个选择菜单，根据用户的选择决定对链栈进行置空栈、进栈、出栈、取栈顶元素和退出程序的操作。,做 一 做,3.2 队列 一、队列的定义及基本操作 1队列的定义 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。向队列中插入元素称为入队，从队列中删除元素称为出队。 (1)允许删除的一端称为队头（Front）。 (2)允许插入的一端称为队尾（Rear）。 (3)当队列中没有元素时称为空队列。 (4)队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。,2队列的基本运算 （1）置空队：InitQueue (Q)构造一个空队列Q。 （2）判队空：QueueEmpty (Q)若队列Q为空，则返回1，否则返回0。 （3）判队满：QueueFull (Q)若队列Q为满，则返回1，否则返回0。 （4）入队：EnQueue(Q，x)若队列Q非满，则将元素x插入Q的队尾。 （5）出队：DeQueue (Q)若队列Q非空，则删去Q的队头元素，并返回该元素。 08顺序队列操作.swf （6） 取队头元素：QueueFront (Q)若队列Q非空，则返回队头元素，但不改变队列Q的状态。,二、顺序队列及基本操作 1顺序队列（Sequence Queue） 队列的顺序存储结构称为顺序队列，它是运算受限的顺序表。 2顺序队列的表示 （1）和顺序表一样，顺序队列用一个数组（向量空间）来存放当前队列中的元素。 （2）由于随着入队和出队操作的变化，队列的队头和队尾的位置是变动的，所以应设置两个整型量front和rear分别指示队头和队尾在向量空间中的位置，它们的初值在队列初始化时均应置为0。通常称front为队头指针，称rear为队尾指针。,3顺序队列的基本操作 （1）入队：入队时将新元素插入rear所指的位置，然后将rear加1。 （2）出队：出队时删去front所指的元素，然后将front加1并返回被删元素。 注意： （1）当头尾指针相等时，队列为空。 （2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。,4顺序队列中的溢出现象 （1）“下溢”现象：当队列为空时，做出队操作产生的溢出现象。 （2）“真上溢”现象：当队列满时，做入队操作产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 （3）“假上溢”现象：由于入队和出队操作中，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用。当队列中实际元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。 5解决“假上溢”现象的方法 （1）当出现“假上溢”现象时，把所有的元素向低位移动，使得空位从低位区移向高位区，显然这种方法很浪费时间。 （2）把队列的向量空间的元素位置0Queuesize-1看成一个首尾相接的环形，当进队的队尾指针等于最大容量，即rear=Queuesize时，使rear=0。,三、循环队列 1循环队列（Cirular Queue） 把向量空间的元素位置首尾相接的顺序队列称为循环队列。 2循环队列头尾指针的操作 循环队列Q进行出队、入队操作时，头尾指针仍要加1。当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： （1）利用选择结构 （2）利用模运算 我们将采用此方法实现循环意义下的队头、队尾指针的加1操作。,（1）利用选择结构 if(i+1=QueueSize)/i为Q-front或Q-rear i=0; else i+;,（2）利用模运算 i=(i+1)%QueueSize;/i为Q-front或Q-rear,3循环队列边界条件的处理方法 由于循环队列Q中，无法通过条件Q-front= Q-rear来判别队列是“空”还是“满”。解决这个问题的方法至少有三种： （1）另设一标志变量flag以区别队列的空和满，比如当条件Q-front= Q-rear成立，且 flag 为0时表示队列空，而为1时表示队列满。 （2）少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于队头指针，若相等则认为队满，此时队空的条件是Q-front= Q-rear，队满的条件是(Q-rear+1)%QueueSize= Q-front。 （3）使用一个计数器count记录队列中元素的总数，当Q-count =0时表示队列空；当Q-count =QueueSize时表示队列满。 我们将使用此方法。,4循环队列的描述 #define QueueSize 100 /定义队列最大容量 typedef char DataType; /定义队列元素类型 typedef struct cirqueue DataType dataQueueSize;/队列元素定义 int front;/队头指针定义 int rear;/队尾指针定义 int count;/计数器定义 CirQueue; CirQueue *Q; /定义循环队列Q,5循环队列的基本运算的算法 （1） 置队空 （2）判队空 （3）判队满 （4）入队 （5）出队 （6）取队头元素,（1） 置队空 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0;/计数器置0 ,（2）判队空 int QueueEmpty(CirQueue *Q) return Q-count=0; /队列无元素为空 ,（3）判队满 int QueueFull(CirQueue *Q) return Q-count=QueueSize; ,（4）入队 int EnQueue(CirQueue *Q,DataType x) if(QueueFull(Q) puts(队满); return 0; Q-count +;/队列元素个数加1 Q-dataQ-rear=x;/新元素插入队尾 Q-rear=(Q-rear+1)%QueueSize;/循环意义下将尾指针加1 return 1; ,（5）出队 int DeQueue(CirQueue *Q ,DataType *x) if(QueueEmpty(Q) puts(队空); return 0; *x=Q-dataQ-front; Q-count-;/队列元素个数减1 Q-front=(Q-front+1)%QueueSize;/循环意义下的头指针加1 return 1; ,（6）取队头元素 int QueueFront(CirQueue *Q ,DataType *x) if(QueueEmpty(Q) puts(队空); return 0; *x=Q-dataQ-front; return 1; ,【课堂实践3-3】 设计一个选择菜单，根据用户的选择决定对循环队列进行置空队、进队、退队、取队头元素和退出程序的操作。,做 一 做,四、链队列及基本操作的实现 1链队列（Linked Queue） 队列的链式存储结构称为链队列，它是限制仅在表头删除和表尾插入的单链表。由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾结点的指针。 2链队列的描述 设Q是LinkQueue类型的指针变量，则Q是指向链队列的指针，队头指针、队尾指可分别表示为Q-front、Q- rear。 设p是QueueNode类型的指针变量，则p是指向链队列某结点的指针，该结点的数据域可表示为p -data，该结点的指针域可表示为p - next。 链队列如图3-5：,2链队列的描述 typedef char DataType; /定义队列元素类型 typedef struct queuenode /队列中结点的类型 DataType data; struct queuenode *next; QueueNode; typedef struct QueueNode *front;/队头指针 QueueNode *rear; /队尾指针 LinkQueue; LinkQueue *Q; /定义链队列Q,3链队列的基本运算 由于链队列结点的存储空间是动态分配的，所以无须考虑判队满的运算。 （1）置队空 （2）判队空 （3）入队 （4）出队 （5）取队头元素 注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。,（1）置队空 void InitQueue(LinkQueue *Q) Q-front=Q-rear=NULL; ,（2）判队空 int QueueEmpty(LinkQueue *Q) return Q-front=NULL; ,（3）入队 int EnQueue(LinkQueue *Q,DataType x) /将元素x插入链队列尾部 QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode); if(p=NULL) puts (空间申请失败!);return 0; p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front=Q-rear=p;/将x插入空队列 else /x插入非空队列的尾 Q-rear-next=p;/*p链到原队尾结点后 Q-rear=p;/队尾指针指向新的尾 return 1; ,（4）出队 int DeQueue(LinkQueue *Q, DataType *x) QueueNode *p; if(QueueEmpty(Q) puts(队空); return 0; p=Q-front;/指向队头结点 *x=p-data;/保存队头结点的数据 Q-front=p-next;/将对头结点从链上摘下 if(Q-rear=p） Q-rear=NULL; free(p);/释放被删队头结点 return 1; ,（5）取队头元素 int QueueFront(LinkQueue *Q, DataType *x) if(QueueEmpty(Q) puts(队空); return 0; *x=Q-front-data; return 1; ,【课堂实践3-4】 设计一个选择菜单，根据用户的选择决定对链队列进行置空队、进队、退队、取队头元素和退出程序的操作。,做 一 做,引例分析与实现,1引例分析 十进制数F可分解为F=N+M，其中N为十进制整数，M为十进制纯小数转换为B进制数，分为十进制整数转换为B进制整数和十进制纯小数转换为B进制纯小数数两部分。 （1）将十进制整数转换为B进制整数 将十进制整数转换为B进制整数，通常采用的方法是“B除取余法”。 【示例】将365转换为16进制数 采用16除取余法，如图3-6。 得365转换为16进制数为16D。,算法思路：定义一个指向链栈的指针S，通过函数malloc确定S的指向，并对链栈进行初始化，当N=0时，输出一个0，当N!=0时，重复进行将N被B除的余数N%B入栈S，并将所得的商N/B作为被除数，即将N/B赋给N，直到N的值为0，这样，得到的余数已经全部入栈S；只要栈S不空，作出栈操作，并输出，如果出栈元素大于等于10，通过加87输出对应字符（基数大于10的大于等于10的数码用对应字母来表示）。,引例分析与实现,（2）将十进制纯小数转换为B进制纯小数 将十进制纯小数转换为B进制纯小数，通常采用的方法是“B乘取整法”。 【示例】将0.618转换为16进制数 采用16乘取整法，如图3-7。 得0.618转换为16进制数近似为0.9E353F。,引例分析与实现,算法思路：确定一个精度E，比如E的值为0.000001，当M=E时，输出一个小数点.，并重复进行将M被B乘的整数部分(int)(M*B)入队Q，并将所得的小数部分M*B-(int)(M*B)作为被乘数，即将M*B-(int)(M*B)赋给M，直到M的值小于E或j值超过队列的最大容量QueueSize，这样，得到的整数已经全部入队Q；只要队Q不空，作出队操作，并输出，如果出队元素大于等于10，通过加87输出对应字符。,引例分析与实现,2引例实现 （1）将十进制整数转换为B进制整数函数 （2）将十进制纯小数转换为B进制纯小数函数 （3）主函数,引例分析与实现,int IntegerConversion(int N,int B) /十进制整数N转换为等值的B进制整数 DataType x; LinkStack *S=(LinkStack *)malloc(sizeof(LinkStack); if(S=NULL) puts(空间申请失败!);return 0; InitStack(S); if(number=10) printf(%c,x+87); else printf(%d,x); return 1; ,int DecimalConversion(double M,int B) /十进制纯小数M转换为等值的B进制小数 DataType x; int j=1; CirQueue *Q=(CirQueue *)malloc(sizeof(CirQueue); if(Q=NULL) puts(空间申请失败!);return 0; InitQueue(Q); if(M=E) printf(.); while(M=E ,int main() int N,B;/N为number的整数部分，B为待转换的进制 double M;/M为number小数部分 printf(请输入一个十进制数：); scanf(%lf, ,再 见,