數(shù)據(jù)結(jié)構(gòu)算法 習(xí)題 答案 帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針)

1、數(shù)據(jù)結(jié)構(gòu)算法題(假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針)試編寫相應(yīng)的隊列初始化,入隊列和出隊列的算法!) (提供兩種答案哦！)一：/既然是算法 就不用源碼了 具體看注釋typedef int datatype;typedef struct queuenodedatatype data;struct queuenode *next;queuenode; /以上是結(jié)點類型的定義typedef structqueuenode rear;linkqueue; /只設(shè)一個指向隊尾元素的指針void initqueue( linkqueue &q) /置空隊：就

2、是使頭結(jié)點成為隊尾元素q.rear=(queuenode*)malloc(sizeof(queuenode)queuenode* s;q-rear = q-rear-next;/將隊尾指針指向頭結(jié)點while(q-rear!=q-rear-next) /當(dāng)隊列非空，將隊中元素逐個出隊s=q-rear-next;q-rear-next=s-next;free(s); /回收結(jié)點空間int emptyqueue( linkqueue &q)/判隊空/當(dāng)頭結(jié)點的next指針指向自己時為空隊return q-rear-next-next=q-rear-next;void enqueue( linkqu

3、eue &q, datatype x)/入隊/也就是在尾結(jié)點處插入元素queuenode *p=(queuenode *) malloc (sizeof(queuenode);/申請新結(jié)點p-data=x; p-next=q-rear-next;/初始化新結(jié)點并鏈入q-rear-next=p; q-rear=p;/將尾指針移至新結(jié)點datatype dequeue( linkqueue &q,datatype &x)/出隊,把頭結(jié)點之后的元素摘下datatype t;queuenode *p;if(emptyqueue( q )error(queue underflow);p=q-rear-n

4、ext-next; /p指向?qū)⒁碌慕Y(jié)點x=p-data; /保存結(jié)點中數(shù)據(jù)if (p=q-rear)/當(dāng)隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點q-rear = q-rear-next; q-rear-next=p-next;else q-rear-next-next=p-next;/摘下結(jié)點pfree(p);/釋放被刪結(jié)點return x; 二：typedef struct nodeint data;struct node *next;node,*cilnode;typedef structcilnode cilrear;ciqueue;void initciqueue

5、(ciqueue &q)/初始化循環(huán)鏈表表示的隊列q q=(cilnode*)malloc(sizeof(cilnode); q-next=q;/initciqueue void enciqueue(ciqueue &q,int x)/把元素x插入循環(huán)鏈表表示的隊列q,q指向隊尾元素,q-next指向頭結(jié)點,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)/從循環(huán)鏈表表示的隊列q頭部刪除元素x if(q=q-next) return infeasible;