1、数据结构上机实验报告题目：在链表中删除相同节点学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 I目 录第一章 需求分析 .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.1 原题表述假设有两个无序的双向循环链表 A 和 B，结构
2、体为：前驱指针 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 中节点值相同节点之后的链表
3、A 和 B计算机学院 2013 级数据结构上机实验报告2第二章 概要设计2.1 抽象数据类型ADT DNode 数据对象：D = a i = ai | ai ElemSet,i = 1,2,3,n, n = 0数据关系：S = | ai -1 ,ai D, i = 2,3,4,，n基本操作：CreatList（typedef struct DNoteListData data;struct DNote * left, * right;DblNode;typedef DblNode * DblList;/构建双循环链表 void CreatList(DblList L = (DblList)ma
4、lloc(sizeof(DblNode);DblList p,q = L;while(scanf(“%d“,p - data = val;p - left = q;q - right = p;q = p;q - right = L;L - left = q;/求交集 void Subset(DblList 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
5、)malloc(sizeof(DblNode);r - data = p - data;r - left = s;s - right = r;s = r;计算机学院 2013 级数据结构上机实验报告5/将相同元素存入新表 L q = q - right;p = p - right;s - right = L;L - left = s;/删除链表中的重复元素 void DeleteSame(DblList while(p != L)q = p - right;while(q != L)if(p - data = q - data)r = q;r - right - left = r - left
6、;r - left - right = r - right;free(r);q = q - right ;p = p - right; /删除 L1，L2 的相同元素 void Delete(DblList 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 Displa
7、y(DblList 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, pH
8、eadC);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;计算机学院 2013 级数据结构上机实验报告7第四章 调试分析4.1 出现的问题及解决方法1、 由于对循环链表算法的理解不够透彻，在构建循环链表的前期，指针指向混乱，导致程序无法通过编译。2、 在建立链表时，没有将表头表尾链接，没有构成循环。3、 开始时未考虑链表中的重复元素，导致程序无法运行。删除重复元素后，恢复正常。在编写 DeleteSame（）函数时，未考虑指针指向，致使无法删除重复元素。修正后，可以删除重复元素。4、 在求交集时只考虑了一个方向，忽略了建立的是双向链表。致使无法建立交集的链表。计算机学院 2013 级数据结构上机实验报告8第五章 测试分析5.1 测试样例测试样例一：图 5-1测试样例二：图 5-2
