七、設(shè)帶表頭結(jié)點(diǎn)的雙向鏈表的定義為
typedef int ElemType；
typedef struct dnode { file://雙向鏈表結(jié)點(diǎn)定義
ElemType data； file://數(shù)據(jù)
struct dnode * lLink， * rLink； file://結(jié)點(diǎn)前驅(qū)與后繼指針
DblNode；
typedef DblNode * DblList； file://雙向鏈表
試設(shè)計(jì)一個(gè)算法，改造一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表，所有結(jié)點(diǎn)的原有次序保持在各個(gè)結(jié)點(diǎn)的右鏈域rLink中，并利用左鏈域lLink把所有結(jié)點(diǎn)按照其值從小到大的順序連接起來(lái)。
八、設(shè)有一個(gè)關(guān)鍵碼的輸入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 ，
（1）從空樹(shù)開(kāi)始構(gòu)造平衡二叉搜索樹(shù)，畫(huà)出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類(lèi)型及平衡旋轉(zhuǎn)的結(jié)果。
（2）計(jì)算該平衡二叉搜索樹(shù)在等概率下的查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。
九、下面是求連通網(wǎng)絡(luò)的最小生成樹(shù)的Prim算法的實(shí)現(xiàn)，中間有5個(gè)地方缺失，請(qǐng)閱讀程序后將它們補(bǔ)上。
const int MaxInt = INT_MAX； file://INT_MAX的值在中
const int n = 6； file://圖的頂點(diǎn)數(shù)，應(yīng)由用戶(hù)定義
typedef int AdjMatrix[n>[n>； file://用二維數(shù)組作為鄰接矩陣表示
typedef struct file://生成樹(shù)的邊結(jié)點(diǎn)
int fromVex， toVex； file://邊的起點(diǎn)與終點(diǎn)
int weight； file://邊上的權(quán)值
TreeEdgeNode；
typedef TreeEdgeNode MST[n-1>； file://最小生成樹(shù)定義
void PrimMST （ AdjMatrix G， MST T， int rt ） {
file://從頂點(diǎn)rt出發(fā)構(gòu)造圖G的最小生成樹(shù)T，rt成為樹(shù)的根結(jié)點(diǎn)
TreeEdgeNode e； int i， k = 0， min， minpos， v；
for （ i = 0； i < n； i++ ） file://初始化最小生成樹(shù)T
if （ i ！= rt ） {
T[k>.fromVex = rt；
T[k>.toVex = I ；
T[k++>.weight = G[rt>；
}
for （ k = 0； k < n-1； k++ ） { file://依次求MST的候選邊
min = MaxInt ；
for （ i = k； i < n-1； i++ ） file://遍歷當(dāng)前候選邊集合
if （ T.weight < min ） file://選具有最小權(quán)值的候選邊
{ min = T.weight； minpos = i ； }
if （ min == MaxInt ） file://圖不連通，出錯(cuò)處理
{ cerr 《“Graph is disconnected！”《 endl； exit（1） ； }
e = T[minpos>； T[minpos> = T[k> ； T[k> = e；
v = T[k>.toVex；
for （ i = k+1； i < n-1； i++ ） file://修改候選邊集合
if （ G[v>[T.toVex> < T.weight ）
T.weight = G[v>[T.toVex>；
T.fromVex = v ；
typedef int ElemType；
typedef struct dnode { file://雙向鏈表結(jié)點(diǎn)定義
ElemType data； file://數(shù)據(jù)
struct dnode * lLink， * rLink； file://結(jié)點(diǎn)前驅(qū)與后繼指針
DblNode；
typedef DblNode * DblList； file://雙向鏈表
試設(shè)計(jì)一個(gè)算法，改造一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表，所有結(jié)點(diǎn)的原有次序保持在各個(gè)結(jié)點(diǎn)的右鏈域rLink中，并利用左鏈域lLink把所有結(jié)點(diǎn)按照其值從小到大的順序連接起來(lái)。
八、設(shè)有一個(gè)關(guān)鍵碼的輸入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 ，
（1）從空樹(shù)開(kāi)始構(gòu)造平衡二叉搜索樹(shù)，畫(huà)出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類(lèi)型及平衡旋轉(zhuǎn)的結(jié)果。
（2）計(jì)算該平衡二叉搜索樹(shù)在等概率下的查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。
九、下面是求連通網(wǎng)絡(luò)的最小生成樹(shù)的Prim算法的實(shí)現(xiàn)，中間有5個(gè)地方缺失，請(qǐng)閱讀程序后將它們補(bǔ)上。
const int MaxInt = INT_MAX； file://INT_MAX的值在中
const int n = 6； file://圖的頂點(diǎn)數(shù)，應(yīng)由用戶(hù)定義
typedef int AdjMatrix[n>[n>； file://用二維數(shù)組作為鄰接矩陣表示
typedef struct file://生成樹(shù)的邊結(jié)點(diǎn)
int fromVex， toVex； file://邊的起點(diǎn)與終點(diǎn)
int weight； file://邊上的權(quán)值
TreeEdgeNode；
typedef TreeEdgeNode MST[n-1>； file://最小生成樹(shù)定義
void PrimMST （ AdjMatrix G， MST T， int rt ） {
file://從頂點(diǎn)rt出發(fā)構(gòu)造圖G的最小生成樹(shù)T，rt成為樹(shù)的根結(jié)點(diǎn)
TreeEdgeNode e； int i， k = 0， min， minpos， v；
for （ i = 0； i < n； i++ ） file://初始化最小生成樹(shù)T
if （ i ！= rt ） {
T[k>.fromVex = rt；
T[k>.toVex = I ；
T[k++>.weight = G[rt>；
}
for （ k = 0； k < n-1； k++ ） { file://依次求MST的候選邊
min = MaxInt ；
for （ i = k； i < n-1； i++ ） file://遍歷當(dāng)前候選邊集合
if （ T.weight < min ） file://選具有最小權(quán)值的候選邊
{ min = T.weight； minpos = i ； }
if （ min == MaxInt ） file://圖不連通，出錯(cuò)處理
{ cerr 《“Graph is disconnected！”《 endl； exit（1） ； }
e = T[minpos>； T[minpos> = T[k> ； T[k> = e；
v = T[k>.toVex；
for （ i = k+1； i < n-1； i++ ） file://修改候選邊集合
if （ G[v>[T.toVex> < T.weight ）
T.weight = G[v>[T.toVex>；
T.fromVex = v ；