软件基础实验指导(学生版)

计算机软件基础实验指导书 －C语言实现

孙旭霞 张晋辉 薛旭

西安理工大学 自动化与信息工程学院 二0一一年六月 计算机软件基础实验指导书 目 录

实验大纲……………………………………... ………………. …… 1 实验报告要求 ……………………………………... ………………. 3 实验一 顺序表的基本操作………………………………………....4 实验二 单链表的基本操作……………………………..……….….5 实验三 堆栈的基本操作……………………………..…………….10 实验四 循环队列的基本操作… …………..…………..…………..14 实验五 稀疏矩阵的转置………………………………....………...18 实验六 二叉排序树的建立与遍历………………………..……….22 实验七 直接插入排序………………………………………..…….24 实验八 直接选择排序……………………………………..……….26 实验九 顺序查找和折半查找……………………………………...28 实验十 二叉排序树查找…………………………………..……….32 计算机软件基础实验指导书

1 《计算机软件基础》课程实验教学大纲 一、制定实验教学大纲的依据 根据本校最新指定的《计算机软件基础》课程教学大纲制定 二、本课程实验教学在培养实验能力中的地位和作用 〈计算机软件基础〉课程主要研究计算机处理数据时数据的结构及其实现方法，是一门有关计算机软件知识及开发技术的专业基础课。其主要任务是使学生深入了解计算机软件，正确选用与使用计算机软件，培养分析、设计新计算机软件的能力以及解决实际问题的能力。实验课是本课程重要的教学环节,其目的是使学生掌握常用的数据结构的使用方法，接受编制基本程序技能的训练，提高学生编制复杂程序的能力。 三、应达到的实验能力标准 1、掌握线性表的概念、线性表的顺序存储结构、线性表的链式存储结构及其操作运算。 2、掌握堆栈和队列的概念、存储结构和操作运算的算法。 3、了解数组的定义和存储结构及其操作运算的算法，学会矩阵的压缩存储方式。 4、掌握二叉树的概念、性质及二叉树的遍历算法 5、掌握插入排序算法，选择排序算法和交换排序算法。 6、掌握顺序表的查找，树表的动态查找及哈希表查找算法。 四、学时、教学文件 学时：本课程总学时为54学时,其中实验为22学时,占总学时的24.5%。 教学文件：校编〈软件基础实验指导书〉；实验报告学生自拟。 要求学生实验前预习实验内容，按照每个实验任务要求画出软件流程图，编制相应的软件程序。指导教师指导学生解决在调试程序中出现的问题，具体软件的测试数据由学生独立完成。 五、实验考核办法与成绩评定 计算机软件基础实验指导书 2 实验课成绩占本课程总成绩20%，对无故缺勤三次以上实验者，本课程不予通过。 六、仪器设备及注意事项 仪器设备：个人计算机 注意事项：注意保护设备 七、实验项目的设置及学时分配

序号 实验项目及内容 学时 性质 要求 适用专业 1 顺序表的插入和删除 2 验证 必修 信息类，通信类，控制类 2 链表的插入和删除 2 设计 必修 同上 3 堆栈的插入和删除 2 验证 必修 同上 4 队列的插入和删除 2 验证 必修 同上 5 对称矩阵和三角矩阵的压缩存储 2 验证 必修 同上

6 二叉树的遍历 （前序遍历、中序遍历和后序遍历） 4 设计 必修 同上

7 插入排序和选择排序 2 验证 必修 同上 8 交换排序（冒泡排序和快速排序） 2 验证 必修 同上 9 顺序查找和二分查找 2 验证 必修 同上 10 二叉排序树查找 2 验证 必修 同上 共计 22 同上 计算机软件基础实验指导书

3 实验报告要求 一、实验目的； 二、实验内容； 三、程序流程图； 四、设计部分程序； 五、实验结果（要求检测所有情况的正确性，写出测试条件及相应的测试结果）； 六、完成思考题。 计算机软件基础实验指导书

