基于单链表实现集合的并交差运算实验浅析.doc

基于单链表实现集合的并交差运算实验报告 一 实验题目: 基于单链表实现集合的并交差运算 二 实验要求: 2.2:编写一个程序，实现顺序表的各种基本运算 (1)初始化单链表h； (2)依次采用尾插法插入a,b,c,d,e元素; (3)输出单链表h (4)输出单链表h的长度 判断单链表h是否为空 输出单链表h的第三个元素 输出元素在a的位置 在第4个元素位置上插入f元素 输出单链表h 删除L的第3个元素 输出单链表 释放单链表 2.2:编写一个程序，采用单链表表示集合(集合中不存在重复的元素),并将其按照递增的方式排序，构成有序单链表，并求这样的两个集合的并,交和差。 三 实验内容: 3.1 线性表的抽象数据类型: ADT List{ 数据对象;D= 数据关系:R1= 基本操作： InitList(L) 操作结果;构造一个空的线性表L DestroyList(L) 初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(L) 初始条件：线性表L已存在 操作结果：将L置为空表 ListEmpty(L) 初始条件：线性表已存在 操作结果：若L为空表，则返回TRUE，否则返回FALSE ListLength(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。 ListDelete(L,i,e) 初始条件:线性表L已存在且非空，1=i=ListLength(L)； 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 }ADT List 3.2存储结构的定义; typedef char ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LinkList; 3.3基本操作实现: /* 单链表的初始化 */ 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 jx-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) { i++; 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 =