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

数据结构算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!) (提供两种答案哦！！！) 一： //既然是算法 就不用源码了 具体看注释typedef int Datatype;typedef struct queuenode{ Datatype data; struct queuenode *next;}QueueNode; //以上是结点类型的定义typedef struct{ queuenode 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;//摘下结点p free(p);//释放被删结点 return x;} 二： typedef struct Node {?int data;?struct Node *next;}Node,*CiLNode;typedef struct{?CiLNode CiLrear;}CiQueue; void InitCiQueue(CiQueue Q)//初始化循环 HYPERLINK /z/Search.e?sp=S%E9%93%BE%E8%A1%A8ch=w.search.yjjlinkcid=w.search.yjjlink \t _blank 链表表示的队列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; //队列已空? p=Q-next-next;? x=p-data;? Q-next-next=p-next;? free(p);? return OK;}//DeCiQueue