《软件技术基础》课程实验指导书
实验环境：C/C++语言编程 Turbo C3.0 / Visual C++6.0 一、实验内容
序号 1 2 3 4 实验内容 单链表的操作 堆栈操作 二叉树操作 数据的查找与排序 实验类型 设计 设计 设计 设计 学时 2 2 2 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)算法原理：从一个空表开始,循环读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到循环结束为止。
(2)算法示意图如下，若要建立L=（1，2，3，4，5）的单链表，则链表结构为：
L
1 2 3 4 5 ^ (3)算法描述： //结点结构体定义 struct node {
int data;
struct node *next; };
//尾插法建立n个结点的单链表L
struct 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;i>0;i--)
{
p=(struct node *) malloc(sizeof(struct node)); scanf(\ 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(\ } }
3．单链表的插入算法
(1)算法原理：在以上算法的基础上，在指定位置插入一个新结点。首先定义一个搜索指针p，从头开始搜索(p=p->next)直到指定位置的前一个位置；然后建立新结点，修改指针使之插入。
(2)算法示意图：若要在3号位置插入一个数据域为6的结点t，则链表结构变为：
L
1 2 3 4 5 ^ 6 (3)算法描述：
//在第i个位置上插入一个新结点t
struct node * insert(struct node * L,int i) {
p=L; j=0;
while(p->next!=NULL && j { p=p->next; j++; } if(j!=i-1) { printf(\ exit(0); } t=(struct node *)malloc(sizeof(struct node)); scanf(\ 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.理解堆栈的特殊性质FILO 2.熟悉顺序堆栈的结构和定义方法 3.掌握顺序堆栈的进栈和出栈操作 二、 预习要求 1.熟悉结构体和指针的用法。 2.熟悉VC环境中的调试方法。 三、 实验内容 1.通过C语言编程，实现十进制到二进制的转换。 (1)要求编写功能函数实现堆栈的定义； (2)编写进栈函数push()； (3)编写出栈函数pop()； (4)将转换结果输出。 2.选做：实现十进制到十六进制的转换。 四、 实验原理 1.算法原理：由于十进制数转换为二进制数的方法是依次将十进制数除以2取余，然后将余数倒排序。这样刚好满足“先进后出”的特性，即可以将除2取余的结果依次进栈，最后再依次出栈。 2.算法示意图：例如将十进制数13转换为二进制，其方法如下： 3.算法描述： //顺序栈结构体定义 #define MAXNUM 20 struct stacktype { int stack[MAXNUM]; int top; }; (1)进栈函数定义 int push(struct stacktype *s，int x) { if(s->top >= MAXNUM-1) return false; else s->top++; s->stack[s->top]=x; return true；