}
}
运行结果、
顺序表得创建显示如下图2-1
顺序表的插入如下2-2
顺序表的删除如下2-3
(二)链式表的基本操作源代码
#include
usingnamespacestd;
#definetrue1
#definefalse0
#defineok1
#defineerror0
#defineoverflow-2
typedefintStatus;
typedefintElemType;
typedefstructLNode//存储结构
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidCreateList(LinkList&L,intn)//尾插法创建单链表
{LinkListp;
L=newLNode;
L->next=NULL;//建立一个带头结点的单链表
LinkListq=L;//使q指向表尾
for(inti=1;i<=n;i++)
{p=newLNode;
cin>>p->data;
p->next=NULL;
q->next=p;
q=p;}
}
StatusGetElem(LinkListL,inti,ElemType&e)//取第i个元素
{LinkListp=L->next;
intj=1;
while(p&&j
{p=p->next;
++j;}
if(!
p||j>i)returnerror;//第i个元素不存在
e=p->data;
returnok;
}
StatusLinkInsert(LinkList&L,inti,ElemTypee)//插入
{LinkListp=L;
intj=0;
while(p&&j{p=p->next;
++j;}//寻找第i-1个结点
if(!
p||j>i-1)
returnerror;//i小于1或者大于表长加1
LinkLists=newLNode;//生成新结点
s->data=e;
s->next=p->next;//插入L中
p->next=s;
returnok;
}
StatusListDelete(LinkList&L,inti,ElemType&e)//删除
{LinkListp=L;
LinkListq;
intj=0;
while(p->next&&j{//寻找第i个结点,并令p指向其前驱
p=p->next;
++j;}
if(!
(p->next)||j>i-1)returnerror;//删除位置不合理
q=p->next;
p->next=q->next;//删除并释放结点
e=q->data;
delete(q);
returnok;
}
voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc)
{//合并两个顺序链表
LinkListpa,pc,pb;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while(pa&&pb)
{if(pa->data<=pb->data)
{pc->next=pa;
pc=pa;
pa=pa->next;}
else
{pc->next=pb;
pc=pb;
pb=pb->next;}
}
pc->next=pa?
pa:
pb;
delete(Lb);
}
voidshow(LinkListL)//显示
{LinkListp;
p=L->next;
while(p)
{cout<data<<"-->";
p=p->next;}
cout<}
intLength(LinkListL,inti)//表长
{i=0;
LinkListp=L->next;
while(p)
{++i;
p=p->next;}
returni;
}
voidxiugai(LinkListL)//修改
{inti,j=1;
ElemTypek;
ElemTypee,m;
LinkListp=L->next;
cout<<"请输入要修改的元素位置(0
";
cin>>i;
GetElem(L,i,e);
cout<<"该位置的元素:
"<cout<<"修改后的元素值:
";
cin>>k;
while(p&&j
{p=p->next;
++j;}
m=p->data;
p->data=k;
cout<<"修改后的单链表显示如下:
"<show(L);
}
voidhebing()//合并两个单链表
{inta,b;
LinkListLa,Lb,Lc;
cout<<"请输入第一个有序链表的长度:
"<cin>>a;
cout<<"请输入第一个有序链表的元素共("<"<CreateList(La,a);
show(La);
cout<<"请输入第二个有序链表的长度:
"<cin>>b;
cout<<"请输入第二个有序链表的元素共("<
"<CreateList(Lb,b);
show(Lb);
MergeList(La,Lb,Lc);
cout<<"合并后的有序链表如下:
"<show(Lc);
}
voidmain()//主函数
{intselect;
intx;
ElemTypey;
LinkListlist;
for(;;)
{cout<<"单链表的基本操作"<cout<<"1.单链表的创建"<cout<<"2.单链表的显示"<cout<<"3.单链表的长度"<cout<<"4.取第i个位置的元素"<cout<<"5.修改第i个位置的元素"<cout<<"6.插入元素到单链表里"<cout<<"7.删除单链表里的元素"<cout<<"8.合并两个单链表"<cout<<"9.退出系统"<cout<<"请选择:
";
cin>>select;
switch(select)
{case1:
cout<<"请输入单链表的长度:
"<cin>>x;
cout<<"请输入"<CreateList(list,x);
break;
case2:
cout<<"单链表显示如下:
"<show(list);
break;
case3:
ints;
cout<<"单链表的长度为:
"<break;
case4:
cout<<"请选择所要取出元素的位置:
";
cin>>x;
while(x<0||x>Length(list,s))
{cout<<"输入有误,请重新输入"<cout<<"请选择所要取出元素的位置:
";
cin>>x;}
GetElem(list,x,y);
cout<<"该位置的元素为:
"<break;
case5:
xiugai(list);break;
case6:
cout<<"请选择要插入的位置:
";cin>>x;
while(x<0||x>Length(list,s))
{cout<<"输入有误,请重新输入"<cout<<"请选择所要插入元素的位置:
";
cin>>x;}
cout<<"要插入的元素值:
";
cin>>y;
LinkInsert(list,x,y);
cout<<"插入后单链表显示如下:
"<show(list);
break;
case7:
cout<<"请选择要删除的位置:
";cin>>x;
while(x<0||x>Length(list,s))
{cout<<"输入有误,请重新输入"<cout<<"请选择所要删除元素的位置:
";
cin>>x;}
ListDelete(list,x,y);
cout<<"要删除的元素值:
"<cout<<"删除后的单链表显示如下:
"<show(list);
break;
case8:
hebing();
break;
case9:
exit(0);
break;
default:
cout<<"输入有误,请重新输入"<break;
}
}
}
运行结果、
单链表的创建如下图2-4
单链表的显示如下图2-5
单链表的插入如下图2-6
单链表的删除如下图2-6
算法分析:
针对上述程序,线性表采用顺序存储,插入操作采用平均移动次数,算法时间复杂性都为:
O(n)……
六、心得体会
在这次设计的过程中,我还遇到了,很多的问题。
顺序表是按顺序存储的,用了一维数组来存储,又结合C++的程序设计,我又用了类,但是,在执行时出现了问题。
后来问同学,指出我的错误,不过获益不少。
我又重新整理思路,把顺序表的基本操作写好了。
虽然走了很多弯路,但是让我认识到,一定要创新,大胆,不能按照旧的思路去干新的事情。
单链表写起来简单多了,这个很快就搞定了。
但是细节上出了问题。
比如说,有些变量的重复定义,有些变量又没有定义,在调用函数,就直接复制过来,没有改参数……通过修改,我深刻理解到:
细节决定成败,在以后,不管做任何事情都要认真,细心。
这次的实验报告,让我受益匪浅,不仅有知识方面的,还有生活和精神上的。
总之,我会继续我的兴趣编程,相信在编程的过程中,能不断的提高自己。
欢迎您的下载,
资料仅供参考!
致力为企业和个人提供合同协议,策划案计划书,学习资料等等
打造全网一站式需求