1、 void PrintList（LinkList head）; LinkList LocateNode（LinkList head,DataType key）; LinkList GetNode（LinkList head,int i）; void InsertList（LinkList *head,DataType x,int i）; void DeleteList（LinkList *head,int i）;/ clrscr（）; head=CreateList（）; /*建立单链表*/ PrintList（head）; /*打印单链表*/ printf（n输入要查找的值：）; scanf
2、（%d,&key）; p=LocateNode（head,key）; /*单链表查找*/n请输入欲插入元素的位置：i）;n请输入欲插入的元素：x）; InsertList（&head,x,i）; /*单链表插入*/n请输入欲删除结点的位置： DeleteList（&head,i）; /*单链表删除*/ /*单链表的建立,从后向前生成*/LinkList CreateList（void） LinkList head,p; int x; head=NULL;input some inteagers until 0! while（x） p=（LinkList）malloc（sizeof（ListNo
3、de）; /*以下三行：新建结点并初始化*/ p-data=x;next=NULL; if（head=NULL） head=p; else p-next=head;head=p; return （head）;/*单链表的打印*/void PrintList（LinkList head） LinkList p; p=head; while（p!=NULL） printf（%5d,p-data）; p=p-next;/*单链表的查找,输入一个整数，显示该结点的位置*/LinkList LocateNode（LinkList head,DataType key）/*在不带头结点的单链表head中查找
4、其值为key的结点*/ if（head=NULL）printf（List is null!return （head）; if（head-data=key）printf（the wanted data is:,head- while（p-data!=key）&（p=NULL） if（p!=NULL）printf（ else printf（the wanted data is not found! return （p）;/*单链表的查找2，在不带头结点的单链表head中查找第i个结点*/LinkList GetNode（LinkList head,int i） int n=1; while（p!=
5、NULL）&（ni） if（n/*单链表的插入*/void InsertList（LinkList *head,DataType x,int i）/*将值为x的新结点插入到不带头结点的单链表head的第i个结点的位置上*/ LinkList p,q; p=（LinkList）malloc（sizeof（ListNode）;/*以下三行： if（inext=*head;*head=p; else/*找到要插入的前一个位置，然后插入*/ q=GetNode（*head,i-1）; p-next=q- q-next=p;/*单链表的删除，删除不带头结点的单链表中的第i个结点*/void Delete
6、List（LinkList *head,int i） if（i=0）|（*head=NULL）printf（List is null or inext）;free（*head）; p=*head;（-i0） q=p; if（p=NULL）printf（iL! else q-next=p-free（p）;实验二 二叉树的建立和遍历1掌握二叉树的建立算法2掌握二叉树的前序、中序和后序遍历算法。复习二叉树的生成及遍历算法，编写完整的程序。要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。分别利用前序遍历、中序遍历、后序遍历所建二叉树。二叉树的建
7、立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如si中存放编号为i的结点的指针，即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s1。当结点编号i1时，产生一个新的结点后，也要将指向该结点的指针存入si，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让sj-lch=si；若i为奇数，则它是双亲结点的右孩子
8、，即让sj-rch=si。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。math.h/*二叉树的定义*/typedef char DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef struct btnode/*结点类型定义*/ DataType data;/*结点的数据域*/ struct btnode *lchild;/*结点的左指针域*/ struct btnode *rchild;/*结点的右指针域*/BtNode; DataType
9、 ch20; BtNode *s20,*bt,*p;int i=0;/* 以下三行按照前中后序遍历二叉树的函数声明*/void pretrav（BtNode *bt）;void intrav（BtNode *bt）;void postrav（BtNode *bt）;/*按满二叉树编号后的顺序输入结点字符，空的位置用#代替，字符个数不要超过20个*/ninput some characters:%s, ch）;/*输入结点字符*/ for（i=0; idata = chi;lchild = NULL;rchild = NULL; si = p; if（chi = ） continue;/*如果输
10、入的是，即该位置没有结点，无需找其父节点*/ if（i 0） if（i%2 = 1） si/2-lchild = p; /*根据i的奇偶性，将p结点链到其父节点的（左/右？）指针上*/ else si/2-1-rchild = p; /*将p结点链到其父节点的（左/右？20 & chi!=; i+） /* 依次输出各结点及其孩子*/ continue; if（si-lchild!=NULL & si-rchild! printf（%c,%c,%cn,si-data,si-lchild-rchild- else if（si-=NULL） %c,%c,%cs rchild is NULL!n%c,
11、%cs lchild is NULL!,%cn else %c,%cis a leaf!/* 以下按照前中后序遍历二叉树*/printf（npretrav!pretrav（s20）;nintrav!intrav（s20）;npostrav!postrav（s20）;while（1）;/*前序遍历二叉树*/void pretrav（BtNode *bt） BtNode *p; p = bt;if（p != NULL）%c pretrav（bt-lchild）;rchild）;/*中序遍历二叉树*/ void intrav（BtNode *bt）if（bt ! intrav（bt-,bt-/*后序
12、遍历二叉树*/void postrav（BtNode *bt） postrav（bt-实验三 二叉排序树的建立和查找1掌握二叉排序树的建立算法2掌握二叉排序树查找算法。复习二叉排序树的生成及查找算法，编写完整的程序。实现二叉排序树上的查找算法。用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。typedef int InfoType;typedef int KeyType; /*假定关键字类型为整数*/typedef struct node /*结点类型*/ KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据域，I
13、nfoType视应用情况而定 下面不处理它*/ struct node *lchild,*rchild;/*左右孩子指针*/BSTNode;typedef BSTNode *BSTree; /*BSTree是二叉排序树的类型*/ 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;请输入关键
14、字（输入0为结束标志）： T=CreateBST（）; ListBinTree（T）;请输入欲查找关键字： p=SearchBST（T,key）; if（p=NULL）没有找到%d！,key）;找到%d！ ListBinTree（p）;BSTNode *SearchBST（BSTree T,KeyType key） /*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/ if（T=NULL|key=T-key） /*递归的终结条件*/ return T; /*若T为空，查找失败；否则成功，返回找到的结点位置*/ if（keykey） return Search
15、BST（T-lchild,key）;rchild,key）; /*继续在右子树中查找*/void InsertBST（BSTree *Tptr,KeyType key） /*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/ BSTNode *f,*p=*Tptr; /*p的初值指向根结点*/ while（p） /*查找插入位置*/ if（p-key=key） return; /*树中已有key，无须插入*/ f=p; /*f保存当前查找的结点*/ p=（keykey）?lchild:rchild; /*若keyrchild=NULL; /*生成新结点*/ if（*Tptr=
16、NULL） /*原树为空*/ *Tptr=p; /*新插入的结点为新的根*/ else/*原树非空时将新结点*p作为*f的左孩子或右孩子插入*/ if（key f-lchild=p; else f-rchild=p;BSTree CreateBST（void） /*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/ BSTree T=NULL; /*初始时T为空树*/ /*读入一个关键字*/ while（key） /*假设key=0是输入结束标志*/ InsertBST（&T,key）; /*将key插入二叉排序树T*/ scanf（ /*读入下一关键字*/ return T; /*返
17、回建立的二叉排序树的根指针*/六、 思考题请思考采用其他存储结构实现的二叉排序树建立算法。七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。实验五 数据库建立1 熟练掌握用SQL语句实现基本表的创建。2 熟练掌握用SQL语句实现数据插入、数据更新和数据查询。3 熟练掌握用SQL语句实现数据的简单查询和连接查询。SQL Server2000SQL Server2000的查询分析器和企业管理器的使用，SQL数据定义和数据操纵语言。（一）用SQL语句建立如下mySPJ数据库
18、，包括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由供应
19、商代码（SNO）、零件代码（PNO）、工程项目代码（JNO）、供应数量（QTY）组成，表示某供应商 供应某种零件 给某工程项目的数量为QTY。（二）分别使用插入、删除、修改的方式更新基本表中的数据。五、 实验方法和步骤（一）使用Microsoft SQL Server企业管理器和查询分析器建立数据库mySPJ：1.打开“开始程序Microsoft SQL Server企业管理器”；2.在企业管理器左边的树标签中依次打开“Microsoft SQL Server SQL Server组（local）（Windows NT）数据库”， （local）（Windows NT）前的红色标记转化为绿色标
20、记表明NT服务已启动；3.从企业管理器的“工具”菜单中选择“SQL 查询分析器”，打开查询分析器后，在其窗口书写创建数据库mySPJ的SQL语句，点击执行按钮（或F5键）执行该SQL语句；4.在企业管理器左边的树标签中查看数据库是否建立成功。（二）在数据库mySPJ中建立S，P，J，和SPJ四个基本表：按照实验内容给出的基本表结构在查询分析器窗口中书写SQL语句分别建立各表，并设置主键和外键约束；（三）更新表数据：1.利用Insert 语句将习题中给出的示例记录插入各表。2.利用Update更新表中的记录：将p表中的所有红色零件的重量增加5。update pset weight=weight+
21、5where color=红将spj表中所有天津供应商的QTY属性值减少10。用子查询。update spjset qty=qty-10where sno in /不能用sno= 因为返回值多于一个.（select snofrom swhere city=天津 3.利用Delete语句删除p表中的所有红色零件的记录。deletefrom p 实验六 数据库查询（一） 完成下面的简单查询：查询所有“天津”的供应商明细；select *查询所有“红色”的14公斤以上的零件。select pname and weight14;查询工程名称中含有“厂”字的工程明细。select jno,jname,cityfrom jwhere jname like%厂%（二） 完成下面的连接查询：等值连接：求s表和j表的相同城
