在链表中删除相同节点

《在链表中删除相同节点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

数据结构上机实验报告题目：在链表中删除相同节点学生姓名学生学号学院名称计算机学院专业计算机科学与技术时间 目录第一章需求分析11.1原题表述11.2问题解决方案1第二章概要设计22.1抽象数据类型22.2主要算法描述22.3主要算法分析3第三章详细设计43.1程序代码4第四章调试分析74.1出现的问题及解决方法7第五章测试分析85.1测试样例8第六章未来展望与思考9 计算机学院2013级数据结构上机实验报告第一章需求分析1.1原题表述假设有两个无序的双向循环链表A和B，结构体为：前驱指针left，后继指针right，数据date。将它们的头指针分别设为：pHeadA，pHeadB，输入A和B的数值，新建链表，接着构造函数，删除两个链表中相同的节点。1.2问题解决方案1、需要构建双循环链表，对于输入的链表，需要删除重复的结点，需要删除结点的函数。2、首先把A中含有与B中相同的数据节点找出来组成一个新的链表C3、遍历链表C，删除A和B的所有和C中节点值相同的节点。解决方案要求：（1）输入参数：pA、pB两个链表（2）输出参数：A和B中所有相同数据节点组成的链表C（3）输出参数：删除与C中节点值相同节点之后的链表A和B8 计算机学院2013级数据结构上机实验报告第二章概要设计2.1抽象数据类型ADTDNode{数据对象：D={ai=ai|aiElemSet,i=1,2,3,…,n,n>=0}数据关系：S={|ai-1,aiD,i=2,3,4,…，n}基本操作：CreatList（&L）操作结果：构建双循环链表DeleteSame（&L）初始条件：已建立双循环链表操作结果：删除链表中的重复元素Subset（&L1,&L2，&L3)初始条件：已建立链表L1，L2操作结果：将L1，L2的交集存入L3Delete（L1，L2）初始条件：已存在链表L1，L2操作结果：在L1中删除L2中的元素Display（&L）初始条件：已存在链表L操作结果：依次输出L中的元素}2.2主要算法描述求pA,pB交集pC开始结束pA,pB,pC删除pA,pB中pA，pB共有的元素删除pB中的重复元素删除pA中的重复元素链表pA，pB8 计算机学院2013级数据结构上机实验报告2.3主要算法分析CreatList(&L)一重循环时间复杂度=O（n）DeleteSame(&L)二重循环时间复杂度=0（n2）Subset（&L1，&L2，&L3）二重循环时间复杂度=0（n2）Delete（&L1，&L2）二重循环时间复杂度=0（n2）Display(&L)一重循环时间复杂度=O（n）8 计算机学院2013级数据结构上机实验报告第三章详细设计3.1程序代码#include#includetypedefintListData;typedefstructDNote{ListDatadata;structDNote*left,*right;}DblNode;typedefDblNode*DblList;//构建双循环链表voidCreatList(DblList&L){intval;L=(DblList)malloc(sizeof(DblNode));DblListp,q=L;while(scanf("%d",&val)&&val!=-1){p=(DblList)malloc(sizeof(DblNode));p->data=val;p->left=q;q->right=p;q=p;}q->right=L;L->left=q;}//求交集voidSubset(DblList&L1,DblList&L2,DblList&L){DblListp,q;L=(DblList)malloc(sizeof(DblNode));DblListr,s=L;p=L1->right;while(p!=L1){q=L2->right;while(q!=L2){if(p->data==q->data){r=(DblList)malloc(sizeof(DblNode));r->data=p->data;r->left=s;s->right=r;s=r;8 计算机学院2013级数据结构上机实验报告}//将相同元素存入新表Lq=q->right;}p=p->right;}s->right=L;L->left=s;}//删除链表中的重复元素voidDeleteSame(DblList&L){DblListp=L->right,q=p,r;while(p!=L){q=p->right;while(q!=L){if(p->data==q->data){r=q;r->right->left=r->left;r->left->right=r->right;free(r);}q=q->right;}p=p->right;}}//删除L1，L2的相同元素voidDelete(DblList&L1,DblList&L2){DblListp,q;p=L1->right;while(p!=L1){q=L2->right;while(q!=L2){if(p->data==q->data){p->right->left=p->left;p->left->right=p->right;free(p);}q=q->right;}p=p->right;}}//依次输出表中元素voidDisplay(DblList&L){8 计算机学院2013级数据结构上机实验报告DblListp=L->right;while(p!=L){printf("%d",p->data);p=p->right;}printf(" ");}intmain(){DblListpHeadA,pHeadB,pHeadC;printf("请输入A表元素(以-1结尾) ");printf("pA:");CreatList(pHeadA);printf("请输入B表元素(以-1结尾) ");printf("pB:");CreatList(pHeadB);DeleteSame(pHeadA);DeleteSame(pHeadB);Subset(pHeadA,pHeadB,pHeadC);printf("SubsetpAandpB:");Display(pHeadC);Delete(pHeadA,pHeadC);printf("AfterDeleteEqualpA:");Display(pHeadA);Delete(pHeadB,pHeadC);printf("AfterDeleteEqualpB:");Display(pHeadB);return0;}8 计算机学院2013级数据结构上机实验报告第四章调试分析4.1出现的问题及解决方法1、由于对循环链表算法的理解不够透彻，在构建循环链表的前期，指针指向混乱，导致程序无法通过编译。2、在建立链表时，没有将表头表尾链接，没有构成循环。3、开始时未考虑链表中的重复元素，导致程序无法运行。删除重复元素后，恢复正常。在编写DeleteSame（）函数时，未考虑指针指向，致使无法删除重复元素。修正后，可以删除重复元素。4、在求交集时只考虑了一个方向，忽略了建立的是双向链表。致使无法建立交集的链表。8 计算机学院2013级数据结构上机实验报告第五章测试分析5.1测试样例测试样例一：图5-1测试样例二：图5-28 计算机学院2013级数据结构上机实验报告第六章未来展望与思考这次的实验对我来说非常的有难度，通过本次实验，我更加熟练地掌握了双向线性表的逻辑特征和熟练掌握带头结点的双向链式表的指针操作。在实验中遇到了一些问题，但通过同学的指导最终解决了。完成这次作业后使我又进一步提高了程序编写的能力和增加了我对数据结构的兴趣。在这次实验中，我发现自己在对循环链表的具体分析不够熟悉，比较吃力，以后要加强这方面的训练。8