在链表中删除相同节点.doc

数据结构上机实验报告 题目：在链表中删除相同节点 学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 目 录 第一章 需求分析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.1 原题表述假设有两个无序的双向循环链表A和B，结构体为：前驱指针left，后继指针 right，数据date。将它们的头指针分别设为：pHeadA，pHeadB，输入A和B的数值，新建链表，接着构造函数，删除两个链表中相同的节点。1.2 问题解决方案 1、需要构建双循环链表，对于输入的链表，需要删除重复的结点，需要删除结点的函数。 2、首先把A中含有与B中相同的数据节点找出来组成一个新的链表C 3、遍历链表C，删除A和B的所有和C中节点值相同的节点。 解决方案要求：（1）输入参数：pA、pB两个链表 （2）输出参数：A和B中所有相同数据节点组成的链表C （3）输出参数：删除与C中节点值相同节点之后的链表A和B第二章 概要设计2.1 抽象数据类型ADT DNode 数据对象：D = ai = ai | ai ElemSet,i = 1,2,3,n, n = 0数据关系：S = | ai -1 ,ai D, 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，pB 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）第三章 详细设计3.1 程序代码#include#includetypedef int ListData;typedef struct DNoteListData data;struct DNote * left, * right;DblNode;typedef DblNode * DblList;/构建双循环链表 void CreatList(DblList &L)int val;L = (DblList)malloc(sizeof(DblNode);DblList p,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;/求交集 void Subset(DblList &L1, DblList &L2, DblList &L)DblList p, q;L = (DblList)malloc(sizeof(DblNode);DblList r, 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;/将相同元素存入新表L q = q - right;p = p - right;s - right = L;L - left = s;/删除链表中的重复元素 void DeleteSame(DblList &L)DblList p = 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 的相同元素 void Delete(DblList &L1, DblList &L2)DblList p, 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; /依次输出表中元素 void Display(DblList &L)DblList p = L - right;while(p != L)printf(%d , p - data);p = p - right;printf(n); int main()DblList pHeadA, pHeadB, pHeadC;printf(请输入A表元素(以-1结尾)n);printf(pA:);CreatList(pHeadA);printf(请输入B表元素(以-1结尾)n);printf(pB:);CreatList(pHeadB);DeleteSame(pHeadA);DeleteSame(pHeadB);Subset(pHeadA, pHeadB, pHeadC);printf(Subset pA and pB:);Display(pHeadC);Delete(pHeadA, pHeadC);printf(After DeleteEqual pA:);Display(pHeadA);Delete(pHeadB, pHeadC);printf(After DeleteEqual pB:);Display(pHeadB);return 0;第四章 调试分析4.1 出现的问题及解决方法1、 由于对循环链表算法的理解不够透彻，在构建循环链表的前期，指针指向混乱，导致程序无法通过编译。2、 在建立链表时，没有将表头表尾链接，没有构成循环。3、 开始时未考虑链表中的重复元素，导致程序无法运行。删除重复元素后，恢复正常。在编写DeleteSame（）函数时，未考虑指针指向，致使无法删除重复元素。修正后，可以删除重复元素。4、 在求交集时只考虑了一个方向，忽略了建立的是双向链表。致使无法建立交集的链表。 第五章 测试分析5.1 测试样例测试样例一： 图 5-1测试样例二：图 5-2第六章 未来展望与思考 这次的实验对我