实验三 二叉排序树的建立和查找
一、 实验目的
1．掌握二叉排序树的建立算法 2．掌握二叉排序树查找算法。
二、 实验环境
操作系统和C语言系统
三、 预习要求
复习二叉排序树的生成及查找算法，编写完整的程序。
四、 实验内容
实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。
五、 参考算法
#include
typedef int KeyType; typedef struct node {
KeyType key;
/*关键字项*/
InfoType otherinfo; /*其它数据域，InfoType视应用情况而定 下面不处理它*/ struct node *lchild,*rchild;/*左右孩子指针*/
/*BSTree是二叉排序树的类型*/
/*假定关键字类型为整数*/ /*结点类型*/
}BSTNode;
typedef BSTNode *BSTree;
void main() {
BSTNode *SearchBST(BSTree T,KeyType key); void InsertBST(BSTree *Tptr,KeyType key); BSTree CreateBST(void); void ListBinTree(BSTree T); BSTree T; BSTNode *p; int key;
printf(\请输入关键字（输入0为结束标志）：\\n\T=CreateBST();
/*用广义表表示二叉树*/
6
}
ListBinTree(T); printf(\
printf(\请输入欲查找关键字：\scanf(\p=SearchBST(T,key); if(p==NULL) else
printf(\找到%d！\\n\ListBinTree(p); printf(\
printf(\没有找到%d！\\n\
BSTNode *SearchBST(BSTree T,KeyType key) { */
}
void InsertBST(BSTree *Tptr,KeyType key) { }
7
/*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返if(T==NULL||key==T->key) /*递归的终结条件*/
return T;
/*若T为空，查找失败；否则成功，返回找到的结点位置
回NULL*/
if(key
return SearchBST(T->rchild,key); /*继续在右子树中查找*/ return SearchBST(T->lchild,key);
/*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/ BSTNode *f,*p=*Tptr; while(p){ }
p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; if(*Tptr==NULL)
*Tptr=p;
/*生成新结点*/ /*原树为空*/
f=p;
/*p的初值指向根结点*/ /*查找插入位置*/
/*树中已有key，无须插入*/ /*f保存当前查找的结点*/
if(p->key==key) return;
p=(key
/*若key
/*新插入的结点为新的根*/
else/*原树非空时将新结点*p作为*f的左孩子或右孩子插入*/
if(key
f->lchild=p; else f->rchild=p;
BSTree CreateBST(void) { }
/*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/ BSTree T=NULL; KeyType key; scanf(\while(key){ } return T;
/*返回建立的二叉排序树的根指针*/
/*读入一个关键字*/
/*假设key=0是输入结束标志*/ /*将key插入二叉排序树T*/
/*初始时T为空树*/
InsertBST(&T,key); scanf(\
/*读入下一关键字*/
六、 思考题
请思考采用其他存储结构实现的二叉排序树建立算法。
七、 实验报告要求
具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。
8
实验四 windows操作系统及应用
一、 实验目的
1．用Windows 2000自带的工具观察内存空间的使用情况； 2．了解Windows 2000注册表的作用，熟悉注册表编辑器； 3．熟悉Windows 2000注册表中5个主要根键的内容与作用； 4．了解备份注册表的重要性，掌握备份注册表的基本方法；
5．学会通过修改注册表，屏蔽桌面“回收站”图标的方法。 6．通过VC++中的跟踪调试技术，了解内存的分配（选做）
二、 实验环境
windows操作系统操作系统和visual c++ 6.0环境
三、 预习要求
搜集注册表相关内容，了解内存分配策略
四、 实验内容
1．观察内存使用情况 用Windows 2000自带的工具观察内存空间的使用情况，观察并写出屏幕显示的内容。
2．使用Windows 2000的注册表屏蔽桌面上的“回收站”。具体内容：（1）备份注册表（或者打开后导出注册表）。（2）运行regedit命令打开注册表。（3）选择注册表中“HKEY_LOCAL_MACHINE”子窗口（即找到此根键），定位到“HKEY_LOCAL_MACHINE\\SOFTWARE\\Microsoft\\Windows\\CurrentVersion\\Explorer\\Desktop\\NameSpace”分支，在该分支下有多个子键对应桌面上的某些系统图标。（4）删除键值为Recycle Bin的子键，如子键645FF040-5081-1-1B-9F08-00AA002F954E。（5）重新启动计算机。（6）根据备份的注册表内容，恢复注册表中被删除的子键，重新启动计算机。（7）观察两次重启后的情况，总结备份、修改和恢复注册表的一般过程。
3．（选做）通过VC++中的跟踪调试技术，了解内存的分配在VC++环境下，编写一个简单计算程序，要求声明的变量中有单个变量、数组、指针变量，等。在变量赋值后设置断点，跟踪程序，在调度窗口中观察变量的值和存储地址。观察数组元素的顺序关系与存储地址之间的关系；观察链式存储的元素的地址关系。
五、 思考题
练习注册表的其他用法。
六、 实验报告要求
具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。
9
实验五 数据库建立
一、 实验目的
1． 熟练掌握用SQL语句实现基本表的创建。
2． 熟练掌握用SQL语句实现数据插入、数据更新和数据查询。 3． 熟练掌握用SQL语句实现数据的简单查询和连接查询。
二、 实验环境
SQL Server2000
三、 预习要求
SQL Server2000的查询分析器和企业管理器的使用，SQL数据定义和数据操纵语言。
四、 实验内容
（一）用SQL语句建立如下mySPJ数据库，包括S，P，J，和SPJ四个基本表（四张表的数据另给），要求实现关系的三类完整性。
S(SNO,SNAME,STATUS,CITY); P(PNO,PNAME,COLOR,WEIGHT); J(JNO,JNAME,CITY); SPJ(SNO,PNO,JNO,QTY)
供应商表S由供应商代码（SNO）、供应商姓名（SNAME）、供应商状态（STATUS）、供应商所在城市（CITY）组成。
零件表P由零件代码（PNO）、零件名（PNAME）、颜色（COLOR）、重量（WEIGHT）组成。
工程项目表J由工程项目代码（JNO）、工程项目名（JNAME）、工程项目所在城市（CITY）组成。
供应情况表SPJ由供应商代码（SNO）、零件代码（PNO）、工程项目代码（JNO）、供应数量（QTY）组成，表示某供应商 供应某种零件 给某工程项目的数量为QTY。 （二）分别使用插入、删除、修改的方式更新基本表中的数据。
五、 实验方法和步骤
（一）使用Microsoft SQL Server企业管理器和查询分析器建立数据库mySPJ：
1.打开“开始－>程序－>Microsoft SQL Server－>企业管理器”；
2.在企业管理器左边的树标签中依次打开“Microsoft SQL Server－> SQL Server组
10