数据结构第一次上机实验报告

数据结构第一次上机实验报告

一 实验题目: 基于顺序表实现集合的并，交，差运算

二 实验要求:

2.1:编写一个程序，实现顺序表的各种基本运算

(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={ai|ai?ElemSet,i?1,2,...,n,n?0} 数据关系:R1={?ai?1,ai?|ai?1,ai?D,i?2,...,n} 基本操作： 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存储结构的定义;

#define LIST_INIT_SIZE 100 #define LISTINCREEMENT 10 typedef char ElemType; typedef struct {

ElemType data[Maxsize]; int length; }SqList;

3.3基本操作实现:

void InitList(SqList *&L)//初始化顺序表 {

L = (SqList *)malloc(sizeof(SqList));//用malloc动态申请一个顺序表的内存空间

L->length = 0; }

void DestroyList(SqList *L) {

free(L);//释放指针L }

bool ListEmpty(SqList *L) {

return (L->length == 0);//length为0表示表空 }

int ListLength(SqList *L) {

return (L->length);

}

void DispList(SqList *L) {

int i;

if(ListEmpty(L)) return ; for(i = 0;i < L->length;i++) {

printf(\ printf(\ } }

bool GetElem(SqList *L,int i,ElemType &e) {

if(i < 1||i > L->length) return false; e = L->data[i-1]; return true; }

int LocateElem(SqList *L,ElemType e) {

int i = 0;

while(i < L->length&&L->data[i]!=e) {

i++; }

if(i >= L->length) return 0; else return i+1; }

bool ListInsert(SqList *&L,int i,ElemType e) {

int j;

if(i < 1||i>L->length+1) return false; i--;

for(j=L->length;j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++; return true; }

bool ListDelete(SqList *&L,int i,ElemType &e) {

int j;

if(i<1||i>L->length) return false; i--;

e = L->data[i];

for(j = i;jlength-1;j++) L->data[j]=L->data[j+1]; L->length--; return true; }

3.4解题思路：

1 首先分别用2个顺序表存储集合A,B中的元素

2 开始集合A，B是无序的，然后用个sort函数（冒泡排序算法）分别对顺序表进行按照从小到大排序，输出有序的集合A,B;

3 在2步骤的基础上，再定义一个线性表C,分别在线性表A，B中去取出一个值，若两个值相等则将其中一个插入线性表C中

若不相等则将其中小的值先插入C中，接着将大的值插入C中，如此循环，直至线性表A,B中有一个遍历完了，把没有遍历完的全部插入线性表C; 那么求集合的并集就完成了。

4 在2步骤的基础上，再定义一个线性表C,分别在线性表A，B中去取出一个值，若两个值相等则将其中一个插入线性表C中,若不相等，

则进行下一个元素的比较；如此循环，最终线性表C中就是集合A,B的交集。 5 在2的步骤的基础上，再定义一个线性表C,分别在线性表A，B中去取出一个值，以A顺序表为基准，

将顺序表A中取出的每一个值都去与顺序表B中的每一个值作比较若不相等，则将A中取出的值插入顺序表C中，若相等则取A中下一个元素，直至A中的值 取完为止，那么最终C中元素就是集合A与集合B的差集。 3.5解题过程： 实验源代码如下： # include # include const int Maxsize=50;

typedef char ElemType;//ElemType 是个虚拟类型 typedef struct {

ElemType data[Maxsize]; int length; }SqList;

void InitList(SqList *&L)//初始化顺序表 {

L = (SqList *)malloc(sizeof(SqList));//用malloc动态申请一个顺序表的内存空间

L->length = 0; }

void DestroyList(SqList *L)//销毁顺序表 {

free(L);//释放指针L }

bool ListEmpty(SqList *L)//判定顺序表是否为空 {

return (L->length == 0);//length为0表示表空 }

int ListLength(SqList *L)//返回顺序表的长度 {

return (L->length); }

void DispList(SqList *L)//输出顺序表 {

int i;

if(ListEmpty(L)) return ; for(i = 0;i < L->length;i++) {

printf(\

}

printf(\}

bool GetElem(SqList *L,int i,ElemType &e)//获取顺序表中的一个值 {

if(i < 1||i > L->length) return false; e = L->data[i-1]; return true; }

int LocateElem(SqList *L,ElemType e)//获取顺序表中值的位序 {

int i = 0;

while(i < L->length&&L->data[i]!=e) {

i++; }

if(i >= L->length) return 0; else return i+1; }

bool ListInsert(SqList *&L,int i,ElemType e)//向顺序表中插入一个元素 {

int j;

if(i < 1||i>L->length+1) return false; i--;

for(j=L->length;j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++;

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教育文库数据结构第一次上机实验报告 全文阅读和word下载服务。