1、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a[i](0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
2、 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是「區域性根」。確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有,則層次序列根結點的後面應是左右子樹的根;若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣,定義乙個全域性變數指標r,指向層次序列待處理元素。演算法中先處理根結點,將根結點和左右子女的資訊入佇列。
然後,在佇列不空的條件下,迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下:
typedef struct
qnode;
bitree creat(datatype in,level,int n)
//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數
qnode s,qq是元素為qnode型別的佇列,容量足夠大
init(q); int r=0; //r是層次序列指標,指向當前待處理的結點
bitree p=(bitree)malloc(sizeof(binode生成根結點
p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料
for (i=0; i if (in[i]==level[0]) break;
if (i==0) //根結點無左子樹,遍歷序列的1—n-1是右子樹
else if (i==n-1) //根結點無右子樹,遍歷序列的1—n-1是左子樹
else //根結點有左子樹和右子樹
while (!empty(q)) //當佇列不空,進行迴圈,構造二叉樹的左右子樹
else if (i==s.h)
else
}//結束while (!empty(q))
return(p);
}//演算法結束
3、請設計乙個演算法,要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表,表頭指標為head。 二叉樹按二叉鍊錶方式儲存,鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。
4、設有一組初始記錄關鍵字序列(k1,k2,…,kn),要求設計乙個演算法能夠在o(n)的時間複雜度內將線性表劃分成兩部分,其中左半部分的每個關鍵字均小於ki,右半部分的每個關鍵字均大於等於ki。
void quickpass(int r, int s, int t)
r[i]=x;
}5、設一棵樹t中邊的集合為,要求用孩子兄弟表示法(二叉鍊錶)表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。
2023年吉林省資料總結大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序,由於每行元素個數相等,按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和,放入一維陣列中,然後選擇一種排序方法,對該陣列進行排序,注意在排序時若有元素移動,則與之相應的行中各元素也必須做相應變動。void translation f...
2023年吉林省資料總結大綱
1 請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法,設二叉樹用llink rlink法儲存。2 有一種簡單的排序演算法,叫做計數排序 count sorting 這種排序演算法對乙個待排序的表 用陣列表示 進行排序,並將排序結果存放到另乙個新的表中。必須注意的是,表中所有待排序的關鍵碼互不相同,計...
2023年吉林省資料總結大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序,由於每行元素個數相等,按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和,放入一維陣列中,然後選擇一種排序方法,對該陣列進行排序,注意在排序時若有元素移動,則與之相應的行中各元素也必須做相應變動。void translation f...