实验一顺序表基本操作.docx
《实验一顺序表基本操作.docx》由会员分享，可在线阅读，更多相关《实验一顺序表基本操作.docx（16页珍藏版）》请在冰点文库上搜索。
实验一顺序表基本操作
实验一顺序表基本操作
一实验目的
1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。
2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。
3.掌握对多函数程序的输入、编辑、调试和运行过程。
二实验要求
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=A∪B。
四思考与提高
假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A∩B？
1．编写程序实现顺序表的下列基本操作：
（1）初始化顺序表La。
（2）将La置为空表。
（3）销毁La。
（4）在La中插入一个新的元素。
（5）删除La中的某一元素。
（6）在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。
（7）打印输出La中的元素值。
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineYES1
#defineNO0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
Statuscmp（ElemTypea,ElemTypeb）
{
if（a==b）
returnYES;
else
returnNO;
}
//构造空的顺序表La
StatusInitList_Sq（SqList&L）
{
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
//撤销线性表L；
StatusDestroy_Sq（SqList&L）
{
free（L.elem）;
L.elem=NULL;
L.length=0;
L.listsize=0;
returnOK;
}
//清空线性表
StatusClearList_Sq（SqList&L）
{
L.length=0;//memset（L,0,sizeof（L））;
returnOK;
}
//在顺序线性表L的第i个元素之前插入新的元素e
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{
ElemType*p;
if（i<1||i>L.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.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）*（p+1）=*p;
*q=e;
++L.length;
returnOK;
}
//在顺序线性表L中删除第i个元素，并用e返回其值
StatusListDelete_Sq（SqList&L,inti,ElemType&e）
{
ElemType*p,*q;
if（i<1||i>L.length）returnERROR;
p=&（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）*（p-1）=*p;
--L.length;
returnOK;
}//ListDelete_Sq
StatusLocateElem_Sq（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType））
{//在顺序线性表L中查找第1个值与e满足compare（）的元素的位序
inti;
ElemType*p;
i=1;
p=L.elem;
while（i<=L.length&&!
（*compare）（*p++,e））
++i;
if（i<=L.length）returni;
elsereturn0;
}
//打印顺序表
voidPrintList_Sq（SqListL）
{
inti;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
}
intmain（）
{
SqListLa;
inti,n,e;
printf（"请输入元素个数：
\n"）;
scanf（"%d",&n）;
if（InitList_Sq（La））
{
for（i=1;i<=n;i++）
{
printf（"请输入第%d个元素\n",i）;
scanf（"%d",&e）;
ListInsert_Sq（La,i,e）;
}
printf（"-------------------------------------\n你输入的元素分别为：
\n"）;
PrintList_Sq（La）;
printf（"-------------------------------------\n"）;
}
else
{
printf（"初始化线性表出错！
\n"）;
printf（"-------------------------------------\n"）;
}
printf（"请输入你要插入的元素及插入的位置：
\n"）;//插入元素
scanf（"%d%d",&e,&i）;
if（ListInsert_Sq（La,i,e））
{
printf（"插入元素后线性表为：
\n"）;
PrintList_Sq（La）;
printf（"-------------------------------------\n"）;
}
else
{
printf（"输入位置有错！
\n"）;
printf（"-------------------------------------\n"）;
}/**/
printf（"请输入你要删除的元素的位置：
\n"）;//删除元素
scanf（"%d",&i）;
if（ListDelete_Sq（La,i,e））
{
printf（"你删除的元素为：
%d,删除元素后线性表为：
\n",e）;
PrintList_Sq（La）;
printf（"-------------------------------------\n"）;
}
else
{
printf（"输入位置有错！
\n"）;
printf（"-------------------------------------\n"）;
}
printf（"请输入你要查找的元素：
\n"）;//查找元素
scanf（"%d",&e）;
if（i=LocateElem_Sq（La,e,cmp））
{
printf（"你要查找的元素在第%d个位置。
\n",i）;
printf（"-------------------------------------\n"）;
}
else
{
printf（"找不到这个元素：
\n"）;
printf（"-------------------------------------\n"）;
}
if（ClearList_Sq（La））//清空线性表
{
printf（"线性表已清空。
\n"）;
printf（"--------------------------------------\n"）;
}
else
{
printf（"线性表清空出错。
\n"）;
printf（"--------------------------------------\n"）;
}
if（Destroy_Sq（La））//撤销线性表
{
printf（"线性表已撤销。
\n"）;
printf（"--------------------------------------\n"）;
}
else
{
printf（"线性表清空出错。
\n"）;
printf（"--------------------------------------\n"）;
}
return0;
}
2．编写程序完成下面的操作：
（1）构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。
（2）实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。
（3）假设两个顺序线性表La和Lb分别表示两个集合A和B，利用
union_Sq操作实现A=A∪B。
#include
#include
#defineTRUE1
#defineFALSE0
#defineYES1
#defineNO0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
#defineLIST_INIT_SIZE100
#defineLISTINCERMENT10
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
StatusInitList_Sq（SqList&L）
{//构造空的顺序表La
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
/**/
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{//在顺序线性表L的第i个元素之前插入新的元素e
ElemType*p;
if（i<1||i>L.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.elem[i-1]）;
for（p=&（L.elem[L.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（i<1||i>L.length）returnERROR;
p=&（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）*（p-1）=*p;
--L.length;
returnOK;
}//ListDelete_Sq
Statuscmp（ElemTypea,ElemTypeb）
{
if（a==b）
returnYES;
else
returnNO;
}
StatusLocateElem_Sq（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType））
{//在顺序线性表L中查找第1个值与e满足compare（）的元素的位序
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的剩余元素
}//MergeList
voidUnion_Sq（SqList&La,SqListLb）
{
intlen1=La.length;
intlen2=Lb.length;
inti,pl;ElemTypee;//
for（i=1;i<=len2;i++）
{
pl=LocateElem_Sq（La,Lb.elem[i-1],cmp）;
if（pl==0）
{
ListInsert_Sq（La,++len1,Lb.elem[i-1]）;
}
}
len1=La.length;
for（i=0;i{
if（La.elem[i]==La.elem[i+1]）
ListDelete_Sq（La,i+2,e）;
}/*注意在原来La中，如果有重复也要删除到只剩下一个*/
}
voidPrintList_Sq（SqListL）
{
inti;
for（i=0;iprintf（"%d",L.elem[i]）;
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++）
{
printf（"请输入La的第%d个元素！
\n",i）;
scanf（"%d",&e）;
ListInsert_Sq（La,i,e）;
}
//printf（"-------------------------------------\nLa的元素分别为：
\n"）;
//PrintList_Sq（La）;
printf（"-------------------------------------\n"）;
}
else
{
printf（"初始化线性表出错！
\n"）;
printf（"-------------------------------------\n"）;
}
printf（"请输入Lb元素个数：
\n"）;
scanf（"%d",&n2）;
if（InitList_Sq（Lb））
{
for（i=1;i<=n2;i++）
{
printf（"请输入Lb的第%d个元素！
\n",i）;
scanf（"%d",&e）;
ListInsert_Sq（Lb,i,e）;
}
//printf（"-------------------------------------\nLb的元素分别为：
\n"）;
//PrintList_Sq（Lb）;
printf（"-------------------------------------\n"）;
}
else
{
printf（"初始化线性表出错！
\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;
}
升级会员 