數據結構(c語言版)第三四章習題答案(編輯修改稿)

　

【文章內容簡介】 0), m (sz) { //建立一個最大具有m個元素的空隊列。 Q = new Type[m]。 //創(chuàng)建隊列空間 assert ( Q != 0 )。 //斷言: 動態(tài)存儲分配成功與否 } 插入函數 templateclass Type void QueueType :: EnQueue ( Type amp。item ) { assert ( ! IsFull ( ) )。 //判隊列是否不滿，滿則出錯處理 rear = ( rear + 1 ) % m。 //隊尾位置進1, 隊尾指針指示實際隊尾位置 Q[rear] = item。 //進隊列 tag = 1。 //標志改1，表示隊列不空 } 刪除函數 templateclass Type Type QueueType :: DeQueue ( ) { assert ( ! IsEmpty ( ) )。 //判斷隊列是否不空，空則出錯處理 front = ( front + 1 ) % m。 //隊頭位置進1, 隊頭指針指示實際隊頭的前一位置tag = 0。 //標志改0, 表示棧不滿return Q[front]。 //返回原隊頭元素的值 } 讀取隊頭元素函數 templateclass Type Type QueueType :: GetFront ( ) { assert ( ! IsEmpty ( ) )。 //判斷隊列是否不空，空則出錯處理return Q[(front + 1) % m]。 //返回隊頭元素的值 }(8）如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求：① 寫出循環(huán)隊列的類型定義；② 寫出“從隊尾刪除”和“從隊頭插入”的算法。[題目分析] 用一維數組 v[0..M1]實現循環(huán)隊列，其中M是隊列長度。設隊頭指針 front和隊尾指針rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，(rear+1)%m=front 為隊滿。約定隊頭端入隊向下標小的方向發(fā)展，隊尾端入隊向下標大的方向發(fā)展。（1）define M 隊列可能達到的最大長度typedef struct { elemtp data[M]。 int front,rear。 } cycqueue。（2）elemtp delqueue ( cycqueue Q) //Q是如上定義的循環(huán)隊列，本算法實現從隊尾刪除，若刪除成功，返回被刪除元素，否則給出出錯信息。 { if (==) {printf(“隊列空”)。 exit(0)。} =(+M)%M。 //修改隊尾指針。 return([(+1+M)%M])。 //返回出隊元素。}//從隊尾刪除算法結束void enqueue (cycqueue Q, elemtp x)// Q是順序存儲的循環(huán)隊列，本算法實現“從隊頭插入”元素x。{if (==(+M)%M) {printf(“隊滿”。 exit(0)。) []=x。 //x 入隊列=(+M)%M。 //修改隊頭指針。}// 結束從隊頭插入算法。（9）已知Ackermann函數定義如下: ① 寫出計算Ack(m,n)的遞歸算法，并根據此算法給出出Ack(2,1)的計算過程。② 寫出計算Ack(m,n)的非遞歸算法。int Ack(int m,n) {if (m==0) return(n+1)。 else if(m!=0amp。amp。n==0) return(Ack(m1,1))。 else return(Ack(m1,Ack(m,m1))。 }//算法結束（1）Ack(2,1)的計算過程 Ack(2,1)=Ack(1,Ack(2,0)) //因m0,n0而得 =Ack(1,Ack(1,1)) //因m0,n=0而得 =Ack(1,Ack(0,Ack(1,0))) // 因m0,n0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m0,n=0而得 =Ack(1,Ack(0,2)) // 因m=0而得 =Ack(1,3) // 因m=0而得 =Ack(0,Ack(1,2)) //因m0,n0而得 = Ack(0,Ack(0,Ack(1,1))) //因m0,n0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m0,n0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得（2）int Ackerman( int m, int n) {int akm[M][N]。int i,j。 for(j=0。jN。j++) akm[0][j]。=j+1。 for(i=1。im。i++) {akm[i][0]=akm[i1][1]。 for(j=1。jN。j++) akm[i][j]=akm[i1][akm[i][j1]]。 } return(akm[m][n])。 }//算法結束（10）已知f為單鏈表的表頭指針, 鏈表中存儲的都是整型數據，試寫出實現下列運算的遞歸算法： ① 求鏈表中的最大整數；② 求鏈表的結點個數；③ 求所有整數的平均值。include //定義在頭文件中class List。 class ListNode { //鏈表結點類friend class List。private: int data。 //結點數據 ListNode *link。 //結點指針 ListNode ( const int item ) : data(item), link(NULL) { } //構造函數}。class List { //鏈表類private: ListNode *first, current。 int Max ( ListNode *f )。 int Num ( ListNode *f )。 float Avg ( ListNode *f, intamp。 n )。public: List ( ) : first(NULL), current (NULL) { } //構造函數 ~List ( ){ } //析構函數 ListNode* NewNode ( const int item )。 //創(chuàng)建鏈表結點, 其值為item void NewList ( const int retvalue )。 //建立鏈表, 以輸入retvalue結束 void PrintList ( )。 //輸出鏈表所有結點數據 int GetMax ( ) { return Max ( first )。 } //求鏈表所有數據的最大值 int GetNum ( ) { return Num ( first )。 } //求鏈表中數據個數 float GetAvg ( ) { return Avg ( first )。 } //求鏈表所有數據的平均值}。 ListNode* List :: NewNode ( const int item ) { //創(chuàng)建新鏈表結點 ListNode *newnode = new ListNode (item)。 return newnode。}void List :: NewList ( const int retvalue ) { //建立鏈表, 以輸入retvalue結束 first = NULL。 int value。 ListNode *q。 cout Input your data:\n。 //提示 cin value。 //輸入while ( value != retvalue ) { //輸入有效 q = NewNode ( value )。 //建立包含value的新結點 if ( first == NULL ) first = current = q。 //空表時, 新結點成為鏈表第一個結點else { currentlink = q。 current = q。 } //非空表時, 新結