下载文档原格式
数据结构实验报告--单链表数据结构实验报告--单链表1.引言1.1 研究目的本实验旨在通过实践的方式，深入了解单链表的数据结构以及相关操作，提升对数据结构的理解和应用能力。
1.2 实验内容本实验主要包括以下几个方面的内容：●单链表的基本定义和实现●单链表的插入、删除、遍历操作●单链表的逆置操作●单链表的查找和修改操作2.理论基础2.1 单链表的定义单链表是一种常见的线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。
2.2 单链表的基本操作①单链表的插入操作在单链表中，可以通过插入操作在指定位置插入一个新节点，该操作主要包括以下步骤：●创建一个新的节点，并为其赋值●将新节点的next指针指向插入位置的后一个节点●将插入位置的前一个节点的next指针指向新节点②单链表的删除操作在单链表中，可以通过删除操作删除指定位置的节点，该操作主要包括以下步骤：●将删除位置的前一个节点的next指针指向删除位置的后一个节点●释放删除节点的内存③单链表的遍历操作单链表的遍历操作主要是依次访问链表中的每一个节点，并执行相应的操作。
④单链表的逆置操作单链表的逆置操作可以将一个单链表中的节点顺序进行颠倒。
⑤单链表的查找操作在单链表中，可以通过查找操作找到指定值的节点。
⑥单链表的修改操作在单链表中，可以通过修改操作修改指定位置的节点的值。
3.实验过程3.1 实验环境本次实验使用C语言进行编程，需要先安装相应的编程环境，如gcc编译器。
3.2 实验步骤①单链表的创建和初始化首先创建一个空链表，并初始化链表的头指针。
②单链表的插入操作按照需求，在链表的指定位置插入一个新节点。
③单链表的删除操作按照需求，删除链表中的指定位置的节点。
④单链表的遍历操作依次访问链表中的每一个节点，并输出其值。
⑤单链表的逆置操作将单链表中的节点顺序进行逆置。
⑥单链表的查找操作按照需求，在链表中查找指定值的节点。
3.2.7 单链表的修改操作按照需求，修改链表中指定位置的节点的值。
班级：计算机11-3班学号：姓名：曲玉昆成绩：_________实验四集合的交、并和差运算的实现1. 问题描述用有序单链表表示集合，实现集合的交、并和差运算。
2. 基本要求⑴对集合中的元素，用有序单链表进行存储；⑵实现交、并、差运算时，不另外申请存储空间；⑶充分利用单链表的有序性，算法有较好的时间性能。
3. 设计思想首先，建立两个带头结点的有序单链表表示集合A和B。
单链表的结点结构和建立算法请参见教材，需要注意的是：利用头插法建立有序单链表，实参数组应该是降序排列。
其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。
⑴根据集合的运算规则，集合BA 中包含所有既属于集合A又属于集合B的元素。
因此，需查找单链表A和B中的相同元素并保留在单链表A中。
算法如下：Array⑵根据集合的运算规则，集合BA 中包含所有或属于集合A或属于集合B的元素。
因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x不相同的元素，则将该结点插入到单链表A中。
算法请参照求集合的交集自行设计。
⑶根据集合的运算规则，集合A-B中包含所有属于集合A而不属于集合B的元素。
因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x相同的结点，则将该结点从单链表A中删除。
算法请参照求集合的交集自行设计。
template<class T>struct Node{T data;N ode<T>*next;};template <class T>class LinkList{public:L inkList(T a[],int n);//建立有n个元素的单链表~LinkList();v oid Interest(Node<T> *A, Node<T> *B);//求交集v oid Sum(Node<T> *A,Node<T> *B);/v oid Subtraction(Node<T> *A,Node<T> *B);v oid PrintList();v oid Show(int i);N ode<T> *first;};template<class T>LinkList<T>::LinkList(T a[],int n){N ode<T>*s;f irst = new Node<T>;f irst->next=NULL;f or(int i=0;i<n;i++){s = new Node<T>;s->data=a[i];s->next=first->next;first->next=s; }}template <class T>LinkList<T>::~LinkList(){N ode<T> *p,*q;p = first;//工作指针p初始化w hile(p) //释放单链表的每一个结点的存储空间{q = p;//暂存被释放结点p = p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开delete q; }}template<class T>void LinkList<T>::Interest(Node<T> *A,Node<T> *B){N ode<T> *pre,*p,*q;p re = A;p =A ->next;q = B->next;w hile(p&&q){if(p->data < q->data){pre->next = p->next;p = pre->next;}else if(p->data > q->data){q = q->next;}else{pre = p;p = p->next;q = q->next;} }}//求并集template<class T>void LinkList<T>::Sum(Node<T> *A,Node<T> *B{N ode<T> *pre,*p,*q;p re = A; p = A->next;q = B->next;w hile(p&&q){if(p->data < q->data){pre = p;p = p->next;}else if(p->data > q->data){q = q->next;}else{pre->next = p->next;p = p->next;q = q->next;}}}template<class T>void LinkList<T>::Subtraction(Node<T> *A,Node<T> *B){N ode<T> *pre,*p,*q,*pra;p re = A; pra = B; p = A->next; q = B->next;w hile(p&&q){if(p->data < q->data){pre = p;p = p->next; }else if(p->data > q->data){q = q->next;}else{pre->next = p->next;p = pre->next;q = q->next;}}}template<class T>void LinkList<T>::PrintList(){N ode<T> *p;p=first->next;//工作指针p初始化w hile(p != NULL)//遍历输出所有元素{cout<<p->data;p = p->next; }c out<<endl;}//菜单函数int meun(){i nt m;d o {c out<<"请输入对应数字(1、求交集2、求并集3、求差集4、结束运行)"<<endl;c in>>m;}while(m<1||m>4);return m;}int a[]={5,4,3,2,1},b[]={6,4,2};i nt n = 5,m = 3;L inkList<int> SL(a,n);L inkList<int> sl(b,m);L inkList<int> s(a,n);L inkList<int> S(b,m);L inkList<int> l(a,n);L inkList<int> L(b,m);static bool bl = true;template<class T>void LinkList<T>::Show(int i){s witch(i) {c ase 1:{Node<T> *p,*q;p = ;q = ;();();(p,q);();cout<<endl;cout<<"已求交集"<<endl;}break;c ase 2:{Node<T> *p,*q;p = ;q = ;();();(p,q);();();cout<<"已求并集"<<endl;}break;c ase 3:{Node<T> *p,*q;p = ;q = ;();();(p,q);();cout<<"已求差集"<<endl;}break;c ase 4:{bl = false; } break; }} void main(){w hile(bl == true){int i=meun();(i);}}。
基于单链表实现集合的并交差运算实验报告一 实验题目: 基于单链表实现集合的并交差运算二 实验要求:2.2:编写一个程序，实现顺序表的各种基本运算(1)初始化单链表h ；(2)依次采用尾插法插入a,b,c,d,e 元素;(3)输出单链表h(4)输出单链表h 的长度(5)判断单链表h 是否为空(6)输出单链表h 的第三个元素(7)输出元素在a 的位置(8)在第4个元素位置上插入f 元素(9)输出单链表h(10)删除L 的第3个元素(11)输出单链表(12)释放单链表2.2:编写一个程序，采用单链表表示集合(集合中不存在重复的元素),并将其按照递增的方式排序，构成有序单链表，并求这样的两个集合的并,交和差。
三 实验内容:3.1 线性表的抽象数据类型:ADT List{数据对象;D=}0,,...,2,1,ElemS et |{≥=∈n n i a a i i数据关系:R1=},...,2,,|,{11n i D a a a a i i i i =∈><--基本操作：InitList(&L)操作结果;构造一个空的线性表LDestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表LClearList(&L)初始条件：线性表L已存在操作结果：将L置为空表ListEmpty(L)初始条件：线性表已存在操作结果：若L为空表，则返回TRUE，否则返回FALSEListLength(L)初始条件：线性表已存在操作结果：返回L中数据元素的个数GetElem(L,i)初始条件:线性表已存在，1<=i<=ListLength(L)操作结果：用e返回L中第i个数据元素的值LocateElem(L,i,e)初始条件：线性表已存在，用循环遍历整个线性表，如果e与线性表中的元素相同；操作结果：用此时的i+1返回该元素在线性表的位序ListInsert(&L,i,e)初始条件：线性表存在，1<=i<=ListLength(L)+1;操作结果：在L中第i个位置之前插入新的数据元素,e,L的长度加1。
数据结构求集合并集交集差集算法一、介绍数据结构中的集合是一种常见的数据类型，它是由不同元素组成的无序集合。
在实际的编程中，经常需要对集合进行一些操作，如求并集、交集和差集等。
本文将从数据结构的角度出发，探讨求集合并集、交集、差集的算法及其实现。
二、集合的表示方法 1. 数组 2. 链表 3. 树 4. 图在编程中，通常使用数组或者链表来表示集合。
另外，树和图也可以表示集合，但在这里不做深入讨论。
三、集合的操作 1. 求并集求并集是指将两个集合中的所有元素合并成一个集合。
假设集合A和集合B分别表示为数组arrA和数组arrB，那么求并集的算法可以按照如下步骤进行：（1）创建一个空集合C。
（2）遍历数组arrA，将其中的元素逐个添加到集合C中。
（3）遍历数组arrB，对于其中的每个元素，先判断其是否已经在集合C中存在，如果不存在则将其添加到集合C中。
（4）返回集合C即为集合A和集合B的并集。
2.求交集求交集是指找出两个集合中共同拥有的元素。
假设集合A和集合B分别表示为数组arrA和数组arrB，求交集的算法可以按照如下步骤进行：（1）创建一个空集合C。
（2）遍历数组arrA，对于其中的每个元素，判断其是否同时存在于数组arrB中，如果是则将其添加到集合C中。
（3）返回集合C即为集合A和集合B的交集。
3.求差集求差集是指找出属于集合A但不属于集合B的元素。
假设集合A和集合B分别表示为数组arrA和数组arrB，求差集的算法可以按照如下步骤进行：（1）创建一个空集合C。
（2）遍历数组arrA，对于其中的每个元素，判断其是否同时存在于数组arrB中，如果不是则将其添加到集合C中。
（3）返回集合C即为集合A和集合B的差集。
四、实现下面，我们通过示例代码来展示如何在实际编程中实现集合的并集、交集和差集的算法。
# 求并集def union(arrA, arrB):setC = arrA.copy() # 将arrA复制给setCfor i in arrB:if i not in arrA:setC.append(i)return setC# 求交集def intersection(arrA, arrB):setC = []for i in arrA:if i in arrB:setC.append(i)return setC# 求差集def difference(arrA, arrB):setC = []for i in arrA:if i not in arrB:setC.append(i)return setC五、总结本文从数据结构的角度出发，探讨了求集合并集、交集、差集的算法及其实现。
单链表求集合的并、交和差运算单链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
在计算机科学中，我们经常需要对集合进行操作，包括求并集、交集和差集。
在本文中，我们将介绍如何使用单链表来实现这些集合操作。
我们需要定义一个单链表的数据结构。
每个节点包含一个数据元素和一个指向下一个节点的指针。
我们可以使用类来实现这个数据结构，例如：```class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None```接下来，我们需要实现集合的并、交和差运算。
首先是并运算，它将两个集合中的所有元素合并为一个新的集合。
我们可以使用两个指针分别遍历两个链表，将两个链表中的元素逐个比较，并将不重复的元素添加到结果链表中。
具体代码如下：```def union(l1, l2):result = LinkedList()p1 = l1.headp2 = l2.headwhile p1 is not None:result.append(p1.data)p1 = p1.nextwhile p2 is not None:if not result.contains(p2.data):result.append(p2.data)p2 = p2.nextreturn result```接下来是交运算，它将两个集合中共有的元素提取出来组成一个新的集合。
同样地，我们可以使用两个指针分别遍历两个链表，将相同的元素添加到结果链表中。
具体代码如下：```def intersection(l1, l2):result = LinkedList()p1 = l1.headwhile p1 is not None:if l2.contains(p1.data):result.append(p1.data)p1 = p1.nextreturn result```最后是差运算，它将第一个集合中不属于第二个集合的元素提取出来组成一个新的集合。
实验报告实验课程：数据结构实验项目：实验一集合的并交差运算专业：计算机科学与技术班级：姓名：学号：指导教师：目录一、问题定义及需求分析（1）实验目的（2）实验任务（3）需求分析二、概要设计：(1)抽象数据类型定义(2)主程序流程(3) 模块关系三、详细设计(1)数据类型及存储结构(2)模块设计四、调试分析(1)调试分析(2)算法时空分析(3)经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图七、附录(1)源代码一、问题定义及需求分析（1）实验目的设计一个能演示集合的并、交、差运算程序。
（2）实验任务1)采用顺序表或链表等数据结构。
2)集合的元素限定为数字和小写英文字母。
（3）需求分析：输入形式为:外部输入字符串；输入值限定范围为:数字和小写英文字母；输出形式为：字符集；程序功能:计算两个集合的交、并、差以及重新输入集合功能；二、概要设计：(1)抽象数据类型定义：线性表(2)主程序流程：调用主菜单函数初始化两个线性表作为集合给两个集合输入数据输出集合数据元素信息另初始化两个线性表创建选择功能菜单界面通过不同选项调用不同功能函数在每个功能函数里面加结束选择功能，实现循环调用功能菜单计算完毕退出程序；（3）模块关系：差运算并运算交运算新建集合结束/返回结束三、详细设计抽象数据类型定义：typedef struct{ElemType *elem;int length;int listsize;}SqList;存储结构：顺序表；模块1-在顺序表的逻辑为i的位置插入新元素e的函数；算法如下：/**在顺序表的逻辑为i的位置插入新元素e的函数**/Status ListInsert_Sq(SqList &L,int i,ElemType e){ElemType *newbase,*p,*q;if(i < 1 || i > L.length + 1) return 0; //i的合法值为(1 <= i <= L.length_Sq(L) + 1)if(L.length >= L.listsize){ //当前储存空间已满，增加分配newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));if(!newbase) exit(-1); //储存分配失败L.elem = newbase; //新基址L.listsize += LISTINCREMENT; //增加储存容量}q = &(L.elem[i - 1]); //q为插入位置for(p = &(L.elem[L.length - 1]); p >= q; --p)(p + 1) = p; //插入位置及之后的元素往右移q = e; //插入e++L.length; //表长加1return 1;}模块二在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0算法如下：/**在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0**/int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)){ElemType *p;int i;i = 1; //i的初值为第1个元素的位序p = L.elem; //p的初值为第1个元素的储存位置while(i <= L.length && !(* compare)(*p++,e))++i; //从表L中的第一个元素开始与e比较，直到找到L中与e相等的元素时返回该元素的位置if(i <= L.length) return i; //若i的大小小于表长，则满足条件返回ielsereturn 0; //否则，i值不满足条件，返回0}模块三集合交运算算法如下：/**求集合的交集的函数**/void Mix_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length = 0; //将表Lc的长度设为0for(i = 1; i <= La.length; i++){ //依次查看表La的所有元素elem = La.elem[i-1]; //将表La中i位置的元素赋值给elemif(LocateElem_Sq(Lb,elem,Equal)) //在表Lb中查找是否有与elem相等的元素ListInsert_Sq(Lc,Lc.length+1,elem); //将表La与Lb 中共同的元素放在Lc中}}模块四集合并运算算法如下：/**求集合的并集的函数**/void Union_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length=0; //将表Lc的长度初设为0for(i = 0; i < La.length; i++) //先将表La 的元素全部复制到表Lc中Lc.elem[Lc.length++]=La.elem[i];for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //依次将表Lb 的值赋给elemif(!LocateElem_Sq(La,elem,Equal)) //判断表La 中是否有与elem相同的值ListInsert_Sq(Lc,Lc.length+1,elem); //若有的话将elem放入表Lc中}}模块五集合的差运算算法如下：/**求集合的差集函数**/void Differ_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length = 0;for(i = 1; i <= La.length; i++){elem = La.elem[i-1]; //把表La 中第i个元素赋值给elemif(!LocateElem_Sq(Lb,elem,Equal)) //判断elem在表Lb中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放}for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //把表Lb 中第i个元素赋值给elemif(!LocateElem_Sq(La,elem,Equal)) //判断elem在表La中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放}}四、调试分析问题分析及解决：首先，在编写程序时没有设置线性表的初始长度，导致集合元素输入错误；然后通过#define LIST_INIT_SIZE 100和#define LISTINCREMENT 10解决；时空分析：int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))时间复杂度为O(n);Status ListInsert_Sq(SqList &L,int i,ElemType e) 时间复杂度为O(n);void Union_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);void Mix_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);void Differ_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(2*m*n);改进设想：当同时求两个以上的结合间的运算是需要先进性两个集合间的运算，然后在于另外的集合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；经验体会：顺序表使用起来比较简单，但长度不可随意变化，适用于大量访问元素，而不适用于大量增添和删除元素；在内存中存储地址连续；五、使用说明第一步：点击运行按钮；第二步: 根据提示输入集合A(可以连续输入，只限输入小写字母和数字)；第三步：程序自动显示输入结果；第四步：输入集合B（同第二步）；第五步：跳出主菜单界面；第六步：根据选项输入对应运算项的数字序号；第七步：显示运算结果，并可继续进行选择运算还是退出；第八步：若继续运算则返回主菜单，否则退出；第九步：循环第六、七、八步，直至选择退出；六、测试结果输入界面：并运算结果：交运算结果：差运算结果：重新建立集合并运算：七、附录#include<stdio.h>#include<stdlib.h>#define LIST_INIT_SIZE 100//初始表空间大小#define LISTINCREMENT 10//表长增量typedef int Status; /**Status是函数类型**/typedef char ElemType;/*ElemType类型根据实际情况而定，这里假设为char*/typedef struct{ElemType *elem; /**储存空间基地址**/int length; /**当前长度**/int listsize;/**当前分配的储存容量（以sizeof(Elemtype)为单位）**/}SqList;SqList La,Lb,Lc,Ld;/**定义全局变量**//**构造一个空的线性表L**/Status InitList_Sq(SqList &L){L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));if(!L.elem) exit(-1); /**储存分配失败**/L.length = 0;L.listsize = LIST_INIT_SIZE;/**初始储存容量**/return 1;}/**在顺序表的逻辑为i的位置插入新元素e的函数**/Status ListInsert_Sq(SqList &L,int i,ElemType e){ElemType *newbase,*p,*q;if(i < 1 || i > L.length + 1)return 0;if(L.length >= L.listsize)//当前储存空间已满，增加分配{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT )*sizeof(ElemType));if(!newbase) exit(-1);//储存分配失败L.elem = newbase;L.listsize += LISTINCREMENT;//增加储存容量}q = &(L.elem[i - 1]);//q为插入位置for(p = &(L.elem[L.length - 1]); p >= q; --p)*(p + 1) = *p;//插入位置及之后的元素往右移*q = e;//插入e++L.length;return 1;}/**创建一个线性表，输入数据**/void CreateList_Sq(SqList &L){ElemType ch='\0';int inlist =0,j;while((ch) != '\n'){scanf("%c",&ch);//输入数据for(j = 0; j < L.length; j++)if(ch == L.elem[j])//判断表L中是否有与ch相等的元素 {inlist = 1; //若有，则inlist置1break; //跳出本轮循环}elseinlist =0; //否则inlist为0if(!inlist && ch != '\n')//若inlist为0且ch不为”\n” ListInsert_Sq(L,L.length+1,ch);//则将ch存入表L中 }}/*判断两元素是否相等,若相等则返回1;否则返回0*/Status Equal(ElemType a,ElemType b){if(a == b)return 1;//相等，返回1elsereturn 0;//否则，返回0}/*在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0*/int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)){ElemType *p;int i;i = 1;p = L.elem;//p的初值为第1个元素的储存位置while(i <= L.length && !(* compare)(*p++,e))//循环查找表L 找出其中与e相等的元素的位置++i;if(i <= L.length)//若i小于表长return i;//则i满足条件，返回i的值elsereturn 0;//否则返回0}/*销毁线性表的函数*/Status Clear_Sq(SqList &L){ElemType elem;free(L.elem);L.elem = NULL;return 1;}/*打印顺序表函数*/void Print_Sq(SqList L){int i;for(i = 0; i < L.length; i++)printf("%2c",L.elem[i]);//通过for循环将表元素全部输出 if(L.length == 0) printf("空集");//若表长为0，则输出空表 printf("\n\t\t\t此集合中的个数 n = %d\n\n",L.length);}/*求集合的并集的函数*/void Union_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length=0; //将表Lc的长度初设为0for(i = 0; i < La.length; i++) //先将表La的元素全部复制到表Lc中Lc.elem[Lc.length++]=La.elem[i];for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //依次将表Lb 的值赋给elemif(!LocateElem_Sq(La,elem,Equal)) //判断表La 中是否有与elem相同的值ListInsert_Sq(Lc,Lc.length+1,elem); //若有的话将elem放入表Lc中}}/*求集合的交集的函数*/void Mix_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length = 0; //将表Lc的长度设为0for(i = 1; i <= La.length; i++){ //依次查看表La的所有元素elem = La.elem[i-1]; //将表La中i位置的元素赋值给elemif(LocateElem_Sq(Lb,elem,Equal)) //在表La中查找是否有与elem相等的元素ListInsert_Sq(Lc,Lc.length+1,elem); //将表La与Lb中共同的元素放在Lc中}}/*求集合的差集函数*/void Differ_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length = 0;for(i = 1; i <= La.length; i++){elem = La.elem[i-1]; //把表La中第i个元素赋值给elemif(!LocateElem_Sq(Lb,elem,Equal)) //判断elem在表Lb中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem);//若有，则把elem放入表Lc中，否则，就不存放}for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //把表Lb中第i个元素赋值给elem if(!LocateElem_Sq(La,elem,Equal)) //判断elem在表La中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放}}void Index_Sq(){//主菜单函数char s;int l=1;InitList_Sq(La);//初始化表Laprintf("\n\t\t 请输入集合A:");CreateList_Sq(La);//创建表Laprintf("\t\t\t集合A为");Print_Sq(La);printf("\n\n");InitList_Sq(Lb);//初始化表Lbprintf("\t\t 请输入集合B:");CreateList_Sq(Lb);//创建表Lbprintf("\t\t\t集合B为");Print_Sq(Lb);printf("\n\n");InitList_Sq(Lc);//初始化表LcInitList_Sq(Ld);//初始化表Ldwhile(l){printf("\t\t ******* 请输入您的操作选项 1、2、3、4. ****** \n\n");printf("\t\t 1、进行集合的并运算\n");printf("\t\t 2、进行集合的交运算\n");printf("\t\t 3、进行集合的差运算\n");printf("\t\t 4、重新建立两个集合\n");printf("\t\t\t");scanf("%c",&s);switch(s){case '1' : system("cls");Union_Sq(La,Lb,Lc);//调用集合的并运算函数printf("\t\t\t集合A与集合B的并集为:");print_Sq(Lc);printf("\n");break;case '2' :system("cls");Mix_Sq(La,Lb,Lc);//调用集合的交集运算函数printf("\t\t\t集合A与集合B的交集为:");print_Sq(Lc);printf("\n");break;case '3' : system("cls");Differ_Sq(La,Lb,Lc);//调用集合的差集运算函数 printf("\t\t\t集合A与集合B的差集为:");print_Sq(Lc);printf("\n");break;case '4' :system("cls");Clear_Sq(La);//销毁表LaClear_Sq(Lb);//销毁表LbClear_Sq(Lc);//销毁表LcClear_Sq(Ld);//销毁表Ldgetchar();Index_Sq();//递归调用此函数break;default : printf("\t\t\t#\tenter data error!\n");printf("\n");}printf("\t\t 继续计算请输入1，停止计算请输入0 \n");printf("\t\t\t");scanf("%d",&l);getchar();system("cls");}printf("\n\t\t**************** 谢谢使用！*****************\n");}int main(){printf("\t\t************* 欢迎使用集合操作运算器************\n");Index_Sq();//调用主菜单函数return 0;}。
实验截图（1）void InitList(LinkNode *&L)//初始化线性表{L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L->next=NULL;//单链表置为空表}void DestroyList(LinkNode *&L)//销毁线性表{LinkNode *pre=L,*p=pre->next;实验截图（2）bool GetElem(LinkNode *L,int i,ElemType &e) //求线性表中第i个元素值{ int j=0;if (i<=0) return false;//i错误返回假LinkNode *p=L;//p指向头结点,j置为0(即头结点的序号为0) while (j<i && p!=NULL)//找第i个结点p{ j++;p=p->next;}if (p==NULL)//存在值为e的结点,返回其逻辑序号ireturn(i);}实验截图（3）bool ListInsert(LinkNode *&L,int i,ElemType e) //插入第i个元素{ int j=0;if (i<=0) return false;//i错误返回假LinkNode *p=L,*s;//p指向头结点,j置为0(即头结点的序号为0) while (j<i-1 && p!=NULL)//查找第i-1个结点p{ j++;p=p->next;}}实验截图（4）编写exp2-2.cpp程序包含有关代码//文件名:exp2-2.cpp#include "linklist.cpp"int main(){LinkNode *h;ElemType e;printf("单链表的基本运算如下:\n");printf(" (1)初始化单链表h\n");InitList(h);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");return 1;}实验截图（5）运行得到结果实验截图（6）。
使⽤单链表来实现集合的交并差运算数据结构使⽤单链表来实现集合的交并差运算数据结构问题描述该算法的设计，要求运⾏结果如下所⽰：集合的运算如下:原集合A: c a e h原集合B: f h b g d a有序集合A: a c e h有序集合B: a b d f g h集合的并C: a b c d e f g h集合的交C: a h集合的差C: c e代码实现⾸先这⾥交并差的实现是基于链表中的元素已经从⼩到⼤排完序的链表。
这⾥排序使⽤的是冒泡排序。
//链表的冒泡排序算法bool BubbleSort(LinkList &L) //链表的冒泡排序{LinkList p, q, tail;tail=NULL;while((L->next->next)!=tail){p=L;q=L->next;while(q->next!=tail){if((q->data) > (q->next->data)){p->next=q->next;q->next=q->next->next;p->next->next=q;q=p->next;}q=q->next;p=p->next;}tail=q;}return true;}//集合的并bool merge(LinkList &L1, LinkList &L2, LinkList &L3)//集合的并这⾥的集合已经排序{LinkList p1=L1->next, p2=L2->next, p3=L3, s;while(p1!=NULL && p2!=NULL){if(p1->data!=p2->data){if(p1->data > p2->data)swap(p1, p2);while(p1!=NULL && p1->data < p2->data){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}}elses->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;p2=p2->next;}}if(p2!=NULL) //这⾥统⼀让p1代表链表中还有剩余元素的那条链p1=p2;while(p1!=NULL){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}return true;}//集合的交bool intersect(LinkList &L1, LinkList &L2, LinkList &L3)//集合的交这⾥的集合已经排序{LinkList p1=L1->next, p2=L2->next, p3=L3, s;if(p1==NULL || p2==NULL)//两者中有⼀个是空链表return false;while(p1!=NULL){while(p2!=NULL){if(p2->data==p1->data){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;}if(p2->data > p1->data)break;p2=p2->next;}p1=p1->next;}return true;}//集合的差bool differ(LinkList &L1, LinkList &L2, LinkList &L3) //集合的差这⾥的集合已经排序{LinkList p1=L1->next, p2=L2->next, p3=L3, s;if(p1->next==NULL)return false;while(p1!=NULL && p2!=NULL){if(p1->data!=p2->data){if(p1->data > p2->data){while(p1->data > p2->data ) //这⾥要保证p2后⾯的值也要不能⼤于p1当前的值{p2=p2->next;}if(p1->data==p2->data)continue;}s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}else{p1=p1->next;p2=p2->next;}}while(p1!=NULL)s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}return true;}//完整的代码实现#include<bits/stdc++.h>using namespace std;typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList;bool init(LinkList &L){L=(LinkList)malloc(sizeof(LNode));if(L==NULL)return false;L->next=NULL;return true;}bool search(LinkList &L, int x){LinkList p=L->next;while(p){if(p->data==x)return false;p=p->next;}return true;}bool creat_list(LinkList &L, char a[], int n) //采⽤尾插法建⽴单链表{LinkList p=L, s;for(int i=0; i<n; i++){if(search(L, a[i])==false)continue;s=(LinkList)malloc(sizeof(LNode));if(s==NULL)return false;s->data=a[i];s->next=NULL;p->next=s;p=s;}return true;}bool display(LinkList &L){LinkList p=L->next;if(p==NULL)return false;while(p){printf("%c ", p->data);p=p->next;}printf("\n");return true;}bool clear(LinkList &L){LinkList p;while(L){p=L->next;free(L);L=p;}L=NULL;return true;}bool BubbleSort(LinkList &L) //链表的冒泡排序{LinkList p, q, tail;tail=NULL;p=L;q=L->next;while(q->next!=tail){if((q->data) > (q->next->data)){p->next=q->next;q->next=q->next->next;p->next->next=q;q=p->next;}q=q->next;p=p->next;}tail=q;}return true;}bool merge(LinkList &L1, LinkList &L2, LinkList &L3)//集合的并这⾥的集合已经排序{LinkList p1=L1->next, p2=L2->next, p3=L3, s;while(p1!=NULL && p2!=NULL){if(p1->data!=p2->data){if(p1->data > p2->data)swap(p1, p2);while(p1!=NULL && p1->data < p2->data){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}}else{s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;p2=p2->next;}}if(p2!=NULL) //这⾥统⼀让p1代表链表中还有剩余元素的那条链p1=p2;while(p1!=NULL){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}return true;}bool intersect(LinkList &L1, LinkList &L2, LinkList &L3)//集合的交这⾥的集合已经排序{LinkList p1=L1->next, p2=L2->next, p3=L3, s;if(p1==NULL || p2==NULL)//两者中有⼀个是空链表return false;while(p1!=NULL){while(p2!=NULL){if(p2->data==p1->data){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;}if(p2->data > p1->data)break;p2=p2->next;}return true;}bool differ(LinkList &L1, LinkList &L2, LinkList &L3) //集合的差这⾥的集合已经排序{LinkList p1=L1->next, p2=L2->next, p3=L3, s;if(p1->next==NULL)return false;while(p1!=NULL && p2!=NULL){if(p1->data!=p2->data){if(p1->data > p2->data){while(p1->data > p2->data ) //这⾥要保证p2后⾯的值也要不能⼤于p1当前的值{p2=p2->next;}if(p1->data==p2->data)continue;}s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}else{p1=p1->next;p2=p2->next;}}while(p1!=NULL){s=(LinkList)malloc(sizeof(LNode));s->data=p1->data;s->next=NULL;p3->next=s;p3=s;p1=p1->next;}return true;}/*产⽣n个[min, max]的随机数。
数据结构实验报告_单链表数据结构实验报告——单链表一、实验目的1.掌握单链表的基本概念和原理。
2.了解单链表在计算机科学中的应用。
3.掌握单链表的基本操作，如插入、删除、遍历等。
4.通过实验，加深对理论知识的理解，提高编程能力。
二、实验内容1.实验原理：单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。
其中，指针域指向下一个节点，最后一个节点的指针域指向空。
单链表的主要操作包括插入、删除、遍历等。
2.实验步骤：（1）创建一个单链表。
（2）实现插入操作，即在链表的末尾插入一个新节点。
（3）实现删除操作，即删除链表中的一个指定节点。
（4）实现遍历操作，即输出链表中所有节点的数据。
3.实验代码：下面是使用Python语言实现的单链表及其基本操作的示例代码。
class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef insert(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeelse:current = self.headwhile current.next is not None:current = current.nextcurrent.next = new_nodedef delete(self, data):if self.head is None:returnif self.head.data == data:self.head = self.head.nextreturncurrent = self.headwhile current.next is not None and current.next.data != data:current = current.nextif current.next is None:returncurrent.next = current.next.nextdef traverse(self):current = self.headwhile current is not None:print(current.data)current = current.next4.实验结果：通过运行上述代码，我们可以看到单链表的基本操作得到了实现。
