电子科技大学信息与通信工程学院标准实验报告.docx

电子科技大学信息与通信工程学院
标 准 实 验 报 告
（实验）课程名称 数据结构与算法
电子科技大学教务处制表
电 子 科 技 大 学
实 验 报 告
学生姓名： 学 号： 指导教师： 居太亮
实验地点： 实验时间：
一、实验室名称：计算机实验中心
二、实验项目名称：链表
三、实验学时：4学时
四、实验原理：
利用计算机和集成开发环境设计 链表 相关程序和软件。
五、实验目的：
掌握链表的存储方法；
掌握链表的常用操作，包括建立、插入、删除、遍历等方法；
利用链表解决一些简单工程问题；
六、实验内容：
设计单链表的数据结构，参考结点结构为：
struct node{
DataType data; // 数据元素
node *next; //后继结点指针
};
完成单链表的建立，按位置插入，按值插入，按位置删除，按值删除，遍历输出，销毁等常见操作函数；
编写一个函数，将两个按元素值递增有序的单链表，合并为一个按元素值递减有序的单链表，并分析算法的时空复杂度。
编写主函数（测试函数，test bench），测试这些函数；要求测试用例丰富，每个函数不少于
3个测试用例，给出测试结果；
用循环链表实现约瑟夫环，测试并分析算法的时空复杂度。
完成单链表的一种排序算法，测试并分析算法的时空复杂度，请不要修改结点的数据域，仅修改指针域实现排序；（选作）
编写单链表反序排列函数（逆序，a1，a2，……，an，修改为an，an-1,……a2,a1），测试并分析算法的时空复杂度，请不要修改结点的数据域，仅修改指针域实现；（选作）
设有一元多项式xn=i=0naixi，分析数据结构特点，完成常规操作函数并测试分析；（选作）
用双向链表实现上述功能，并验证链表的双向性能（7除外）；（选作）
七、实验器材（设备、元器件）：
计算机、操作系统、IDE
八、实验步骤：
编写代码、输入测试数据，分析结果
九、实验数据及结果分析：
粘贴代码
给出函数测试用例和测试结果；测试用例和测试结果编排按如下表格所示：
序号
目标函数