软件技术基础实验指导书.doc

《软件技术基础实验指导书.doc》由会员分享，可在线阅读，更多相关《软件技术基础实验指导书.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件技术基础实验指导书目 录实验一 单链表的运算2实验二 二叉树的建立和遍历5实验三 二叉排序树的建立和查找8实验一 单链表的运算一、 实验目的1掌握单链表的基本运算：建立、插入和删除2掌握运用C语言上机调试单链表的基本方法。二、 实验环境操作系统和C语言系统三、 预习要求了解单链表的建立、插入和删除算法，编写完整的程序。四、 实验内容设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：（1）从键盘输入n个整数，以0作为结束标记，产生不带表头的单链表，并输入结点值。（2）从键盘输入1个结点值，在单链表中查找该结点的位置。若找到，则显示“找到了”，并输出它在链表中的位

2、置；否则显示“找不到”。（3）从键盘输入2个整数，一个表示欲插入的结点值x，另一个表示欲插入的数值key，将x插入到值为x的结点前，输出单链表所有结点值，观察输出结果。（4）从键盘输入1个结点值x，表示欲删除的结点，删除该结点，输出单链表所有结点值，观察输出结果。五、 参考算法#include #include /*单链表的定义*/typedef int DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef struct node/*结点类型定义*/DataType data;/*结点的数据域*/struct node *next;/

3、*结点的指针域*/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

4、 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,

5、&x);head2=DeleteList(head1,x);/*单链表删除*/PrintList(head2);/*打印单链表*/*单链表的建立,从前向后或从后向前生成*/LinkList CreateList(void) /在此插入必要语句/*单链表的打印*/void PrintList(LinkList head)/在此插入必要语句/*单链表的查找,输入一个结点值key，显示该结点的位置*/LinkList LocateNode(LinkList head,DataType key)/在此插入必要语句/*单链表的插入，将值为key的新结点插入到不带头结点的单链表值为x的结点前*/void

6、InsertList(LinkList head,DataType x,DataType key)/在此插入必要语句/*单链表的删除，删除不带头结点的单链表中值为x的结点*/int DeleteList(LinkList head,DataType x)/在此插入必要语句六、 思考题如果生成带头结点的单链表，程序应如何修改？七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。实验二 二叉树的建立和遍历一、 实验目的1掌握二叉树的建立算法2掌握二叉树的前序、中序和后序遍历

7、算法。二、 实验环境操作系统和C语言系统三、 预习要求复习二叉树的生成及遍历算法，编写完整的程序。四、 实验内容要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。五、 参考算法二叉树的建立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如si中存放编号为i的结点的指针，

8、即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s1。当结点编号i1时，产生一个新的结点后，也要将指向该结点的指针存入si，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让sj-lch=si；若i为奇数，则它是双亲结点的右孩子，即让sj-rch=si。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。二叉树的建立也可使用递归算法实现。ABCDEGFDEFG可以按如下次序依次输入给定二叉树及左右子树中的各结点值：（1） 输入根结点值。（2） 若左子树不空，则输入左子树，否则输入一个空格（或其它特殊字符）。（3） 若

9、右子树不空，则输入右子树，否则输入一个空格（或其它特殊字符）。如图所示二叉树，按先序遍历次序输入：A B C F F D E F G F F F F F F (/n)二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。参考算法：#include #include /*二叉树的链式存储表示 */typedef char DataType;/*应由用户定义DataType的实际类型 */typedef struct nodeDataType data;struct node *lchild, *rchild;/*左右孩子指针 */ BinTNode;/*结点类型 *

10、/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);pr

11、intf(n);/*建立二叉树 */void CreateBinTree(BinTree &T)/在此插入必要语句/*前序遍历二叉树 */void Preorder(BinTree T)/在此插入必要语句/*中序遍历二叉树 */void Midorder(BinTree T);/在此插入必要语句/*后序遍历二叉树 */void Postorder(BinTree T);/在此插入必要语句六、 思考题请思考其它的二叉树建立算法。七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验

12、总结等。实验三 二叉排序树的建立和查找一、 实验目的1掌握二叉排序树的建立算法2掌握二叉排序树查找算法。二、 实验环境操作系统和C语言系统三、 预习要求复习二叉排序树的生成及查找算法，编写完整的程序。四、 实验内容实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。五、 参考算法#include #include typedef int KeyType;/*假定关键字类型为整数*/typedef struct node/*结点类型*/KeyType key;/*关键字项*/struct node *lchild,*rch

13、ild; /*左右孩子指针*/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); /*中序遍历二叉排序树，

14、输出排序后序列 */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(BSTr

15、ee *Tptr,KeyType key)/*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/在此插入必要语句/*二叉排序树的创建*/BSTree CreateBST(void)/*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/在此插入必要语句/*中序遍历二叉排序树 */void Midorder(BSTree T)/在此插入必要语句六、 思考题请思考采用其他存储结构实现的二叉排序树建立算法。七、 实验报告要求具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。