4 实验一 顺序表的基本操作(2学时) 一、实验目的 了解顺序表的逻辑特征，掌握顺序表的描述方法、特点及有关的概念，掌握顺序表上的插入和删除等基本操作算法。 二、实验内容 在顺序表List []中，实现顺序表的基本操作，包括：初始化顺序表，在表中插入元素、删除元素。 基本要求： （1） 初始化顺序表； （2） 程序具有顺序表插入、删除和显示功能，可根据用户需要连续操作（插入、删除位置及要插入元素数值均从键盘输入）； （3） 任一操作结束后将顺序表中的内容输出； （4） 程序能检测并提示发生上溢或下溢错误。 （5） 可由用户选择退出程序。 三、实验要点及说明 顺序表又称为线性表的顺序存储结构，它是用一组地址连续的存储单元依次存放线性表的各个元素。 可按如下格式定义顺序表： #define MAXLEN 10 /* 定义顺序表最大元素个数50 */ typedef int datatype; typedef struct{ datatype List[MAXLEN]; /* 定义顺序表List */ int Num; /* 定义顺序表表长（1~MAXLEN）*/ }Seqlist; 模块划分： （1）initiq(Seqlist *la )函数：初始化顺序表 操作前提： la为未初始化线性表。 操作结果： 将la初始化为空表。 （2）insertq(la, i , e)函数：实现插入功能 操作前提：表la已存在，e为合法元素值，1≤i≤ListLength(la)+1。  操作结果：在la中第i个位置插入新的数据元素e，la的长度加1。 （3）deleteq(la, i, e )函数：实现删除功能 操作前提：表la已存在且非空，1≤i≤ListLength(la)。 操作结果： 删除la的第i个数据元素，并用e返回其值，la的长度减1。 （4）print( )函数：实现输出功能 计算机软件基础实验指导书 5 四、参考源程序 #include #define MAXLEN 10 typedef int datatype; typedef struct {datatype List[MAXLEN]; int Num; // Num:1~ MAXLEN }Seqlist; void initiq(Seqlist *la ); int insertq(Seqlist *la,int i,datatype e); int deleteq(Seqlist *la,int i,datatype *e); int print(Seqlist *la); void main() { Seqlist la; datatype e; int s,n,i; /* s 选择操作功能， i 插入或删除数据的位置*/ printf("请输入你的选择: 1---initiate 2---insert 3---delete 4---print 5---exit\nyour choice ="); scanf("%d",&s); while(s!=5) { if(s==1) { initiq( &la ); printf("完成初始化 !\n"); } else if(s==2) { printf("请输入待插入的数据位置:"); scanf("%d",&i); printf("请输入待插入的数据值:"); scanf("%d",&e); n=insertq(&la,i,e); if(n!=0) print(&la); } else if(s==3) { printf("请输入待删除的数据位置:"); scanf("%d",&i); n=deleteq(&la,i,&e); if (n!=0) {printf("已删除的数据为:%d",e); 计算机软件基础实验指导书 6 print(&la); } } else if(s==4) print(&la); else printf("你的选择是错误的!\n "); printf("请输入你的选择: 1---initiate 2---insert 3---delete 4---print 5---exit\nyour choice ="); scanf("%d",&s); } } /*初始化*/ void initiq(Seqlist *la ) { } /*插入*/ int insertq(Seqlist *la,int i,datatype e)/* i 插入位置:0~Num， */ { } /*删除*/ int deleteq(Seqlist *la,int i,datatype *e) { } /*显示输出*/ int print (Seqlist *la) { int m; if (la->Num<=0) { printf("顺序表为空!\n"); return 0; } else { printf("当前的顺序表为:\n"); for(m=0;mNum;m++) printf("List[%d]=%d ",m,la->List[m]); printf("\n表长为%d\n",la->Num); return 1; } } 五、思考题 1．在以上参考程序基础上，增加按数据元素值（key）前插入和删除功能。 2．设顺序表L中的数据元素按递增排列，编写一个算法，将数据元素x插入到顺序表L的适当位置上，以保持顺序表的有序性。 3．设计一算法实现删除顺序表a中第i个元素起的k个元素。