精选在二叉排序树中查找关键字为key的记录资料

学院名称

专业班级

学号

实验题目

学生姓名

课程名称

数据结构

4查找

一、实验目的与要求

通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。

二、主要仪器设备

Cfree

三、实验内容和原理

[问题描述]

[存储结构]

[算法的基本思想]

精品文档

[参考源程序]

KeyTypekey;

}ElemType;//元素类型

typedefstructBiTNode{

ElemTypedata;

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

elsereturnsearchBST(bt->rchild,key);

}

voidinsertBST(BiTree*bt,BiTrees){

/*在二叉排序树中插入一个新结点,即依次插入输入的数*/

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

/*二叉排序树的查找，可多次查找，并输出查找的结果*/

do{

s=searchBST(bt,key);

if(s!=NULL)printf("\n成功!这个等价元素是%d.\n",s->data.key);

else

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

printf("\n是否继续?(y/n)：");

scanf("%c",&ch);

ch=getchar();

}

}//main

实验结果：

精品文档

精品文档

学院名称计算机科学与技术

实验成绩

实验日期

5内排序

学生姓名

课程名称

郑海兵

1月2日

数据结构

实验题目

通过本次实验，掌握线性表的排序方法，并分析时间复杂度。

二、主要仪器设备

Cfree

三、实验内容和原理

[问题描述]

设计一个用链表表示的直接选择排序算法，并用程序实现。

[输入]

n个数据。

[输出]

n个数据由小到大排列的结果。

[存储结构]

精品文档

structNumber{

intdata;

structNumber*next;

};

structNumber*Creat_H(intk){//创建单链表

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){//第一次找最小数时的初始化

temp=min=max=r;

}

else{

temp=min=max=r->next;

}//do

while(1){//找出最小数

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

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

max=max->next;

}

else{

break;

}

}//if

else{

temp=max;//相当于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{//初始化时min就已经指向了最小数

if(flag==0){//第一次找到最小数

精品文档

flag++;//又排好一个数

if(flag==n-1){

returnp;

}

}while(1);

}

intmain(){

structNumber*H;

printf("\n请输入元素个数n(n>=2)：");//输入数据(不得少于2个)

scanf("%d",&n);

while(n<2){

}

H=Creat_H(n);

H=Sort(H);

printf("\n排序后的数为：");//数据排序后的序列

while(H!=NULL){

精品文档

}

system("pause");

}

五、实验结果与分析

习题1：这题要从前面和后面同时进行处理，只有这样才能保证时间复杂度为O(N)。

精品文档

六、实验心得及体会

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