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

1、数据结构算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!) (提供两种答案哦！)一：/既然是算法 就不用源码了 具体看注释typedef int datatype;typedef struct queuenodedatatype data;struct queuenode *next;queuenode; /以上是结点类型的定义typedef structqueuenode rear;linkqueue; /只设一个指向队尾元素的指针void initqueue( linkqueue &q) /置空队：就

2、是使头结点成为队尾元素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( linkqu

3、eue &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-n

4、ext-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

5、(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;