數(shù)據(jù)結(jié)構(gòu)作業(yè)

《數(shù)據(jù)結(jié)構(gòu)》

作業(yè)要求：

(1)排序方法需描述算法思路并用程序描述算法，程序請(qǐng)?zhí)砑幼⑨?

(2)排序算法的評(píng)價(jià)和比較主要從復(fù)雜度入手。

第一題

〃二叉樹(shù)結(jié)點(diǎn)

typedefstructBiTNode{

〃數(shù)據(jù)

chardata;

〃擺布孩子指針

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

〃按前序遍歷創(chuàng)建二叉樹(shù)

intCreateBiTree(BiTree&T){

chardata;

〃按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符）'#'

表示空樹(shù)

seanf("%c",&data);

if(data==#){

T=NULL;

)

else{

T=(BiTree)malloc(sizeof(BiTNode));

//生成根結(jié)點(diǎn)

T->data=data;

〃構(gòu)造左子樹(shù)

CreateBiTree(T->lchild);

〃構(gòu)造右子樹(shù)

CreateBiTree(T->rchild);

return0;

〃輸出

voidVisit(BiTreeT){if(T->data!='#'){printf("%c",T->data);

)

}

〃前序遍歷

voidPreOrder(BiTreeT){if(T!=NULL){

//訪問(wèn)根節(jié)點(diǎn)

Visit(T);

//訪問(wèn)左子結(jié)點(diǎn)

PreOrder(T->lchild);

〃訪問(wèn)右子結(jié)點(diǎn)

PreOrder(T->rchild);

〃中序遍歷

voidInOrder(BiTreeT){if(T!=NULL){

//訪問(wèn)左子結(jié)點(diǎn)

InOrder(T->lchild);

〃訪問(wèn)根節(jié)點(diǎn)

Visit(T);

〃訪問(wèn)右子結(jié)點(diǎn)

InOrder(T->rchild);

)

)

〃后序遍歷

voidPostOrder(BiTreeT){if(T!=NULL){

〃訪問(wèn)左子結(jié)點(diǎn)

PostOrder(T->lchild)

〃訪問(wèn)右子結(jié)點(diǎn)

PostOrder(T->rchild)

〃訪問(wèn)根節(jié)點(diǎn)

Visit(T)

)

)

前序/先序遍歷：

結(jié)果：1245736

特征：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其擺布子樹(shù)之前中序遍歷：

結(jié)果：4275136

特征：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其擺布子樹(shù)之中(間)后

序遍歷：

結(jié)果：4752631

特征：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其擺布子樹(shù)之后

第二題

采用中序遍歷的結(jié)果：4275136從大到小排序

直接插入排序：

voidlnsSort(inta[],intk)

(

intj;

for(inti=1;i<k;i++)〃循環(huán)從第2個(gè)元素開(kāi)始

(