《数据结构算法.doc》由会员分享，可在线阅读，更多相关《数据结构算法.doc（3页珍藏版）》请在三一文库上搜索。
1、数据结构算法题 （假设以带头结点的循环链表表示队列 , 并且只设一个 指针指向队尾元素结点 （注意不设头指针 ）试编写相应的队列初始化 , 入 队列和出队列的算法 !） （ 提供两种答案哦！ ）/ 既然是算法 就不用源码了 具体看注释 typedef int Datatype;typedef struct queuenodeDatatype data; struct queuenode *next;QueueNode; / 以上是结点类型的定义typedef struct queuenode rear;LinkQueue; / 只设一个指向队尾元素的指针void InitQueue( Link
2、Queue &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) / 判队空/
3、 当头结点的 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;/ 将尾指针移至新结点
4、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;
5、Q->rear->next=p->next;elseQ->rear->next->next=p->next;/ 摘下结点 p free(p);/ 释放被删结点 return x;typedef struct Nodeint data;struct Node *next; Node,*CiLNode; typedef struct CiLNode CiLrear;CiQueue;void InitCiQueue(CiQueue &Q)/ 初始化循环 链表 表示的队列 QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-&g
6、t;next=Q;/InitCiQueuevoid 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 头部删除元素 xif(Q=Q->next) return INFEASIBLE; /队列已空p=Q->next->next;x=p->data;Q->next->next=p->next;free(p);return OK;/DeCiQueue