数据结构实验报告 线性表的基本操作文档格式.docx
《数据结构实验报告 线性表的基本操作文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告 线性表的基本操作文档格式.docx（23页珍藏版）》请在冰点文库上搜索。
（6）根据算法，将两个有序的单链表合并成一个有序单链表。
[测试数据]
由学生任意指定。
（一）顺序表的基本操作
#include<
iostream>
usingnamespacestd;
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefstruct{//结构体
ElemType*elem;
intlength;
intlistsize;
}SqList;
SqListLx;
StatusInitList_Sq（SqList&
L）//分配空间
{L.elem=newElemType[LIST_INIT_SIZE];
if（!
L.elem）exit（OVERFLOW）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
StatusListInsert（SqList&
L,inti,ElemTypee）//插入新元素
{int*q,*p;
ElemType*newbase;
if（i<
1||i>
L.length+1）returnERROR;
if（L.length>
=L.listsize）
{newbase=newElemType[L.listsize+LISTINCREMENT];
newbase）exit（OVERFLOW）;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&
（L.elem[i-1]）;
for（p=&
（L.elem[L.length-1]）;
p>
=q;
--p）
*（p+1）=*p;
*q=e;
++L.length;
StatusListlength（SqListL）//长度
{int*p=L.elem;
//判断线形表是否存在
while（p）
{return（L.length）;
StatusGetElem（SqListL,inti,ElemType&
e）//取元素
{if（i<
L.length）
returnERROR;
else
{e=L.elem[i-1];
returne;
voidMergeList（SqListLa,SqListLb,SqList&
Lc）//合并
{ElemTypeai,bj;
InitList_Sq（Lc）;
inti=1,j=1,k=0;
intLa_len,Lb_len;
La_len=Listlength（La）;
Lb_len=Listlength（Lb）;
while（（i<
=La_len）&
&
（j<
=Lb_len））
{GetElem（La,i,ai）;
GetElem（Lb,j,bj）;
if（ai<
=bj）
{ListInsert（Lc,++k,ai）;
++i;
else
{ListInsert（Lc,++k,bj）;
++j;
while（i<
=La_len）
{GetElem（La,i++,ai）;
ListInsert（Lc,++k,ai）;
while（j<
=Lb_len）
{GetElem（Lb,j++,bj）;
ListInsert（Lc,++k,bj）;
voidshow（SqListL,inti）//显示
{intj;
ElemTypek;
cout<
<
"
顺序表显示如下:
endl;
for（j=0;
j<
i-1;
j++）
{k=L.elem[j];
k<
->
;
if（j==i-1&
i>
0）
{k=L.elem[j];
cout<
k;
voidcreate（SqList&
L,intn）//输入元素
{inte;
for（inti=0;
i<
n;
i++）
{cin>
>
e;
L.elem[i]=e;
L.length=i+1;
StatusListDelete_Sq（SqList&
L,inti,ElemType&
e）//删除
{ElemType*p,*q;
L.length）returnERROR;
p=&
e=*p;
q=L.elem+L.length-1;
for（++p;
p<
++p）*（p-1）=*p;
--L.length;
returnOK;
StatusListxiugei（SqList&
e）//修改
{L.elem[i-1]=e;
returnOK;
voidshuru（SqList&
L1）//顺序表的创建
{inta;
InitList_Sq（L1）;
请输入顺序表的长度：
cin>
a;
请输入顺序表的元素（共"
a<
个）"
create（L1,a）;
show（L1,a）;
voidchaxun（SqList&
L1）//取第i个位置的元素
ElemTypee1;
请选择所要取出元素的位置:
j;
0||j>
Listlength（L1））
{cout<
输入有误，请重新输入"
cout<
cin>
GetElem（L1,j,e1）;
取出的元素为:
e1<
voidxiugai（SqList&
L1）//修改第i个位置的元素
intj;
ElemTypee1;
a=L1.length;
请选择所要修改元素的位置:
{cout<
要修改成的元素:
e1;
Listxiugei（L1,j,e1）;
修改后的顺序表数据:
voidshanchu（SqList&
L1）//删除顺序表里的元素
请选择所要删除元素的位置:
ListDelete_Sq（L1,j,e1）;
show（L1,a-1）;
voidcharu（SqList&
L1）//插入元素到顺序表里
请选择所要插入元素的位置:
}
要插入的元素:
ListInsert（L1,j,e1）;
show（L1,a+1）;
voidhebing（SqList&
L3）//合并两个顺序表
{SqListL1,L2;
inta,b;
InitList_Sq（L2）;
请输入第一个有序表的长度：
请输入第一个有序表的元素（共"
请输入第二个有序表的长度：
b;
请输入第二个有序表的元素（共"
b<
create（L2,b）;
show（L2,b）;
MergeList（L1,L2,L3）;
合并后的有序表如下：
show（L3,a+b）;
voidmain（）//主菜单
{intchoice;
for（;
）
{cout<
顺序表的基本操作"
1.顺序表的创建"
2.顺序表的显示"
3.顺序表的长度"
4.取第i个位置的元素"
5.修改第i个位置的元素"
6.插入元素到顺序表里"
7.删除顺序表里的元素"
8.合并两个顺序表"
9.退出系统"
请选择：
choice;
switch（choice）
{case1:
shuru（Lx）;
break;
case2:
show（Lx,Lx.length）;
case3:
顺序表的长度:
Listlength（Lx）<
case4:
chaxun（Lx）;
case5:
xiugai（Lx）;
case6:
charu（Lx）;
case7:
shanchu（Lx）;
case8:
hebing（Lx）;
case9:
退出系统!
exit（0）;
default:
输入有误，请重新选择"
}
（二）单链表的基本操作
#definetrue1
#definefalse0
#defineok1
#defineerror0
#defineoverflow-2
typedefstructLNode//存储结构
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidCreateList（LinkList&
L,intn）//尾插法创建单链表
{LinkListp;
L=newLNode;
L->
next=NULL;
//建立一个带头结点的单链表
LinkListq=L;
//使q指向表尾
for（inti=1;
=n;
{p=newLNode;
p->
data;
p->
q->
next=p;
q=p;
StatusGetElem（LinkListL,inti,ElemType&
e）//取第i个元素
{LinkListp=L->
next;
intj=1;
while（p&
i）
{p=p->
++j;
p||j>
i）returnerror;
//第i个元素不存在
e=p->
returnok;
StatusLinkInsert（LinkList&
L,inti,ElemTypee）//插入
{LinkListp=L;
intj=0;
i-1）
++j;
}//寻找第i-1个结点
i-1）
returnerror;
//i小于1或者大于表长加1
LinkLists=newLNode;
//生成新结点
s->
data=e;
next=p->
//插入L中
next=s;
StatusListDelete（LinkList&
e）//删除
LinkListq;
while（p->
next&
{//寻找第i个结点，并令p指向其前驱
p=p->
（p->
next）||j>
i-1）returnerror;
//删除位置不合理
q=p->
next=q->
//删除并释放结点
e=q->
delete（q）;
voidMergeList（LinkList&
La,LinkList&
Lb,LinkList&
Lc）
{//合并两个顺序链表
LinkListpa,pc,pb;
pa=La->
pb=Lb->
Lc=pc=La;
while（pa&
pb）
{if（pa->
data<
=pb->
data）
{pc->
next=pa;
pc=pa;
pa=pa->
else
next=pb;
pc=pb;
pb=pb->
pc->
next=pa?
pa:
pb;
delete（Lb）;
}
voidshow（LinkListL）//显示
p=L->
while（p）
-->
p=p->
intLength（LinkListL,inti）//表长
{i=0;
LinkListp=L->
{++i;
returni;
voidxiugai（LinkListL）//修改
{inti,j=1;
ElemTypek;
ElemTypee,m;
请输入要修改的元素位置（0<
length）:
i;
GetElem（L,i,e）;
该位置的元素:
e<
修改后的元素值:
m=p->
data=k;
修改后的单链表显示如下:
show（L）;
voidhebing（）//合并两个单链表
{inta,b;
LinkListLa,Lb,Lc;
请输入第一个有序链表的长度:
请输入第一个有序链表的元素共（"
个）：
CreateList（La,a）;
show（La）;
请输入第二个有序链表的长度:
请输入第二个有序链表的元素共（"
CreateList（Lb,b）;
show（Lb）;
MergeList（La,Lb,Lc）;
合并后的有序链表如下：
show（Lc）;
voidmain（）//主函数
{intselect;
intx;
ElemTypey;
LinkListlist;
for（;
单链表的基本操作"
1.单链表的创建"
2.单链表的显示"
cout<
3.单链表的长度"
6.插入元素到单链表里"
7.删除单链表里的元素"
8.合并两个单链表"
请选择:
cin>
select;
switch（select）
{case1:
cout<
请输入单链表的长度:
cin>
x;
请输入"
x<
个元素"
CreateList（list,x）;
break;
case2:
单链表显示如下:
show（list）;
case3:
ints;
单链表的长度为:
Length（list,s）<
break;
case4:
while（x<
0||x>
Length（list,s））
{cout<
cout<
GetElem（list,x,y）;
该位置的元素为:
y<
case5:
xiugai（list）;
break;
case6:
请选择要插入的位置:
要插入的元素值:
y;
LinkInsert（list,x,y）;
插入后单链表显示如下:
show（list）;
break;
case7:
请选择要删除的位置:
while（x<
cout<
cin>
ListDelete（list,x,y）;
要删除的元素值:
升级会员 