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

《2011-软件技术基础实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《软件技术基础》课程实验指导书实验环境：C/C++语言编程TurboC3.0/VisualC++6.0一、实验内容序号实验内容实验类型学时要求1单链表的操作设计2必做2堆栈操作设计2必做3二叉树操作设计2必做4数据的查找与排序设计2必做二、实验指导实验一单链表的操作一、实验目的1.掌握线性表的链式存储结构(1)线性表的链式存储原理(2)链式存储结构的优缺点2.掌握结构体的应用以及数据结点的生成(1)结构体的定义(2)动态存储分配函数的使用(3)强制类型转换的方法3.掌握指针的应用(1)巩固指针的含义和用法(2)结

2、构体指针的使用二、预习要求1.复习C语言(1)巩固C语言程序设计的基本方法(2)巩固在TC或VC环境中编写和调试C程序2.复习指针和结构体两部分的知识(1)巩固指针的含义以及定义方式(2)理解结构体的定义以及其成员的赋值和引用3.理解课本关于单链表部分的知识(1)掌握单链表的生成原理和过程(2)在草稿纸上画出简单程序流程图三、实验内容1.通过C语言编程，用函数实现不低于五个结点的单链表的建立：(1)要求编写功能函数实现单链表的建立；(2)链表中结点的数据类型为任意原子类型，以下参考算法假设的是整型；(3)采用循环

3、结构建表，请同学自定义循环结束标志，以下是次数循环，同学们可设计为输入某个键值结束，如数字‘-1’结束；(4)编写访问各结点的算法，把建成的单链表顺序输出。2.实现单链表的插入和删除算法。3.编写主函数调用以上各算法函数，调试并运行整个程序，分析运行结果。一、实验原理1．尾插法建立单链表(1)算法原理：从一个空表开始,循环读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到循环结束为止。12345L^(2)算法示意图如下，若要建立L=（1，2，3，4，5）的单链表，则链

4、表结构为：(3)算法描述：//结点结构体定义structnode{intdata;structnode*next;};//尾插法建立n个结点的单链表Lstructnode*CreateList(structnode*L,intn){inti;intx;structnode*p,*q;L=(structnode*)malloc(sizeof(structnode));L->data=n;L->next=NULL;q=L;for(i=n;i>0;i--){p=(structnode*)malloc(sizeof(st

5、ructnode));scanf("%d",&x);p->data=x;q->next=p;p->next=NULL;q=p;}returnL;}2.单链表的访问从头节点开始，依次输出每个节点的值。voidaccess(structnode*h){structnode*p;p=h;while(p->next!=NULL){p=p->next;printf("%d",p->data);}}3．单链表的插入算法(1)算法原理：在以上算法的基础上，在指定位置插入一个新结点。首先定义一个搜索指针p，从头开始搜索(p=p-

6、>next)直到指定位置的前一个位置；然后建立新结点，修改指针使之插入。(2)算法示意图：若要在3号位置插入一个数据域为6的结点t，则链表结构变为：12345L^6(3)算法描述：//在第i个位置上插入一个新结点tstructnode*insert(structnode*L,inti){p=L;j=0;while(p->next!=NULL&&jnext;j++;}if(j!=i-1){printf("iisinvalid!");exit(0);}t=(structnode*)mallo

7、c(sizeof(structnode));scanf("%d",&x);t->data=x;t->next=p->next;p->next=t;returnL;}4.单链表的删除算法请同学们参见课本P14的算法5，注意相关定义和语句的修改和完善。5.同学自行编写主程序，完成整个实验。一、实验报告要求1.按教务处印发的标准的计算机实验报告格式填写实验报告(1)字迹工整，内容属实规范；(2)报告不得打印或复印，也不得抄袭或有雷同。2.本实验为软件设计，报告中应先画程序流程图，再阐述你的设计思路和过程；3.避免纯粹的

8、抄写源程序，应适当地填写一些调试情况以及问题的产生原因和处理办法；4.设计感想可包括你对本次实验的收获、启示以及不足和希望。一、思考题1.如果结点指针P指向链表中某一中间结点，问：如何用P表示P之后的每一个结点？2.单链表可以按随意顺序输出吗？3.单链表和顺序表所花的存储空间相同吗？二、注意事项1.算法和程序是不同的，课本上的算法不能直接拿来调试和运行，必须将其改写为程序