作业解答4 C语言课件幻灯片课件.pptVIP

数据结构作业 2002 年 第三章 栈和队列 3.28 假设带表头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队和出队的算法。 /// a1 a2 an 非空情况： 头结点指针：rear-next; 首元素指针：rear-next-next; rear /// 空队情况： 空队条件：rear-next=rear; rear 用指针rear 表示队列 （1） 定义类型： typedef struct Node{ ElemType data; struct Node *next; } Node, *LinkQue; LinkQue InitQue(void); LinkQue EnQueue(LinkQue rear, ElemType e); LinkQue DeQueue(LinkQue rear, ElemType e); main() {LinkQue que1,que2; int elem; que1=InitQue(); que2=InitQue(); que1= EnQueue(que1, 10); que1= DeQueue(que1, elem); } （2） 初始化算法： 返回值为NULL表示初始化失败，非NULL表示成功。 LinkQue InitQue(void) { LinkQue p; p=malloc(sizeof(Node)); if (!p) { printf(“OVERFLOW”); return NULL;} p-next=p; return p; } （3） 入队列算法： 返回值为NULL表示入队列失败，非NULL表示成功。 LinkQue EnQueue(LinkQue rear, ElemType e); { LinkQue p; p=malloc(sizeof(Node)); if (!p) { printf(“OVERFLOW”); return NULL;} p-data=e; p-next=rear-next; /*新结点指向表头结点*/ rear-next=p; /*原表尾结点指向新结点*/ rear=p; /*表尾指针指向新结点为新表尾*/ return rear; } /*返回表尾指针*/ 首元素序号：( rear-length+1+MAXSIZE)%MAXSIZE 队满条件： length=MAXSIZE 类型定义： typedef struct { ElemType elem[MAXSIZE]; int rear, length; } SeQueue; main() {SeQueue que1,que2; ElemType e; que1.length=0; que1.rear=0; EnQueue(que1,10); DeQueue(que1,e); } * *