单链表的存储与操作

成 绩 评阅人 重庆邮电大学 课程设计实验报告 班级 1301416 姓名 陈昊 学号 2014214156 指导老师 夏晨洋 课程名称 数据结构 实验时间 2015 年 10 月 26 日 2015 年 11 月 2 日 实验地点 数字图书馆负一楼 B132 实验二 单链表的存储与操作 一 实验目的 1 理解线性表的逻辑结构 2 理解单链表的存储结构特点 掌握单链表的存储分配要点 3 掌握单链表的基本操作及实现 并能正确分析其时间复杂度 二 主要数据结构描述 LinkList 建立只有头结点的空链表 LinkList T a int n 建立有 n 个元素的单链表 LinkList 析构函数 int Length 求单链表的长度 T Get int i 取单链表中第 i 个结点的元素值 int Locate T x 求单链表中值为 x 的元素序号 void Insert int i T x 在单链表中第 i 个位置插入元素值为 x 的结点 T Delete int i 在单链表中删除第 i 个结点 void PrintList 遍历单链表 按序号依次输出各元素 Node first 单链表的头指针 在单链表中 需要有构造函数用来构造整个单链表 需要析构函数来删除 整个单链表 需要一个 Length 函数来求单链表的长度 需要一个取值函数 Get 传入节点的编号 返回节点的值 需要一个求序号的函数 传入数据的值 返回数据对应的编号 即在单链表中的位置 需要一个插入函数 用来在特定 的位置插入一个节点用来存储新数据 需要一个删除函数 用来删除某个节点 并将该节点两端的节点连起来 需要一个遍历函数 用以遍历单链表 三 算法的基本思想描述 1 按位置 值查找 按位置和按值查找的思路大体相同 需要一个工作指针来 对整个链表进行遍历 如果所遇到的编号或值与想要的一致 便会把工作指针 的信息返回 此函数只需对链表遍历一次 所以平均时间复杂度为 O n 2 在位置 i 插入一个数据元素 此函数可以大体分成两个部分 第一个部分是 遍历 寻找到要插入的位置 这个与上面的方法相同 第二个部分是插入 要 先申请一个新节点 s 在让 s 的指针域等于前一个节点 p 的指针域 最后让 p 的 指针域等于 s 此函数只需对链表遍历一次 所以平均时间复杂度为 O n 3 删除位置 i 的数据元素 删除函数也有两个部分 第一个与插入相同 第二 个先要暂存被删节点 用以返回 再让前一个节点的指针域等于后一个节点 最后删除被删节点 此函数只需对链表遍历一次 所以平均时间复杂度为 O n 4 初始化单链表 有参 有前插法和尾插法 实际上都是在链表的后面再添 加一个新节点 所以时间复杂度为 O n 5 遍历单链表 求单链表长度 销毁单链表 这三个函数都是要遍历单链表 所以时间复杂度为 O n 四 运行的结果截图 五 实验体会和收获 通过这次试验 我熟悉了如何取单链表中第 i 个结点的元素值 如何按位 查找位置为 i 的元素并输出值 如何构建一个单链表 总之这次试验然我熟悉 了很多单链表的操作 六 程序清单 LinkList h LinkList cpp LinkListMain cpp