数据结构算法习题答案带头结点的循环链表表示队列并且只设一个指针指向队尾元素结点注意不设头指针.docx

数据结构算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!) (提供两种答案哦！)一：/既然是算法 就不用源码了 具体看注释typedef int Datatype;typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是结点类型的定义typedef structqueuenode rear;LinkQueue; /只设一个指向队尾元素的指针void InitQueue( LinkQueue &Q) /置空队：就是使头结点成为队尾元素Q.rear=(queuenode*)malloc(sizeof(queuenode)QueueNode* s;Q-rear = Q-rear-next;/将队尾指针指向头结点while(Q-rear!=Q-rear-next) /当队列非空，将队中元素逐个出队s=Q-rear-next;Q-rear-next=s-next;free(s); /回收结点空间int EmptyQueue( LinkQueue &Q)/判队空/当头结点的next指针指向自己时为空队return Q-rear-next-next=Q-rear-next;void EnQueue( LinkQueue &Q, Datatype x)/入队/也就是在尾结点处插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申请新结点p-data=x; p-next=Q-rear-next;/初始化新结点并链入Q-rear-next=p; Q-rear=p;/将尾指针移至新结点Datatype DeQueue( LinkQueue &Q,Datatype &x)/出队,把头结点之后的元素摘下Datatype t;QueueNode *p;if(EmptyQueue( Q )Error(Queue underflow);p=Q-rear-next-next; /p指向将要摘下的结点x=p-data; /保存结点中数据if (p=Q-rear)/当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点Q-rear = Q-rear-next; Q-rear-next=p-next;else Q-rear-next-next=p-next;/摘下结点pfree(p);/释放被删结点return x; 二：typedef struct Nodeint data;struct Node *next;Node,*CiLNode;typedef structCiLNode CiLrear;CiQueue;void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列Q Q=(CiLNode*)malloc(sizeof(CiLNode); Q-next=Q;/InitCiQueue void EnCiQueue(CiQueue &Q,int x)/把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q-next指向头结点,Q-next-next指向队头元素 p=(CiLNode*)malloc(sizeof(CiLNode); p-data=x; p-next=Q-next; /直接把p加在Q的后面 Q-next=p; Q=p; /修改尾指针 Status DeCiQueue(CiQueue &Q,int x)/从循环链表表示的队列Q头部删除元素x if(Q=Q-next) return INFEASIBLE;