上大数据结构课件第4章-栈和队列 沈 俊.pptVIP

4) 链接队列的出队运算 ①检查队列是否为空，若队空，则进行下溢出错误处理； ②否则，在删除队列的第一个结点a1之前，先保存该结点信息，以便返回删除元素的数据值； ③修改头指针head的指针域，使其指向队列的第二个结点a2建立新的链接队列； ④删除并释放原队列中第一个结点a1的存储空间； ⑤若出队成功，则函数返回原队列的第一个结点a1的信息。 图3.17　链接队列出队运算示意图 datatype LINK_DEQUEUE (linkqueue *head,linkqueue *rear) /*带头结点的链接队出队运算*/ { datatype x; 　if (LINK_EMPTY(head, rear)) /*若队空，则打印错误信息，终止程序运行*/ {printf(队列已空，不能进行出队运算!\n); return (NULL);}　 else { s = head -next; /*指针s指向原队列的第一个结点*/ x= s-data; 　 /*保存原第一个结点的数据值*/ head-next =s -next; /*删除第一个结点*/ free(s); 　　/*释放原队列中第一个结点的存储空间*/ 　　return (x); }　 /*出队成功，则函数返回原第一个结点的数据值*/ } * 【例3.9】设计程序：将一个正整数转换为其它r (2≤r≤9)进制数输出。 例子： (28)10 = 3×81+4×80=(34)8 (72)10 = 1×43+0×40+2×41+0×40=(1020)4 (53)10 = 1×25+1×24+0×23+1×22+1×20=(110101)2 　　把一个十进制数x转换为r进制数y，其转换是逐次除基数r取余法。具体转换过程是：首先用十进制数x除以基数r，得到的整余数是r进制数y的最低位y0，接着以x除以r的整数商作为被除数，用它除以r得到的整除数是y的次低位y1，依次类推，直至商为0时得到整余数是y的最高位ym。 #include sqstack9.c /*将顺序栈的类型定义及5种运算等包含进来*/ seqstack S; /*定义一个顺序栈*/ void transform(int num, int r) /*将十进制数num转换为r进制数并输出*/ { int k, n, kk=num; char rname[10][10]={\0,一,二,三,四,五,六, 七,八,九}; INITSTACK(S) /*将顺序栈初始化为空*/ while (num!=0) /*由低到高输出r进制数的每一位数字*/ 　 {k=num%r; PUSH(S, k); num = num/r;} /*余数按k0,k1,k2…kn顺序进栈*/ printf(将十进制数%d转换为%s进制数为:, kk, rname[r]); while(EMPTY(S) == 0) /*若栈非空*/ { n = POP(S); printf(%d , n); } 　/*由高到低输出r进制数的每一位数字*/ } 3.5 队列的基本概念 队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out， 缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 在队列中插入一个新元素的操作简称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除一个元素的操作简称为出队或离队，当元素出队后，其后继元素就成为新的队头元素 　　假设队列为q=(a1，a2，…，an)，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的， 退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列。 图3.11 队列的结构示意图 3.6 队列的存储结构 3.6.1 队列的顺序存储结构 3.6.2 顺序存储的循环队列 3.6.3 队列的链接存储结构 3.6.1 队列的顺序存储结构 队列的顺序存储结构称为顺序队列。顺序队列可以利用一个一维数组和两个指针来实现。一维数组用来存储当前队列中的所有元素，两个指针head和rear分别指向当前队列的队首元素和队尾元素，分别称为队首指针和队尾指针。 顺序队列的类型定义如下： #define