软件技术基础实验指导书.doc
软件技术基础实验指导书目 录实验一 单链表的运算2实验二 二叉树的建立和遍历5实验三 二叉排序树的建立和查找8实验一 单链表的运算一、 实验目的1掌握单链表的基本运算：建立、插入和删除2掌握运用C语言上机调试单链表的基本方法。二、 实验环境操作系统和C语言系统三、 预习要求了解单链表的建立、插入和删除算法，编写完整的程序。四、 实验内容设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个结点值，在单链表中查找该结点的位置。若找到，则显示“找到了”，并输出它在链表中的位置；否则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的结点值x，另一个表示欲插入的数值key，将x插入到值为x的结点前，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个结点值x，表示欲删除的结点，删除该结点，输出单链表所有结点值，观察输出结果。五、 参考算法#include <stdio.h>#include <stdlib.h>/*单链表的定义*/typedef int DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef struct node/*结点类型定义*/DataType data;/*结点的数据域*/struct node *next;/*结点的指针域*/ListNode;typedef ListNode *LinkList;void main()DataType key,x;LinkList head,head1,head2;ListNode *s;LinkList CreateList(void);void PrintList(LinkList head);LinkList LocateNode(LinkList head,DataType key);LinkList InsertList(LinkList head,DataType x,DataType key);LinkList DeleteList(LinkList head,DataType x);head=CreateList();/*建立单链表*/PrintList(head);/*打印单链表*/ printf("输入要查找的值：");scanf("%d",&key);s=LocateNode(head,key); /*单链表查找*/ printf("请输入欲插入到哪个元素前：");scanf("%d",&x);printf("请输入欲插入的元素：");scanf("%d",&key);head1=InsertList(head,x,key); /*单链表插入*/PrintList(head1);/*打印单链表*/ printf("请输入欲删除的结点：");scanf("%d",&x);head2=DeleteList(head1,x);/*单链表删除*/PrintList(head2);/*打印单链表*/*单链表的建立,从前向后或从后向前生成*/LinkList CreateList(void) /在此插入必要语句/*单链表的打印*/void PrintList(LinkList head)/在此插入必要语句/*单链表的查找,输入一个结点值key，显示该结点的位置*/LinkList LocateNode(LinkList head,DataType key)/在此插入必要语句/*单链表的插入，将值为key的新结点插入到不带头结点的单链表值为x的结点前*/void InsertList(LinkList head,DataType x,DataType key)/在此插入必要语句/*单链表的删除，删除不带头结点的单链表中值为x的结点*/int DeleteList(LinkList head,DataType x)/在此插入必要语句六、 思考题如果生成带头结点的单链表，程序应如何修改？七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。实验二 二叉树的建立和遍历一、 实验目的1掌握二叉树的建立算法2掌握二叉树的前序、中序和后序遍历算法。二、 实验环境操作系统和C语言系统三、 预习要求复习二叉树的生成及遍历算法，编写完整的程序。四、 实验内容要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。五、 参考算法二叉树的建立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如si中存放编号为i的结点的指针，即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s1。当结点编号i>1时，产生一个新的结点后，也要将指向该结点的指针存入si，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让sj->lch=si；若i为奇数，则它是双亲结点的右孩子，即让sj->rch=si。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。二叉树的建立也可使用递归算法实现。ABCDEGFDEFG可以按如下次序依次输入给定二叉树及左右子树中的各结点值：（1） 输入根结点值。（2） 若左子树不空，则输入左子树，否则输入一个空格（或其它特殊字符）。（3） 若右子树不空，则输入右子树，否则输入一个空格（或其它特殊字符）。如图所示二叉树，按先序遍历次序输入：A B C F F D E F G F F F F F F (/n)二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。参考算法：#include <stdio.h>#include <stdlib.h>/*二叉树的链式存储表示 */typedef char DataType;/*应由用户定义DataType的实际类型 */typedef struct nodeDataType data;struct node *lchild, *rchild;/*左右孩子指针 */ BinTNode;/*结点类型 */typedef BinTNode *BinTree;main()BinTree T;void CreateBinTree(BinTree &T);void Preorder(BinTree T);void Midorder(BinTree T);void Postorder(BinTree T);printf("请输入先序序列（虚结点用空格表示）：n");CreateBinTree(&T);printf("前序遍历：n");Preorder(T);printf("n");printf("中序遍历：n");Midorder(T);printf("n");printf("后序遍历：n");Postorder(T);printf("n");/*建立二叉树 */void CreateBinTree(BinTree &T)/在此插入必要语句/*前序遍历二叉树 */void Preorder(BinTree T)/在此插入必要语句/*中序遍历二叉树 */void Midorder(BinTree T);/在此插入必要语句/*后序遍历二叉树 */void Postorder(BinTree T);/在此插入必要语句六、 思考题请思考其它的二叉树建立算法。七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。实验三 二叉排序树的建立和查找一、 实验目的1掌握二叉排序树的建立算法2掌握二叉排序树查找算法。二、 实验环境操作系统和C语言系统三、 预习要求复习二叉排序树的生成及查找算法，编写完整的程序。四、 实验内容实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。五、 参考算法#include <stdio.h>#include <stdlib.h>typedef int KeyType;/*假定关键字类型为整数*/typedef struct node/*结点类型*/KeyType key;/*关键字项*/struct node *lchild,*rchild; /*左右孩子指针*/BSTNode;typedef BSTNode *BSTree;/*BSTree是二叉排序树的类型*/void main()BSTree T;BSTNode *p;int key;BSTNode *SearchBST(BSTree T,KeyType key);void InsertBST(BSTree *Tptr,KeyType key);void Midorder(BSTree T);BSTree CreateBST(void);printf("请输入关键字（输入0为结束标志）：n");T=CreateBST();Midorder(T); /*中序遍历二叉排序树，输出排序后序列 */printf("n");printf("请输入欲查找关键字：");scanf("%d",&key);p=SearchBST(T,key);if(p=NULL)printf("没有找到%d！n",key);elseprintf("找到%d！n",key);Midorder(T); /*中序遍历二叉排序树*/printf("n");/*二叉排序树的查找 */BSTNode *SearchBST(BSTree T,KeyType key)/*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/在此插入必要语句/*二叉排序树的插入 */void InsertBST(BSTree *Tptr,KeyType key)/*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/在此插入必要语句/*二叉排序树的创建*/BSTree CreateBST(void)/*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/在此插入必要语句/*中序遍历二叉排序树 */void Midorder(BSTree T)/在此插入必要语句六、 思考题请思考采用其他存储结构实现的二叉排序树建立算法。七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。
