精選在二叉排序樹中查找關(guān)鍵字為key的記錄資料

學(xué)院名稱

專業(yè)班級

學(xué)號

實(shí)驗(yàn)題目

學(xué)生姓名

課程名稱

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

4查找

一、實(shí)驗(yàn)?zāi)康呐c要求

通過本次實(shí)驗(yàn)，掌握查找表上的有關(guān)查找方法，并分析時(shí)間復(fù)雜度。

二、主要儀器設(shè)備

Cfree

三、實(shí)驗(yàn)內(nèi)容和原理

[問題描述]

[存儲(chǔ)結(jié)構(gòu)]

[算法的基本思想]

精品文檔

[參考源程序]

KeyTypekey;

}ElemType;//元素類型

typedefstructBiTNode{

ElemTypedata;

elseif(key<bt->data.key)returnsearchBST(bt->lchild,key);

elsereturnsearchBST(bt->rchild,key);

}

voidinsertBST(BiTree*bt,BiTrees){

/*在二叉排序樹中插入一個(gè)新結(jié)點(diǎn),即依次插入輸入的數(shù)*/

if(*bt==NULL)*bt=s;

elseif(s->data.key<(*bt)->data.key)insertBST(&((*bt)->lchild),s);

elseif(s->data.key>(*bt)->data.key)insertBST(&((*bt)->rchild),s);

}

精品文檔

KeyTypekey;

scanf("%d",&key);

bt=NULL;

while(key!=-1){

scanf("%d",&key);

}//while

/*二叉排序樹的查找，可多次查找，并輸出查找的結(jié)果*/

do{

s=searchBST(bt,key);

if(s!=NULL)printf("\n成功!這個(gè)等價(jià)元素是%d.\n",s->data.key);

else

printf("\n沒有找到!\n");

printf("\n是否繼續(xù)?(y/n)：");

scanf("%c",&ch);

ch=getchar();

}

}//main

實(shí)驗(yàn)結(jié)果：

精品文檔

精品文檔

學(xué)院名稱計(jì)算機(jī)科學(xué)與技術(shù)

實(shí)驗(yàn)成績

實(shí)驗(yàn)日期

5內(nèi)排序

學(xué)生姓名

課程名稱

鄭海兵

1月2日

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

實(shí)驗(yàn)題目

通過本次實(shí)驗(yàn)，掌握線性表的排序方法，并分析時(shí)間復(fù)雜度。

二、主要儀器設(shè)備

Cfree

三、實(shí)驗(yàn)內(nèi)容和原理

[問題描述]

設(shè)計(jì)一個(gè)用鏈表表示的直接選擇排序算法，并用程序?qū)崿F(xiàn)。

[輸入]

n個(gè)數(shù)據(jù)。

[輸出]

n個(gè)數(shù)據(jù)由小到大排列的結(jié)果。

[存儲(chǔ)結(jié)構(gòu)]

精品文檔

structNumber{

intdata;

structNumber*next;

};

structNumber*Creat_H(intk){//創(chuàng)建單鏈表

structNumber*L;

structNumber*p;

p=(structNumber*)malloc(sizeof(structNumber));

L=p;

inttemp;

inti;

printf("\n請輸入元素：");

for(i=1;i<=k;i++){

scanf("%d",&temp);

p->data=temp;

if(i==k){

p->next=NULL;

break;

}

p->next=(structNumber*)malloc(sizeof(structNumber));

p=p->next;

}//for

returnL;

精品文檔

structNumber*min;

do{

if(flag==0){//第一次找最小數(shù)時(shí)的初始化

temp=min=max=r;

}

else{

temp=min=max=r->next;

}//do

while(1){//找出最小數(shù)

if(min->data<=max->next->data){

if(max->next->next!=NULL){

max=max->next;

}

else{

break;

}

}//if

else{

temp=max;//相當(dāng)于temp->next=min

min=max->next;

if(max->next->next!=NULL){

max=max->next;

}

精品文檔

}//else

}

else{

temp->next=min->next;

}

if(flag==0){

r=min;

r->next=p;

p=r;

}

else{

min->next=r->next;

r->next=min;

r=min;

}

}//if

else{//初始化時(shí)min就已經(jīng)指向了最小數(shù)

if(flag==0){//第一次找到最小數(shù)

精品文檔

flag++;//又排好一個(gè)數(shù)

if(flag==n-1){

returnp;

}

}while(1);

}

intmain(){

structNumber*H;

printf("\n請輸入元素個(gè)數(shù)n(n>=2)：");//輸入數(shù)據(jù)(不得少于2個(gè))

scanf("%d",&n);

while(n<2){

}

H=Creat_H(n);

H=Sort(H);

printf("\n排序后的數(shù)為：");//數(shù)據(jù)排序后的序列

while(H!=NULL){

精品文檔

}

system("pause");

}

五、實(shí)驗(yàn)結(jié)果與分析

習(xí)題1：這題要從前面和后面同時(shí)進(jìn)行處理，只有這樣才能保證時(shí)間復(fù)雜度為O(N)。

精品文檔

六、實(shí)驗(yàn)心得及體會(huì)

排序有很多種方法，如冒泡排序、直接插入排序、希爾