用单链表实现集合的操作

基于单链表实现集合的交集、并集、差集的运算解题思路（单链表求交集、并集、差集的思想和顺序表求交集、并集、差集的思想基本相同）1.先通过CreateListR 函数将集合 a 和 b 中的元素添加到顺序表 ha 和 hb 中，添加过程使⽤的是顺序表原有的Initlist 函数（初始化表）和ListInsert 函数（向表中插⼊元素）。

2.因为原集合是⽆序的，所以我通过 sort 函数（选择排序），使得集合变得有序。

3.得到有序集合 ha 和 hb 后，便可以使⽤ Union 函数（类似归并的思想写出来的求并集的函数），求出 ha 和 hb 的并集。

4.⽽求交集的⽅法则是，通过将集合 a 中的元素⼀个⼀个取出，并通过函数LocateElem ，查看集合 hb 中是否存在该元素，如果存在则将元素放⼊ hc ，如果不存在，则舍去。

以此求得两集合的交集。

5.求两集合的差则可以反过来，同样通过将集合 a 中的元素⼀个⼀个取出，并通过函数LocateElem ，查看集合 hb 中是否存在该元素，如果不存在则将元素放⼊ hc ，如果存在，则舍去。

以此求得两集合的差集。

#include <iostream>#include <cstdio>#include <malloc.h>using namespace std;/* 定义单链表数据 */typedef char ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LinkList;/* 单链表的初始化 */void InitList(LinkList *&L){L = (LinkList *)malloc(sizeof(LinkList));L->next=NULL;}/* 向单链表中插⼊数据元素 */bool ListInsert(LinkList *&L,int x,char e){int j = 0;LinkList *p = L, *s;while(p!=NULL && j<x-1){p = p->next;j++;}if(p==NULL){return false;}else{s = (LinkList *)malloc(sizeof(LinkList));s->data = e;s->next = p->next;p->next = s;return true;}}/* 输出单链表 */void DispList(LinkList *L){LinkList *p = L->next;while(p!=NULL){printf("%c ",p->data);p = p->next;}printf("\n");}/* 求单链表的长度 */int ListLength(LinkList *L){LinkList *p = L->next;int i = 0;while(p!=NULL){p = p->next;}return i;}/* 查看单链表是否为空 */bool ListEmpty(LinkList *L){return L->next==NULL;}/* 求单链表中某个数据元素值 */bool GetElem(LinkList *L,int i, ElemType &e) {LinkList *p = L;int j = 0;while(p!=NULL && j < i){p=p->next;j++;}if(p==NULL){return false;}else{e = p->data;return true;}}/* 在单链表中查找元素 */int LocateElem(LinkList *L,ElemType e){LinkList *p = L;int i = 0;while(p!=NULL && p->data!=e){p = p->next;i++;}if(p==NULL){return0;}else{return i;}}/* 删除单链表中第 i 个元素*/bool ListDelete(LinkList *&L,int i,ElemType &e) {int j = 0;LinkList *p = L, *q;while(p!=NULL && j < i - 1){p = p->next;j++;}if(p==NULL)return false;else{q = p->next;if(q==NULL)return false;e = q->data;p->next = q->next;free(q);return true;}}/* 删除单链表 */void DestroyList(LinkList *&L){LinkList *p = L;LinkList *q = p->next;while(q!=NULL){p = q;q = p->next;}free(p);}void CreateListR(LinkList *&L,ElemType e[],int n) {InitList(L);int i;for(i = 0;i < n; ++i){if(!LocateElem(L,e[i]))ListInsert(L,i+1,e[i]);}}void InsterSect(LinkList *a,LinkList *b,LinkList *&c) {DestroyList(c);InitList(c);LinkList *p = a->next;int i = 0;while(p!=NULL){if(LocateElem(b,p->data))ListInsert(c,++i,p->data);p = p->next;}}void Subs(LinkList *a,LinkList *b,LinkList *&c){DestroyList(c);InitList(c);LinkList *p = a->next;int i = 0;while(p!=NULL){if(!LocateElem(b,p->data))ListInsert(c,++i,p->data);p = p->next;}}void Union(LinkList *a,LinkList *b,LinkList *&c){InitList(c);LinkList *p = a->next;LinkList *q = b->next;int k = 0;while(p!=NULL && q!=NULL){if(p->data < q->data){ListInsert(c,k+1,p->data);p = p->next;k++;}else if(p->data == q->data){ListInsert(c,k+1,p->data);p = p->next;q = q->next;k++;}else{ListInsert(c,k+1,q->data);q = q->next;k++;}}while(p!=NULL){ListInsert(c,k+1,p->data);p = p->next;k++;}while(q!=NULL){ListInsert(c,k+1,q->data);q = q->next;}///cout<<"hehe"<<endl;}void sort(LinkList *&L){LinkList *p , *pre, *q, *k;InitList(p);int i = 0;char c;while(!ListEmpty(L)){pre = L ->next;c = pre->data;while(pre!=NULL){if(c>=pre->data)c = pre->data;pre = pre->next;}ListInsert(p,++i,c);int tag = LocateElem(L,c);ListDelete(L,tag,c);}L = p;}int main( ){LinkList *ha, *hb, *hc;ElemType a[]={'c','a','e','h'};ElemType b[]={'f','h','b','g','d','a'};printf("集合的运算如下\n");CreateListR(ha,a,4);CreateListR(hb,b,6);printf("原集合 A: "); DispList(ha); printf("原集合 B: "); DispList(hb); sort(ha);sort(hb);printf("有序集合A："); DispList(ha); printf("有序集合B："); DispList(hb); Union(ha,hb,hc);printf("集合的并C："); DispList(hc); InsterSect(ha,hb,hc);printf("集合的交C："); DispList(hc); Subs(ha,hb,hc);printf("集合的差C："); DispList(hc); DestroyList(ha);DestroyList(hb);DestroyList(hc);return0;}。

