数据结构实验报告-顺序表基本操作.pdf

数据结构实验报告-顺序表基本操作.pdf

《数据结构实验报告-顺序表基本操作.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告-顺序表基本操作.pdf（12页珍藏版）》请在冰点文库上搜索。

-1-实验报告1课程数据结构实验名称顺序表基本操作第页专业计算机科学与技术班级__学号__姓名实验日期：

2010年9月8日评分一、实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。

2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。

二、实验要求1预习C语言中结构体的定义与基本操作方法。

2对顺序表的每个基本操作用单独的函数实现。

3编写完整程序完成下面的实验内容并上机运行。

4整理并上交实验报告。

三、实验内容1编写程序实现顺序表的下列基本操作：

编写程序实现顺序表的下列基本操作：

（1）初始化顺序表La。

（2）将La置为空表。

（3）销毁La。

（4）在La中插入一个新的元素。

（5）删除La中的某一元素。

（6）在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。

（7）打印输出La中的元素值。

2编写程序编写程序完成下面的操作：

完成下面的操作：

（1）构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。

（2）实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。

（3）假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=AB。

四、实验步骤一一1.编写头文件。

定义数据类型。

分别写各个函数如ListInsern_Sq，ListDelete_Sq，LocateElem等函数。

2.编写主函数。

在主函数里构造空的线性表，然后利用ListInsert函数使用户初始化线性表。

然后调用函数操作，操作结果用PrintList_Sq打印出线性表的内容3.运行程序，完整代码见下：

-2-/datastruct实验一线性表基本操作1#include#include/#include/usingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineYES1#defineNO0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize;SqList;Statuscmp（ElemTypea,ElemTypeb）if（a=b）returnYES;elsereturnNO;StatusInitList_Sq（SqList&L）/构造空的顺序表LaL.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType）;if（!

L.elem）exit（OVERFLOW）;L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;StatusDestroy_Sq（SqList&L）/撤销线性表L；free（L.elem）;L.elem=NULL;L.length=0;L.listsize=0;-3-returnOK;StatusClearList_Sq（SqList&L）/清空线性表L.length=0;/memset（L,0,sizeof（L）;returnOK;StatusListInsert_Sq（SqList&L,inti,ElemTypee）/在顺序线性表L的第i个元素之前插入新的元素eElemType*p;if（iL.length+1）returnERROR;if（L.length=L.listsize）ElemType*newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType）;if（!

newbase）returnERROR;L.elem=newbase;L.listsize+=LISTINCREMENT;ElemType*q=&（L.elemi-1）;for（p=&（L.elemL.length-1）;p=q;-p）*（p+1）=*p;*q=e;+L.length;returnOK;StatusListDelete_Sq（SqList&L,inti,ElemType&e）/在顺序线性表L中删除第i个元素，并用e返回其值ElemType*p,*q;if（iL.length）returnERROR;p=&（L.elemi-1）;e=*p;q=L.elem+L.length-1;for（+p;p=q;+p）*（p-1）=*p;-L.length;returnOK;/ListDelete_SqStatusLocateElem_Sq（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType）/在顺序线性表L中查找第1个值与e满足compare（）的元素的位序inti;ElemType*p;i=1;p=L.elem;-4-while（i=L.length&!

（*compare）（*p+,e）+i;if（i=L.length）returni;elsereturn0;voidPrintList_Sq（SqListL）inti;for（i=0;iL.length;i+）printf（%d,L.elemi）;printf（n）;intmain（）SqListLa;inti,n,e;printf（请输入元素个数：

n）;scanf（%d,&n）;if（InitList_Sq（La）for（i=1;i=n;i+）scanf（%d,&e）;ListInsert_Sq（La,i,e）;printf（-n你输入的元素分别为：

n）;PrintList_Sq（La）;printf（-n）;elseprintf（初始化线性表出错！

n）;printf（-n）;printf（请输入你要插入的元素及插入的位置：

n）;/插入元素scanf（%d%d,&e,&i）;if（ListInsert_Sq（La,i,e）printf（插入元素后线性表为：

n）;PrintList_Sq（La）;printf（-n）;-5-elseprintf（输入位置有错！

n）;printf（-n）;/*/printf（请输入你要删除的元素的位置：

n）;/删除元素scanf（%d,&i）;if（ListDelete_Sq（La,i,e）printf（你删除的元素为：

%d,删除元素后线性表为：

n,e）;PrintList_Sq（La）;printf（-n）;elseprintf（输入位置有错！

n）;printf（-n）;printf（请输入你要查找的元素：

n）;/查找元素scanf（%d,&e）;if（i=LocateElem_Sq（La,e,cmp）printf（你要查找的元素在第%d个位置。

n,i）;printf（-n）;elseprintf（找不到这个元素：

n）;printf（-n）;if（ClearList_Sq（La）/清空线性表printf（线性表已清空。

n）;printf（-n）;elseprintf（线性表清空出错。

n）;printf（-n）;if（Destroy_Sq（La）/撤销线性表-6-printf（线性表已撤销。

n）;printf（-n）;elseprintf（线性表清空出错。

n）;printf（-n）;return0;二二1.编写头文件。

定义数据类型。

分别写需要用到的函数。

在Union_Sq里需要用的函数有ListInsert_Sq和ListDelete_Sq和LocateElem_Sq函数，所以这三个函数需要编写。

同样设有PrintList_Sq函数来打印操作结果。

2.编写主函数分别使用户输入La与Lb的各个元素值，操作后用PrintList_Sq输出操作结果。

3.运行程序，完整代码见下。

/datastruct实验一线性表基本操作2#include#include#defineTRUE1#defineFALSE0#defineYES1#defineNO0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;#defineLIST_INIT_SIZE100#defineLISTINCERMENT10typedefstructElemType*elem;intlength;intlistsize;SqList;StatusInitList_Sq（SqList&L）/构造空的顺序表LaL.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType）;if（!

L.elem）exit（OVERFLOW）;-7-L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;/*/StatusListInsert_Sq（SqList&L,inti,ElemTypee）/在顺序线性表L的第i个元素之前插入新的元素eElemType*p;if（iL.length+1）returnERROR;if（L.length=L.listsize）ElemType*newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCERMENT）*sizeof（ElemType）;if（!

