线性表的插入和删除运算

实训题一线性表的插入和删除运算一、实验目的：1、掌握线性表顺序存储结构2、能熟练地利用顺序存储结构实现线性表的基本操作3、能熟练地掌握顺序存储结构中算法的实现二、实验内容：1、建立含有若干个元素的顺序表，并将结果在屏幕上输出2、对建立的顺序表实现插入和删除，并将结果在屏幕上输出3、对建立的链式线性表实现插入和删除，并将结果在屏幕上输出三、算法程序：1、顺序存储1)插入运算#include<iostream.h>#defineelemtypeintconstintmaxsize=1000;classsequenlist{protected:elemtypea[maxsize];intlen;public:voidinput(intn){for(inti=1;i<=len;i++)cin>>a[i];len=n;cout<<endl;}voidinsert(elemtypex,inti){intj;if(len>=maxsize-1)cout<<"overflow"<<endl;elseif((ivl)ll(i>len+l))coutvv"positionisnotcorrect!"vvendl;else{for(j=len;j>=i;j--)a[j+1]=a[j];a[i]=x;len++;}}voidprint(){for(inti=1;i<=len;i++)coutvva[i]vv"\n";coutvvendl;}};voidmain(){sequenlistL;elemtypex;inti,j,n;coutvv"请输入表中的元素个数:"；cin>>n;coutvv"请输入"vvnvv"个元素，建立顺序表"vvendl;L.input(n);coutvv"请输入要插入的元素及位置:"；cin>>x>>j;L.insert(x,j);L.print();}2）删除运算#include<iostream.h>#defineelemtypeintconstintmaxsize=1000;classsequenlist{protected:elemtypea[maxsize];intlen;public:voidinput(intn){for(inti=1;i<=n;i++)cin>>a[i];len=n;cout<<endl;}voiddel(inti){intj;if((i<1)||(i>len))cout<<"positionisnotcorrect!"<<endl;else{for(j=i+1;j<=len;j++)a[j-1]=a[j];len--;}}voidprint(){for(inti=1;i<=len;i++)cout<<a[i]<<"\n";cout<<endl;}};voidmain(){sequenlistL;elemtypex,n;inti,j;coutvv"请输入表中的元素个数:"；cin>>n;coutvv"请输入"vvnvv"个元素，建立顺序表"vvendl;L.input(n)；coutvv"请输入要删除的元素位置:"；cin>>j;L.del(j);L.print();}运行结果:运行结果:2、链式存储1)头插法删除运算#include<iostream.h>#defineelemtypeintclasslink{public:elemtypedata;link*next;};classlinklist{protected:link*head;public:link*hcreat(){link*s,*p;elemtypei;cout<<"输入多个结点数值，为0时算法结束";cin>>i;p=newlink;p->next=NULL;while(i){s=newlink;s->data=i;s->next=p->next;p->next=s;cin>>i;}returnp;}voidprint(link*head){link*p;p=head->next;while(p->next!=NULL){cout<<p->data<<"->";p=p->next;}cout<<p->data;cout<<endl;}voiddel(link*head,elemtypex){link*p,*q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}if(p==NULL)cout〈〈要删除的结点不存在！";else{q->next=p->next;delete(p);}}};voidmain(){elemtypex,y;link*p,*q;linklista;p=a.hcreat();a.print(p);cout〈〈‘请输入要删除的元素："；cin»y;a.del(p,y);a.print(p);}j\tri 0111iiica \iviii_iLrnpilwinu口i输人多个結点数値，为0时算法结束122334505->4->33->22->1養输入要删除的元素；335->4->22->1Pressnnykeytocontinu.e—运算结果:2）尾插法插入运算#includeviostream.h>#defineelemtypeintclasslink{public:elemtypedata;link*next;};classlinklist{protected:link*head;public:link*hcreat(){link*s,*p,*r;elemtypei;coutvv"输入多个结点数值，为0时算法结束";cin>>i;p=r=newlink;p->next=NULL;while(i){s=newlink;s->data=i;r->next=s;r=s;cin>>i;}r->next=NULL;returnp;}voidprint(link*head){link*p;p=head->next;while(p->next!=NULL){cout<<p->data<<"->";p=p->next;}cout<<p->data;cout<<endl;}link*Locate(link*head,elemtypex){link*p;p=head->next;while((p!=NULL)&&(p->data!=x))p=p->next;returnp;}voidinsert(link*head,elemtypex,elemtypey){link*p,*s;s=newlink;s->data=y;if(head->next==NULL){head->next=s;s->next=NULL;}p=Locate(head,x);if(p==NULL)cout<<"插入位置非法！”；else{s->next=p->next；p->next=s；}}}；voidmain(){

elemtypex,y;link*p,*q;linklista;p=a.hcreat();a.print(p);coutvv"请输入插入位置的元素值:cin>>x;coutvv"请输入待插入元素值：";cin»y;a.insert(p,x,y);a.print(p);}1/21/2一口5个4331->2->33->4->533腮素严331->2->33->3->4->5PressanyIteytocontinLie运算结果:四、实验小结：