班级：计算机11-3班学号：姓名：曲玉昆成绩：_________实验四集合的交、并和差运算的实现1. 问题描述用有序单链表表示集合，实现集合的交、并和差运算。

2. 基本要求⑴对集合中的元素，用有序单链表进行存储；⑵实现交、并、差运算时，不另外申请存储空间；⑶充分利用单链表的有序性，算法有较好的时间性能。

3. 设计思想AB。

单链表的结点结构和建立算法和首先，建立两个带头结点的有序单链表表示集合请参见教材，需要注意的是：利用头插法建立有序单链表，实参数组应该是降序排列。

其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。

AB的元素。

又属于集合⑴根据集合的运算规则，集合中包含所有既属于集合BA?因此，需查找单链表A和B中的相同元素并保留在单链表A中。

算法如下：的元素。

BA或属于集合中包含所有或属于集合⑵根据集合的运算规则，集合B?A xx不相同的元素，则中进行查找，若存在和B中的每个元素，在单链表A因此，对单链表A中。

算法请参照求集合的交集自行设计。

将该结点插入到单链表的元素。

因而不属于集合AB根据集合的运算规则，集合⑶ A-B中包含所有属于集合xx相同的结点，则将该中进行查找，若存在和AB此，对单链表中的每个元素，在单链表中删除。

算法请参照求集合的交集自行设计。