newbase）returnERROR;L.elem=newbase;L.listsize+=LISTINCERMENT;ElemType*q=&（L.elemi-1）;for（p=&（L.elemL.length-1）;p=q;-p）*（p+1）=*p;*q=e;+L.length;returnOK;StatusListDelete_Sq（SqList&L,inti,ElemType&e）/在顺序线性表L中删除第i个元素，并用e返回其值ElemType*p,*q;if（iL.length）returnERROR;p=&（L.elemi-1）;e=*p;q=L.elem+L.length-1;for（+p;p=q;+p）*（p-1）=*p;-L.length;returnOK;/ListDelete_SqStatuscmp（ElemTypea,ElemTypeb）if（a=b）returnYES;elsereturnNO;StatusLocateElem_Sq（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType）/在顺序线性表L中查找第1个值与e满足compare（）的元素的位序-8-inti;ElemType*p;i=1;p=L.elem;while（i=L.length&!

（*compare）（*p+,e）+i;if（i=L.length）returni;elsereturn0;voidMergeList_Sq（SqListLa,SqListLb,SqList&Lc）/已知顺序线性表La和Lb的元素按值非递减排列。

归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。

ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=（ElemType*）malloc（Lc.listsize*sizeof（ElemType）;if（!

Lc.elem）exit（OVERFLOW）;/存储分配失败pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while（pa=pa_last&pb=pb_last）/归并if（*pa=*pb）*pc+=*pa+;else*pc+=*pb+;while（pa=pa_last）*pc+=*pa+;/插入La的剩余元素while（pb=pb_last）*pc+=*pb+;/插入Lb的剩余元素/MergeListvoidUnion_Sq（SqList&La,SqListLb）intlen1=La.length;intlen2=Lb.length;inti,pl;ElemTypee;/for（i=1;i=len2;i+）pl=LocateElem_Sq（La,Lb.elemi-1,cmp）;if（pl=0）ListInsert_Sq（La,+len1,Lb.elemi-1）;len1=La.length;for（i=0;ilen1;i+）-9-if（La.elemi=La.elemi+1）ListDelete_Sq（La,i+2,e）;/*注意在原来注意在原来La中，如果有重复也要删除到只剩下一个中，如果有重复也要删除到只剩下一个*/voidPrintList_Sq（SqListL）inti;for（i=0;iL.length;i+）printf（%d,L.elemi）;printf（n）;intmain（）SqListLa,Lb,Lc;inti,n1,n2,e;printf（请输入La元素个数：

n）;scanf（%d,&n1）;if（InitList_Sq（La）for（i=1;i=n1;i+）scanf（%d,&e）;ListInsert_Sq（La,i,e）;/printf（-nLa的元素分别为：

n）;/PrintList_Sq（La）;printf（-n）;elseprintf（初始化线性表出错！

n）;printf（-n）;printf（请输入Lb元素个数：

n）;scanf（%d,&n2）;if（InitList_Sq（Lb）for（i=1;i=n2;i+）-10-scanf（%d,&e）;ListInsert_Sq（Lb,i,e）;/printf（-nLb的元素分别为：

n）;/PrintList_Sq（Lb）;printf（-n）;elseprintf（初始化线性表出错！

n）;printf（-n）;printf（La与Lb合并后按非递减顺序排列得到Lc如下:

n）;MergeList_Sq（La,Lb,Lc）;PrintList_Sq（Lc）;printf（-n）;printf（La与Lb的并集如下：

n）;Union_Sq（La,Lb）;PrintList_Sq（La）;printf（-n）;return0;五、实验结果与讨论一：

运行结果1：

输入都合法-11-运行结果2：

输入不合法二：

运行结果：

-12-六、总结1.函数指针的使用：

定义函数，写函数代码。

函数头，是一个函数指针，值向调用的函数，这个调用的函数即为主函数中的上面一段的意思即：

在主函数中调用这个LocateElem_Sq函数，然后其中就是的*compare指向cmp这个函数的入口，所以compare=cmp，LocateElem_Sq函数中将调用cmp函数。

2.使用malloc函数需要包含一个头文件#include3.用TypedefintElemType之后，定义数据类型直接用ElemType，这样需要改变数据类型是只需改变Typedef*ElemType即可，*为需要改变为什么类型的数据。

4.疑问：

疑问：

在写ClearList_Sq函数时，直接使用memset函数会出错。

出错时提示，数据类型不一致。

七、思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=AB？

答：

对于每一个Lb中的元素利用LocateElem_Sq查找在La中是否有，有则返回该元素在La中的位置，然后用ListDelete_Sq删除该元素。

同时删除A中其他相同的元素。