资源描述：
《计算机软件基础实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《计算机软件基础》实验指导书信息工程学院实验一线性表及其应用实验实验二约瑟夫实验实验三二叉树的遍历实验实验四无序表的查找与排序实验实验五学生成绩管理系统实验实验一线性表及其应用一、实验目的1•熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。二、实验原理♦在数据处理中，大量数据均以表格
2、形式出现，称为线性表，它是一种最简单也是最常见的数据结构。♦线性表是数据元素的有限序列。♦线性表的结构特点是:数据元素之间是线性关系，线性表中存在唯一的“第一个元素”（表头），必存在一个唯一的“最后一个元素”（表尾）。除第一个元素外，每个元素有且只有一个前趋元素，除最后一个元素外，每个元素有且只有一个后续元素。三、实验内容1.顺序线性表的建立、插入及删除。2•链式线性表的建立、插入及删除。四、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2•利用前面的实验先建立一个顺
3、序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68o3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。五、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#defineMAXSIZE1024typedefintelemtype;/*线性表中存放整型元素*/typedefstruct{elemt
4、ypevec[MAXSIZE];intlen;/*顺序表的长度*/Jsequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序(顺序表中元素的次序)的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：typedefintelemtype;typedefstructnode{elemtypedata;〃数
5、据域structnode*next;〃指针域}linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc(),如给指针变量p分配一个结点的地址：p=(linklist*)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值(NULL)。六、实验报告要求♦简述实验目的、原理♦写出线性表插入
6、、删除结点算法♦比较利用数组和指针实现线性表的插入与删除的不同。♦附上程序清单实验二约瑟夫实验一、实验目的♦理解队列的概念♦熟悉队列的操作原则（FIFO）♦用循环队列求解约瑟夫问题二、实验原理队列是一种特殊的线性表，它只允许在一端进行插入、在另一端进行删除。允许插入的端称为队尾，允许删除的端称为排头。显然，在队列中，最先插入的元素将最先删除，因此又称队列为先进先出（FIFO）线性表。队的分类1、顺序队：用一维数组连续存放队列元素。特殊：存放队列的数组形成一个头尾相接的环形一一循环队列。2、链队：队
7、列的容量无法预估计时，可以采用链表作存储结构，称为链队。队的应用♦队列的操作遵循FIFO原则，常被应用在模拟排队的一类问题中。1、多用户的CPU管理2、缓冲区的设计三、实验要求：n个人围坐在圆桌周围，从某个人开始编号为1,2,3,4,…，n,编号为1的位置上的人从1开始报数，数到m的人出列，从下一个人又从1开始报数，数到m的人便是第二个出列的人。如此重复下去，直到最后一个人出列为止。四、方法说明：1、构建循环队列以自然数1,2,3,…，n为元素构成一个循环队列，首先定义一个数组A[n]存放此队列中
8、个元素的直接后续，其中数组元素A[i]表示自然数i的下一个整数。显然，在初始时，此数组的各元素为：2、出列相应操作以后由于不断有元素从这个队列中出来，假设当前要出列的整数为k的前一个数为P，则有A[m]=k,且k的下一个数为A(k),即：•••,p,k,A[k],•••当k出列以后，队列将变为：…，p,A[k],使队列中整数k出列，需做一下工作：1、将出列的整数k依次存入另一数组B[n];2、将元素A[k]的值赋给A[p]o3、模拟报数当整数k出列后，下一轮第一个报数者应是A[k]
