(完整word版)在二叉排序树中查找关键字为key地记录簿

1、实用标准文案学院名称专业班级实验成绩学生姓名学号实验日期课程名称数据结构实验题目4 查找一、实验目的与要求通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。二、主要仪器设备Cfree三、实验内容和原理2.实习题1问题描述编写程序实现下面运算：在二叉排序树中查找关键字为key的记录。输入排序二叉树，以及要查找的数字（节点）。输出显不该节点是否存在。存储结构有序表采用顺序方式存储。算法的基本思想若一叉排序树为空树，查找失败，返回null或0;否则，将key与根节点的关键字比较：若key=根节点的关键字，查找成功；若key根节点的关键字，继续在左子树中查找；若key根节点的关键字，继续在右

2、子树中查找。精彩文档参考源程序#include <malloc.h>#include <stdio.h>#define NULL 0typedef int KeyType;typedef struct KeyType key;ElemType; 元素类型typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree searchBST(BiTree bt,KeyType key)/*在二叉排序树bt中查找其关键字等于给定值的结点是否存在，并输出相应信息*/

3、if (bt=NULL) return NULL;/在排序二叉树中进行递归查找else if (bt->data.key=key) return bt;else if (key<bt->data.key) return searchBST(bt->lchild,key);else return searchBST(bt->rchild,key);void insertBST(BiTree *bt,BiTree s)/*在二叉排序树中插入一个新结点，即依次插入输入的数*/if (*bt=NULL) *bt=s;else if (s->data.key<(

4、*bt)->data.key) insertBST(&(*bt)->lchild),s);else if (s->data.key>(*bt)->data.key) insertBST(&(*bt)->rchild),s);main()char ch;KeyType key;BiTree bt,s;int i=0;/*建立一棵二叉排序树，元素从键盘按先序输入，直到输入关键字等于-1为止*/printf("n请输入元素(-1:结束)：n");以-1为结束scanf("%d",&key);bt=NU

5、LL;while (key!=-1)s=(BiTree)malloc(sizeof(BiTNode);(s->data).key=key;s->lchild=s->rchild=NULL;insertBST(&bt,s);scanf("%d",&key);/while/*二叉排序树的查找，可多次查找，并输出查找的结果*/do printf("n输入你想要查找的元素：");scanf("%d",&key);s=searchBST(bt,key);if (s!=NULL) printf("

6、;n 成功！这个等价元素是%d.n",s->data.key);elseprintf("n 没有找到！n");printf("n 是否继续？(y/n):");scanf("%c",&ch);ch=getchar();while (ch='y' | ch='Y');getchar();main实验结果：1FJ 相 U 入 J L,本4-1 -)：Q3 4 35 324 23 354 65 34 23 3 45 23 12kl，入你楣要杳找的7T素；2 k有找到？出否继续？y谕入你想

7、熨古找的.元素二34女功，这外警价元素足34. k由继续五、实验结果与分析(2)习题1:采用先序遍历的方式生成二叉树，程序中多次使用的递归的算法。使程序看起来很简洁。如果把头结点的生成也放到生成树的函数中，会使程序看起来更加调理。六、实验心得及体会查找是很多程序的基础， 很多程序中都会用到查找。比如在线性表的插入和删除时要查找合适的位置。所以学好查找是很必要的。本次实验只要是采取了这般查找的方法。其实还有很多查找的方法。如顺序查找，索引顺序表查找。每种查找方法各有优劣。如折半查找的平均查找长度小于顺序查找，但它要求查找的表为有序的。所以需将无序表排序成有序表。这又会浪费运行时间。编写程序时遇到

8、了很多的困难，如先序生成树更好还是中序生成更好。太原理工大学学生实验报告学院名称计算机科学与技术专业班级计Z1002班实验成绩学生姓名郑海兵学号2010001420实验日期1月2日课程名称数据结构实验题目5内排序一、实验目的与要求通过本次实验，掌握线性表的排序方法，并分析时间复杂度。二、主要仪器设备Cfree三、实验内容和原理问题描述设一个用链表表示的直接选择排序算法，并用程序实现。输入n个数据。输出n个数据由小到大排列的结果。存储结构待排序记录顺序存储。算法的基本思想已知待排序初始序列用单链表存储，头指针head指向A个结点，从这个待排序列中找出最小结点，插入 head之后，用r来指示。r以

9、前为已排序序列，r以后为未排序序列。再从 未排序序列中找出最小结点插入r的后面，让r指向这个结点。反复执行这个过程， 直到排好序。参考源程序#include<stdio.h>#include<malloc.h>int n;struct Numberint data;struct Number* next;；struct Number* Creat_H(int k)/ 创建单链表struct Number* L;struct Number* p;p=(struct Number*)malloc(sizeof(struct Number);L=p;int temp;int

10、i;printf("n请输入元素：");for(i=1;i<=k;i+)scanf("%d",&temp);p->data=temp;if(i=k)p->next=NULL;break;p->next=(struct Number*)malloc(sizeof(struct Number);p=p->next;/forreturn L;/struct Number* Creat_Hstruct Number* Sort(struct Number* p)/直接选择排序struct Number* max;struct

11、 Number* min;struct Number* temp;struct Number* r;r=p;int flag=0;doif(flag=0)第一次找最小数时的初始化 temp=min=max=r;elsetemp=min=max=r->next;/dowhile(1)找出最小数if(min->data<=max->next->data)if(max->next->next!=NULL)max=max->next;elsebreak;/ifelsetemp=max; 相当于 temp->next=minmin=max->n

12、ext;if(max->next->next!=NULL)max=max->next;elsebreak;elsewhileif(temp!=min)if(min->next=NULL)temp->next=NULL;elsetemp->next=min->next;if(flag=0)r=min;r->next=p;p=r;elsemin->next=r->next;r->next=min;r=min;/ifelse初始化时min就已经指向了最小数if(flag=0)/第一次找到最小数r=min;p=r;elser=min;/

13、elseflag+;又排好一个数if(flag=n-1)return p;while(1);int main()struct Number* H;printf("n请输入元素个数n (n>=2) :");/输入数据(不得少于2个)scanf("%d",&n);while(n<2)printf("nError!请重新输入元素个数n：");scanf("%d",&n);H=Creat_H(n);H=Sort(H);printf("n排序后的数为：");/数据排序后的序列while(H!=NULL)printf("%-4d”,H->data);H=H->next;printf("n");system("pause");return 0;getchar();五、实验结果与分析习题1:这题要从前面和后面同时进行处理，只有这样才能保证