作业解答4-数据结构-教学课件.ppt

《作业解答4-数据结构-教学课件.ppt》由会员分享，可在线阅读，更多相关《作业解答4-数据结构-教学课件.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构作业数据结构作业2002 年第三章 栈和队列3.28 假设带表头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队和出队的算法。/a1a2an非空情况：头结点指针：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

2、(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 NU

3、LL;p-next=p;return p;（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 r

4、ear;/*返回表尾指针*/2.30 假设将循环队列定义为：以域变量假设将循环队列定义为：以域变量rear和和length分别指分别指向循环队列的队尾元素的位置和元素的个数。试给出此循环向循环队列的队尾元素的位置和元素的个数。试给出此循环队列的队满条件，并写出相应的入队和出队的算法队列的队满条件，并写出相应的入队和出队的算法。A BCD 0123456.MAXSIZE-1 rear length=4首元素序号：rear-length+1=6-4+1=3 CDA BCDAB0123456.MAXSIZE-1 rear length=4首元素序号：rear-length+1+MAXSIZE=1-4

5、+1+MAXSIZE =MAXSIZE-2首元素序号首元素序号：(rear-length+1+MAXSIZE)%MAXSIZE队满条件：队满条件：length=MAXSIZE(1)类型定义：(2)typedef struct (3)ElemType elemMAXSIZE;(4)int rear,length;(5)SeQueue;(6)main()(7)SeQueue que1,que2;ElemType e;(8)que1.length=0;que1.rear=0;(9)EnQueue(&que1,10);(10)DeQueue(&que1,&e);（3）出队列算法：int DeQueue

6、(SeQueue *Q,ElemType *e);if (Q-length=0)printf(“空队列”);return 0;*e=Q-elem(rear-length+1+MAXSIZE)%MAXSIZE;Q-length-;return 1;2.31 假设称正读和反读都相同的字符序列为假设称正读和反读都相同的字符序列为“回文回文”，试写，试写一算法判别读入的一个以一算法判别读入的一个以为结束的字符序列是否为为结束的字符序列是否为“回文回文”。int huiwen()InitStack(S);InitQueue(Q);while (c=getchar()!=)Push(S,c),EnQueue(Q,c);while (!StackEmpty(S)Pop(S,c1);DeQueue(Q,c2);if(c1!=c2)return 0;return 1;