《数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)》由会员分享,可在线阅读,更多相关《数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)(4页珍藏版)》请在金锄头文库上搜索。
1、数据构造算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(留意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!)(供给两种答案哦!)一:/既然是算法就不用源码了具体看注释typedef int Datype;typedef struct quenodeDatype data; struct quenode *next;QueNode; /以上是结点类型的定义typedef structquenode rear;LinkQue; /只设一个指向队尾元素的指针void InitQue( LinkQue &Q)/置空队:就是使头结点成为队尾元素Q.rear=(qu
2、enode*)malloc(sizeof(quenode) QueNode* s;Q-rear = Q-rear-next;/将队尾指针指向头结点while(Q-rear!=Q-rear-next) /当队列非空,将队中元素逐个出队s=Q-rear-next;Q-rear-next=s-next; free(s); /回收结点空间int EmptyQue( LinkQue &Q)/判队空4 / 4/当头结点的 next 指针指向自己时为空队return Q-rear-next-next=Q-rear-next;void EnQue( LinkQue &Q, Datypex)/入队/也就是在尾结
3、点处插入元素QueNode *p=(QueNode *) malloc (sizeof(QueNode);/申请新结点p-data=x; p-next=Q-rear-next;/初始化新结点并链入 Q-rear-next=p;Q-rear=p;/将尾指针移至新结点Datype DeQue( LinkQue &Q,Datype &x)/出队,把头结点之后的元素摘下Datype t; QueNode *p; if(EmptyQue( Q )Error(“Que underflow“);p=Q-rear-next-next; /p 指向将要摘下的结点x=p-data; /保存结点中数据if (p=Q
4、-rear)/当队列中只有一个结点时,p 结点出队后,要将队尾指针指向头结点Q-rear = Q-rear-next; 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 structCiLNode CiLrear;CiQue;void InitCiQue(CiQue &Q)/初始化循环链表表示的队列QQ=(CiLNode*)malloc(sizeo
5、f(CiLNode);Q-next=Q;/InitCiQuevoidEnCiQue(CiQue&Q,intx)/把元素 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 DeCiQue(CiQue &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;/DeCiQue