C语言数据结构线性表的基本操作实验报告.docx
《C语言数据结构线性表的基本操作实验报告.docx》由会员分享，可在线阅读，更多相关《C语言数据结构线性表的基本操作实验报告.docx（42页珍藏版）》请在冰点文库上搜索。
C语言数据结构线性表的基本操作实验报告
C语言数据结构线性表的基本操作实验报告
实验一线性表的基本操作
一、实验目的与基本要求
1．掌握数据结构中的一些基本概念。
数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。
2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。
3．掌握顺序表和链表的基本操作：
插入、删除、查找以及表的合并等运算。
4．掌握运用C语言上机调试线性表的基本方法。
二、实验条件
1．硬件：
一台微机
2．软件：
操作系统和C语言系统
三、实验方法
确定存储结构后，上机调试实现线性表的基本运算。
四、实验内容
1．建立顺序表，基本操作包括：
初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。
2．建立单链表，基本操作包括：
初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。
3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。
编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。
（可以利用将B中元素插入A中，或新建C表）
4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。
编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。
五、附源程序及算法程序流程图
1.源程序
（1）源程序（实验要求1和3）
#include
#include
#include
#defineLIST_INIT_SIZE100
case2:
ListEmpty（&La）;break;
case3:
printf（"请输入插入的位序:
\n"）;
scanf（"%d",&m）;
printf（"请出入要插入的数:
\n"）;
scanf（"%d",&x）;
ListInsert（&La,m,x）;break;
case4:
printf（"请输入删除元素的位序:
\n"）;
scanf（"%d",&m）;
ListDelete（&La,m,x）;
printf（"删除的元素为:
%d\n",x）;break;
case5:
printf（"请输入要找的与线性表中相等的数:
\n"）;
scanf（"%d",&m）;
LocateElem（&La,m）;break;
case6:
printf（"请输入查找的位序:
\n"）;
scanf（"%d",&m）;
GetList（&La,m,x）;
printf（"La中第%d个元素的值为%d\n",m,x）;break;
case7:
ShowList（&La）;break;
case8:
InitList（&Lb）;break;
case9:
MergeList_L（&La,&Lb）;
printf（"归并成功!
"）;break;
}
menu（）;
scanf（"%d",&n）;
}
}
/*菜单*/
voidmenu（）
{
printf（"********************\n\n"）;
printf（"0.退出\n\n"）;
printf（"1.创建线性表La\n\n"）;
printf（"2.判断La是否为空表\n\n"）;
printf（"3.插入元素（La）\n\n"）;
printf（"4.删除元素（La）\n\n"）;
printf（"5.定位元素（La）\n\n"）;
printf（"6.取元素（La）\n\n"）;
printf（"7.输出线性表\n\n"）;
printf（"8.创建线性表Lb\n\n"）;
printf（"9.归并为一个线性表La\n\n"）;
printf（"********************\n\n"）;
}
/*创建顺序线性表L*/
voidInitList（Sqlist*L）
{
intn;
inti=0;
L->elem=（int*）malloc（LIST_INIT_SIZE*sizeof（int））;
if（NULL==L->elem）
printf（"储存分配失败!
\n"）;
else
{
L->length=0;
L->listsize=LIST_INIT_SIZE;
printf（"输入顺序表a:
\n"）;
scanf（"%d",&n）;
while（n）
{
L->elem[i]=n;
i++;
L->length++;
L->listsize=L->listsize-4;
scanf（"%d",&n）;
}
}
}
/*输出顺序线性表*/
voidShowList（Sqlist*p）
{
inti;
if（0==p->length）
printf（"数组为空!
\n"）;
else
for（i=0;ilength;i++）
printf（"%d",p->elem[i]）;
printf（"\n"）;
}
/*判断L是否为空表*/
voidListEmpty（Sqlist*p）
{
if（0==p->length）
printf（"L是空表!
\n"）;
else
printf（"L不是空表!
\n"）;
}
/*在顺序线性表中第i个元素前插入新元素e*/
voidListInsert（Sqlist*p,inti,inte）
{
int*newbase;
int*q1;
int*q2;
while（i<1||i>p->length+1）
{
printf（"您输入的i超出范围!
\n请重新输入要插入的位置\n:
"）;
scanf（"%d",&i）;
}
if（p->length>=p->listsize）
{
newbase=（int*）realloc（p->elem,（p->listsize+LISTINCREMENT）*sizeof（int））;
if（!
newbase）
exit（0）;
else
{
p->elem=newbase;
p->listsize+=LISTINCREMENT;
}
}
q1=&（p->elem[i-1]）;
for（q2=&（p->elem[p->length-1]）;q2>=q1;--q2）
*（q2+1）=*q2;
*q1=e;
++p->length;
}
/*/在顺序线性表中删除第i个元素，并用e返回其值*/
voidListDelete（Sqlist*p,inti,int&e）
{
int*q1,*q2;
while（i<1||i>p->length）
{
printf（"您输入的i超出范围!
请重新输入:
"）;
scanf（"%d",&i）;
}
q1=&（p->elem[i-1]）;
e=*q1;
q2=p->elem+p->length-1;
for（++q1;q1<=q2;++q1）
*（q1-1）=*q1;
--p->length;
}
/*对比a与b相等*/
boolcompare（inta,intb）
{
if（a==b）
return1;
else
return0;
}
/*在顺序线性表L中查找第1个值与e满足compare（）d元素的位序*/
voidLocateElem（Sqlist*L,inte）
{
inti=1;
int*p;
p=L->elem;
while（i<=L->length&&!
compare（*p++,e））
++i;
if（i<=L->length）
printf（"第1个与e相等的元素的位序为%d\n",i）;
else
printf（"没有该元素!
\n"）;
}
/*用e返回L中第i个数据元素的值*/
voidGetList（Sqlist*p,inti,int&e）
{
Sqlist*p1;
p1=p;
e=p1->elem[i-1];
}
/*已知顺序线性表La和Lb是元素按值非递减排列*/
/*把La和Lb归并到La上,La的元素也是按值非递减*/
voidMergeList_L（Sqlist*La,Sqlist*Lb）
{
inti=0,j=0,k,t;
int*newbase;
Sqlist*pa,*pb;
pa=La;
pb=Lb;
while（ilength&&jlength）
{
if（pa->elem[i]>=pb->elem[j]）
{
if（pa->listsize==0）
{
newbase=（int*）realloc（pa->elem,（pa->listsize+LISTINCREMENT）*sizeof（int））;
if（!
newbase）
exit（0）;
}
for（k=pa->length-1;k>=i;k--）
pa->elem[k+1]=pa->elem[k];
pa->length++;
pa->elem[i]=pb->elem[j];
i++;
j++;
}
else
i++;
}
while（jlength）
{
if（pa->listsizelength-j）
{
newbase=（int*）realloc（pa->elem,（pa->listsize+LISTINCREMENT）*sizeof（int））;
if（!
newbase）
exit（0）;
}
for（j;jlength;j++,i++）
{
pa->elem[i]=pb->elem[j];
pa->length++;
}
}
for（i=0;ilength/2;i++）
{
t=pa->elem[i];
pa->elem[i]=pa->elem[pa->length-i-1];
pa->elem[pa->length-i-1]=t;
}
}
（2）源程序（实验要求2和4）
#include
#include
#include
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
voidmenu（）;
LinkListInitList（）;
voidShowList（LinkListL）;
voidListDelete（LinkListL,inti,int&e）;
voidListEmpty（LinkListL）;
voidGetList（LinkListL,inti,int&e）;
voidListInsert（LinkListL,inti,inte）;
boolcompare（inta,intb）;
voidLocateElem（LinkListL,inte）;
LinkListMergeList_L（LinkListLa,LinkListLb）;
inttotal=0;
voidmain（）
{
LinkListLa;
LinkListLb;
La=（LinkList）malloc（sizeof（structLNode））;
La->next=NULL;
Lb=（LinkList）malloc（sizeof（structLNode））;
Lb->next=NULL;
intn;
intm;
intx;
menu（）;
scanf（"%d",&n）;
while（n）
{
switch（n）
{
case0:
;break;
case1:
La->next=InitList（）;break;
case2:
ListEmpty（La）;break;
case3:
printf（"请输入要插入到第几个节点前:
\n"）;
scanf（"%d",&m）;
printf（"请输入插入的数据:
\n"）;
scanf（"%d",&x）;
ListInsert（La,m,x）;break;
case4:
printf（"请输入删除元素的位序:
\n"）;
scanf（"%d",&m）;
ListDelete（La,m,x）;
printf（"删除的元素为:
%d\n",x）;break;
case5:
printf（"请输入要找的与线性表中相等的数:
\n"）;
scanf（"%d",&m）;
LocateElem（La,m）;break;
case6:
printf（"请输入查找的位序:
\n"）;
scanf（"%d",&m）;
GetList（La,m,x）;
printf（"La中第%d个元素的值为%d\n",m,x）;break;
case7:
ShowList（La）;break;
case8:
Lb->next=InitList（）;break;
case9:
La=MergeList_L（La,Lb）;
printf（"归并成功\n"）;break;
}
menu（）;
scanf（"%d",&n）;
}
}
voidmenu（）
{
printf（"********************\n\n"）;
printf（"0.退出\n\n"）;
printf（"1.创建线性表La\n\n"）;
printf（"2.判断是否为空表\n\n"）;
printf（"3.插入元素\n\n"）;
printf（"4.删除元素\n\n"）;
printf（"5.定位元素\n\n"）;
printf（"6.取元素\n\n"）;
printf（"7.输出线性表\n\n"）;
printf（"8.创建线性表Lb\n\n"）;
printf（"9.归并两线性表\n\n"）;
printf（"********************\n\n"）;
}
//创建链式线性表L
LinkListInitList（）
{
intcount=0;
LinkListpHead=NULL;
LinkListpEnd,pNew;
pEnd=pNew=（LinkList）malloc（sizeof（structLNode））;
printf（"请输入数据:
\n"）;
scanf（"%d",&pNew->data）;
while（pNew->data）
{
count++;
if（count==1）
{
pNew->next=pHead;
pEnd=pNew;
pHead=pNew;
}
else
{
pNew->next=NULL;
pEnd->next=pNew;
pEnd=pNew;
}
pNew=（LinkList）malloc（sizeof（structLNode））;
printf（"请输入数据:
\n"）;
scanf（"%d",&pNew->data）;
}
free（pNew）;
total=total+count;
returnpHead;
}
//判断L是否为空表
voidListEmpty（LinkListL）
{
if（NULL==L->next）
printf（"此表为空表!
\n"）;
else
printf（"此表不为空表!
\n"）;
}
//在链式线性表中第i个元素前插入新元素e
voidListInsert（LinkListL,inti,inte）
{
LinkListp;
LinkLists;
p=L;
intj=0;
while（p&&j{
p=p->next;
++j;
}
if（!
p||j>i-1）
printf（"不存在您要找的节点!
\n"）;
else
{
s=（LinkList）malloc（sizeof（int））;
s->data=e;
s->next=p->next;
p->next=s;
printf（"插入节点成功!
\n"）;
}
}
//输出链式线性表
voidShowList（LinkListL）
{
LinkListp;
p=L->next;
if（p==NULL）
printf（"此表为空表!
\n"）;
else
while（p）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
//在链式线性表中删除第i个元素，并用e返回其值
voidListDelete（LinkListL,inti,int&e）
{
LinkListp;
LinkListq;
p=L;
intj=0;
while（p->next&&j{
p=p->next;
++j;
}
if（!
（p->next）||j>i-1）
printf（"没有找到要删除的位置!
"）;
else
{
q=p->next;
p->next=q->next;
e=q->data;
free（q）;
}
}
//用e返回L中第i个数据元素的值
voidGetList（LinkListL,inti,int&e）
{
LinkListp;
p=L->next;
intj=0;
while（p->next&&j{
p=p->next;
++j;
}
if（!
（p）||j>i-1）
printf（"没有找到要查找的位置!
"）;
else
e=p->data;
}
//对比a与b相等
boolcompare（inta,intb）
{
if（a==b）
return1;
else
return0;
}
//在链式线性表L中查找第1个值与e满足compare（）d元素的位序
voidLocateElem（LinkListL,inte）
{
inti=0;
LinkListp;
p=L;
while（p->next&&!
compare（p->data,e））
{
p=p->next;
i++;
}
if（NULL==p->next）
{
if（0==compare（p->data,e））
printf（"没有该元素!
\n"）;
else
printf（"第1个与e相等的元素的位序为%d\n",i）;
}
else
if（compare（p->data,e））
printf（"没有该元素!
\n"）;
}
LinkListMergeList_L（LinkListLa,LinkListLb）
{
inti,j,k;
LinkListpa_1,pb_1,pa_2,pb_2,pc,pd;
pa_1=La->next;
pc=pa_2=La;
pb_1=pb_2=Lb->next;
if（pa_1->data>pb_1->data）
{
pc=pa_2=Lb;
pa_1=Lb->next;
pb_1=pb_2=La->next;
}
while（pa_1&&pb_1）
{
if（pa_1->data>=pb_1->data）
{
pa_2->next=pb_1;
pb_2=pb_1->next;
pb_1->next=pa_1;
pb_1=pb_2;
pa_2=pa_2->next;
}
else
{
pa_1=pa_1->next;
pa_2=pa_2->next;
}
}
if（pb_1）
pa_2->next=pb_1;
pd=（LinkList）malloc（sizeof（structLNode））;
pd->next=NULL;
pa_2=pd;
k=total;
for（i=0;i{
pa_1=pc->next;
for（j=1;jpa_1=pa_1->next;
pb_1=（LinkList）malloc（sizeof（structLNode））;
pa_2->next=pb_1;
pa_2=pa_2->next;
pa_2->data=pa_1->data;
k--;
}
pa_2->next=NULL;
returnpd;
}
2.流程图（实验要求1和3）
图1主函数流程图
图2创建线性表La流程图
图3判断La是否为空表流程图
图4插入元素（La）流程图
图5删除元素（La）流程图
图6定位元素（La）流程图
图7取元素（La）流程图
图8输出线性表流程图
图9输出线性表流程图
流程图（实验要求2和4）
图10主函数流程图
图11创建线性表La流程图
图12判断是否为空表流程图
图13插入元素流程图
图14删除元素流程图
图15定位元素流程图图图16取元素流程图
图17创建Lb流程图
图18归并两表流程图
六、运行结果
升级会员 