【正文】 * 成功 */ } (2)鏈式存儲結構 在對線性表的討論中可知，對于應用中數(shù)據(jù)元素變動較大的數(shù)據(jù)結構，采用鏈式存儲結構更有利。 (a)鏈式結構定義 struct LQueueNode { int data。 struct LQueueNode *next。 }。 將鏈隊列的頭、尾指針封裝為以下的鏈隊列結構： typedef struct { struct LQueueNode *front。 struct LQueueNode *rear。 } LinkQueue。 圖 。頭指針 front指向隊頭和尾指針 rear指向隊尾。為了操作方便起見，也給鏈隊列增加一個頭結點，并令頭指針 front指向頭結點。由此，空的鏈隊列的判決條件為頭指針 front和尾指針 rear均指向頭結點。 在對帶有頭結點的鏈隊列操作時，建立一個空隊列是需初始化，即置 front=rear且等于頭結點的地址；在正常出列操作時，尾指針不變；但當出列操作后，隊列為空時，要修改隊尾指針，使 rear = front。入列操作是申請一個結點，數(shù)據(jù)域賦 x，指針域賦 NULL，再將該結點鏈結到隊尾，同時，使隊尾指針指向該結點。 (a)鏈隊列 (b)空隊列 圖 帶頭結點的鏈隊列 (b)鏈隊列的算法 算法 初始化算法。 說明： 在對帶有頭結點的鏈隊列操作前，首先需要初始化。即申請頭結點，并置 front、 rear共同指向頭結點。 int LinkQueue_Init(LinkQueue *Q) { Qfront=(struct LQueueNode *)malloc(sizeof(struct LQueueNode))。 if(Qfront==NULL) return(0)。 /* 申請空間失敗 */ Qrear=Qfront。 Qforntnext=NULL。 return(1)。 /* 成功 */ } 算法 鏈式隊列的入列算法。 說明： 入列操作需要申請一個新結點；然后賦值；再將該新結點鏈接 到隊尾；最后調整隊尾指針指向該結點。 int LinkQueue_Enter(LinkQueue *Q, int e) { struct LQueueNode *p。 p=(struct LQueueNode *)malloc(sizeof(struct LQueueNode))。 if(p==NULL) return(0)。 /* 系統(tǒng)資源不夠，申請空間失敗 */ pdata=e。 plink=NULL。 Qrearnext=p。 Qrear=p。 return(1)。 /* 成功 */ } 算法 鏈式隊列的出列算法 。 說明： 一般在出列操作中，尾指針不變；但若出列操作前，隊列只有一個數(shù)據(jù)結點，則尾結點出隊列之后，必須調整隊尾指針，使頭、尾指針共同指向頭結點。 int LinkQueue_Leave(LinkQueue *Q, int *e) /*出列元素值存于 *e中 */ { struct LQueueNode *p。 if(Qrear==Qfront) return(0)。 /* 隊列為空，失敗 */ p=Qfrontnext。 *e=pdata。 Qfrontnext=pnext。 if(pnext==NULL) Qrear=Qfront。 /* 若原隊列中只有一個數(shù)據(jù)結點 */ free(p)。 return(1)。 /* 成功 */ } 隊列的應用 例：下面是一個逐行打印二項展開式 (a + b)n的系數(shù)的例子。 (a + b)n系數(shù)比較繁瑣，不容易記憶，但借助楊輝三角形可以很容易寫出所有系數(shù)值，且不需做一次乘除操作。圖 ，其中第 i行的值依次為 (a + b)i的所有系數(shù)。仔細觀察楊輝三角形，可以發(fā)現(xiàn)這樣的數(shù)據(jù)規(guī)律：第 i+1行的數(shù)據(jù)來源于第 i行相鄰的數(shù)據(jù)兩兩之和。若將第 i行的數(shù)據(jù)存入某隊列結構中，然后將依次出隊列的數(shù)值兩兩相加，即可求出第 i+1行的所有數(shù)據(jù)。以此方法類推，可求出第 i+2行、 … 、第 n行的所有數(shù)據(jù)。 算法 打印楊輝三角形 /* 計算 (a + b)n的所有系數(shù) (即楊輝三角形第 n行數(shù)據(jù) )，并存入 coef[] */ void YANGVI(int n, int coef[]) { Queue q。 /* q為整數(shù)隊列結構 */ int e1,e2。 /* 前后二個出隊列的整數(shù) */ int i,j。 QueueInit(amp。q)。 /* 初始化隊列結構 */ QueueEnter(amp。q,1)。 QueueEnter(amp。q,1)。 /* 楊輝三角形第 1行數(shù)據(jù)進隊列 */ for(i=2。 i=n。 i++ ) /* 逐行計算 */ { QueueEnter(amp。q, 1)。 /* 每行首數(shù)據(jù)必為 1 */ e1=QueueLeave(amp。q)。 e2=QueueLeave(amp。q)。 /* 出隊列 */ for(j=1。 ji。 j++) /* 第 i行的中間數(shù)具有 i1個 */ { QueueEnter(amp。q, e1+e2)。 /* 中間數(shù)據(jù)為 e1+e2 */ if(ji1) /* 循環(huán)中，出列 i2次 */ { e1=e2。 e2=QueueLeave(amp。q)。 } } QueueEnter(amp。q, 1)。 /* 每行尾數(shù)據(jù)必為 1 */ } for(i=0。 !QueueEmpty(q)。 i++) /* 隊列不空，循環(huán) */ coef[i]=QueueLeave(amp。q)。 /* 出隊列，將結果存于 coef[]中 */ }