实验三、链表验证实验报告

班级 计算机 11 1 学号 姓名 成绩 实验三实验三 单链表操作验证单链表操作验证 一 实验目的一 实验目的 掌握线性表的链接存储结构 验证单链表及其基本操作的实现 进一步掌握数据结构及算法的程序实现的基本方法 二 二 实验内容实验内容 用头插法 或尾插法 建立带头结点的单链表 2 对已建立的单链表实现插入 删除 查找等基本操作 三 三 设计与编码设计与编码 include using namespace std template struct Node T data Node next template class LinkList public LinkList T a int n 建立有 n 个元素的单链表 LinkList 析构函数 void Insert int i T x 在单链表中第 i 个位置插入元素值为 x 的结点 T Delete int i 在单链表中删除第 i 个结点 int Locate T x 求单链表中值为 x 的元素序号 void PrintList 遍历单链表 按序号依次输出各元素 private Node first 单链表的头指针 template LinkList LinkList T a int n Node s int i first new Node first next NULL 初始化一个空链表 for i 0 i n i s new Node s data a i 为每个数组元素建立一个结点 s next first next 插入到头结点之后 first next s template LinkList LinkList Node p q p first 工作指针 p 初始化 while p 释放单链表的每一个结点的存储空间 q p 暂存被释放结点 p p next 工作指针 p 指向被释放结点的下一个结点 使单链表不断 开 delete q template void LinkList Insert int i T x Node p s p first int j 0 工作指针 p 初始化 while p 工作指针 p 后移 j if p throw 位置 else s new Node s data x 向内存申请一个结点 s 其数据域为 x s next p next 将结点 s 插入到结点 p 之后 p next s template T LinkList Delete int i Node p q int x p first int j 0 工作指针 p 初始化 while p j if p p next throw 位置 结点 p 不存在或结点 p 的后继 结点不存在 else q p next x q data 暂存被删结点 p next q next 摘链 delete q return x template int LinkList Locate T x Node p p first next int j 1 while p 工作指针 p 后移 j if p return j else return 0 template void LinkList PrintList Node p p first next while p NULL cout data next cout endl void meun cout 单链表的实现 endl cout endl cout 1 显示 endl cout 2 插入 endl cout 3 删除 endl cout 4 查找 endl cout 5 退出 endl cout endl int main meun int a 5 23 45 86 95 78 LinkLists1 a 5 int n j k loc int flag 1 while flag cout j switch j case 1 s1 PrintList break case 2 cout n k s1 Insert n k break case 3 cout n s1 Delete n break case 4 cout k loc s1 Locate k cout 所查数据所在 loc 位 endl break case 5 flag 0 break default cout 错误 endl break return 0 四 四 运行与调试运行与调试 a 在调试程序的过程中遇到什么问题 是如何解决的 b 设计了哪些设计数据 测试结果是什么 c 程序运行的结果如何 五 五 实验小结实验小结 本单链表验证实验与顺序表非常之类似 不同的是链表是通过指针来描述元素 关系的一种数据结构 对于数组 可以动态的改变数据