软件基础实验指导书.docx
- 文档编号:16265122
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:19
- 大小:40.69KB
软件基础实验指导书.docx
《软件基础实验指导书.docx》由会员分享,可在线阅读,更多相关《软件基础实验指导书.docx(19页珍藏版)》请在冰点文库上搜索。
软件基础实验指导书
《软件技术基础》课程实验指导书
实验环境:
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)结构体指针的使用
二、预习要求
1.复习C语言
(1)巩固C语言程序设计的基本方法
(2)巩固在TC或VC环境中编写和调试C程序
2.复习指针和结构体两部分的知识
(1)巩固指针的含义以及定义方式
(2)理解结构体的定义以及其成员的赋值和引用
3.理解课本关于单链表部分的知识
(1)掌握单链表的生成原理和过程
(2)在草稿纸上画出简单程序流程图
三、实验内容
1.通过C语言编程,用函数实现不低于五个结点的单链表的建立:
(1)要求编写功能函数实现单链表的建立;
(2)链表中结点的数据类型为任意原子类型,以下参考算法假设的是整型;
(3)采用循环结构建表,以下的循环条件是‘Q’,同学们也可以自定义循环结束标志;
(4)编写访问各结点的算法,把建成的单链表顺序输出。
2.实现单链表的插入和删除算法。
3.编写主函数调用以上各算法函数,调试并运行整个程序,分析运行结果。
四、实验原理
1.尾插法建立单链表
(1)算法原理:
从一个空表开始,循环读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到循环结束为止。
(2)算法示意图如下,若要建立L=(A,B,C,D,E)的单链表,则链表结构为:
(3)算法描述:
//结点结构体定义
structnode
{
chardata;
structnode*next;
};
////尾插法,返回单链表的头结点
structnode*create()
{structnode*h,*p,*s;
elemtypex;
h=(structnode*)malloc(sizeof(structnode));
h->next=NULL;
printf("\nInputastringandexitwithQ:
");
scanf("%c",&x);
while(x!
='Q')
{
s=(structnode*)malloc(sizeof(structnode));
s->data=x;
if(h->next==NULL)
h->next=s;
else
p->next=s;
p=s;
scanf("%c",&x);
}
p->next=NULL;
return(h);
}
2.单链表的访问
从头节点开始,依次输出每个节点的值。
voidaccess(structnode*h)
{
structnode*p;
p=h;
while(p->next!
=NULL)
{
p=p->next;
printf("\n%c\t",p->data);
}
}
3.单链表的插入算法
(1)算法原理:
在以上算法的基础上,在指定位置插入一个新结点。
首先定义一个搜索指针p,从头开始搜索(p=p->next)直到指定位置的前一个位置;然后建立新结点,修改指针使之插入。
(2)算法示意图:
若要在3号位置插入一个数据域为W的结点t,则链表结构变为:
(3)算法描述:
//在第i个位置上插入一个新结点t
structnode*insert(structnode*h,inti)
{
structnode*p,*t;
charx;intj;
p=h;
j=0;
while(p->next!
=NULL&&j { p=p->next; j++; } if(j! =i-1) { printf("iisinvalid! \n"); exit(0); } t=(structnode*)malloc(sizeof(structnode)); scanf("%c",&x); t->data=x; t->next=p->next; p->next=t; return(h); } 4.单链表的删除算法请同学们参见课本P14的算法5,注意相关定义和语句的修改和完善。 5.同学自行编写主程序,完成整个实验。 五、实验报告要求 1.按教务处印发的标准的计算机实验报告格式填写实验报告 (1)字迹工整,内容属实规范; (2)报告不得打印或复印,也不得抄袭或有雷同。 2.本实验为软件设计,报告中应先画程序流程图,再阐述你的设计思路和过程; 3.避免纯粹的抄写源程序,应适当地填写一些调试情况以及问题的产生原因和处理办法; 4.设计感想可包括你对本次实验的收获、启示以及不足和希望。 六、思考题 1.如果结点指针P指向链表中某一中间结点,问: 如何用P表示P之后的每一个结点? 2.找出一单链表的中间结点? 3.用头插法建立一个单链表。 4.头指针和头结点有什么区别? 七、注意事项 1.算法和程序是不同的,课本上的算法不能直接拿来调试和运行,必须将其改写为程序; 2.算法到程序的完善方法: (1)将变量类型具体化; (2)将每一个语句标准化; (3)补充主函数,实现变量定义、函数调用等功能。 3.注意本题在输入字符数据的时候,键盘上的任意按键都是字符,包括回车。 八、实验环境、条件 1.P4、Windows操作系统、台式计算机每人一套; 2.TurboC/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.算法描述: //顺序栈结构体定义 #defineMAXNUM20 structstacktype { intstack[MAXNUM]; inttop; }; (1)进栈函数定义 intpush(structstacktype*s,intx) {if(s->top>=MAXNUM-1) returnfalse; else s->top++; s->stack[s->top]=x; returntrue; } (2)出栈函数定义 intpop(structstacktype*s) {if(s->top<0) returnNULL; else s->top--; return(s->stack[s->top+1]); } (3)进制转换函数定义,以十进制转换为二进制为例 voiddec_to_bin(intN,intB) { inte; 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.如果涉及十六进制的转换,注意A~F需要存储其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)的二叉树,结构可如下图所示: (3)算法描述: //结点结构体定义 structtree { intdata; structtree*lchild; structtree*rchild; }; //递归先序建立二叉树 structtree*create(structtree*BT,intk) {structtree*p,*h; intx; printf("Inputaninteger: "); scanf("%d",&x); if(x! =0) {if(! (p=(structtree*)malloc(sizeof(structtree))))//申请结点空间不成功 return(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.递归遍历 将以上建立的二叉树进行先序遍历每一个结点。 //递归先序遍历二叉树 intvisit(structtree*BT) {if(BT! =NULL) { printf("%d",BT->data); visit(BT->lchild); visit(BT->rchild); } return0; } 3.同学们模仿先序遍历编写中序和后序遍历算法,再编写主函数调用上述算法实现整个程序的调试和运行。 五、实验报告要求 如实验一所述。 六、思考题 1.递归的执行过程是怎样的? 能否用堆栈画图描述? 七、注意事项 1.注意在写递归程序时不要进入死循环; 2.先序建立二叉树时对数据输入的顺序要求是怎样的? 3.主程序调用create()时的实参k应该如何取值? 4.二叉树的三种遍历方式的区别。 八、实验环境、条件 如实验一所述。 实验四数据的查找与排序 一、实验目的 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.对关键字序列为(4938659776132758)的线性表分别进行简单排序和冒泡排序,并分析比较它们的性能。 3.了解和学习其它查找与排序方法。 四、实验原理 1.顺序查找 (1)算法原理: 从一个给定的表中的最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,若直至第一个记录,其关键字和给定值比较都不相等,则表明表中没有所查的记录,查找不成功。 (2)算法描述(注意: a数组应该比a[MAX]有更大的容量): intsearch_seq(inta[MAX],intkey) { a[0]=key; for(i=MAX;i>=1;i--) if(a[i]==key) returni; } 2.折半查找 (1)算法原理: 在一个有序表中,先确定待查记录所在的范围(区间),然后逐步缩小范围直道找到或找不到该记录为止。 (2)算法描述: //升序排列的有序表查找算法 intsearch_bin(inta[Max],intkey) { low=1; high=MAX; while(low<=high) { mid=(low+high)/2; if(key==a[mid]) returnmid;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件 基础 实验 指导书
![提示](https://static.bingdoc.com/images/bang_tan.gif)