線性表操作實驗報告3頁

1、忻州師范學院計算機科學與技術系實 驗 報 告（第六組）組長：梁啟超組員：晉丹丹 張艷華馬軍 劉雪梅孫鈺林 劉濤忻州師范學院計算機科學與技術系實驗報告實驗名稱 線性表的操作 專業(yè)班級 計本1504班 姓名 梁啟超 學號 201508112036 指導教師 成績 日期 2016/9/26 組員分工 晉丹丹（頭插法構造單鏈表），張艷華（尾插法構造單鏈表;） 馬軍（遍歷單鏈表;）劉雪梅（按位序查找單鏈表;）孫鈺林（按值查找 單鏈表;） 劉濤（向單鏈表中插入元素;） 一、實驗目的熟練掌握線性表的類型定義方法、存儲方法及其基本運算（元素的插入、刪除等）的實現(xiàn)方法，培養(yǎng)綜合運用所學知識，根據(jù)具體問題進行數(shù)據(jù)

2、結構設計和算法設計的能力。二、實驗內容用鏈表建立線性表，并進行線性表相關操作。要求：要有良好的人機界面，有菜單形式實現(xiàn)，具備頭插法、尾插法建鏈表、插入、刪除、顯示、以及按值與位序查找的功能。三、實驗要求1在問題分析的基礎上選擇合適的存儲結構，進行算法設計，編制程序并上機調試成功。2按要求完成實驗報告。3保存和打印出程序的運行結果，并結合程序進行分析。四、實驗步驟1需求分析本演示程序用C語言編寫，要有良好的人機界面，實現(xiàn)線性表操作的基本功能：頭插法、尾插法建鏈表、插入、刪除、顯示、以及按值與位序查找的功能。1輸入的形式和輸入值的范圍：插入元素時需要輸入插入的位置和元素的值；刪除元素時輸入刪除元素

3、的位置；查找操作時需要輸入元素的值。在所有輸入中，元素的值都是整數(shù)。 2輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內容。其中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。 3程序所能達到的功能：完成單鏈表的生成、插入、刪除、查找操作 4測試數(shù)據(jù)2概要設計 1為了實現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：（1）createlist_l 初始化：頭插法構造單鏈表；（2）createlist_l2初始化：尾插法構造單鏈表；兩種二選一； （2）listinsert_l 操作結果：向單鏈表中插入元素;（3）listdelete_l操作結果：刪除單鏈表中的元素;

4、（4）printlist_l 操作結果：遍歷單鏈表;（5）getelem_l操作結果：按位序查找單鏈表; （6）locateElem_l操作結果按值查找單鏈表;各函數(shù)間關系如下:main()linklist/單鏈表結構scan()createlist_l listinsert_l listdelete_l printlist_l getelem_l locateElem_lcreatelist_l23詳細設計實現(xiàn)概要設計中定義的所有的數(shù)據(jù)類型，對每個操作給出偽碼算法。對主程序和其他模塊也都需要寫出偽碼算法。單鏈表定義typedef struct lnodeint data;struct lno

