《软件基础实验指导(学生版)》由会员分享,可在线阅读,更多相关《软件基础实验指导(学生版)(38页珍藏版)》请在金锄头文库上搜索。
1、计算机软件基础实验指导书C 语言实现孙旭霞张晋辉薛旭西安理工大学自动化与信息工程学院二 0 一一年六月计算机软件基础实验指导书目 录实验大纲 . . 1 实验报告要求. . 3 实验一顺序表的基本操作 4 实验二单链表的基本操作 .5 实验三堆栈的基本操作 .10 实验四循环队列的基本操作 14 实验五稀疏矩阵的转置 .18 实验六二叉排序树的建立与遍历 .22 实验七直接插入排序 .24 实验八直接选择排序 .26 实验九顺序查找和折半查找 .28 实验十二叉排序树查找 .32 计算机软件基础实验指导书1 计算机软件基础课程实验教学大纲一、制定实验教学大纲的依据根据本校最新指定的计算机软件基
2、础课程教学大纲制定二、本课程实验教学在培养实验能力中的地位和作用计算机软件基础课程主要研究计算机处理数据时数据的结构及其实现方法,是一门有关计算机软件知识及开发技术的专业基础课。其主要任务是使学生深入了解计算机软件,正确选用与使用计算机软件,培养分析、设计新计算机软件的能力以及解决实际问题的能力。实验课是本课程重要的教学环节,其目的是使学生掌握常用的数据结构的使用方法,接受编制基本程序技能的训练,提高学生编制复杂程序的能力。三、应达到的实验能力标准1、掌握线性表的概念、线性表的顺序存储结构、线性表的链式存储结构及其操作运算。2、掌握堆栈和队列的概念、存储结构和操作运算的算法。3、了解数组的定义
3、和存储结构及其操作运算的算法,学会矩阵的压缩存储方式。4、掌握二叉树的概念、性质及二叉树的遍历算法5、掌握插入排序算法,选择排序算法和交换排序算法。6、掌握顺序表的查找,树表的动态查找及哈希表查找算法。四、学时、教学文件学时:本课程总学时为54 学时 ,其中实验为22 学时 ,占总学时的24.5%。教学文件:校编软件基础实验指导书;实验报告学生自拟。要求学生实验前预习实验内容,按照每个实验任务要求画出软件流程图,编制相应的软件程序。指导教师指导学生解决在调试程序中出现的问题,具体软件的测试数据由学生独立完成。五、实验考核办法与成绩评定计算机软件基础实验指导书2 实验课成绩占本课程总成绩20%,
4、对无故缺勤三次以上实验者,本课程不予通过。六、仪器设备及注意事项仪器设备:个人计算机注意事项:注意保护设备七、实验项目的设置及学时分配序号实验项目及内容学时性质要求适用专业1 顺序表的插入和删除2 验证必修信息类,通信类,控制类2 链表的插入和删除2 设计必修同上3 堆栈的插入和删除2 验证必修同上4 队列的插入和删除2 验证必修同上5 对称矩阵和三角矩阵的压缩存储2 验证必修同上6 二叉树的遍历(前序遍历、中序遍历和后序遍历)4 设计必修同上7 插入排序和选择排序2 验证必修同上8 交换排序(冒泡排序和快速排序)2 验证必修同上9 顺序查找和二分查找2 验证必修同上10 二叉排序树查找2 验
5、证必修同上共计22 同上计算机软件基础实验指导书3 实验报告要求一、实验目的;二、实验内容;三、程序流程图;四、设计部分程序;五、实验结果(要求检测所有情况的正确性,写出测试条件及相应的测试结果);六、完成思考题。计算机软件基础实验指导书4 实验一顺序表的基本操作(2 学时 ) 一、实验目的 了解顺序表的逻辑特征,掌握顺序表的描述方法、特点及有关的 概念,掌握顺序表上的插入和删除等基本操作算法。 二、实验内容 在顺序表List 中,实现顺序表的基本操作, 包括:初始化顺序表, 在表中插入元素、删除元素。 基本要求: (1) 初始化顺序表; (2) 程序具有顺序表插入、删除和显示功能,可根据 用
6、户需要连续操作(插入、删除位置及要插入元 素数值均从键盘输入); (3) 任一操作结束后将顺序表中的内容输出; (4) 程序能检测并提示发生上溢或下溢错误。 (5) 可由用户选择退出程序。 三、实验要点及说明 顺序表又称为线性表的顺序存储结构,它是用一组地址连续的存 储单元依次存放线性表的各个元素。 可按如下格式定义顺序表: #define MAXLEN 10 /* 定义顺序表最大元素个数50 */ typedef int datatype;typedef struct datatype ListMAXLEN;/* 定义顺序表 List */int Num; /* 定义顺序表表长( 1MAXL
7、EN)*/ Seqlist; 模块划分: (1)initiq(Seqlist *la )函数:初始化顺序表操作前提:la 为未初始化线性表。操作结果:将 la 初始化为空表。 (2)insertq(la, i , e)函数:实现插入功能操作前提: 表 la 已存在, e 为合法元素值, 1iListLength(la)+1 。操作结果:在la 中第 i 个位置插入新的数据元素e,la 的长度加1。(3)deleteq(la, i, e )函数:实现删除功能操作前提:表la 已存在且非空,1iListLength(la) 。操作结果:删除 la 的第 i 个数据元素,并用e返回其值, la 的长
8、度减 1。(4)print( )函数:实现输出功能计算机软件基础实验指导书5 四、参考源程序#include #define MAXLEN 10 typedef int datatype; typedef struct datatype ListMAXLEN; 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)
9、; void main() Seqlist la; datatype e; int s,n,i; /* s 选择操作功能,i 插入或删除数据的位置*/ printf(“ 请输入你的选择: 1-initiate 2-insert 3-delete 4-print 5-exitnyour choice =“); scanf(“%d“, while(s!=5) if(s=1) initiq( printf(“ 完成初始化!n“); else if(s=2) printf(“ 请输入待插入的数据位置:“); scanf(“%d“, printf(“ 请输入待插入的数据值:“); scanf(“%d“,
10、 n=insertq( if(n!=0) print( else if(s=3) printf(“ 请输入待删除的数据位置:“); scanf(“%d“, n=deleteq( if (n!=0) printf(“ 已删除的数据为:%d“,e); 计算机软件基础实验指导书6 print( else if(s=4) print( else printf(“ 你的选择是错误的!n “); printf(“ 请 输 入 你 的 选 择 : 1-initiate 2-insert 3-delete 4-print 5-exitnyour choice =“); scanf(“%d“, /*初始化 */
11、 void initiq(Seqlist *la ) /*插入 */ int insertq(Seqlist *la,int i,datatype e)/* i 插入位置 :0Num,*/ /*删除 */ int deleteq(Seqlist *la,int i,datatype *e) /*显示输出 */ int print (Seqlist *la) int m; if (la-NumNum;m+) printf(“List%d=%d “,m,la-Listm); printf(“n 表长为 %dn“,la-Num); return 1; 五、思考题 1在以上参考程序基础上,增加按数据元
12、素值(key)前插入和删除 功能。 2设顺序表 L 中的数据元素按递增排列,编写一个算法,将数据元素 x 插入到顺序表 L 的适当位置上,以保持顺序表的有序性。3设计一算法实现删除顺序表a 中第 i 个元素起的 k 个元素。计算机软件基础实验指导书7 typedef struct int datatype100; int length; /*顺序表的长度 */ SqList;4设已有线性表 la 的数据结构定义同上, 编写一个算法, 删除顺序表 la 中所有值为 x 的数据元素。 5编写一个算法,实现将两个不同的顺序表复制到一个顺序表中。计算机软件基础实验指导书8 实验二单链表的基本操作(2
13、学时)一、实验目的 了解链表的逻辑结构特征,掌握链表的描述方法、特点及有关概 念,掌握链表的建立、插入、删除以及查找的基本操作算法。 二、实验内容 实现单链表的基本操作,包括:建立单链表,插入结点,删除结 点,查找结点,打印输出单链表中的所有结点。 基本要求: (1)初始化单链表; (2)程序具有单链表插入、删除和显示功能,可根据用 户需要连续操作(插入位置、插入结点的数据及被删除 结点的数据要从键盘输入) ; (3)根据键盘输入的数据在单链表中查找结点; (4)任一操作结束后将单链表中的内容输出; (5)可由用户选择退出程序。 三、实验要点及说明 线性表的链式存储结构是一种物理存储单元上非连
14、续、非顺序的 存储结构,数据元素的逻辑顺序是通过链表中的指针链接的次序实现 的。线性表的链式存储结构中只有一个指针域的链表称为单链表。 可按如下格式定义单链表的结点结构: typedef struct node datatype data; /*结点数据域 */ struct node *next; /* 结点指针域 */ slnode; 划分各功能模块: (1)initiate(slnode *h) 函数:初始化单链表 (2)int Creat1(slnode * h, int n)函数:建立单链表 (3)insert(slnode *h ,int i , datatype x)函数:在带头
15、结点的单链表h 中第 i 个位置前插入新结点x。 (4)delete(slnode *h ,int i)函数:删除第 i 个位置的结点 (5)search(slnode *h ,int i )函数:查找第 i 个位置结点的值。 (6)print(slnode *h )函数:显示输出单链表中的所有结点。 四、参考源程序#include #include #include typedef int datatype; 计算机软件基础实验指导书9 typedef struct node datatype data; struct node *next; slnode; /int l; /*保存查找到的结点位置*/ int initiate (slnode *h ); int Creat1(slnode * h); int insert(slnode *h, int i,datatype x); int deletet(slnode *h, int i,datatype *x); slnode * search