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

软件技术基础课程实验指导书实验环境：C/C+语言编程 Turbo C3.0 / Visual C+6.0一、实验内容序号实验内容实验类型学时要求1单链表的操作设计2必做2堆栈操作设计2必做3二叉树操作设计2必做4数据的查找与排序设计2必做二、实验指导实验一 单链表的操作一、 实验目的1.掌握线性表的链式存储结构(1)线性表的链式存储原理(2)链式存储结构的优缺点2.掌握结构体的应用以及数据结点的生成(1)结构体的定义(2)动态存储分配函数的使用(3)强制类型转换的方法3.掌握指针的应用(1)巩固指针的含义和用法(2)结构体指针的使用二、 预习要求1.复习C语言(1)巩固C语言程序设计的基本方法(2)巩固在TC或VC环境中编写和调试C程序2.复习指针和结构体两部分的知识(1)巩固指针的含义以及定义方式(2)理解结构体的定义以及其成员的赋值和引用3.理解课本关于单链表部分的知识(1)掌握单链表的生成原理和过程(2)在草稿纸上画出简单程序流程图三、 实验内容1.通过C语言编程，用函数实现不低于五个结点的单链表的建立：(1)要求编写功能函数实现单链表的建立；(2)链表中结点的数据类型为任意原子类型，以下参考算法假设的是整型；(3)采用循环结构建表，请同学自定义循环结束标志，以下是次数循环，同学们可设计为输入某个键值结束，如数字-1结束；(4)编写访问各结点的算法，把建成的单链表顺序输出。2.实现单链表的插入和删除算法。3.编写主函数调用以上各算法函数，调试并运行整个程序，分析运行结果。四、 实验原理1尾插法建立单链表(1)算法原理：从一个空表开始,循环读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到循环结束为止。12345L (2)算法示意图如下，若要建立L=（1，2，3，4，5）的单链表，则链表结构为：(3)算法描述：/结点结构体定义struct node int data; struct node *next; ;/尾插法建立n个结点的单链表Lstruct node* CreateList(struct node *L,int n) int i; int x; struct node *p,*q; L=(struct node *) malloc(sizeof(struct node); L-data=n; L-next=NULL; q=L; for(i=n;i0;i-) p=(struct node *) malloc(sizeof(struct node); scanf(%d,&x); p-data=x; q-next=p; p-next=NULL; q=p; return L;2. 单链表的访问从头节点开始，依次输出每个节点的值。void access(struct node *h) struct node *p; p=h; while(p-next!=NULL) p=p-next; printf(%d ,p-data); 3单链表的插入算法(1)算法原理：在以上算法的基础上，在指定位置插入一个新结点。首先定义一个搜索指针p，从头开始搜索(p=p-next)直到指定位置的前一个位置；然后建立新结点，修改指针使之插入。(2)算法示意图：若要在3号位置插入一个数据域为6的结点t，则链表结构变为：12345L 6(3)算法描述：/在第i个位置上插入一个新结点tstruct node * insert(struct node * L,int i) p=L; j=0; while(p-next!=NULL & jnext; j+; if(j!=i-1) printf(i is invalid!n); exit(0); t=(struct node *)malloc(sizeof(struct node); scanf(%d,&x); t-data=x; t-next=p-next; p-next=t; return L; 4.单链表的删除算法请同学们参见课本P14的算法5，注意相关定义和语句的修改和完善。5.同学自行编写主程序，完成整个实验。五、 实验报告要求1.按教务处印发的标准的计算机实验报告格式填写实验报告(1)字迹工整，内容属实规范；(2)报告不得打印或复印，也不得抄袭或有雷同。2.本实验为软件设计，报告中应先画程序流程图，再阐述你的设计思路和过程；3.避免纯粹的抄写源程序，应适当地填写一些调试情况以及问题的产生原因和处理办法；4.设计感想可包括你对本次实验的收获、启示以及不足和希望。六、 思考题1.如果结点指针P指向链表中某一中间结点，问：如何用P表示P之后的每一个结点？2.单链表可以按随意顺序输出吗？3.单链表和顺序表所花的存储空间相同吗？七、 注意事项1.算法和程序是不同的，课本上的算法不能直接拿来调试和运行，必须将其改写为程序；2.算法到程序的完善方法：(1)将变量类型具体化；(2)将每一个语句标准化；(3)补充主函数，实现变量定义、函数调用等功能。八、 实验环境、条件1.P4、Windows操作系统、台式计算机每人一套；2.Turbo C/VC+ 软件编程环境；3.学生自备实验报告纸一张，最好有U盘用以备份自己的程序。实验二 堆栈的基本操作一、 实验目的1.理解堆栈的特殊性质FILO2.熟悉顺序堆栈的结构和定义方法3.掌握顺序堆栈的进栈和出栈操作二、 预习要求1.熟悉结构体和指针的用法。2.熟悉VC环境中的调试方法。三、 实验内容1.通过C语言编程，实现十进制到二进制的转换。(1)要求编写功能函数实现堆栈的定义；(2)编写进栈函数push()；(3)编写出栈函数pop()；(4)将转换结果输出。2.选做：实现十进制到十六进制的转换。四、 实验原理1.算法原理：由于十进制数转换为二进制数的方法是依次将十进制数除以2取余，然后将余数倒排序。这样刚好满足“先进后出”的特性，即可以将除2取余的结果依次进栈，最后再依次出栈。2.算法示意图：例如将十进制数13转换为二进制，其方法如下：3.算法描述：/顺序栈结构体定义#define MAXNUM 20struct stacktype int stackMAXNUM; int top;(1)进栈函数定义int push(struct stacktype *s，int x) if(s-top = MAXNUM-1) return false; else s-top+; s-stacks-top=x; return true； (2)出栈函数定义int pop(struct stacktype *s) if(s-top top-; return(s-stacks-top+1); (3)进制转换函数定义void dec_to_bin(int N,int B)int e;InitStack(S); /初始化堆栈，算法定义见课本while(N)push(S,N%B);N=N/B;while(!StackEmpty(S) /堆栈判空，算法定义见课本e=pop(S);printf(“%d”,e);（4）同学自行编写主函数完成上述功能函数的调用，调试和运行该程序，并分析结果。五、 实验报告要求如实验一所述。六、 思考题1.能否编写功能全面的任意进制之间的相互转换的程序？要求程序有一定的交互性能。七、 注意事项1.以上转换函数中的InitStack(S)和StackEmpty(S)两个函数需要自己定义；2.如果涉及十六进制，注意AF的需要存储其ASCII码，然后用%c的格式输出。八、 实验环境、条件如实验一所述。实验三 二叉树实验一、 实验目的1.了解二叉树在存储器中的表示；2.掌握二叉链表的实现方法；3.掌握用二叉链表遍历二叉树的过程；4.深入理解对二叉树的递归遍历过程。二、 预习要求1.二叉树的相关定义和概念(1)预习二叉树的层次概念和左右子树的概念；(2)预习二叉树的性质。2.复习课本上二叉树的两种存储方法(1)理解二叉链表的表示方法和结构特点；(2)理解结构体和指针在二叉树的存储结构中的应用。3.理解课本上二叉树的三种遍历的原理和方法4.复习并掌握C语言中递归程序设计的方法三、 实验内容1.采用递归方法建立二叉树；2.给出三种遍历序列；3.理解递归中堆栈的用处。四、 实验原理1.递归建树(1)算法原理：从根开始，采用先序的方式依次建立含有n个结点的二叉树。(2)算法示意图：若要建立H=（1，2，3，4，5）的二叉树,结构可如下图所示：12345(3)算法描述：/结点结构体定义struct tree int data; struct tree *lchild; struct tree *rchild;/递归建立二叉树struct tree *create(struct tree *BT,int k) struct tree *p,*h; int x; printf(Input an integer: ); scanf(%d,&x); if(x!=0) if(!(p=(struct tree *)malloc(sizeof(struct tree) /申请结点空间不成功 exit(0); p-data=x; p-lchild=NULL; p-rchild=NULL; if(k=0) /是根结点 h=p; if(k=1) /是左结点 BT-lchild=p; if(k=2) /是右结点 BT-rchild=p; create(p,1); /建立左结点 create(p,2); /建立右结点 return(h); 2递归遍历将以上建立的二叉树进行先序遍历每一个结点。/递归先序遍历二叉树int visit(struct tree *BT) if(BT!=NULL) printf(%d ,BT-data); visit(BT-lchild); visit(BT-rchild); return 0;3.同学们模仿先序遍历编写中序和后序遍历算法，再编写主函数调用上述算法实现整个程序的调试和运行。五、 实验报告要求如实验一所述。六、 思考题1.递归的执行过程是怎样的？能否用堆栈画图描述？七、 注意事项1.注意在写递归程序时不要进入死循环；2.二叉树的三种遍历方式的区别。八、 实验环境、条件如实验一所述。实验四 数据的查找与排序一、 实验目的1.了解数据查找的一系列方法(1)了解查找表的分类(2)掌握折半查找法的原理2.掌握各种排序（简单插入，简单选择，冒泡排序，快速排序等）方法及适用场合，并能在解决实际问题时灵活应用。3.了解查找与排序在实际生活中的应用。二、 预习要求1.预习课本有关查找和排序的概念2.预习查找表的分类以及各类查找表的查找方法3.在草稿纸上画出四种排序方法的简单程序流程图4.重点预习如下算法：(1)折半查找法的基本原理和过程(2)简单排序和冒泡排序算法三、 实验内容现有给定序列(5，13，19，21，37，56，64，75，80，88)，写出查找关键字K分别是21和85的完整程序。1.通过C语言编程，用函数实现折半查找(1)对于给定的记录集可以是有序或无序的；(2)对于无序的记录集，考虑先排序再查找。2.对关键字序列为（49 38 65 97 76 13 27 58）的线性表分别进行简单排序和冒泡排序，并分析比较它们的性能。3.了解和学习其它查找与排序方法。四、 实验原理1.顺序查找(1)算法原理：从一个给定的表中的最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找不成功。(2)算法描述（注意：a数组应该比aMAX 有更大的容量）：int search_seq(int aMAX,int key) a0=key; for(i=MAX;i=1;i-) if(ai=key) return i; 2.折半查找(1)算法原理：在一个有序表中，先确定待查记录所在的范围（区间），然后逐步缩小范围直道找到或找不到该记录为止。(2)算法描述：/升序排列的有序表查找算法int search_bin(int aMax,int key) low=1;high=MAX;while(low=high) mid=(low+high)/2; if(key=amid) return mid; else if(keyamid) high=mid-1; else low=mid+1;return 0;3.简单插入排序(1)算法原理：把n个数据元素的序列分为两部分，（R1,Ri-1）为已排好序的有序部分，（Ri,Ri+1,Rn）为未排好序的部分。这时，把未排序的部分的第1个元素Ri依次与R1,Ri-1比较，并插入到有序部分的合适位置上，使得（R1,Ri）变为新的有序部分。(2)算法描述：insertsort(int x,int n) int i,j,a; for(i=0;i-1 & a xj) xj+1=xj; j-; xj+1=a; 4.简单选择排序(1)算法原理：第一趟排序是在无序的（R1,R2,R3,Rn）按排序码选出最小的元素，将它与R1交换；第二趟排序是在无序的（R2,R3,Rn）中选出最小的元素，将它与R2交换；如此经过n-1趟后整个数据元素序列就是有序的。(2)算法描述：selectsort (int x,int n) int i,j,small,swap;for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(xjRi+1则交换Ri和Ri+1的位置。第一趟完毕时Rn是序列中最大的数据元素。再从R1开始，两两比较Ri和Ri+1（i=1,2,n-2）的大小，若RiRi+1则交换Ri和Ri+1的位置。第二趟完毕时Rn-1是序列中次大的数据元素。如此反复进行n-1趟排序后将全部有序。(2)算法描述：bubblesort (int x,int n) int i,j,flag,swap; flag=1;