實驗1-2順序表和鏈表基本操作-參考答案

實驗1-2順序表和鏈表基本操作_參考答案實驗1-2順序表和鏈表基本操作_參考答案實驗1-2順序表和鏈表基本操作_參考答案xxx公司實驗1-2順序表和鏈表基本操作_參考答案文件編號：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計，管理制度實驗1、2：線性表的應(yīng)用參考代碼一、實驗預(yù)備知識1．復(fù)習(xí)C中編寫函數(shù)的相關(guān)內(nèi)容。2．復(fù)習(xí)如何用主函數(shù)將多個函數(shù)連在一起構(gòu)成一個C完整程序。二、實驗?zāi)康?．掌握線性表的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)2．熟練運用線性表在順序存儲方式下的初始化、創(chuàng)建、輸出、插入和刪除運算3．熟練運用線性表在鏈?zhǔn)酱鎯Ψ绞较碌膭?chuàng)建、輸出、插入和刪除運算三、實驗要求1．編寫初始化并創(chuàng)建線性表和輸出線性表的算法。2．編寫對線性表插入和刪除運算算法，要判斷位置的合法性和溢出問題。3．編寫有序表的插入和刪除運算算法。4．編寫一個主函數(shù)，將上面函數(shù)連在一起，構(gòu)成一個完整的程序。5．將實驗源程序調(diào)試并運行，寫出輸入、輸出結(jié)果，并對結(jié)果進行分析。四、實驗內(nèi)容順序表實驗內(nèi)容：1．給定的線性表為L=（12，25，7，42，19，38），元素由鍵盤輸入。2．初始化并建立順序表。（開辟的存儲空間大小為8）3．編寫順序表輸出算法。4．依次插入3、21、15、99四個數(shù)，分別插入在第1、8、4和12位置，每插入一次都要輸出一次順序表。5．刪除第1，第9和第12個位置上的元素，每刪除一個元素都要輸出一次順序表。6．編寫一個排序算法，對線性表中元素從小到大排列。7．向有序表分別插入20和50，插入后表仍然有序。（修改開辟的存儲空間大小為15）單鏈表實驗內(nèi)容：1．給定的線性表為L=（12，25，7，42，19，38），元素由鍵盤輸入。2．建立一個帶表頭結(jié)點的單鏈表（前插入法和尾插入法均可）。3．編寫單鏈表輸出算法。4．依次插入3、21、15、99四個數(shù)，分別插入在第1、8、4和12位置，每插入一次都要輸出一次單鏈表。5．刪除第1，第9和第12個位置上的元素，每刪除一個元素都要輸出一次單鏈表。6．編寫一個排序算法，對鏈表中元素從小到大排列。7．向有序鏈表分別插入20和50，插入后表仍然有序。五、實驗結(jié)果順序表源程序：#include<iostream>usingnamespacestd;constintMAXSIZE=8;//做有序表插入操作時，將8改為15typedefintDataType;typedefstruct{ DataTypedata[MAXSIZE]; intlength;}SeqList;voidInit_SeqList(SeqList&L);//創(chuàng)建空順序表算法voidShow_SeqList(SeqListL);//順序表輸出算法voidCreate_SeqList(SeqList&L);//順序表創(chuàng)建算法intInsert_SeqList(SeqList&L,DataTypex,inti);//順序表的插入算法intDelete_SeqList(SeqList&L,inti);//順序表的刪除算法intLocate_SeqList(SeqListL,DataTypex);//順序表的按值查找算法voidSort_SeqList(SeqList&L);//順序表的排序算法intInsert_SeqList_sort(SeqList&L,DataTypex);//有序表的插入算法voidMerge(SeqListLA,SeqListLB,SeqList&LC);//兩個有序順序表的合并算法voidmenu();//菜單算法voidmain(){menu();}voidmenu()//菜單算法{ SeqListL; Init_SeqList(L);intm;while(1) { cout<<"\n根據(jù)所做操作選擇以下數(shù)字序號："<<endl;cout<<"1:創(chuàng)建順序表2:執(zhí)行插入操作3:執(zhí)行刪除操作"<<endl; cout<<"4:執(zhí)行輸出操作5:執(zhí)行查找操作6:執(zhí)行排序操作"<<endl; cout<<"7:執(zhí)行有序表的插入操作8:執(zhí)行有序表的合并操作0:退出"<<endl; intn,i,x; cin>>n; switch(n) { case1: {Create_SeqList(L); break; } case2: {cout<<"請輸入插入位置："; cin>>i; cout<<endl<<"請輸入插入元素值："; cin>>x; cout<<endl;m=Insert_SeqList(L,x,i);if(m==1) cout<<"插入操作成功！"<<endl; else if(m==0) cout<<"插入位置不合法！"<<endl; else cout<<"發(fā)生溢出！"<<endl; break; } case3: { cout<<"請輸入刪除位置："; cin>>i; cout<<endl;m=Delete_SeqList(L,i);if(m==1) cout<<"刪除操作成功！"<<endl; else if(m==0) cout<<"刪除位置不合法！"<<endl; else cout<<"空表！"<<endl; break; } case4: { Show_SeqList(L); break; } case5: { cout<<"請輸入所要查找的元素值："; cin>>x; cout<<endl;m=Locate_SeqList(L,x);if(m==0) cout<<"所查找元素不在順序表中！"<<endl; else cout<<"所查找元素是順序表的第"<<m<<"個元素！"<<endl; break; } case6: { Sort_SeqList(L); cout<<"排序操作完成！"<<endl; break; } case7: { cout<<endl<<"請輸入插入元素值："; cin>>x; cout<<endl;m=Insert_SeqList_sort(L,x);if(m==1) cout<<"插入操作成功！"<<endl; else cout<<"發(fā)生溢出！"<<endl; break; } case8: { SeqListL1,L2,L3; Init_SeqList(L1); Init_SeqList(L2); Init_SeqList(L3);cout<<"創(chuàng)建有序表1："<<endl;Create_SeqList(L1); Sort_SeqList(L1); cout<<"創(chuàng)建有序表2："<<endl;Create_SeqList(L2); Sort_SeqList(L2);cout<<"有序表1："<<endl; Show_SeqList(L1);cout<<"有序表2："<<endl; Show_SeqList(L2);Merge(L1,L2,L3); cout<<"合并后："<<endl; Show_SeqList(L3); break; }case0: return; } }}voidInit_SeqList(SeqList&L)//創(chuàng)建空順序表算法{ =0;}voidShow_SeqList(SeqListL)//順序表輸出算法{ if==0) cout<<"空表！"<<endl; else for(inti=0;i<;i++) cout<<[i]<<""; cout<<endl;}voidCreate_SeqList(SeqList&L)//順序表創(chuàng)建算法{ cout<<"請輸入元素個數(shù):"; cin>>; cout<<"依次輸入各個元素的值:"<<endl; for(inti=0;i<;i++) cin>>[i];}intInsert_SeqList(SeqList&L,DataTypex,inti)//順序表的插入算法{ if(MAXSIZE<= return-1; if(i<1||i>+1) return0; for(intj=;j>=i-1;j--) [j+1]=[j]; [i-1]=x; ++; return1;}intDelete_SeqList(SeqList&L,inti)//順序表的刪除算法{ if==0) return-1; if(i<1||i> return0; for(intj=i;j<;j++) [j-1]=[j]; ; return1;}intLocate_SeqList(SeqListL,DataTypex)//順序表的按值查找算法{ inti=0; while(i<&&[i]!=x) i++; if(i<) returni+1; else return0;}voidSort_SeqList(SeqList&L)//排序算法{ inti,k,j; DataTypetemp; for(i=0;i<;i++) { k=i; for(j=i+1;j<=-1;j++) if[j]<[k]) k=j; if(i!=k) { temp=[i]; [i]=[k]; [k]=temp; } }}intInsert_SeqList_sort(SeqList&L,DataTypex)//有序表的插入算法{ if(MAXSIZE<= return-1; inti=0; while(i<&&[i]<x) i++; for(intj=;j>=i;j--) [j+1]=[j]; [i]=x; ++; return1;}voidMerge(SeqListLA,SeqListLB,SeqList&LC)//兩個有序順序表的合并算法{ inti,j,k; i=j=k=0; while(i<&&j< { if[i]<[j]) { [k]=[i]; i++; k++; } else { [k]=[j]; j++; k++; } } while(i< { [k]=[i]; i++; k++; } while(j< { [k]=[j]; j++; k++; } =k;}輸入輸出結(jié)果：圖1-1主菜單圖1-2順序表的創(chuàng)建和輸出操作圖1-3順序表的插入操作圖1-4順序表的刪除操作圖1-5順序表的排序操作圖1-6有序表的插入操作圖1-7兩個有序表的合并操作單鏈表的源程序：#include"iostream"usingnamespacestd;typedefintDataType;typedefstructnode{ DataTypedata; structnode*next;}LNode,*LinkList;voidInit_LinkList(LinkList&L);//創(chuàng)建空單鏈表voidCreate1LinkList(LinkList&L,intn);//前插入法創(chuàng)建單鏈表的算法voidCreate2LinkList(LinkList&L,intn);//后插入法創(chuàng)建單鏈表的算法voidPrintLinkList(LinkListL);//單鏈表的輸出算法intInsertLinkList(LinkList&L,inti,DataTypex);//單鏈表的插入算法intDeleteLinkList(LinkList&L,inti);//單鏈表的刪除算法voidSelect_Sort_LinkList(LinkList&L);//鏈表的排序算法（選擇排序）voidInsert2(LinkListL,DataTypex);//有序表的插入voidMerge(LinkListL1,LinkListL2,LinkList&L3);//兩個有序表的合并算法voidmenu();//菜單函數(shù)intmain(){ menu();return0;}voidInit_LinkList(LinkList&L)//創(chuàng)建空單鏈表{ L=newLNode; L->next=NULL;}voidCreate1LinkList(LinkList&L,intn)//前插入法創(chuàng)建單鏈表的算法{ LNode*s; for(inti=1;i<=n;i++) { s=newLNode; cout<<"請輸入第"<<i<<"個元素的值："; cin>>s->data; s->next=L->next; L->next=s; }}voidCreate2LinkList(LinkList&L,intn)//后插入法創(chuàng)建單鏈表的算法{ LNode*s,*r=L; for(inti=1;i<=n;i++) { s=newLNode; cout<<"請輸入第"<<i<<"個元素的值："; cin>>s->data; r->next=s; r=s; } r->next=NULL;}voidPrintLinkList(LinkListL)//單鏈表的輸出算法{ if(L->next==NULL) { cout<<"空表！"<<endl; return; } cout<<"當(dāng)前單鏈表為："<<endl; LNode*p=L->next; while(p) { cout<<p->data<<""; p=p->next; } cout<<endl;}intInsertLinkList(LinkList&L,inti,DataTypex)//單鏈表的插入算法{ intj=0; LNode*p=L,*s; while(p&&j<i-1) { p=p->next; j++; } if(!p||j>i-1) return0; s=newLNode; s->data=x; s->next=p->next; p->next=s; return1;}intDeleteLinkList(LinkList&L,inti)//單鏈表的刪除算法{ if(L->next==NULL) return-1; intj=0; LNode*p=L,*q; while((p->next!=NULL)&&(j<i-1)) { p=p->next; j++; } if((p->next==NULL)||(j>i-1)) return0; q=p->next; p->next=q->next; deleteq; return1;}voidSelect_Sort_LinkList(LinkList&L)//鏈表的排序算法（選擇排序）{ if(L->next==NULL) { cout<<"空表，不需要排序！"<<endl; return; } LNode*p,*q,*s; DataTypetemp; if(L->next==NULL)return; for(p=L->next;p->next!=NULL;p=p->next) { s=p; for(q=p->next;q!=NULL;q=q->next) { if(q->data<s->data) s=q; } if(s!=p) { temp=s->data;s->data=p->data;p->data=temp; } } cout<<"排序成功！"<<endl;}voidInsert2(LinkListL,DataTypex)//有序表的插入{ LNode*p=L,*s; while(p->next!=NULL&&p->next->data<x) p=p->next; s=newLNode; s->data=x; s->next=p->next; p->next=s; cout<<"插入操作成功！"<<endl;}voidMerge(LinkListL1,LinkListL2,LinkList&L3)//兩個有序表的合并算法{ LNode*p1,*p2,*p3,*s; p1=L1->next; p2=L2->next; L3=p3=newLNode; L3->next=NULL; while(p1&&p2) { s=newLNode; if(p1->data<p2->data) { s->data=p1->data; p1=p1->next; } else { s->data=p2->data; p2=p2->next; } p3->next=s; p3=s; } if(p1) p3->next=p1; if(p2) p3->next=p2;}voidmenu()//菜單函數(shù){ LinkListL; Init_LinkList(L); intm; while(1) { cout<<"\n根據(jù)所做操作選擇以下數(shù)字序號："<<endl;cout<<"1:前插入創(chuàng)建單鏈表2:尾插入創(chuàng)建單鏈表3:執(zhí)行插入操作"<<endl; cout<<"4:執(zhí)行刪除操作5:執(zhí)行輸出操作6:執(zhí)行排序操作"<<endl; cout<<"7:執(zhí)行有序表的插入操作8:執(zhí)行有序表的合并操作0:退出"<<endl; intn,i,x; cin>>n; switch(n) { case1: {cout<<"請輸入結(jié)點個數(shù)："; cin>>i; Create1LinkList(L,i); PrintLinkList(L); break; } case2: {cout<<"請輸入結(jié)點個數(shù)："; cin>>i; Create2LinkList(L,i); PrintLinkList(L); break; }case3: {cout<<"請輸入插入位置："; cin>>i; cout<<endl<<"請輸入插入元素值："; cin>>x; cout<<endl;if(InsertLinkList(L,i,x)==1) cout<<"插入操作成功！"<<endl; elsecout<<"插入位置不合法！"<<endl; break; }case4: {cout<<"請輸入刪除位置："; cin>>i; cout<<endl; m=DeleteLinkList(L,i);if(m==1) cout<<"刪除操作成功！"<<endl; else if(m==-1) cout<<"空表！"<<endl; else