目 录
实验一单链表的运算 ................................................................................... 2 实验二 二叉树的建立和遍历 ..................................................................... 5 实验三 二叉排序树的建立和查找 ............................................................. 6 实验四 windows操作系统及应用 .............................................................. 9 实验五 数据库建立 ................................................................................. 10 实验六 数据库查询 ................................................................................. 12 附录 ............................................................................................................. 13
1
实验一单链表的运算
一、 实验目的
1．掌握单链表的基本运算：建立、插入和删除 2．掌握运用C语言上机调试单链表的基本方法。
二、 实验环境
操作系统和C语言系统
三、 预习要求
了解单链表的建立、插入和删除算法，编写完整的程序。
四、 实验内容
设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。
五、 参考算法
#include
#include
typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct node /*结点类型定义*/ { DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode;
typedef ListNode *LinkList; void main() { int i; DataType key,x; LinkList head; ListNode *p; LinkList CreateList(void); void PrintList(LinkList head); LinkList LocateNode(LinkList head,DataType key); LinkList GetNode(LinkList head,int i); void InsertList(LinkList head,DataType x,int i);
2
void DeleteList(LinkList head,int i); head=CreateList(); /*建立单链表*/ PrintList(head); /*打印单链表*/ printf(\输入要查找的值：\ scanf(\ p=LocateNode(head,key); /*单链表查找*/ printf(\请输入欲插入元素的位置：\ scanf(\ printf(\请输入欲插入的元素：\ scanf(\ InsertList(head,x,i); /*单链表插入*/ PrintList(head); /*打印单链表*/ printf(\请输入欲删除结点的位置：\ scanf(\ DeleteList(head,i); /*单链表删除*/ PrintList(head); /*打印单链表*/ }
/*单链表的建立,从后向前生成*/ LinkList CreateList(void) {
//在此插入必要语句 }
/*单链表的打印*/
void PrintList(LinkList head) {
//在此插入必要语句 }
/*单链表的查找,输入一个整数，显示该结点的位置*/ LinkList LocateNode(LinkList head,DataType key)
{/*在不带头结点的单链表head中查找其值为key的结点*/ //在此插入必要语句 }
/*单链表的查找2，在不带头结点的单链表head中查找第i个结点*/ LinkList GetNode(LinkList head,int i) {
//在此插入必要语句 }
/*单链表的插入*/
void InsertList(LinkList head,DataType x,int i)
{/*将值为x的新结点插入到不带头结点的单链表head的第i个结点的位置上*/
3
//在此插入必要语句
}
/*单链表的删除，删除不带头结点的单链表中的第i个结点*/ void DeleteList(LinkList head,int i) {
//在此插入必要语句 }
六、 思考题
如果生成带头结点的单链表，程序应如何修改？
七、 实验报告要求
具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。
4
实验二 二叉树的建立和遍历
一、 实验目的
1．掌握二叉树的建立算法
2．掌握二叉树的前序、中序和后序遍历算法。
二、 实验环境
操作系统和C语言系统
三、 预习要求
复习二叉树的生成及遍历算法，编写完整的程序。
四、 实验内容
要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。
五、 参考算法
二叉树的建立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如s[i]中存放编号为i的结点的指针，即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s[1]。当结点编号i>1时，产生一个新的结点后，也要将指向该结点的指针存入s[i]，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让s[j]->lch=s[i]；若i为奇数，则它是双亲结点的右孩子，即让s[j]->rch=s[i]。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。
二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。
六、 思考题
请思考其它的二叉树建立算法。
七、 实验报告要求
具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。
5