任务5 进位制转换.ppt

1、2,教学目标 1、知识目标 1）掌握队列的定义及基本运算； 2）掌握循环队列、链队列基本运算的实现算法。 2、能力目标 1）具有恰当的选择队列作为数据的逻辑结构、循环队列、链队列作为数据的存储结构的能力； 2）具有应用队列解决实际问题的能力。 3、素质目标 养成善于思考解决实际问题的良好习惯。,3,一、任务描述 进位制转换包括B1进制数转换为B2进制数，十进制数转换为B进制数，B进制数转换为十进制数等，这里，我们仅讨论十进制数转换为B进制数。 十进制数转换为B进制数可分为：十进制整数转换为B进制整数和十进制纯小数转换为B进制纯小数两部分。 为完成整数部分的转换和纯小数部分的转换，需要弄清楚这两

2、部分分别应该选择何种数据结构。为此，我们来学习下面的相关知识。,4,二、相关知识 （一）队列的定义及基本操作 队列与栈一样都是运算受限的线性表，但与栈的限制不同。 1、队列的定义 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。向队列中插入元素称为入队，从队列中删除元素称为出队。 (1)允许删除的一端称为队头。 (2)允许插入的一端称为队尾。 (3)当队列中没有元素时称为空队列。 (4)队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许“加塞”），每次离开的

3、成员总是队列头上的成员（不允许中途离队），即当前“最老的”成员离队。,5,2、队列的基本运算 1）置空队：InitQueue (Q)构造一个空队列Q。 2）判队空：QueueEmpty (Q)若队列Q为空，则返回真值，否则返回假值。 3）判队满：QueueFull (Q)若队列Q为满，则返回真值，否则返回假值。 注意：此操作只适用于队列的顺序存储结构。 4）入队：EnQueue(Q，x)若队列Q非满，则将元素x插入Q的队尾。 5）出队：DeQueue (Q)若队列Q非空，则删去Q的队头元素，并返回该元素。 6） 取队头元素：QueueFront (Q)若队列Q非空，则返回队头元素，但不改变队列

4、Q的状态。,6,（二）顺序队列及基本操作的实现 1、顺序队列：队列的顺序存储结构称为顺序队列，它是运算受限的顺序表。 2、顺序队列的表示 和顺序表一样，顺序队列用一个数组（向量空间）来存放当前队列中的元素。 由于随着入队和出队操作的变化，队列的队头和队尾的位置是变动的，所以应设置两个整型量front和rear分别指示队头和队尾在向量空间中的位置，它们的初值在队列初始化时均应置为0。通常称front为队头指针，称rear为队尾指针。 3、顺序队列的基本操作 入队：入队时将新元素插入rear所指的位置，然后将rear加1。 出队：出队时删去front所指的元素，然后将front加1并返回被删元素。

5、,7,注意： 当头尾指针相等时，队列为空。 在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 顺序队列基本操作如图：,8,4、顺序队列中的溢出现象 “下溢”现象：当队列为空时，做出队运算产生的溢出现象。 “真上溢”现象：当队列满时，做入队运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 “假上溢”现象：由于入队和出队操作中，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用。当队列中实际元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。 5、解决“假上溢”现象的方法 当出现“假上溢”现

6、象时，把所有的元素向低位移动，使得空位从低位区移向高位区，显然这种方法很浪费时间。 把队列的向量空间的元素位置0Queuesize-1看成一个首尾相接的环形，当进队的队尾指针等于最大容量，即rear=Queuesize时，使rear=0。,9,三、循环队列 1、循环队列：把向量空间的元素位置首尾相接的顺序队列称为循环队列。循环队列示意图： 2、循环队列头尾指针的操作 循环队列进行出队、入队操作时，头尾指针仍要加1。当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： 利用选择结构 if(i+1=QueueSize)/i为f

7、ront或rear i=0; else i+; 利用模运算 i=(i+1)%QueueSize;/i为front或rear,10,3、循环队列边界条件的处理方法 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。解决这个问题的方法至少有三种： 另设一标志变量flag以区别队列的空和满，比如当条件front=rear成立，且 flag 为0时表示队列空，而为1时表示队列满； 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：r

8、ear所指的单元始终为空）； 使用一个计数器count记录队列中元素的总数，当count =0时表示队列空；当count =QueueSize时表示队列满。 我们将使用此方法。,10,11,4、循环队列的描述#define QueueSize 100 /定义队列最大容量typedef char DataType; /定义队列元素类型 typedef struct cirqueue DataType dataQueueSize;/队列元素定义int front;/头指针定义int rear; /尾指针定义 int count; /计数器定义 CirQueue; 5、循环队列的基本运算 置队空；