A结点从单链表．template<class T>struct Node{T data;Node<T>*next;};template <class T>class LinkList{public:LinkList(T a[],int n);//建立有n个元素的单链表~LinkList();void Interest(Node<T> *A, Node<T> *B);//求交集void Sum(Node<T> *A,Node<T> *B);/void Subtraction(Node<T> *A,Node<T> *B);void PrintList();void Show(int i);Node<T> *first;};template<class T>LinkList<T>::LinkList(T a[],int n){Node<T>*s;first = new Node<T>;first->next=NULL;for(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(){Node<T> *p,*q;p = first;//工作指针p初始化while(p) //释放单链表的每一个结点的存储空间{q = p;//暂存被释放结点p = p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开 delete q; }}template<class T>void LinkList<T>::Interest(Node<T> *A,Node<T> *B){Node<T> *pre,*p,*q;re = A;p =A ->next;q = B->next;pwhile(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{Node<T> *pre,*p,*q;pre = A; p = A->next;q = B->next;while(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){ Node<T> *pre,*p,*q,*pra;pre = A; pra = B; p = A->next; q = B->next;while(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(){Node<T> *p;p=first->next;//工作指针p初始化while(p != NULL)//遍历输出所有元素{cout<<p->data;p = p->next; }cout<<endl;}//菜单函数int meun(){int m;do {c畯?尼请输入对应数字(1、求交集2、求并集3、求差集4、结束运行)<<endl; cin>>m;}while(m<1||m>4);return m;}int a[]={5,4,3,2,1},b[]={6,4,2};int n = 5,m = 3;LinkList<int> SL(a,n);LinkList<int> sl(b,m);LinkList<int> s(a,n);LinkList<int> S(b,m);LinkList<int> l(a,n);LinkList<int> L(b,m);static bool bl = true;template<class T>void LinkList<T>::Show(int i){switch(i) {case 1:{Node<T> *p,*q;p = ;q = ;();();(p,q);();cout<<endl;<<endl;}break;已求交集潣瑵?case 2:{Node<T> *p,*q;p = ;q = ;();();(p,q);();();潣瑵?已求并集<<endl;}break;case 3:{Node<T> *p,*q;p = ;q = ;();();(p,q);();潣瑵?已求差集<<endl;}break;case 4:{bl = false; } break; }}void main(){while(bl == true){int i=meun();(i);}}。

实验一创建链表和链表操作一、实验目的掌握线性表的基本操作：插入、删除、查找、以及线性表合并等操作在顺序存储结构和链式存储结构上的实现。

二、实验内容：1. 创建单链表2．在链表上进行插入、删除操作；3．设计一个程序，用两个单链表分别表示两个集合，并求出这两个集合的并集。

四、测试数据：∙（3，9，5，6，11，8）；在5之前插入4，7，并删除11∙求集合{1，12，8，6，4，9}和{2，5，12，7，4}的并集五、概要设计：本操作应完成如下功能：（1）创建链表说明：分配一定的空间，根据给定的链表长度输入值，创建链表。

（2）合并链表说明：将两个链表合并为一个链表只需修改链表头、尾指针即可实现。

（3）在链表中插入值说明：将给定的值插入到指定位置上，只需修改插入位置的前后结点的指针即可。

（4）在链表中删除值说明：将指定位置的值删除，只需修改删除位置的前后结点的指针即可。

六、详细设计：源代码：#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<iostream.h>#define OK 1#define ERROR 0#define OVERFLOW 0//线性链表的存储结构，一个结点typedef struct LNode{int data; // 数据域struct LNode *next; // 指针域}LNode,*LinkList; //结点结构类型和指向结点的指针类型int TraverseList_L(LinkList L) //遍历单链表{LinkList p;p=L->next;while(p){printf("-->%d",p->data);p=p->next;}return OK;}//尾插法创建的带头结点的单链表。

void CreateList_L(LinkList &L,int &n){L=(LinkList)malloc(sizeof (LNode));//建立一个空链表L。

单链表求集合的并、交和差运算单链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

在计算机科学中，我们经常需要对集合进行操作，包括求并集、交集和差集。

在本文中，我们将介绍如何使用单链表来实现这些集合操作。

我们需要定义一个单链表的数据结构。

每个节点包含一个数据元素和一个指向下一个节点的指针。

我们可以使用类来实现这个数据结构，例如：```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```最后是差运算，它将第一个集合中不属于第二个集合的元素提取出来组成一个新的集合。

广义表的单链表示是一种数据结构，它采用链式存取方式，利用结点的方式表示数据。

在这一数据结构中，每个结点由一个元素和一个指向其他结点的指针组成。

单链表的创建有两种方法，分别是头插入法和尾插入法。

头插入法的效果是使得整个链表的元素逆序，而尾插入法则能够保证结点次序与输入数据保持一致。

我们以一个简单的例子来说明如何进行广义表的单链表示。

假设我们有一个名为"A,B"的广义表，表示元素为"A"和"B"的两个元素组成的集合。

这个广义表可以转换成一个单链表来进行存储。

首先，我们可以创建两个空结点，分别表示"A"和"B"的元素，并且在每个结点上设置一个指向下一个结点的指针。

例如，我们可以将第一个结点设置为指向第二个结点的指针，而将第二个结点设置为指向空的指针。

然后，我们可以使用尾插入法将"A"和"B"这两个元素依次插入到链表的尾部。

这就需要我们不断地使用递归的方法，将当前结点插入到链表的尾部。

在每一次递归中，我们都需要递增一个指针来指向当前结点的下一个结点。

当我们完成整个插入操作后，整个链表的结构将类似于一个无穷的链表，其中"A"和"B"分别在链表的首尾两个位置。

值得注意的是，由于广义表的元素可能是多元组或者无穷集，因此单链表的长度和深度也可能是无限的。

这就需要我们在实现单链表的操作时，需要进行一些特殊的处理。

例如，我们可以使用栈或者树等数据结构来管理结点的插入和删除操作。

总之，广义表的单链表示是一种非常实用的数据结构，它能够有效地表示和管理无穷集和多元组等复杂数据。

通过采用单链表的结构，我们能够方便地进行元素的插入、删除、查找等操作，并在需要时进行递归处理。

实验二单链表求集合的并集一．实验目的1．熟悉数据结构的设计过程，并实现的数据结构链表的设计。

2．用设计的链表实现求集合的并集。

3．设计单链表、单向循环链表、双向链表和双向循环链表。

二、实验内容1．设计带头结点的单链表：设计头文件LinkList.h，其内容如下：#include "stdlib.h"typedef struct node{elemtype data;node *next;}Lnode,*Linklist;void InitList(Linklist &h){h=new Lnode;h->next=NULL;}void Creat(Linklist &h,int n){InitList(h);cout<<"Please input "<<n<<" number!";Lnode *r;r=h;for(int i=1;i<=n;i++){Lnode *p;//动态生成一个结点，用p保存其地址p=new Lnode;//从键盘输入一个数据元素，放入动态生成结点的数据域cin>>p->data;//将动态生成的p所指结点插入到表尾，即插入到r指针所指结点的后面p->next=NULL;//p->next=r->next;r->next=p;//r指针指向新的表尾r=p;}}Lnode *GetElem(Linklist h,int i){int j=0;Lnode *p;p=h;while(p&&j<i){p=p->next;j++;}return p;}void Insert(Linklist h,int i,elemtype e){if(i<1){cout<<"Position error!"<<endl;exit(-1);}Lnode *p=GetElem(h,i-1);if(p){Lnode *q=new Lnode;q->data=e;//将q指针所指结点插入到p指针所指结点后面q->next=p->next;p->next=q;}else{cout<<"Position error!"<<endl;exit(-1);}}void Delete(Linklist h,int i){if(i<1){cout<<"Position error!"<<endl;exit(-1);}Lnode *p=GetElem(h,i-1);if(p==NULL||p->next==NULL){cout<<"The element is not exit!"<<endl;return;}//删除p指针所指结点的后继结点Lnode *q=p->next;p->next=q->next;e=q->data;delete q;}void Display(Linklist h){Lnode *p;p=h->next;while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;}2．利用单链表求集合的并集：设计测试文件test.cpp，其内容如下：#include "iostream.h"#include "stdio.h"typedef int elemtype;#include "LinkList.h"void unionlist(Linklist &LA,Linklist &LB,Linklist &LC){cout<<"创建表LA："<<endl;Creat(LA,5);cout<<"创建表LB："<<endl;Creat(LB,5);InitList(LC);LC=LA;Lnode *p=GetElem(LC,5);p->next=LB->next;//因为LB是带头结点的单链表，所以就得指向next域}void main(){LinkList L;Creat(h,5);Display(h);Insert(h,6,22);Display(h);elemtype e;Delete(h,3,e);cout<<e<<endl;Display(h);}3．思考：1．带头结点的单向循环链表如何实现。

目录序言 (1)中文摘要 (2)1.采用类C语言定义相关数据类型 (3)2.各模块流程图及伪码算法 (4)3.函数的调用关系图 (12)4.调试分析 (13)5.测试结果 (14)6.设计总结 (19)参考文献 (20)致谢 (21)附录（源程序） (22)序言云计算来袭，计算机技术的飞速发展，给我们的生活带来了很大的便利，特别是对于数学运算，一些以前人工计算很麻烦的甚至做不出的问题，计算机在几秒钟就可以算出来。

毫无疑问，计算机技术的应用已是不可阻挡的。

这里我们要做的是集合的简单操作，包括集合的交、并、差。

经过分析，我们使用已经为业界所公认的成熟的稳定的开发工具VC6.0，利用其提供的简单操作，首先在短时间内建立程序原形，然后，对初始原型程序需求分析，编写源程序，不断修正和改进，直到形成满足要求的可行程序。

集合的操作是数据结构中最简单的操作，对集合的学习实践可以帮助我们加深对数据结的掌握程度。

本程序是用单链表的基本操作升华到集合上的操作，来实现集合运算。

中文摘要利用单链表的插入删除操作进一步升华到求两个集合的交、并、差，笛卡尔积等运算。

在Visual C++6.0中实现程序的编译，调试，运行，利用随机数验证并输出这个程序的结果。

通过该题目的设计过程，可以进一步理解和熟练掌握课本中所学的各种数据结构的知识，加深对链表的认识，特别是对于指针、文件的应用，有了更多的认识。

学会如何把学到的知识用于解决实际问题，培养自己的动手能力。

关键词：集合；链表；指针；随机数；文件；1.采用类C语言定义相关数据类型定义单链表typedef struct ListNode{int data; //集合中元素的值struct ListNode *next;//集合的指针域}ListNode,*LinkList;//结点，结构体指针2．各模块流程图及伪码算法建立链表模块LinkList CreateSet(LinkList L) {LinkList p = L,q = NULL;//读取产生的随机数作为集合的元素 FILE *rfile;rfile = fopen("jihe.txt","rb"); if ( rfile == NULL ) { printf("open data.txt error.");return 0;Linklist p,q从文件中读取数据成功randomm()否打开文件失败把生成的随机数读取到文件中fread （）是结束}int rs = 0;int rra[20] = {0};rs = fread(rra, sizeof(int),20,rfile);for ( int j = 0 ; j < rs; j++){q = NULL;q = (LinkList)malloc(sizeof(ListNode));q->next=NULL;q->data = rra[j]; //读取元素值p->next = q;p = p->next;}//forfclose(rfile);return L;}计算集合并的函数模块//求并集LinkList Union(LinkList A,LinkList B,LinkList C) {LinkList pa, pb, pc,tail; pa = A->next; pb = B->next; tail = C; while(pa && pb) { if((pa->data) <= (pb->data)){pc = (LinkList)malloc(sizeof(ListNode)); LinkList pa, pb, pc,tail;pa!=null &&pb!=nullpa->data<=pb->datapc->data = pa->datapc->data = pb->data结束否否是是pc->data = pa->data;pc->next=tail->next;tail->next = pc;tail = pc;pc = pc->next;pa = pa->next;}//ifelse{pc = (LinkList)malloc(sizeof(ListNode));pc->data = pb->data;pc->next=tail->next;tail->next = pc;tail = pc;pc = pc->next;pb = pb->next;}//else}if(pa == NULL){pc = pb;tail->next = pc;tail = pc;}//ifelse{pc = pa;tail->next = pc;tail = pc;}//else}//whilereturn(C);}计算集合交的函数模块//求交集LinkList Intersection(LinkList A,LinkList B,LinkList L) {ListNode *pa, *pb, *pc,*tail; tail = L; pa = A->next; pb = B->next; while (pa && pb) { if (pa->data < pb->data) {pa = pa->next;LinkList pa, pb, pc,tail;pa!=null &&pb!=nullpa->data==pb->datapc->data = pa->data释放pa,pb结束否否是是}//ifelse if (pa->data > pb->data){pb = pb->next;}//else ifelse{pc = (LinkList)malloc(sizeof(ListNode));pc->data = pa->data;pc->next=tail->next;tail->next = pc;tail = pc;pc = pc->next;pa = pa->next;pb = pb->next;}//else}//whilereturn L;}计算集合1与集合2的差 的函数模块//求差集LinkList Difference(LinkList A,LinkList B,LinkList C) {LinkList pa, pb, pc; pa = A->next; pb = B->next; pc = A;while(pa && pb) { if (pa->data != pb->data) {pc->next = pa;LinkList pa, pb, pc,tail;pa!=null &&pb!=nullpa->data ！=pb->datapc->data = pa->data释放pa,pb结束否否是是pc = pa;pa = pa->next;}//ifelse{pa = pa->next;pb = pb->next;}//else}//whilereturn A;}3.函数的调用关系图main()menu_select()CreateSet CreateSet2 Difference Union Intersection PrintSet4.调试分析a.调试中遇到的问题及对问题的解决方法调试中遇到的问题中主要是内存泄露问题，指针何时分配空间何时释放空间没有搞清楚，还有随机数产生完成后不知道怎么读入到链表中，对于这些问题，我上网查阅相关的资料，来进一步的确定问题的本质，从而解决问题的每一步。

数据结构第二章习题第2章线性表一、单选题1．线性表是具有n个_________的有限序列。

a、表元素B.字符C.数据元素D.数据项2。

线性表格是。

a．一个有限序列，可以为空b．一个有限序列，不可以为空c．一个无限序列，可以为空d．一个无限序列，不可以为空3．线性表采用链表存储时，其地址_________。

a、 U4。

列表中不连续的部分必须是U4。

a．可随机访问任一结点b．插入删除不需要移动元素c．不必事先估计存储空间d．所需空间与其长度成正比5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。

a、输出I（1≤ 我≤ n） th元素值b．交换第1个元素与第2个元素的值c．顺序输出这n个元素的值d、输出与线性表中给定值x相等的元素序列号6．设线性表中有2n个元素，以下操作中，_________在单链表上实现要比在顺序表上实现效率更高。

a．删除指定的元素b、在最后一个元素后插入新元素。

C.按顺序输出前k个元素d．交换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7.如果最常见的操作是获取第i个节点及其前体，请使用___________________。

a．单链表b．双链表c、与单链表相比，双链表的优点之一是。

a．插入和删除操作更简单b．可以进行随机访问c．可以省略表头指针或表尾指针d．访问前后相邻结点更灵活9．带头结点的单链表l为空的判定条件是_________。

a、 l==nullb.l->next==nullc.l->next==ld.l！=无效的10．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_________。

a、 o（1）b.o（n）c.o（n2）d.o（nlog2n）11．在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_________操作与链表的长度有关。

linkedlist中remove方法### 单链表（LinkedList）中remove方法的探讨单链表（LinkedList）是计算机科学中一种常见的基础数据结构，它通过节点间的指针链接实现一系列元素的线性集合。

在许多编程语言中，如Java，单链表通常提供了多种操作方法，其中`remove`方法用于删除链表中的元素。

以下是对`remove`方法的具体分析。

#### remove方法的作用`remove`方法的主要目的是从单链表中删除指定的元素或满足特定条件的元素。

根据实现的不同，`remove`方法可能有以下几种变体：1.删除指定位置的元素。

2.删除链表中首次出现的特定值的元素。

3.删除所有匹配特定值的元素。

#### remove方法的实现以下是`remove`方法的一种典型实现逻辑：##### 删除指定位置的元素```javapublic E remove(int index) {// 检查索引是否有效if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}// 获取要删除的节点Node<E> x = head;for (int i = 0; i < index; i++) {x = x.next;}// 删除节点return unlink(x);}private E unlink(Node<E> x) {// 获取要删除节点的元素和前后节点final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {// 如果是头节点head = next;} else {prev.next = next;x.prev = null;}if (next == null) {// 如果是尾节点last = prev;} else {next.prev = prev;x.next = null;}x.item = null; // 清除元素，帮助GCsize--; // 链表大小减一return element;}```##### 删除特定值的元素删除特定值的元素通常需要遍历链表，找到匹配的节点后，使用上述`unlink`方法进行删除。

实验一：以单链表表示集合，设计算法建立先后输入的两个集合的差。

说明：已知两个集合A和B，集合A-B中包含所有属于集合A而不属于集合B 的元素。

步骤：1.首先建立A和B的单链表2.然后对集合B中的每个元素x，在A中查找，若存在和x相同的元素，则从该链表中删除。

3.打印A-B，进行验证。

实验二：建立一个二叉树，并进行先序和中序遍历。

（递归和非递归算法）步骤1.补充元素0建立一个满二叉树，存储到一维数组2.利用递归算法建立二叉树，注意零的元素处置3．进行递归、非递归的中序和先序遍历。

打印结果。

实验三：先从键盘输入26个字母生成无序数组，对数组排序后，再从键盘输入一个字符进行折半查找。

实验四：为一个图（maxnode＝20）建立一个邻接表、编写深度遍历和广度遍历算法并给出遍历结果。

实验一答案：#include<stdio.h>typedef struct linknode{int data;struct linknode *next;} node;node *creatlist(){node *head,*r,*s;int x;head=(node*)malloc(sizeof(node));r=head;printf("input int and end with \n");scanf("%d",&x);while(x!=0){s=(node*)malloc(sizeof(node));s->data=x;r->next=s;s->next=NULL;r=s;scanf("%d",&x);}r->next=NULL;s=head;head=head->next;free(s);return(head);}void subs(){node *p,*p1,*p2,*q,*heada,*headb;heada=creatlist();headb=creatlist();p=heada;p1=p;while(p!=NULL){q=headb;while(q->data!=p->data && q!=NULL) q=q->next; if(q!=NULL){if(p==heada){heada=heada->next;p1=heada;}else if(p->next==NULL) p1->next=NULL;else p1->next=p->next;p2=p->next;p->next=NULL;free(p);p=p2;}else{p1=p;p=p->next;}}p=heada;if(p==NULL)printf("kong\n");elseprintf(" A - B \n");while(p!=NULL){printf("%d\n",p->data);p=p->next;}}main(){subs();}实验二答案：//程序目的建立二叉树，同时对他进行先序排列。

西安建筑科技大学华清学院课程设计（论文）题目：院（系）：专业班级：计算机姓学名：号：指导教师：2016 年9 月8 日西安建筑科技大学华清学院课程设计（论文）任务书专业班级：学生姓名：指导教师（签名）：一、课程设计（论文）题目集合运算：使用链表来表示集合，完成集合的合并，求交集等操作。

二、本次课程设计（论文）应达到的目的数据结构是实践很强的课程，课程设计是加强学生实践能力的一个强有力的手段。

课程设计要求我们完成程序设计的同时能够写出比较规范的设计报告。

严格实施课程设计这一环节，对于我们基本程序素养的培养和软件工作者工作作风的训练。

将起到显著的促进作用。

本题目要达到目的：熟练掌握链表的各种操作三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）输入数据：输入10个以内的字符进行程序测试。

1、自己输入两了任意集合。

2、用对话框的形式显示集合运算的结果。

3、优化对话框。

四、应收集的资料及主要参考文献：由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“线性表”的基本操作。

参考文献：1. 数据结构-C语言描述，西安电子科技大学出版社，2011.5，耿国华编著2．数决结构与算法分析(C++版),电子工业出版社,2005.7,Clifford A.Shaffer 编著3.数据结构与算法,科学出版社,2005.08,赵文静祁飞等编著4.数据结构-C++语言描述，西安交通大学出版社，1999.01，赵文静编著5.VC++深入详解,电子工业出版社,2007.7,孙鑫,于安萍编著五、审核批准意见教研室主任（签字）设计总说明该设计主要应实现以下功能：1.利用尾差法建立单链表2.对于输入的链表进行有序排列3.删除有序链表中不符合要求的元素4.调用函数对单链表进行交，并，差运算，并输出系统主要由8 个模块组成，分别是：1. 单链表的建立2.单链表的有序排列3.删除单链表中不符合条件的元素4.集合交集5.集合并集6.集合差集7.单链表输出8.主函数1.设技种算学其的别的都过理象提的计作用3.需3.13.2可3.3用硬可误5. 概4.1数（1）（2）Check(char ch,LinkList Head)：检查p1或p2所指向数据结点该不该加入到Head为起始的集合中（2）Merge(LinkList Head1,LinkList Head2)：合并两个集合（4）IsExist(char data,LinkList Head)；IsExist2(char data,LinkList Head)：集合A中的元素，B中是否存在（5）Deprive(LinkList Head1,LinkList Head2)：两个集合的差集（6）Insection(LinkList Head1,LinkList Head2)：两个集合交集（7）PrintLinkList(LinkList Head)：打印集合元素4.2 系统包含的函数InitLinkList(LinkList Head)Check(char ch,LinkList Head)Merge(LinkList Head1,LinkList Head2)IsExist2(char data,LinkList Head)Deprive(LinkList Head1,LinkList Head2)Insection(LinkList Head1,LinkList Head2)PrintLinkList(LinkList Head)4.3 函数间的关系1.求两个集合的并集时，Merge(LinkListHead1,LinkList Head2)函数首先调用了InitLinkList(LinkList Head)函数，多次调用了Check(char ch,LinkList Head)函数。

一、题目要求：用Java语言实现单链表的基本操作，并实现集合的交、并和差运算。

二、程序功能定义：1、输出两个集合的交集，即找出两个集合的相同元素。

2、输出两个集合的并集，即把两个集合的全部元素不重复的加起来。

3、输出两个集合的差集，即从一个集合中找出另一个集合里没有的元素。

三、设计思路：程序1：单链表结点public class Node<T> //单链表结点类，T指定结点的元素类型{public T data; //数据域，保存数据元素public Node<T> next; //地址域，引用后继结点public Node(T data, Node<T> next) //构造结点，data指定数据元素，next指定后继结点{this.data = data;this.next = next;}public Node(){this(null, null);}}程序2：import java.util.ArrayList;public class SinglyList<T>{public Node<T> head;public int length;//以上为默认构造方法，构造空单链表public static ArrayList<String> union=new ArrayList<String>();public SinglyList(){this.head = new Node<T>();}//以上为构造单链表public SinglyList(T[] element){this(); //创建空单链表，只有头结点this.length = element.length;Node<T> rear = this.head; //rear指向单链表最后一个结点for (int i = 0; i < element.length; i++)//若element==null，跑出空对象异常；element.length==0时，构造空链表{rear.next = new Node<T>(element[i], null); //创建结点链入rear结点之后rear = rear.next; //rear指向性的链尾结点}}public String toString(){String str = "(";Node<T> p = this.head.next;while (p != null){str += p.data.toString();if (p.next != null){str += ",";} //不是最后一个结点时，后加分隔符p = p.next;}return str + ")"; //空表返回()}public String addAll(SinglyList list){Node<T> p = this.head.next;String str = "(";while (p != null){Node<T> q = list.head.next;while (q != null){if ( p.data.toString().equals(q.data.toString())) //集合的元素值相等{if (!str.equals("(")){str += ",";} //用逗号间隔str += p.data.toString();this.union.add(p.data.toString()) ;}q = q.next;}p = p.next;}return str + ")";}//以上为求交集过程。