5、de *next;lnode,*linklist;單鏈表的生成、插入、刪除、查找操作linklist createlist_l(int n) int i; linklist l,p; l=(linklist)malloc(sizeof(lnode); l-next=NULL; printf(please input the data of :); for(i=n;i0;-i) p=(linklist)malloc(sizeof(lnode); scanf(%d,&p-data); p-next=l-next;l-next=p; return l;linklist createlist_l2(i

6、nt n) int i; linklist l,p,r; l=(linklist)malloc(sizeof(lnode); l-next=NULL;r=l; printf(please input the data of:); for(i=1;idata); p-next=NULL;r-next=p;r=p;return l;linklist listinsert_l(linklist l,int i,int e) int j; linklist p,s; p=l;j=0; while(p&jnext;+j; if(!p|ji-1)printf(data is not lefal!); s=

7、(linklist)malloc(sizeof(lnode); s-data=e;s-next=p-next; p-next=s; return l;linklist listdelete_l(linklist l,int i,int &e)int j; linklist p,q; p=l;j=0; while(p-next&jnext;+j; if(!(p-next)|ji-1)printf(data is note legal!); q=p-next;p-next=q-next;e=q-data;free(q);return l;void printlist_l(linklist l) l

8、inklist p; printf(the data of L is:n); for(p=l-next;p!=NULL;p=p-next) printf(%d,p-data); printf(n);int getelem_l(linklist l,int i) linklist p; int j,e; p=l-next;j=1; while(p&jnext;+j; if(!p|jdata; return e;int locateElem_l(linklist l,int e) linklist p=l-next; int j=1;while(p&p-data!=e)p=p-next;j+;if

9、(!p) return -1;else return j;4調試分析1)分析算法的總體結構，分清程序中各部分應實現(xiàn)的功能；2)調試方法通常有二種：總體調試、分塊調試。你主要采用哪種調試方法？ 總體調試：把算法組裝成單個程序，按C程序結構標準分層檢查調試； 分塊調試：把算法分拆成幾個功能模塊，按C程序結構標準分模塊調試；3)錯誤跟蹤有兩種方法：錯誤信息排查法、執(zhí)行路線跟蹤法。 錯誤信息排查法：根據(jù)錯誤信息進行分類排查，要求分析者對C的錯誤代碼要有足夠的了解和認識，有經(jīng)驗的程序員多用此法。 執(zhí)行路線跟蹤法：變量分析法（跟蹤變量的值）、插入標簽法（插入輸出標簽），這種方法適合初學者。4）調試分析不宜

10、面面俱到，具體寫出關鍵問題就行。分析如下：主函數(shù)main()首先調用顯示操作菜單函數(shù)scan()，再根據(jù)用戶輸入的數(shù)字選項分別調用以下函數(shù)：（1）createlist_l頭插法構造單鏈表；（2）createlist_l2尾插法構造單鏈表；兩種二選一； （2）listinsert_l向單鏈表中插入元素;（3）listdelete_l刪除單鏈表中的元素;（4）printlist_l遍歷單鏈表;（5）getelem_l按位序查找單鏈表; （6）locateElem_l按值查找單鏈表; 由上述結構可知，采用分功能模塊調試的方法較合理，即主要功能按以下順序實現(xiàn)：添加查找刪除遍歷。5使用說明與測試結果程序

11、名為TXL.exe，運行環(huán)境為DOS。程序執(zhí)行后顯示 （下圖為參考截圖例子。）第一次操作需選擇1或者2，并且只能選擇一種。程序執(zhí)行顯示我們選擇的的是頭插法構造單鏈表，輸入1后顯示要輸入幾個數(shù)1我們寫5個請輸入要插入的數(shù)據(jù)：我們插入15 25 35 45 55 遍歷單鏈表刪除表中第2個元素在第3個元素中插入68按位序查找單鏈表;查找第4個元素五、實驗總結（調試和運行程序過程中產(chǎn)生的問題及采取的措施；對算法的程序的討論、分析，改進設想以及其它經(jīng)驗教訓；對實驗方式、組織、設備、題目的意見和建議等）附源程序清單：#include#include typedef struct lnodeint data

12、;struct lnode *next;lnode,*linklist; linklist createlist_l(int n) int i; linklist l,p; l=(linklist)malloc(sizeof(lnode); l-next=NULL; printf(please input the data of :); for(i=n;i0;-i) p=(linklist)malloc(sizeof(lnode); scanf(%d,&p-data); p-next=l-next;l-next=p; return l;linklist createlist_l2(int n)

13、 int i; linklist l,p,r; l=(linklist)malloc(sizeof(lnode); l-next=NULL;r=l; printf(please input the data of:); for(i=1;idata); p-next=NULL;r-next=p;r=p;return l;linklist listinsert_l(linklist l,int i,int e) int j; linklist p,s; p=l;j=0; while(p&jnext;+j; if(!p|ji-1)printf(data is not lefal!); s=(link

14、list)malloc(sizeof(lnode); s-data=e;s-next=p-next; p-next=s; return l;linklist listdelete_l(linklist l,int i,int &e)int j; linklist p,q; p=l;j=0; while(p-next&jnext;+j; if(!(p-next)|ji-1)printf(data is note legal!); q=p-next;p-next=q-next;e=q-data;free(q);return l;void printlist_l(linklist l) linkli

15、st p; printf(the data of L is:n); for(p=l-next;p!=NULL;p=p-next) printf(%d,p-data); printf(n);int getelem_l(linklist l,int i) linklist p; int j,e; p=l-next;j=1; while(p&jnext;+j; if(!p|jdata; return e;int locateElem_l(linklist l,int e) linklist p=l-next; int j=1;while(p&p-data!=e)p=p-next;j+;if(!p)

16、return -1;else return j;int scan()int d ; printf( n); printf( 請選擇所要進行的操作，注意頭插法與尾插法建鏈表。 n); printf( 1.頭插法構造單鏈表; n); printf( 2.尾插法構造單鏈表; n); printf( 3.遍歷單鏈表; n); printf( 4.按位序查找單鏈表; n); printf( 5.按值查找單鏈表; n); printf( 6.向單鏈表中插入元素; n); printf( 7.刪除單鏈表中的元素; n); printf( n); printf(n); scanf(%d,&d);return

17、(d);void main()int quit=0,n,i,e; linklist l; printf( 單鏈表基本操作 n); printf( n); printf(第一次操作需選擇1或者2，并且只能選擇一種。 第6小組n); while(!quit) switch(scan() case 1:printf(please input n:); scanf(%d,&n); l=createlist_l(n);break; case 2:printf(please input n:); scanf(%d,&n); l=createlist_l2(n);break; case 3:printf(當前鏈表中元素為:n); printlist_l(l); break; case 4:printf(請輸入要查找的元素的位置in); scanf(%d,&i); if(getelem_l(l,i)=-1)printf(第i個元素不存在！); else printf(表中第%d個元素的值為:%dn,i,getelem_l(l,i); break; case 5:printf(請輸入要查找的元素的值en); scanf(%d,&e); if(locateElem_l(l,e)=-1)printf(該元素不存在！); else printf(順序表中%d的位置是：%dn,e,locateEle