9、判队空； 判队满； 入队； 出队； 取队头元素。,11,11,11,11, 置队空void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; /计数器置0 , 判队空 int QueueEmpty(CirQueue *Q) return Q-count=0; /队列无元素为空, 判队满int QueueFull(CirQueue *Q) return Q-count=QueueSize; /队中元素个数等于QueueSize时队满, 入队void EnQueue(CirQueue *Q,DataType x) if(QueueFull(Q)

10、 puts(“队满”); exit(0); /队满上溢Q-count +; /队列元素个数加1Q-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加1 , 出队DataType DeQueue(CirQueue *Q) DataType temp; if(QueueEmpty(Q) puts(“队空”); exit(0); /队空下溢 temp=Q-dataQ-front; Q-count-; /队列元素个数减1 Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加1 return tem

11、p; ,取队头元素DataType QueueFront(CirQueue *Q) if(QueueEmpty(Q) puts(“队空”); exit(0); return Q-dataQ-front;,12,（三） 链队列及基本操作的实现 1、链队列：队列的链式存储结构称为链队列，它是限制仅在表头删除和表尾插入的单链表。由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾结点的指针。 2、链队列的描述 typedef struct queuenode/队列中结点的类型DataType data;struct queuenode *next; QueueNode;type

12、def structQueueNode *front; /队头指针 QueueNode *rear; /队尾指针 LinkQueue; 3、链队列示意图,13,13,13,13,13,13,4、链队列的基本运算 由于链队列结点的存储空间是动态分配的，所以无须考虑判队满的运算。 置空队 判队空 入队 出队 取队头元素 注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。,置空队 void InitQueue(LinkQueue *Q) Q-front=Q-rear=NULL;,判队空 int Queue

13、Empty(LinkQueue *Q) return Q-front=NULL/实际上只须判断队头指针是否为空即可,入队 void EnQueue(LinkQueue *Q,DataType x)/将元素x插入链队列尾部 QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode);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; /队尾指针指向新的尾,出队 Data

14、Type DeQueue (LinkQueue *Q) DataType x; QueueNode *p; if(QueueEmpty(Q) puts(“队空”); exit(0); p=Q-front;/指向队头结点x=p-data;/保存队头结点的数据Q-front=p-next;/将对头结点从链上摘下if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q-rear=NULL;free(p); /释放被删队头结点return x; /返回原队头数据,取队头元素DataType QueueFront(LinkQueue *Q) if(QueueEmpty(Q)

15、puts(“队空”); exit(0); return Q-front-data;,14,三、任务分析 十进制数转换为B进制数，分为十进制整数转换为B进制整数和十进制纯小数转换为B进制纯小数数两部分。 1、将十进制整数转换为B进制整数 将十进制整数转换为B进制整数，通常采用的方法是“B除取余法”。 例如：将365转换为16进制数 从上面的求解过程可以看出，最后得到的余数最先写出来，具有后进先出的特性，因此，将十进制整数转换为B进制整数应该选择栈的数据结构，可采用顺序栈，也可采用链栈，但由于要转换的十进制数的位数是不确定的，所以，转换成的B进制数的位数也是不确定的，为避免浪费存储空间，应该选择链

16、栈的存储结构。,15,2、将十进制纯小数转换为B进制纯小数 将十进制纯小数转换为B进制纯小数，通常采用的方法是“B乘取整法”。 例如：将0.618转换为16进制数 从上面的转换过程可以看出，最先得到的整数最先写出来，具有先进先出的特性，因此，将十进制纯小数转换为B进制纯小数应该选择队列的数据结构，可采用循环队列，也可采用链队列，但由于转换后得到的B进制纯小数需要精确到某一位，有确定的最大位数，所以，应该选择循环队列的存储结构。,16,四、任务分解 为完成十进制数转换为B进制数的任务，需要用到链栈的4个基本操作（初始化、判栈空、进栈和退栈）和循环队列的5个基本操作（初始化、判队空、判队满、入队和

17、出队），还要对该任务进行如下的分解： 任务5.1 十进制整数转换为B进制整数 任务5.2 十进制纯小数转换为B进制纯小数,17,五、完成任务 任务5.1 十进制整数转换为B进制整数 将需要转换的十进制整数N和待转换的进制B作为函数参数，该函数没有返回值，函数名使用IntegerConversion。 具体操作： 定义一个指向链栈的指针S，通过函数malloc确定S的指向，并对链栈进行初始化，当N=0时，输出一个0，当N!=0时，重复进行将N被B除的余数N%B入栈S，并将所得的商N/B作为被除数，即将N/B赋给N，直到N的值为0，这样，得到的余数已经全部入栈S；只要栈S不空，作出栈操作，并输出，

18、如果出栈元素大于等于10，通过加87输出对应字符（基数大于10的大于等于10的数码用对应字母来表示）。算法如下：,任务5.1 十进制整数转换为B进制整数 void IntegerConversion(int N,int B) /十进制整数N转换为等值的B进制整数 int i; LinkStack *S=(LinkStack *)malloc(sizeof(LinkStack); InitStack(S); if(N=0) printf(0); while(N)/求N对应B进制数的各位数字，并将其进栈 Push(S,N%B); N=N/B; while(!StackEmpty(S)/栈非空时退栈

19、输出 i=Pop(S); if(i=10) printf(%c,i+87); else printf(%d,i); ,18,任务5.2 十进制纯小数转换为B进制纯小数 将需要转换的十进制纯小数M和待转换的进制B作为函数参数，该函数没有返回值，函数名使用DecimalConversion。 具体操作： 定义一个指向循环队列的指针Q，通过函数malloc确定Q的指向，并对循环队列进行初始化，当M!=0时，输出一个小数点.，并重复进行将M被B乘的整数部分(int)(M*B)入队Q，并将所得的小数部分M*B-(int)(M*B)作为被乘数，即将M*B-(int)(M*B)赋给M，直到M的值为0或j值超

20、过队列的最大容量QueueSize，这样，得到的整数已经全部入队Q；只要队Q不空，作出队操作，并输出，如果出队元素大于等于10，通过加87输出对应字符。 算法如下：,任务5.2 十进制纯小数转换为B进制纯小数 void DecimalConversion(double M,int B) int i,j=1; CirQueue *Q=(CirQueue *)malloc(sizeof(CirQueue); InitQueue(Q); if(M) printf(.); while(M ,19,六、归纳总结 通过“任务5 进位制转换”任务的完成，要求大家理解和掌握以下主要内容： 1、队列的概念 队列（Queue）是限制仅在表的一端进行插入操作，在表的另一端