实验3-线性表的链式存储

实验报告三实验报告三 线性表的链式存储线性表的链式存储 班级 班级 姓名 姓名 李鑫李鑫 学号 学号 专业 专业 信息安全信息安全 一 一 实验目的 实验目的 1 1 掌握单链表的基本操作的实现方法 掌握单链表的基本操作的实现方法 2 2 掌握循环单链表的基本操作实现 掌握循环单链表的基本操作实现 3 3 掌握两有序链表的归并操作算法 掌握两有序链表的归并操作算法 二 二 实验内容 请采用模板类及模板函数实现 实验内容 请采用模板类及模板函数实现 1 1 线性表链式存储结构及基本操作算法实现 线性表链式存储结构及基本操作算法实现 实现提示实现提示 同时可参见教材 同时可参见教材 p64 p73p64 p73 页的页的 ADTADT 描述及算法实现及描述及算法实现及 pptppt 函数 类名称 函数 类名称 等可自定义 部分变量请加上学号后等可自定义 部分变量请加上学号后 3 3 位 也可自行对类中所定义的操作进行扩展 位 也可自行对类中所定义的操作进行扩展 所加载的库函数或常量定义 所加载的库函数或常量定义 1 1 单链表存储结构类的定义 单链表存储结构类的定义 文件包含在文件包含在 LinList hLinList h 中中 templatetemplate classdatatype classclass LinkList LinkList templatetemplate classdatatype classclass NodeNode friendfriend classclass LinkList LinkList private private NodeNode next next datatypedatatype data data templatetemplate classdatatype classclass LinkListLinkList public public LinkList LinkList 建立只有头结点的空链表建立只有头结点的空链表 LinkList datatypeLinkList datatype a inta int n n 建立有建立有 n n 个元素的单链表个元素的单链表 LinkList LinkList 析构函数析构函数 释放整个链表空间释放整个链表空间 intint Length Length 求单链表的长度求单链表的长度 datatypedatatype Get intGet int i i 取单链表中第取单链表中第 i i 个结点的元素值个结点的元素值 intint Location datatypeLocation datatype x x 求单链表中值为求单链表中值为 x x 的元素序号的元素序号 voidvoid Insert intInsert int i datatypei datatype x x 在单链表中第在单链表中第 i i 个位置插入元素值为个位置插入元素值为 x x 的结的结 点点 datatypedatatype Delete intDelete int i i 在单链表中删除第在单链表中删除第 i i 个结点个结点 voidvoid PrintList PrintList 遍历单链表 按序号依次输出各元素遍历单链表 按序号依次输出各元素 boolbool IsEmpty IsEmpty 是否为空 空返回是否为空 空返回 1 1 否则返回 否则返回 0 0 voidvoid DeleteAll DeleteAll 删除所有的元素删除所有的元素 private private NodeNode head head 单链表的头指针单链表的头指针 2 2 初始化带头结点空单链表构造函数实现 初始化带头结点空单链表构造函数实现 输入 无输入 无 前置条件 无前置条件 无 动作 初始化一个带头结点的空链表动作 初始化一个带头结点的空链表 输出 无输出 无 后置条件 头指针指向头结点 后置条件 头指针指向头结点 templatetemplate classdatatype LinkList LinkList LinkList LinkList head newhead new Node Node head next NULL head next NULL 利用数组初始化带头结点的单链表构造函数实现 利用数组初始化带头结点的单链表构造函数实现 输入 已存储数据的数组及数组中元素的个数输入 已存储数据的数组及数组中元素的个数 前置条件 无前置条件 无 动作 利用头插或尾插法创建带头结点的单链表动作 利用头插或尾插法创建带头结点的单链表 输出 无输出 无 后置条件 头指针指向头结点 且数组中的元素为链表中各结点的数据成员 后置条件 头指针指向头结点 且数组中的元素为链表中各结点的数据成员 templatetemplate classdatatype LinkList LinkList datatypeLinkList LinkList datatype a inta int n n head newhead new Node Node head next NULL head next NULL NodeNode s s forfor int int i 0 i n i i 0 i n i s news new Node Node s data a i s data a i s next head next s next head next head next s head next s 在带头结点单链表的第 在带头结点单链表的第 i i 个位置前插入元素个位置前插入元素 e e 算法算法 输入 插入位置输入 插入位置 i i 待插入元素 待插入元素 e e 前置条件 前置条件 i i 的值要合法的值要合法 动作 在带头结点的单链表中第动作 在带头结点的单链表中第 i i 个位置之前插入元素个位置之前插入元素 e e 输出 无输出 无 后置条件 单链表中增加了一个结点后置条件 单链表中增加了一个结点 templatetemplate classdatatype voidvoid LinkList Insert intLinkList Insert int i datatypei datatype x x NodeNode p head int p head int j 0 j 0 while pp p next j j if p if p throwthrow i i 不合法不合法 elseelse NodeNode s new s new Node Node s data x s data x s next p next s next p next p next s p next s 在带头结点单链表中删除第 在带头结点单链表中删除第 i i 个元素算法个元素算法 输入 删除第输入 删除第 i i 个结点 待存放删除结点值变量个结点 待存放删除结点值变量 e e 前置条件 单链表不空 前置条件 单链表不空 i i 的值要合法的值要合法 动作 动作 在带头结点的单链表中删除第在带头结点的单链表中删除第 i i 个结点 并返回该结点的值 由个结点 并返回该结点的值 由 e e 传出 传出 输出 无输出 无 后置条件 单链表中减少了一个结点后置条件 单链表中减少了一个结点 templatetemplate classdatatype datatypedatatype LinkList Delete intLinkList Delete int i i NodeNode p p p head intp head int j 0 j 0 while pp p next j j ifif p p next p p next throwthrow i i 不合法不合法 elseelse NodeNode q q datatypedatatype x x q p next q p next x q data x q data p next q next p next q next deletedelete q q returnreturn x x 遍历单链表元素算法 遍历单链表元素算法 输入 无输入 无 前置条件 单链表不空前置条件 单链表不空 动作 动作 遍历输出单链表中的各元素 遍历输出单链表中的各元素 输出 无输出 无 后置条件 无后置条件 无 templatetemplate classdatatype voidvoid LinkList PrintList LinkList PrintList NodeNode p p p head p head ifif p next p next cout cout next while p next p p next p p next cout data cout data NodeNode p head next p head next while p while p cout data cout data next p p next 求单链表表长算法 求单链表表长算法 输入 无输入 无 前置条件 无前置条件 无 动作 动作 求单链表中元素个数 求单链表中元素个数 输出 返回元素个数输出 返回元素个数 后置条件 无后置条件 无 templatetemplate classdatatype intint LinkList Length LinkList Length NodeNode p p intint i 0 i 0 p head next p head next while p while p i i p p next p p next returnreturn i i 判单链表表空算法 判单链表表空算法 输入 无输入 无 前置条件 无前置条件 无 动作 动作 判表是否为空 判表是否为空 输出 为空时返回 不为空时返回输出 为空时返回 不为空时返回 0 0 后置条件 无后置条件 无 templatetemplate classdatatype boolbool LinkList IsEmpty LinkList IsEmpty ifif head next NULL head next NULL returnreturn 1 if head next 1 if head next returnreturn 1 1 returnreturn 0 0 if this Length 0 if this Length 0 returnreturn 1 1 获得单链表中第 获得单链表中第 i i 个结点的值算法个结点的值算法 输入 无输入 无 前置条件 前置条件 i i 不空 不空 i i 合法合法 动作 动作 找到第找到第 i i 个结点 个结点 输出 返回第输出 返回第 i i 个结点的元素值 个结点的元素值 后置条件 无后置条件 无 templatetemplate classdatatype datatypedatatype LinkList Get intLinkList Get int i i NodeNode p head next p head next intint j 1 j 1 while pp p next j j if p if p throwthrow i i 不合法不合法 elseelse returnreturn p data p data p next data p next data 错误错误 10 10 删除链表中所有结点算法 这里不是析构函数 但功能相同 删除链表中所有结点算法 这里不是析构函数 但功能相同 输入 无输入 无 前置条件 单链表存在前置条件 单链表存在 动作 动作 清除单链表中所有的结点 清除单链表中所有的结点 输出 无输出 无 后置条件 头指针指向空后置条件 头指针指向空 templatetemplate classdatatype voidvoid LinkList DeleteAll LinkList DeleteAll NodeNode p p while head next while head next p head next p head next head next p next head next p next deletedelete p p NodeNode p q p q p head p head whilewhile p p q p q p p p next p p next deletedelete q q head next NULL head next NULL 11 11 上机实现以上基本操作 写出上机实现以上基本操作 写出 main main 程序 程序 参考参考 p72p72 voidvoid main main intint s 10 9 8 7 6 5 4 3 2 1 ints 10 9 8 7 6 5 4 3 2 1 int n 10 n 10 cout cout 构造函数插入元素 构造函数插入元素 endl endl LinkListLinkList mylist1 s 10 mylist1 s 10 mylist1 PrintList mylist1 PrintList cout endl cout endl cout cout 删除全部元素后为 删除全部元素后为 endl endl mylist1 DeleteAll mylist1 DeleteAll mylist1 PrintList mylist1 PrintList cout endl cout endl 单链表为空单链表为空 1 1 是 是 0 0 不是不是 mylist1 IsEmpty endl mylist1 IsEmpty endl LinkListLinkList mylist mylist cout endl cout endl 非构造函数插入元素 非构造函数插入元素 endl endl for intfor int i 0 i 10 i i 0 i 10 i mylist Insert i s i mylist Insert i s i mylist Insert 0 10 mylist Insert 0 10 mylist Insert 1 9 mylist Insert 1 9 mylist PrintList mylist PrintList cout endl cout endl cout cout 表长为 表长为 mylist Length endl mylist Length endl cout cout 得到第得到第 3 3 个元素为 个元素为 mylist Get 3 endl mylist Get 3 endl cout cout 删除第删除第 7 7 个元素为 个元素为 mylist Delete 7 endl mylist Delete 7 endl cout cout 单链表为 单链表为 mylist PrintList mylist PrintList cout endl cout endl cout cout 第第 5 5 个元素后插入个元素后插入 9999 后单链表为 后单链表为 mylist Insert 5 99 mylist Insert 5 99 cout endl cout endl mylist PrintList mylist PrintList cout endl cout endl 粘贴测试数据及运行结果 粘贴测试数据及运行结果 2 2 参考单链表操作定义与实现 自行完成单循环链表的类的定义与相操作操作算法 参考单链表操作定义与实现 自行完成单循环链表的类的定义与相操作操作算法 利用数组初始化带头结点的单循环链表构造函数实现 利用数组初始化带头结点的单循环链表构造函数实现 输入 已存储数据的数组及数组中元素的个数输入 已存储数据的数组及数组中元素的个数 前置条件 无前置条件 无 动作 利用头插或尾插法创建带头结点的单循环链表动作 利用头插或尾插法创建带头结点的单循环链表 输出 无输出 无 后置条件 头指针指向头结点 且数组中的元素为链表中各结点的数据成员 尾指针指向后置条件 头指针指向头结点 且数组中的元素为链表中各结点的数据成员 尾指针指向 头结点 头结点 templatetemplate classdatatype classclass LinkList LinkList templatetemplate classdatatype classclass NodeNode friendfriend classclass LinkList LinkList private private NodeNode next next datatypedatatype data data templatetemplate classdatatype classclass LinkListLinkList public public LinkList LinkList 建立只有头结点的空链表建立只有头结点的空链表 LinkList datatypeLinkList datatype a inta int n n 建立有建立有 n n 个元素的单链表个元素的单链表 LinkList LinkList 析构函数析构函数 释放整个链表空间释放整个链表空间 int int Length Length 求单链表的长度求单链表的长度 datatype datatype Get intGet int i i 取单链表中第取单链表中第 i i 个结点的元素值个结点的元素值 int int Location datatypeLocation datatype x x 求单链表中值为求单链表中值为 x x 的元素序号的元素序号 voidvoid Insert intInsert int i datatypei datatype x x 在单链表中第在单链表中第 i i 个位置插入元素值为个位置插入元素值为 x x 的结的结 点点 datatypedatatype Delete intDelete int i i 在单链表中删除第在单链表中删除第 i i 个结点个结点 voidvoid PrintList PrintList 遍历单链表 按序号依次输出各元素遍历单链表 按序号依次输出各元素 bool bool IsEmpty IsEmpty void void DeleteAll DeleteAll void void sort sort private private NodeNode head head 单链表的头指针单链表的头指针 templatetemplate classdatatype LinkList LinkList LinkList LinkList head newhead new Node Node head next head head next head templatetemplate classdatatype LinkList LinkList datatypeLinkList LinkList datatype a inta int n n head newhead new Node Node head next head head next head NodeNode s s forfor int int i 0 i n i i 0 i n i s news new Node Node s data a i s data a i s next head next s next head next head next s head next s 在带头结点单循环链表的第 在带头结点单循环链表的第 i i 个位置前插入元素个位置前插入元素 e e 算法算法 输入 插入位置输入 插入位置 i i 待插入元素 待插入元素 e e 前置条件 前置条件 i i 的值要合法的值要合法 动作 在带头结点的单循环链表中第动作 在带头结点的单循环链表中第 i i 个位置之前插入元素个位置之前插入元素 e e 输出 无输出 无 后置条件 单循环链表中增加了一个结点后置条件 单循环链表中增加了一个结点 templatetemplate classdatatype voidvoid LinkList Insert intLinkList Insert int i datatypei datatype x 1 i n x 1 i n NodeNode p head int p head int j 0 j 0 while p next headp p next j j if j i 1 if j i 1 throwthrow i i 不合法不合法 elseelse NodeNode s new s new Node Node s data x s data x s next p next s next p next p next s p next s 在带头结点单循环链表中删除第 在带头结点单循环链表中删除第 i i 个元素算法个元素算法 输入 删除第输入 删除第 i i 个结点 待存放删除结点值变量个结点 待存放删除结点值变量 e e 前置条件 单循环链表不空 前置条件 单循环链表不空 i i 的值要合法的值要合法 动作 在带头结点的单循环链表中删除第动作 在带头结点的单循环链表中删除第 i i 个结点 并返回该结点的值 由个结点 并返回该结点的值 由 e e 传出 传出 输出 无输出 无 后置条件 单循环链表中减少了一个结点后置条件 单循环链表中减少了一个结点 templatetemplate classdatatype datatypedatatype LinkList Delete intLinkList Delete int i i NodeNode p p p head intp head int j 0 j 0 while p next headp p next j j ifif j i 1 p next head j i 1 p next head cout i cout i 不合法不合法 throwthrow i i 不合法不合法 elseelse NodeNode q q datatypedatatype x x q p next q p next x q data x q data p next q next p next q next deletedelete q q returnreturn x x 遍历单循环链表元素算法 遍历单循环链表元素算法 输入 无输入 无 前置条件 单循环链表不空前置条件 单循环链表不空 动作 遍历输出单循环链表中的各元素 动作 遍历输出单循环链表中的各元素 输出 无输出 无 后置条件 无后置条件 无 templatetemplate classdatatype voidvoid LinkList PrintList LinkList PrintList NodeNode p p p head p head ifif p next head p next head cout cout next head while p next head p p next p p next cout data cout data NodeNode p head next p head next while p while p cout data cout data next p p next 上机实现以上基本操作 写出上机实现以上基本操作 写出 main main 程序 程序 include include include include LinList h LinList h voidvoid main main intint a 1 5 8 2 9 4 3 6 7 10 n 10 a 1 5 8 2 9 4 3 6 7 10 n 10 LinkListLinkList mylist a 10 mylist a 10 cout cout 循环链表为 循环链表为 endl endl mylist PrintList mylist PrintList cout endl cout endl cout cout 在第一个元素前插入在第一个元素前插入 2020 后为 后为 endl endl mylist Insert 1 20 mylist Insert 1 20 mylist PrintList mylist PrintList cout endl cout endl cout cout 在第三个元素前插入在第三个元素前插入 3030 后为 后为 endl endl mylist Insert 3 30 mylist Insert 3 30 mylist PrintList mylist PrintList cout endl cout endl cout cout 删除第一个元素后为 删除第一个元素后为 endl endl mylist Delete 1 mylist Delete 1 mylist PrintList mylist PrintList cout endl cout endl cout cout 删除最后一个元素后为 删除最后一个元素后为 endl endl mylist Delete 11 mylist Delete 11 mylist PrintList mylist PrintList cout endl cout endl 粘贴测试数据及运行结果 粘贴测试数据及运行结果 采用链式存储方式 并利用单链表类及类中所定义的算法加以实现线性表 采用链式存储方式 并利用单链表类及类中所定义的算法加以实现线性表 La LbLa Lb 为非为非 递减的有序线性表 将其归并为新线性表递减的有序线性表 将其归并为新线性表 LcLc 该线性表仍有序 未考虑相同时删除一重复 该线性表仍有序 未考虑相同时删除一重复 值 的算法 值 的算法 模板函数 模板函数 include include include include include include LinList h LinList h templatetemplate classdatatype voidvoid LinkList sort LinkList sort NodeNode r head next r head next datatypedatatype temp temp forfor i 0 i Length i i 0 i Length i NodeNode s r next s r next for j i 1 j Length j for j i 1 jdata s data r data s data temp r data temp r data r data s data r data s data s data temp s data temp s s next s s next delete delete q q deletedelete s s r r next r r next deletedelete r r while r while r NodeNode s r next s r next while s while s ifif r data s data r data s data temp r data temp r data r data s data r data s data