资源描述：
《在链表中删除相同节点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构上机实验报告题目：在链表中删除相同节点学生姓名学生学号学院名称计算机学院专业计算机科学与技术时间目录第一章需求分析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，后继指针rig
2、ht，数据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和B
3、8计算机学院2013级数据结构上机实验报告第二章概要设计2.1抽象数据类型ADTDNode{数据对象：D={ai=ai
4、aiElemSet,i=1,2,3,…,n,n>=0}数据关系：S={
5、ai-1,aiD,i=2,3,4,…，n}基本操作：CreatList（&L）操作结果：构建双循环链表DeleteSame（&L）初始条件：已建立双循环链表操作结果：删除链表中的重复元素Subset（&L1,&L2，&L3)初始条件：已建立链表L1，L2操作结果：将L1，L2的交集存入L3Delete
6、（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
7、）二重循环时间复杂度=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;//构建双循环链
8、表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
9、){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=
10、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)
