線性表的操作算法實驗報告

實驗報告2013學(xué)年第一學(xué)期任課老師：課程名稱數(shù)據(jù)結(jié)構(gòu)班級學(xué)號姓名實驗名稱實驗一線性表的操作算法實驗時間實驗環(huán)境VisualC++6.0

實驗?zāi)康暮蛢?nèi)容要求實驗一線性表的操作算法1．實驗?zāi)康?/p>

用C/C++,Java程序?qū)崿F(xiàn)課本中的有關(guān)算法，以達(dá)到對算法熟練的目的。2．實驗內(nèi)容

分別用數(shù)組和鏈表作為存儲結(jié)構(gòu)，實現(xiàn)線性表的插入、刪除、查找、排序、合并等操作。實驗過程記錄（學(xué)生寫出實驗步驟及中間的結(jié)果與現(xiàn)象，在實驗中做了什么，怎么做，發(fā)生的現(xiàn)象和中間結(jié)果）鏈表：在寫主函數(shù)之前，先創(chuàng)建一個長度為n的鏈表typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;建立鏈表的函數(shù)框架，根據(jù)實驗要求完善功能插入：intListInsert(LinkList&L,inti,inte){LinkListp=L;intj=0;while(p&&j<i-1){ p=p->next;++j;}if(!p||j>i-1)return0;LinkLists=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}刪除：intListDelete(LinkList&L,inti,int&e){LinkListp=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return0;LinkListq=p->next;p->next=q->next;e=q->data;free(q);cout<<"被刪除的元素數(shù)據(jù)為"<<e<<"\n";return0;}查找：intGetElem(LinkList&L,inti,int&e){LinkListp=L->next;intj=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)return0;e=p->data;cout<<"該元素的值為"<<e<<"\n";return1;}排序：LinkListSort(LinkListL){ LinkListp,q; inttemp; for(p=L;p!=NULL;p=p->next) { for(q=p->next;q!=NULL;q=q->next) { if(p->data>q->data) { temp=q->data; q->data=p->data; p->data=temp; } } } returnL;}合并:voidMergeList_L(LinkList&L,LinkList&La,LinkList&Lb){LinkListp,pa,pb; p=L->next; pa=La->next; Lb=pb=L;//用L的頭結(jié)點作為Lb的頭結(jié)點 while(p&&pa){ if(p->data<=pa->data){ pb->next=p; pb=p; p=p->next; } else{ pb->next=pa; pb=pa; pa=pa->next; } } pb->next=p?p:pa; free(La);}完成函數(shù)框架后開始寫主函數(shù)，先輸入一個鏈表L，然后出現(xiàn)功能欄目，可供選擇，此處應(yīng)做一個循環(huán)，使其可不斷對該鏈表L操作，用多支選擇語句加上do…while循環(huán)。intmain(){LinkListL; intn,s,e,i,f,g,h; cout<<"輸入鏈表長度n:"; cin>>n; cout<<"請輸入L中的元素:"<<endl; CreateList(L,n); cout<<"輸入的鏈表為:"<<""; LNode*q=L->next;while(q){cout<<q->data<<"";q=q->next;} cout<<endl; intchoice; cout<<"請選擇功能:"<<endl; cout<<"1.插入元素"<<endl; cout<<"2.刪除元素"<<endl; cout<<"3.查找元素"<<endl; cout<<"4.給元素排序"<<endl; cout<<"5.合并鏈表"<<endl; cout<<"0.退出程序"<<endl; cout<<"PS:若先排序再合并，可將得到新的排序后的合并鏈表。"<<endl; do{ cout<<endl; cout<<"請選擇功能:"<<endl; cin>>choice; switch(choice) { case1: { cout<<"輸入插入的位置:"; cin>>s;cout<<"輸入插入的數(shù)據(jù)元素:"; cin>>e; ListInsert(L,s,e);cout<<"插入后的鏈表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case2: { cout<<"輸入刪除位置:"; cin>>g; ListDelete(L,g,h); cout<<"刪除后的鏈表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case3: { cout<<"輸入查找位置:"; cin>>i; GetElem(L,i,f); break; } case4: { LinkListp; Sort(L); cout<<"排序后的鏈表為:"<<endl; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case5: { LinkListLa,Lb; intm; cout<<"請輸入另一個鏈表La的長度m:"; cin>>m; cout<<"請輸入La中的元素:"<<endl; CreateList(La,m); cout<<"輸入的鏈表La為:"<<""; LNode*q=La->next; while(q){ cout<<q->data<<""; q=q->next; } Sort(La);MergeList_L(L,La,Lb); cout<<endl;cout<<"合并后的鏈表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } } } while(choice!=0); return0;}數(shù)組：同理，代碼附在報告后。實驗結(jié)果分析與總結(jié)1、程序運行結(jié)果（請?zhí)峁┧瓿傻母鞯李}運行結(jié)果界面截圖）：2、在實驗過程中遇到的問題與解決方法：問題有很多，比如局部變量與全局變量的聲明，常常顧此失彼，此處概念仍然不清。數(shù)組的概念出從零開始的命名與使用者角度的轉(zhuǎn)換也常常忘記，所以經(jīng)常出現(xiàn)空出一位的表，那一位為系統(tǒng)隨機(jī)賦值。還有便是在值的傳遞上，思路不甚明確，導(dǎo)致常常斷開，不能調(diào)用函數(shù)后改變表的值。3、實驗過程中的發(fā)現(xiàn)與收獲，未解決或需進(jìn)一步解決的問題：在循環(huán)嵌套方面還是有些害怕，不能一次調(diào)試成功，常常需要加減來改變。收獲是學(xué)會了在寫代碼前畫流程圖來清晰思路，畢竟在算法這方面并不擅長，還需要更多的世間來適應(yīng)并練習(xí)。指導(dǎo)老師評閱意見指導(dǎo)老師：年月日填寫內(nèi)容時，可把表格擴(kuò)大。附：實驗源程序代碼順序表（鏈表）：//線性表（鏈表）#include<stdio.h>#include"malloc.h"#include<iostream>usingnamespacestd;typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;//創(chuàng)建一個長度為n的鏈表voidCreateList(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(inti=n;i>0;--i){LinkListp=(LinkList)malloc(sizeof(LNode));cin>>p->data;p->next=L->next;L->next=p;}}//在鏈表L第i個元素之前插入元素eintListInsert(LinkList&L,inti,inte){LinkListp=L;intj=0;while(p&&j<i-1){ p=p->next;++j;}if(!p||j>i-1)return0;LinkLists=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}//在鏈表L中刪除第i個元素，并由e返回其值intListDelete(LinkList&L,inti,int&e){LinkListp=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return0;LinkListq=p->next;p->next=q->next;e=q->data;free(q);cout<<"被刪除的元素數(shù)據(jù)為"<<e<<"\n";return0;}//查找第i個元素,并由e返回其值intGetElem(LinkList&L,inti,int&e){LinkListp=L->next;intj=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)return0;e=p->data;cout<<"該元素的值為"<<e<<"\n";return1;}//讓鏈表L中的元素按從小到大的順序排列LinkListSort(LinkListL){ LinkListp,q; inttemp; for(p=L;p!=NULL;p=p->next) { for(q=p->next;q!=NULL;q=q->next) { if(p->data>q->data) { temp=q->data; q->data=p->data; p->data=temp; } } } returnL;}//歸并L和La得到新的單鏈性表LbvoidMergeList_L(LinkList&L,LinkList&La,LinkList&Lb){LinkListp,pa,pb; p=L->next; pa=La->next; Lb=pb=L;//用L的頭結(jié)點作為Lb的頭結(jié)點 while(p&&pa){ if(p->data<=pa->data){ pb->next=p; pb=p; p=p->next; } else{ pb->next=pa; pb=pa; pa=pa->next; } } pb->next=p?p:pa; free(La);}intmain(){LinkListL; intn,s,e,i,f,g,h; cout<<"輸入鏈表長度n:"; cin>>n; cout<<"請輸入L中的元素:"<<endl; CreateList(L,n); cout<<"輸入的鏈表為:"<<""; LNode*q=L->next;while(q){cout<<q->data<<"";q=q->next;} cout<<endl; intchoice; cout<<"請選擇功能:"<<endl; cout<<"1.插入元素"<<endl; cout<<"2.刪除元素"<<endl; cout<<"3.查找元素"<<endl; cout<<"4.給元素排序"<<endl; cout<<"5.合并鏈表"<<endl; cout<<"0.退出程序"<<endl; cout<<"PS:若先排序再合并，可將得到新的排序后的合并鏈表。"<<endl; do{ cout<<endl; cout<<"請選擇功能:"<<endl; cin>>choice; switch(choice) { case1: { cout<<"輸入插入的位置:"; cin>>s;cout<<"輸入插入的數(shù)據(jù)元素:"; cin>>e; ListInsert(L,s,e);cout<<"插入后的鏈表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case2: { cout<<"輸入刪除位置:"; cin>>g; ListDelete(L,g,h); cout<<"刪除后的鏈表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case3: { cout<<"輸入查找位置:"; cin>>i; GetElem(L,i,f); break; } case4: { LinkListp; Sort(L); cout<<"排序后的鏈表為:"<<endl; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case5: { LinkListLa,Lb; intm; cout<<"請輸入另一個鏈表La的長度m:"; cin>>m; cout<<"請輸入La中的元素:"<<endl; CreateList(La,m); cout<<"輸入的鏈表La為:"<<""; LNode*q=La->next; while(q){ cout<<q->data<<""; q=q->next; } Sort(La);MergeList_L(L,La,Lb); cout<<endl;cout<<"合并后的鏈表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } } } while(choice!=0); return0;}順序表（數(shù)組）：//順序表(數(shù)組).cpp//#include"stdafx.h"#include<stdio.h>#include"malloc.h"#include<iostream>usingnamespacestd;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10structS{int*p;intlength;intlistsize;};//構(gòu)造一個空的線性表LintInitList(S&L){L.p=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.p)return0;L.length=0;L.listsize=LIST_INIT_SIZE;return1;}//在表中第i個位置之前插入新的元素eintListInsert(S&L,inti,inte){if(i<1||i>L.length+1)return0;if(L.length>=L.listsize){int*newbase=(int*)realloc(L.p,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)return0; L.p=newbase; L.listsize+=LISTINCREMENT;}int*q=&(L.p[i-1]);for(int*y=&(L.p[L.length-1]);y>=q;--y)*(y+1)=*y;*q=e;++L.length;return1;}//在表中刪除第i個元素，并用e返回其值intListDelete(S&L,inti,int&e){if((i<1)||(i>L.length))return0;int*k=&(L.p[i-1]);e=*k;int*q=L.p+L.length-1;for(++k;k<=q;++k)*(k-1)=*k;--L.length;return1;}//在表中查找某位置上的元素intGetElem(S&L,inti,int&e){if((i<1)||(i>L.length))return0;int*k=&(L.p[i-1]);e=*k;returne;}//給表中元素按從小到大的順序排序/*SLSort(S&L){ int*p; intn,t; for(intj=0;j<n-1;j++){ for(intk=0;k<n-j-1;k++){ if(p[k]>p[k+1]){ t=p[k+1]; p[k+1]=p[k]; p[k]=t; } } } for(inti=0;i<n;i++) cout<<p[i]<<endl; returnL;}*///與另一個表La合并成為新的表Lb//voidMergeList_L(S&L,S&La,S&Lb){//}voidLSort(S&L){inta=L.p[0];for(inti=1;i<L.length;++i){if(L.p[i]<L.p[i-1]){L.p[0]=L.p[i];for(intj=i-1;L.p[0]<L.p[j];--j)L.p[j+1]=L.p[j];L.p[j+1]=L.p[0];}}L.p[0]=a;}Smerge(S&L,S&La){ structSLb;int*p=L.p;int*pa=La.p;Lb.length=L.length+La.length;int*pb=Lb.p=(int*)malloc(Lb.length*sizeof(int));int*p_last=p+L.length-1;int*pa_last=pa+La.length-1;while(p<=p_last&&pa<=pa_last){if(*p<=*pa)*pb++=*p++;else*pb++=*pa++;}while(p<=p_last)*pb++=*p++;while(pa<=pa_last)*pb++=*pa++;returnLb;}intmain(){intn; structSlist;InitList(list); cout<<"輸入鏈表長度n:"; cin>>n; cout<<"請輸入L中的元素:"<<endl; for(inti=0;i<=n-1;i++) {cin>>list.p[i]; list.length++; }; cout<<"輸入的鏈表為:"<<endl; for(ints=0;s<=n-1;s++) { cout<<list.p[s]<<""; } cout<<endl; intchoice; cout<<"請選擇功能:"<<endl; cout<<"1.插入元素"<<endl; cout<<"2.刪除元素"<<endl; cout<<"3.查找元素"<<endl; cout<<"4.給元素排序"<<endl; cout<<"5.合并鏈表"<<endl; cout<<"0.退出程序"<<endl; do{ cout<<endl; cout<<"請選擇功能:"<<endl;