基于單鏈表實現(xiàn)集合的并交差運算實驗報告

1、基于單鏈表實現(xiàn)集合的并交差運算實驗報告一 實驗題目: 基于單鏈表實現(xiàn)集合的并交差運算二 實驗要求: 2.2:編寫一個程序，實現(xiàn)順序表的各種基本運算(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:編寫一個程序，采用單鏈表表示集合(集合中不存在重復的元素),并將其按照遞增的方式排序，構(gòu)成有序單鏈表，并求這樣的兩個集合的并

2、,交和差。三 實驗內(nèi)容:3.1 線性表的抽象數(shù)據(jù)類型:ADT List數(shù)據(jù)對象;D=數(shù)據(jù)關(guān)系:R1=基本操作：InitList(&L)操作結(jié)果;構(gòu)造一個空的線性表LDestroyList(&L)初始條件：線性表L已存在操作結(jié)果：銷毀線性表LClearList(&L)初始條件：線性表L已存在操作結(jié)果：將L置為空表ListEmpty(L)初始條件：線性表已存在操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSEListLength(L)初始條件：線性表已存在操作結(jié)果：返回L中數(shù)據(jù)元素的個數(shù)GetElem(L,i)初始條件:線性表已存在，1<=i<=ListL

3、ength(L)操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值LocateElem(L,i,e)初始條件：線性表已存在，用循環(huán)遍歷整個線性表，如果e與線性表中的元素相同；操作結(jié)果：用此時的i+1返回該元素在線性表的位序ListInsert(&L,i,e)初始條件：線性表存在，1<=i<=ListLength(L)+1;操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素,e,L的長度加1。ListDelete(&L,i,&e)初始條件:線性表L已存在且非空，1<=i<=ListLength(L)；操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1

4、ADT List3.2存儲結(jié)構(gòu)的定義;typedef char ElemType;typedef struct LNode ElemType data; struct LNode *next;LinkList;3.3基本操作實現(xiàn):/* 單鏈表的初始化 */void InitList(LinkList *&L) L = (LinkList *)malloc(sizeof(LinkList); L->next=NULL;/* 向單鏈表中插入數(shù)據(jù)元素 */bool ListInsert(LinkList *&L,int x,char e) int j = 0; LinkList

5、 *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("

6、;%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;/* 求單鏈表中某個數(shù)據(jù)元素值 */bool GetElem(LinkList *L,int i, E

7、lemType &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

8、(p=NULL) return 0; 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

9、->next; free(q); return true; /* 刪除單鏈表 */void DestroyList(LinkList *&L) LinkList *p = L; LinkList *q = p->next; while(q!=NULL) free(p); p = q; q = p->next; free(p);3.4解題思路：1. 先通過CreateListR 函數(shù)將集合 a 和 b 中的元素添加到順序表 ha 和 hb 中 ，添加過程使用的是順序表原有的Initlist 函數(shù)（初始化表） 和 ListInsert 函數(shù) （向表中插入元素） 。2. 因

10、為原集合是無序的， 所以我通過 sort 函數(shù) （選擇排序），使得集合變得有序。3. 得到有序集合 ha 和 hb 后， 便可以使用 Union 函數(shù)（類似歸并的思想寫出來的求并集的函數(shù)），求出 ha 和 hb 的并集。4. 而求交集的方法則是， 通過將 集合 a 中的元素一個一個取出，并通過 函數(shù)LocateElem ，查看集合 hb 中是否存在該元素，如果存在則將 元素放入 hc ，如果不存在，則舍去。 以此求得 兩 集合的交集。5. 求兩集合的差 則可以反過來，同樣通過將 集合 a 中的元素一個一個取出，并通過 函數(shù)LocateElem ，查看集合 hb 中是否存在該元素，如果不存在則將

11、 元素放入 hc ，如果存在，則舍去。 以此求得兩集合的差集。（ 單鏈表求交并差集合的思想和順序表求交并差集合的思想基本相同 ）3.5解題過程：實驗源代碼如下：3.5.1單鏈表的各種運算#include <iostream>#include <cstdio>#include <malloc.h>using namespace std;/* 定義單鏈表數(shù)據(jù) */typedef char ElemType;typedef struct LNode ElemType data; struct LNode *next;LinkList;/* 單鏈表的初始化 */vo

12、id InitList(LinkList *&L) L = (LinkList *)malloc(sizeof(LinkList); L->next=NULL;/* 向單鏈表中插入數(shù)據(jù)元素 */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(Li

13、nkList); 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; in

14、t i = 0; while(p!=NULL) i+; p = p->next; return i;/* 查看單鏈表是否為空 */bool ListEmpty(LinkList *L) return L->next=NULL;/* 求單鏈表中某個數(shù)據(jù)元素值 */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 =

15、 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) return 0; else return i; /* 刪除單鏈表中第 i 個元素*/bool ListDelete(LinkList *&L,int i,ElemType &e) int j = 0; LinkList *p

16、 = 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!

17、=NULL) free(p); p = q; q = p->next; free(p);int main( ) LinkList *h; ElemType e; printf("單鏈表的基本運算如下：n"); printf("（1）初始化單鏈表n"); InitList(h); printf("（2）依次采用尾插法插入 a，b，c，d，e 元素n"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); Li

18、stInsert(h,4,'d'); ListInsert(h,5,'e'); printf("（3）輸出單鏈表："); DispList(h); printf("（4）單鏈表h的長度 = %dn",ListLength(h); printf("（5）單鏈表h為%sn",(ListEmpty(h)?"空":"非空"); GetElem(h,3,e); printf("（6）單鏈表h的第3個元素 = %cn",e); printf("（

19、7）元素a的位置 = %dn",LocateElem(h,'a'); printf("（8）在第4個元素位置上插入f元素n"); ListInsert(h,4,'f'); printf("（9）輸出單鏈表h："); DispList(h); printf("（10）刪除h的第3個元素n"); ListDelete(h,3,e); printf("（11）輸出單鏈表h："); DispList(h); printf("（12）釋放單鏈表hn"); Dest

20、royList(h); return 0;3.5.2求集合的并交差#include <iostream>#include <cstdio>#include <malloc.h>using namespace std;/* 定義單鏈表數(shù)據(jù) */typedef char ElemType;typedef struct LNode ElemType data; struct LNode *next;LinkList;/* 單鏈表的初始化 */void InitList(LinkList *&L) L = (LinkList *)malloc(sizeof(

21、LinkList); L->next=NULL;/* 向單鏈表中插入數(shù)據(jù)元素 */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

22、 = 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;/* 查看單

23、鏈表是否為空 */bool ListEmpty(LinkList *L) return L->next=NULL;/* 求單鏈表中某個數(shù)據(jù)元素值 */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(Lin

24、kList *L,ElemType e) LinkList *p = L; int i = 0; while(p!=NULL && p->data!=e) p = p->next; i+; if(p=NULL) return 0; 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->

25、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) free(p); p = q; q = p->next; free(p);void CreateL

26、istR(LinkList *&L,ElemType e,int n) InitList(L); int i; for(i = 0;i < n; +i) if(!LocateElem(L,ei) ListInsert(L,i+1,ei); 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) ListIn

27、sert(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) I

28、nitList(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; k+; /cout<<"hehe"<<endl;void sort(LinkList *&L) L