华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）作业解答4

7感门 20023

数据结构作业 2002 年 第三章 栈和队列

328假设带表头结点的循环链表表示队列,并且只设一不指 针指向队尾元素结点(注意不设头指针),试编写相应的队 列初始化、入队和出队的算法。 非空情况:四 rear an 头结点指针:rear>next; 首元素指针:rear>next->next 用指针rear 空队情况:「∥ rear 表示队列 空队条件:rear->next=rear;

3.28 假设带表头结点的循环链表表示队列，并且只设一个指 针指向队尾元素结点（注意不设头指针），试编写相应的队 列初始化、入队和出队的算法。 非空情况： /// a1 a2 an 头结点指针：rear->next; 首元素指针：rear->next->next; rear 空队情况： /// 空队条件：rear->next=rear; rear 用指针rear 表示队列

(1)定义类型: typedef struct Nodei ElemType data struct Node *next 3 Node, * LinkQue Link Que InitQue( void) Link Que EnQueue(Link Que rear, ElemType e) LinkQue DeQueue Link Que rear, ElemType e) main Link Que que l, que2; int elem quel=InitQueo; que2-InitQueo quel= EnQueue(quel, 10); que l= DeQueue( quel, &elem)

（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表示成功 Link Que InitQue(void) f Link Que p; p=malloc(sizeof(Node)) if (p printf(OVERFLOW); return NULL, p-next-p return p

（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表示入队列失败,非NUL表示成功 Link Que EnQueue Link Que rear, ElemType e) f Link Que p p=malloc(sizeof(Node) if (p)i printfcoVerFloW); return NULL, p-data=e p->next-rear->next /*新结点指向表头结点* rear->ne /*原表尾结点指向新结点* reap 表尾指针指向新结点为新表尾* return rear;}*返回表尾指针*

（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; } /*返回表尾指针*/

(3)出队列算法: 返回值为NULL表示出队列失败,非NULL表示成功 Link Que DeQueue(Link Que rear, Elem Type *e) i Link Que p if(rear>next=rear){ printi(“空队列”); return NuLL;} p= rear->next->next /*p指向待出队列的首结点* e=p->da /*出队列的首结点元素值* rear->next->next=p->next *出队:删除首结点* if (rear==p) *仅有一个结点* rear=rear>next;/伴队尾指针志向表头结点* return rear. /*返回表尾指针*

（3） 出队列算法： 返回值为NULL表示出队列失败，非NULL表示成功。 LinkQue DeQueue(LinkQue rear, ElemType *e); { LinkQue p; if (rear->next=rear) { printf(“空队列”); return NULL;} p= rear->next->next; /*p指向待出队列的首结点*/ *e=p->data; /*出队列的首结点元素值*/ rear->next->next =p->next; /*出队：删除首结点*/ if (rear==p) /*仅有一个结点*/ rear=rear->next; /*队尾指针志向表头结点*/ return rear; } /*返回表尾指针*/

2.30假设将循环队列定义为:以域变量rear和ngth分别指 向循环队列的队尾元素的位置和元素的个数。试给出此循环 队列的队满条件,并写出相应的入队和出队的算法。 ABC D MAXSIZE-I rear length=4 首元素序号: rear-length+1=6-4+1=3 C D ABC D A B 0123456 MAXSIZE-1 rear length=4 首元素序号: rear-length++ MAXSIZE=1-4+1 MAXSIZE MAXSIZE-2

2.30 假设将循环队列定义为：以域变量rear和length分别指 向循环队列的队尾元素的位置和元素的个数。试给出此循环 队列的队满条件，并写出相应的入队和出队的算法。 A B C D 0 1 2 3 4 5 6 … .. MAXSIZE-1 rear length=4 首元素序号：rear-length+1=6-4+1=3 C D A B C D A B 0 1 2 3 4 5 6 … .. MAXSIZE-1 rear length=4 首元素序号：rear-length+1+MAXSIZE==1-4+1+MAXSIZE = MAXSIZE-2

首元素序号:(rear- ength++ MAXSIZEY% MAXSIZE 队满条件: length= MAXSIZE (1)类型定义: typedef struct ElemType elem MAXSIZEI int rear, length 3 SeQuel maino i SeQueue quel, que2, Elem Type e quel length=0; quel. rear=0 EnQueue(&quel, 10) DeQueue( &quel, &e);)

首元素序号：( rear-length+1+MAXSIZE)%MAXSIZE 队满条件： length=MAXSIZE (1) 类型定义： 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); }

(2)入队列算法: int EnQueue( SeQueue *Q, ElemType e) if (Q->length==MAXSIZE i printf(OVERFLOW ); return 0; 1 Q→>rear=(Q->rear+1)% MAXSIZE;/*取下一空位置* Q->elem Q->rear=e Q->length++ return 1

（2） 入队列算法： int EnQueue(SeQueue *Q, ElemType e); { if (Q->length==MAXSIZE) { printf(“OVERFLOW”); return 0;} Q->rear=(Q->rear+1)%MAXSIZE; /*取下一空位置*/ Q->elem[Q->rear]=e; Q->length++; return 1; }

(3)出队列算法: int DeQueue(seQueue *Q, Elem Type *e) if (Q->length==0) printf(空队列”); return0;} e=Q->elem( rear-length+1+MAXSIZE)%OMAXSIZEI Q->length return 1

（3） 出队列算法： int DeQueue(SeQueue *Q, ElemType *e); { if (Q->length==0) { printf(“空队列”); return 0;} *e=Q->elem[( rear-length+1+MAXSIZE)%MAXSIZE]; Q->length--; return 1; }