2022年双链表深拷贝链接 .pdf

《2022年双链表深拷贝链接 .pdf》由会员分享，可在线阅读，更多相关《2022年双链表深拷贝链接 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一 实验目的和要求线性表是最简单的一种基本数据结构，本实验通过实现对线性表各种操作的算法设计， 理解和掌握线性表的概念， 存储结构及操作要求， 体会两种存储结构的特点；根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度和空间复杂度分析，从而达到掌握数据结构的研究方法，算法设计和分析方法的目的。本章程序设计训练的重点是单链表，要求掌握单链表的遍历、 插入和删除等操作算法， 通过指针表达和改变结点间的链接关系，熟悉循环单链表、 双链表和循环双链表的结构和基本操作。要求熟练运用 c+语言实现数据结构设计和算法设计，了解程序运行中出现的各种错误，掌握设置断点、单步运行等程序调

2、试技术，即使发现错误，针对不同的错误，采取不同的手段进行处理。二 题目及题意分析题目：以深拷贝的方式在双链表后面添加另一双链表。题意分析 : 由指定数组构成带头结点的循环双链表，将两条双链表连接，把要连接的双链表的每个节点复制建立一个新的节点，依次链接在要链接到双链表的后边，使用指针依次指向要链接的双链表进行遍历操作完成复制，最后把链表的头节点和尾节点环起来， 建立析构函数， 验证深拷贝是否成功， 完成题目要求。三 设计方案和功能说明设计方案：源程序如下Node.h：template / 双链表节点类class DLinkNode public: T date; DLinkNode*prev,

3、*next; / 指针域，前驱和后继DLinkNode() prev=next=NULL; DLinkNode(T date, DLinkNode*prev=NULL,DLinkNode*next=NULL) / 构造节点this-date=date; this-prev=prev; this-next=next; ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - list.h: / 带头结点的循环双链表类#include #

4、includeNode.h template class DoublyLinkedList public: DLinkNode*head; concat(DoublyLinkedList &list); / 深拷贝链接函数DoublyLinkedList(); / 构造空链表DoublyLinkedList(); / 析构DLinkNode*insert(T x); / 在链表后插入节点friend ostream& operator(ostream &out,DoublyLinkedList &list); DoublyLinkedList(T value,int n); / 由指定数组构造

5、双链表void clear(); / 清空void printprev(); / 沿着前驱域输出链表; template DoublyLinkedList:DoublyLinkedList() / 构造空链表 this-head=new DLinkNode(); head-prev=head; head-next=head; template DLinkNode*DoublyLinkedList:insert(T x) DLinkNode*q=new DLinkNode(x,head-prev,head); head-prev-next=q; head-prev=q; return q; te

6、mplate DoublyLinkedList:DoublyLinkedList() / 析构 clear(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - template ostream& operator(ostream &out,DoublyLinkedList &list) DLinkNode *p=list.head-next; / 输出双链表out(; while(p!=list.head) outdate;

7、p=p-next; if(p!=list.head) out,; out)n; return out; template DoublyLinkedList:concat(DoublyLinkedList &list) / 深拷贝链接函数 DLinkNode *p=list.head-next; DLinkNode *q=this-head-prev; while(p!=list.head) q-next=new DLinkNode(p-date,q,this-head); /新建节点链接在链表后q=q-next; p=p-next; this-head-prev=q; / 头尾链接起来 tem

8、plate DoublyLinkedList:DoublyLinkedList(T value,int n) / 由指定数组构造双链表 this-head=new DLinkNode(); DLinkNode *p=head; int i=0; while(inext=new DLinkNode(valuei+,p); p=p-next; head-prev=p; p-next=head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - -

9、 - - template void DoublyLinkedList:clear() DLinkNode*p=head-next; while(p!=head) DLinkNode *q=p; p=p-next; delete q; template void DoublyLinkedList:printprev() / 沿着前驱域输出链表 DLinkNode*p=head-prev; while(p!=head) cout date; p=p-prev; coutendl; 主函数#includelist.h int main() int a5=1,2,3,4,5; int b3=6,7,

10、9; DoublyLinkedList lista(a,5); DoublyLinkedList listb(b,3); couta: lista; coutb: listb; lista.concat(listb); coutlista; lista.printprev(); return 0; 四 运行结果及分析a: (1,2,3,4,5) b: (6,7,9) (1,2,3,4,5,6,7,9) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - -

11、 - - - - - 沿着前驱域输出链表：9 7 6 5 4 3 2 1 Press any key to continue 结果分析：构造链表a，b 并以深拷贝方式链接，沿着前驱域输出链表说明循环双联表链接，调用析构函数析构没出错，则深拷贝成功。五 实验总结及改进措施通过对双链表深拷贝链接的操作，熟练掌握了双链表的结构和基本操作，用指针对链表进行遍历， 复制并创建节点， 完成深拷贝链接， 添加析构函数对链表析构以此证明深拷贝成功， 对原来链接链表进行添加节点操作，不影响链接后的链表，程序可行。 循环双链表后边添加节点后各个前驱后继关系理解清晰，沿着前驱域输出链表可说明链接后的循环无出错。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -