数据结构实验指导书

《数据结构实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验指导书实验一线性表【实验目的】1、掌握用Turboc上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。【实验学时】2学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删

2、除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立线性表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。二、用C语言编程实现建立一个单链表，并在此表中插入一个元

3、素和删除一个元素1、通过键盘读取元素建立单链表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。三、用C语言编程实现两个按递增顺序排列线性表的合并1、编程实现合并按递增顺序排列的两个顺序表算法；2、编程实现合并按递增顺序排列的两个单链表算法。【思考问题】结合实验过程，回答下列问题：1、何时采用顺序表处理线性结构的问题为最佳选择；2、何时采用链表处理线性结构的问题为最佳选择。【实验报告要求】1、根据对线性表的理解，如何创建顺序表和单链表；1、实现顺序表插入和删除操作的程序设计思路；2、实现链表插入和删除操作的程序设计思路；3、实现两

4、表合并操作的程序设计思路；4、调试程序过程中遇到的问题及解决方案；5、本次实验的结论与体会。实验二栈和队列【实验目的】1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用；2、掌握栈和队列的特点，即后进先出与先进先出的原则；3、掌握栈和队列的基本操作，如入栈与出栈、入队与出队等；4、运用栈和队列解决问题。【实验学时】2学时【实验类型】设计型【实验内容】1、编程实现建栈、入栈、出栈操作；2、编程实现数制转换程序；3、编程实现队列的建立，在队列中插入元素和删除元素。【实验原理】1、栈是限定仅在表尾进行插入或删除操作的线性表，具有后进先出的特点。

5、栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素；2、队列是一种先进先出的线性表，在队尾进行插入操作，在队头进行删除操作；3、详细原理请参考教材。【实验步骤】一、用C语言编程实现建立一个顺序栈，并在此顺序栈中实现入栈和出栈操作1、通过键盘读取元素建立顺序栈；2、给定一个元素，在此元素压入此栈中；3、将栈顶一个元素弹出此栈。二、用C语言编程实现将一个十进制数转换成二进制数（或八进制数、或十六进制数）1、通过键盘输入一个十进制数；2、将此数转换成对应的非十进制数（如二进制数、八进制数或十六进制数）。三、用C语言编程实现建立一个链式队列，

6、并在此链队列中实现入队和出队操作1、通过键盘读取元素建立链队列；2、给定一个元素，在此元素插入此队列中；3、将队头一个元素出队。【思考问题】结合实验过程，回答下列问题：1、入栈、出栈操作，如何移动栈顶指针TOP；2、如何判断队列是否已满【实验报告要求】1、根据对栈和队列的理解，如何创建顺序栈和链队列；2、调试程序过程中遇到的问题及解决方案；3、本次实验的结论与体会。实验三数组【实验目的】1、了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址计算方法；2、了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。【实验学时】2学

7、时【实验类型】设计型【实验内容】编程实现稀疏矩阵转置和两稀疏矩阵乘积。【实验原理】1、压缩存储是只存储稀疏矩阵的非零元，除了存储非零元的值之外，还必须同时记下它所在行和列的位置；2、采用三元组顺序表存储稀疏矩阵，一个稀疏矩阵的转置矩阵仍是稀疏矩阵；3、采用行逻辑链接的顺序表存储稀疏矩阵，方便于两个稀疏矩阵相乖；1、详细原理请参考教材。【实验步骤】一、用C语言编程实现稀疏矩阵的转置1、采用三元组顺序表创建一个稀疏矩阵；2、将矩阵的行列值相互交换；3、将每个三元组中的i和j相互调换；4、重排三元组之间的次序实现矩阵转置。二、用C语言编程实现两稀疏矩阵的乘积1、采

8、用行逻辑链接的顺序表建立两个稀疏矩阵；2、求两稀疏矩