1、我們用l代表最長平台的長度,用k指示最長平台在陣列b中的起始位置(下標)。用j 記住區域性平台的起始位置,用i指示掃瞄b陣列的下標,i從0開始,依次和後續元素比較,若區域性平台長度(i-j)大於l時,則修改最長平台的長度k(l=i-j)和其在b中的起始位置(k=j),直到b陣列結束,l即為所求。
void platform (int b[ ], int n)
//求具有n個元素的整型陣列b中最長平台的長度。
//區域性最長平台
i++; j=i新平台起點
printf(「最長平台長度%d,在b陣列中起始下標為%d」,l,k);
}// platform
2、設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。
3、後序遍歷最後訪問根結點,即在遞迴演算法中,根是壓在棧底的。採用後序非遞迴演算法,棧中存放二叉樹結點的指標,當訪問到某結點時,棧中所有元素均為該結點的祖先。本題要找p和q 的最近共同祖先結點r ,不失一般性,設p在q的左邊。
後序遍歷必然先遍歷到結點p,棧中元素均為p的祖先。將棧拷入另一輔助棧中。再繼續遍歷到結點q時,將棧中元素從棧頂開始逐個到輔助棧中去匹配,第乙個匹配(即相等)的元素就是結點p 和q的最近公共祖先。
typedef struct
stack;
stack s,s1;//棧,容量夠大
bitree ancestor(bitree root,p,q,r)//求二叉樹上結點p和q的最近的共同祖先結點r。 //沿左分枝向下
if(bt==p) //不失一般性,假定p在q的左側,遇結點p時,棧中元素均為p的祖先結點//將棧s的元素轉入輔助棧s1 儲存
if(bt==q) //找到q 結點。
for(i=top;i>0;i--)//;將棧中元素的樹結點到s1去匹配
}while(top!=0 && s[top].tag==1) top退棧
if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍歷
}//結束while(bt!=null ||top>0)
return(null);//q、p無公共祖先
}//結束ancestor
2023年湖南省資料總結要領
1 二路插入排序是將待排關鍵字序列r 1.n 中關鍵字分二路分別按序插入到輔助向量d 1.n 前半部和後半部 注 向量d可視為迴圈表 其原則為,先將r l 賦給d 1 再從r 2 記錄開始分二路插入。編寫實現二路插入排序演算法。2 設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞...
2023年湖南省資料總結高階
free p k1 pre next新的報數起點 printf 4d k1 data 輸出最後乙個結點 free k1 main r next head 生成迴圈鍊錶 jose head,s,m 呼叫函式 3 因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指...
2023年湖南省資料總結綱要
1 有一種簡單的排序演算法,叫做計數排序 count sorting 這種排序演算法對乙個待排序的表 用陣列表示 進行排序,並將排序結果存放到另乙個新的表中。必須注意的是,表中所有待排序的關鍵碼互不相同,計數排序演算法針對表中的每個記錄,掃瞄待排序的表一趟,統計表中有多少個記錄的關鍵碼比該記錄的關鍵...