数据结构线性表设计代码Word文档格式.docx
《数据结构线性表设计代码Word文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构线性表设计代码Word文档格式.docx(22页珍藏版)》请在冰点文库上搜索。
}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;
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;
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(;
)
顺序表的基本操作"
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:
输入有误,请重新选择"
}
运行结果、
顺序表得创建显示如下图2-1
顺序表的插入如下2-2
顺序表的删除如下2-3
(二)链式表的基本操作源代码
#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;
while(p&
i-1)
++j;
}//寻找第i-1个结点
i-1)
returnerror;
//i小于1或者大于表长加1
LinkLists=newLNode;
//生成新结点
s->
data=e;
next=p->
//插入L中
p->
next=s;
StatusListDelete(LinkList&
e)//删除
LinkListq;
while(p->
next&
{//寻找第i个结点,并令p指向其前驱
p=p->
if(!
(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->
-->
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;
单链表的基本操作"
1.单链表的创建"
2.单链表的显示"
3.单链表的长度"
6.插入元素到单链表里"
7.删除单链表里的元素"
8.合并两个单链表"
请选择:
select;
switch(select)
cout<
请输入单链表的长度:
cin>
x;
请输入"
x<
个元素"
CreateList(list,x);
break;
单链表显示如下:
show(list);
break;
ints;
cout<
单链表的长度为:
Length(list,s)<
while(x<
0||x>
Length(list,s))
GetElem(list,x,y);
该位置的元素为:
y<
xiugai(list);
break;
请选择要插入的位置:
要插入的元素值:
y;
LinkInsert(list,x,y);
插入后单链表显示如下:
请选择要删除的位置:
ListDelete(list,x,y);
要删除的元素值:
删除后的单链表显示如下:
hebing();
exit(0);
default:
单链表的创建如下图2-4
单链表的显示如下图2-5
单链表的插入如下图2-6
单链表的删除如下图2-6
算法分析:
针对上述程序,线性表采用顺序存储,插入操作采用平均移动次数,算法时间复杂性都为:
O(n)……
六、心得体会
在这次设计的过程中,我还遇到了,很多的问题。
顺序表是按顺序存储的,用了一维数组来存储,又结合C++的程序设计,我又用了类,但是,在执行时出现了问题。
后来问同学,指出我的错误,不过获益不少。
我又重新整理思路,把顺序表的基本操作写好了。
虽然走了很多弯路,但是让我认识到,一定要创新,大胆,不能按照旧的思路去干新的事情。
单链表写起来简单多了,这个很快就搞定了。
但是细节上出了问题。
比如说,有些变量的重复定义,有些变量又没有定义,在调用函数,就直接复制过来,没有改参数……通过修改,我深刻理解到:
细节决定成败,在以后,不管做任何事情都要认真,细心。
这次的实验报告,让我受益匪浅,不仅有知识方面的,还有生活和精神上的。
总之,我会继续我的兴趣编程,相信在编程的过程中,能不断的提高自己。
欢迎您的下载,
资料仅供参考!
致力为企业和个人提供合同协议,策划案计划书,学习资料等等
打造全网一站式需求