数据结构实验指导(16学时)

《数据结构实验指导(16学时)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验指导书（16学时）计算机专业实验中心实验一C语言结构体与指针3实验二线性顺序表的实现及操作4实验三串的匹配与替换5实验四线性链表的实现及操作6实验五栈和队列的应用7实验六二叉树的实现及遍历8实验七图的实现及遍历9实验八查找算法的实现及比较10实验一C语言结构体与指针1、实验目的：巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。2、实验内容：1）学生信息的显示，具体要求如下：®定义一个结构体描述学生信息（学号，姓名，性别，年龄，住址）；®设计一个函数，

2、用于显示单个学生信息，函数的参数为前面定义的结构体类型；®设计一个主函数，在主函数屮输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。2）输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如输入：1023045,逆置后显示为：5430210o3、思考题：分析结果是否正确，如果不正确是什么原因。实验二线性顺序表的实现及操作1、实验目的：1）掌握建立线性顺序表的基木方法。2）理解和掌握线性顺序表元素查找算法。3）

3、掌握线性顺序表的插入、删除算法的思想和实现。2、实验内容:1）建立一个线性顺序表，要求从键盘输入10个整数，并将该线性顺序表的元素从屏幕显示出来；2）编写查找函数，在上面的线性顺序表中查找其中一个元素，如果找到，返回该元素在线性顺序表屮的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。3）编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的线性顺序表输出；由用户输入删除第儿个元素，将完成删除后的线性顺序表输出。3、思考题:分析线性顺序表结构卜•插入和删除算法的时间复杂度。

4、实验三串的匹配与替换1、实验目的：1)掌握串存储结构；2)掌握串的匹配算法，并能进行相关应用。2、实验内容：设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中从位置start歼始查找是否存在子串T。若存在，则用子串V去替换子串T,FL函数返回1；若主串S屮不存在子串T,则函数返回0。要求设计主函数进行测试。3、思考题：使用串的块链存储结构，改写上述程序。实验四线性链表的实现及操作1、实验目的：1）深入理解线性链表的逻辑结构和链式存储结构；2）掌握

5、线性链表的基木操作及应用：3）培养学生灵活使用结构解决实际问题的能力。2、实验内容：1）设计一个100位以内的长整数加减运算的程序。要求如下：®输入输出要求：每四位一组，组间用逗号分隔；®加和减分别用不同的程序实现®程序应考虑输入数据的符号2）用循环链表实现约瑟夫环问题3、思考题：尝试按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减,并将结果输出。实验五栈和队列的应用1、实验目的：掌握栈与队列的基木结构和操作方法，培养学牛灵活使用结构解决实际问题的能力。2、实验内容：1）利用栈深度优

6、先进行迷宫求解。®用数组表示迷宫®建立栈，利用栈实现深度优先搜索2）利用队列宽度优先进行迷宫求解。®用数纽表示迷宫®建立队列，利用队列实现宽度优先搜索3、思考题:1）考虑用栈结构实现数制转换问题和字符匹配问题；2）考虑用队列结构实现杨辉三角输出问题和冋文问题；3）利用栈和队列模拟停车场管理。实验六二叉树的实现及遍历1、实验目的：1）掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围。2）掌握用指针类型描述、访问和处理二叉树的运算。3）掌握二叉树的建立方法4）掌握二叉树遍历的基本方法（前序、

7、屮序、后序）2、实验内容:1）采用二叉树链表作为存储结构，完成二叉树的建立，先序、屮序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。2）输岀树的深度，最大元，最小元。3、思考题:画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。实验七图的实现及遍历1、实验目的：1）掌握冇向图和无向图的概念；2）掌握邻接矩阵和邻接链表建立图的存储结构；3）掌握DFS及BFS对图的遍历操作和过程；4）了解图结构在人工智能、工程等领域的广泛应用。2、实验内容:1）采用邻接矩阵作为图的存储结构，完成冇向

8、图和无向图的DFS和BFS操作；2）采用邻接链表作为图的存储结构，完成冇向图和无向图的DFS和BFS操作。3、思考题：1）画出DFS方法和BFS方法遍历图G的示意图。2）画出你所设计的图，写出两种方法的遍历序列。实验八查找算法的实现及比较1、实验目的：1）掌握线性结构（顺序查找、折半查找）上查找的基木思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。2）掌握树形结构（二叉排序树）实现查找的基本思想和算法实现，了解怎样对各种査找方法进行时间性能（平