北方民族大学~数据结构实验指导书(最新)
- 格式：doc
- 大小：103.50 KB
- 文档页数：16
《数据结构》实验指导书姚建绩编北方民族大学计算机科学与工程学院2009年8月目录实验一：线性表的实现（设计，2学时） 3 实验二：顺序栈、链栈的实现（设计，2学时） 6 实验三：队列的实现（设计，2学时）8 实验四：特殊矩阵的压缩存储实现及访问（设计，2学时）10 实验五：二叉树的存储和实现（设计，2学时）12 实验六：图的存储和实现（设计，2学时）13 实验七：常用排序算法的实现（设计，2学时）14 实验八：基本查找算法的实现（设计，2学时）15课程编号：11100713 课程类别：专业基础课适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统课程总学时：80 实验学时：16开设实验项目数：8实验一：线性表的实现（设计，2学时）一、实验目的与要求1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。
2.掌握线性表的顺序存储结构的定义及C语言实现。
3.掌握线性表的链式存储结构——单链表的定义及C语言实现。
4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。
5.掌握线性表在链式存储结构——单链表中的各种基本操作。
二、实验环境安装有Visual C++6.0或其它C编译环境的PC机一台。
三、实验预习与准备1．复习教材相关章节内容。
2．复习C语言中关于结构体与指针的相关内容。
3．认真阅读实验题目，事先写好程序。
四、实验内容和步骤实验题目1：实现顺序表各种基本运算的算法。
编写一个程序，实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初如化顺序表L。
（2）依次采用尾插法插入A，B，C，D，E元素。
（3）输出顺序表L。
（4）输出顺序表L的长度。
（5）判断顺序表L是否为空。
（6）输出顺序表L的第3个元素。
（7）输出元素A的位置。
（8）在第4个元素位置上插入F元素。
（9）输出顺序表L。
（10）删除L的第3个元素。
（11）输出顺序表L。
（12）释放顺序表L。
实验题目2：实现单链表各种基本运算的算法。
编写一个程序，实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初如化单链表L。
（2）依次采用尾插法插入A，B，C，D，E元素。
（3）输出单链表L。
（4）输出单链表L的长度。
（5）判断单链表L是否为空。
（6）输出单链表L的第3个元素。
（7）输出元素A的位置。
（8）在第4个元素位置上插入F元素。
（9）输出单链表L。
（10）删除L的第3个元素。
（11）输出单链表L。
（12）释放单链表L。
实验题目3：实现双链表各种基本运算的算法。
编写一个程序，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初如化双链表L。
（2）依次采用尾插法插入A，B，C，D，E元素。
（3）输出双链表L。
（4）输出双链表L的长度。
（5）判断双链表L是否为空。
（6）输出双链表L的第3个元素。
（7）输出元素A的位置。
（8）在第4个元素位置上插入F元素。
（9）输出双链表L。
（10）删除L的第3个元素。
（11）输出双链表L。
（12）释放双链表L。
实验题目4：实现循环单链表各种基本运算的算法。
编写一个程序，实现循环单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初如化循环单链表L。
（2）依次采用尾插法插入A，B，C，D，E元素。
（3）输出循环单链表L。
（4）输出循环单链表L的长度。
（5）判断循环单链表L是否为空。
（6）输出循环单链表L的第3个元素。
（7）输出元素A的位置。
（8）在第4个元素位置上插入F元素。
（9）输出循环单链表L。
（10）删除L的第3个元素。
（11）输出循环单链表L。
（12）释放循环单链表L。
五、实验报告要求按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。
六、实验注意事项1．依据线性表的操作，程序中必须包含如下函数：●InitList()：初如化线性表。
●DestroyList(*L)：释放线性表L。
●ListEmpty(*L)：判断线性表L是否为空表。
●ListLength(*L)：返回线性表L的长度。
●DispList(*L)：输出线性表L。
●GetElem(*L,int i)：返回线性表L的第i个元素。
●LocateElem(*L,ElemType e)：在线性表L中查找元素e，若存在，则返回第一个e在线性表中的们置，若不存在，则返回0。
●ListInsert(*L,int i,ElemType e)：在线性表L中第i个位置上插入元素e。
●ListDelete(*L,int i)：在线性表L中删除第i个元素。
2．在四个实验题目中任选一题完成。
七、思考题1．如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。
2．假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A∩B?3．假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A∪B?实验二：顺序栈、链栈的实现（设计，2学时）一、实验目的与要求1、加深理解栈作为一种操作受限的特殊线性表的特殊性所在。
2、掌握栈的基本操作，初始化栈、判栈空、入栈、出栈、等运算在两种存储结构上的实现。
二、实验环境安装有Visual C++6.0或其它C编译环境的PC机一台。
三、实验预习与准备1．复习教材相关章节内容。
2．认真阅读实验题目，事先写好程序。
四、实验内容和步骤实验题目1：实现顺序栈各种基本运算的算法。
编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初如化栈S。
（2）判断栈S是否非空。
（3）依次进栈元素a,b,c,d,e。
（4）判断栈S是否非空。
（5）输出栈S的长度。
（6）输出从栈顶到栈底的元素。
（7）输出出栈序列。
（8）判断栈S是否非空。
（9）释放栈。
实验题目2：实现链栈各种基本运算的算法。
编写一个程序，实现链栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初如化栈S。
（2）判断栈S是否非空。
（3）依次进栈元素a,b,c,d,e。
（4）判断栈S是否非空。
（5）输出栈S的长度。
（6）输出从栈顶到栈底的元素。
（7）输出出栈序列。
（8）判断栈S是否非空。
（9）释放栈。
五、实验报告要求按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。
六、实验注意事项1．对于顺序栈的初始化算法要注意用动态内存分配和不用动态内存分配时在实现上的区别。
2．对于顺序栈要注意栈满与栈空的判断条件。
3．对于链栈要注意栈空的判断条件。
七、思考题1．考虑设计一算法实现对于给定的入栈序列，给出所有的出栈可能。
2．如何实现两个顺序栈共用同一空间。
实验三：队列的实现（设计，2学时）一、实验目的与要求1、加深理解队列作为一种操作受限的特殊线性表的特殊性所在。
2、掌握队列的基本操作，初始化队列、判队空、入队、出队、等运算在两种存储结构上的实现。
二、实验环境安装有Visual C++6.0或其它C编译环境的PC机一台。
三、实验预习与准备1．复习教材相关章节内容。
2．认真阅读实验题目，事先写好程序。
四、实验内容和步骤实验题目1：实现顺序队列各种基本运算的算法。
编写一个程序实现顺序循环队列的各种基本运算，并在此基础上设计一个主程序完成如下功能。
（1）初始化队列Q。
（2）判断队列Q是否非空。
（3）依次进队元素A，B，C。
（4）出队一个元素，输出该元素。
（5）输出队列Q的元素个数。
（6）依次进队元素D，E，F。
（7）输出队列Q的元素个数。
（8）输出出队序列。
（9）释放队列。
实验题目2：实现链队各种基本运算的算法编写一个程序实现链队的各种基本运算，并在此基础上设计一个主程序完成如下功能。
（1）初始化队列Q。
（2）判断队列Q是否非空。
（3）依次进队元素A，B，C。
（4）出队一个元素，输出该元素。
（5）输出队列Q的元素个数。
（6）依次进队元素D，E，F。
（7）输出队列Q的元素个数。
（8）输出出队序列。
（9）释放队列。
五、实验报告要求按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。
六、实验注意事项1．程序中一般应包含如下几函数；初始化队列函数，释放队列函数，判断队列是否为空函数，进队函数，出队函数，求当前队列长度函数。
2．顺序队列实现时是否采用动态内存分配将关系到初始化函数和释放队列函数的形式，这个需注意。
七、思考题1．书上作为队列应用而给出的迷宫问题能否用栈的方式实现求解。
实验四：特殊矩阵的压缩存储实现及访问（设计，2学时）一、实验目的与要求1．理解数组在内存中是如何存储和访问时是如何寻址的。
2．掌握用三元组实现特殊矩阵压缩存储的方法和操作实现。
二、实验环境安装有Visual C++6.0或其它C编译环境的PC机一台。
三、实验预习与准备1．复习教材相关章节内容。
2．认真阅读实验题目，事先写好程序。
四、实验内容和步骤实验题目1：求n阶螺旋方阵。
以下是一个5*5阶螺旋方阵，设计一个算法输出该形式的n*n(n<10)阶方阵（顺时针方向旋转）。
1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9实验题目2：求一个矩阵的马鞍点。
如果矩阵A存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是j列中值最大的元素，则称之为该矩阵的一个以鞍点。
编写一个程序计算出m*n的矩阵A的所有马鞍点。
实验题目3：求两个对称矩阵的和与乘积。
已知A和B为两个n*n阶的对称矩阵，输入时，对称矩阵只输入下三角元素，存入一维数组。
编写一个程序实现如下功能：（1）求对称矩阵A和B之和。
（2）求对称矩阵A和B之积。
实验题目4：实现稀疏矩阵（采用三元组表示）的基本运算。
（1）生成如下两个稀疏矩阵的三元组A和B；1 0 3 0 3 0 0 00 1 0 0 0 4 0 00 0 1 0 0 0 1 00 1 1 0 0 0 2（2）输出A转置矩阵的三元组。
（3）输出A+B的三元组。
（4）输出A*B的三元组。
五、实验报告要求按实验报告单的格式认真填写实验报告，附运行通过的程序清单，要有必要的注释。
六、实验注意事项1．注意压缩存储的矩阵在显示输出时应恢复原样。
七、思考题1．考虑用十字链表的存储形式实现实验题目2。
实验五：二叉树的存储和实现（设计，2学时）一、实验目的与要求1、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。
2、掌握如何在内存中创建二叉树。
3、掌握二叉树的各种遍历算法的递归和非递归实现。
二、实验环境安装有Visual C++6.0或其它C编译环境的PC机一台。
三、实验预习与准备1．复习教材相关章节内容。
2．认真阅读实验题目，事先写好程序。
四、实验内容和步骤编写一个程序，建立一个二叉树，并实现二叉树的先序遍历、中序遍历和后序遍历算法。
