實驗一線性表

1、姓名:學號:時間:專業(yè)班級:數(shù)據(jù)結(jié)構(gòu)試驗報告線性表線性表一、實驗目的1 掌握線性結(jié)構(gòu)中順序表和鏈表的基本概念、基本操作和應用；2 掌握線性表的基本操作：建表、插入、刪除、輸出等運算在順序存儲結(jié)構(gòu)和鏈式存 儲結(jié)構(gòu)上的實現(xiàn)。3. 通過本次實習加深對高級語言 C語言的使用（特別是函數(shù)參數(shù)、指針類型、鏈表的使用） 熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)（順序結(jié)構(gòu)和鏈式結(jié)構(gòu)）上的實現(xiàn)。二、實驗內(nèi)容1. 編寫生成線性表的函數(shù)，線性表的元素從鍵盤輸入，分別使用順序和鏈式存儲結(jié)構(gòu)存 儲；2. 編寫在線性表中插入一個元素的函數(shù)；3. 編寫在線性表中刪除一個元素的函數(shù)；4. 編寫輸出線性表的函數(shù)；5. 編寫主函數(shù)，調(diào)

2、用以上各函數(shù)，以便能觀察出原線性表以及作了插入或刪除后線性表的屏幕輸出。三、實驗報告要求1. 畫出程序流程圖并做簡單分析2. 源代碼（包括主要結(jié)構(gòu)、主要語句、函數(shù)注釋說明）3. 運行結(jié)果（包括程序如何使用，輸入數(shù)據(jù)和輸出結(jié)果）4. 實驗體會和問題分析四、基本原理（一）線性表是最常用的而且也是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，線性表是N個數(shù)據(jù)元素的有限序列。例如26個英文元素的字母表（A, B, C, D, ）,其數(shù)據(jù)結(jié)構(gòu)的描述為：Linear_list=（D ， R）其中，D= ai lai 屬于 ElemSet, i=1 , 2, 3, , R=| i=2 , 3, 4,。本實驗是以數(shù)組的形式把線性表存

3、放在計算機內(nèi)存的一個連續(xù)的區(qū)域內(nèi)，這樣便有：LOC(ai +1)=LOC(ai )+mLOC（ai ）=L0+m*（i-1）其中，m是存放每個元素所占的內(nèi)存字數(shù)，L0是a的地址，即首地址。（二）程序說明插入一個新元素到第 i 個位置，既把元素 ai 向后移一個位置，成為元素 ai+1 ，把新元 素放入到第 i 個位置，其他元素依次后移。插入后的表長是n+1（n 是原表長）。修改第 i 個元素，到第 i 個位置是把元素 ai 沖掉后存上新值。刪除第i個元素就是把余后的元素依次向前移一個位置。即：以元素ai+i, a+2, , 依次取代ai，ai+i，。刪除后的表長是 n-1 （n是原表長）。（三

4、）線性表鏈式存儲（選作） 。五、實驗程序#include #include #define MAXSIZE 20/typedef int ElemType; / typedef structElemType aMAXSIZE; / int length; / SqList;/SqList a,b,c;void creat_list(SqList *L); void out_list(SqList L);數(shù)組最大界限數(shù)據(jù)元素類型一維數(shù)組子域表長度域順序存儲的結(jié)構(gòu)體類型void insert_sq(SqList *L,int i,ElemType e);ElemType delete_sq(SqL

5、ist *L,int i);int locat_sq(SqList L,ElemType e); /主函數(shù)void main()int i,k,loc;ElemType e,x; char ch;do printf(nnn);printf(n 1.建立線性表 );printf(n 2.插入數(shù)據(jù)元素);printf(n 3.刪除數(shù)據(jù)元素);printf(n 4.查找數(shù)據(jù)元素);printf(n 0.結(jié)束程序運行);printf(n=);printf(n 請輸入你的選擇 (1,2,3,4,0);scanf(%d,&k);switch(k)case 1:creat_list(&a);out_list

6、(a);break;case 2:printf(n 請輸入插入位置： );scanf(%d,&i);printf(n 請輸入要插入的數(shù)據(jù)元素值： ); scanf(%d,&e);insert_sq(&a,i,e);out_list(a);break;case 3:printf(n 請輸入刪除位置： );scanf(%d,&i);x=delete_sq(&a,i);out_list(a);if(x!=-1)printf(n 刪除數(shù)據(jù)元素為： %dn,x);elseprintf( 要刪除的數(shù)據(jù)元素不存在！ );break;case 4:printf(n 請輸入要查找的數(shù)據(jù)元素值： ); scanf

7、(%d,&e);loc=locat_sq(a,e);if(loc=-1)printf(n 未找到指定數(shù)據(jù)元素！ );elseprintf(n 已找到，數(shù)據(jù)元素位置是 %d,loc);break;while(k!=0);printf(n 按回車鍵，返回 .n);ch=getchar();/ 建立線性表void creat_list(SqList*L)int i;printf( 請輸入線性表的長度： );scanf(%d,&L-length);for(i=0;ilength;i+)printf( 數(shù)據(jù)元素 %d=,i);scanf(%d,&(L-ai);/ 輸出線性表void out_list(S

8、qList*L)int i;for(i=0;ilength-1;i+)printf(%10d,L-ai);/ 在線性表的第 i 個位置插入數(shù)據(jù)元素 e void insert_sq(SqList*L,int i,ElemType e) int j;if(iL-length)printf(n 輸入插入的位置不存在： ); for(j=L-length;j=i;j-)L-aj=L-aj-1;L-ai-1=e;L-length+;/ 刪除第 i 個數(shù)據(jù)元素，返回其值ElemType delete_sq(SqList*L,int i)int j,y;if(iL-length)return -1;y=L

9、-ai-1;for(j=i;jlength;j+) L-aj-1=L-aj;L-length-;return y;/ 查找值為 e 的元素，返回它的值in t locat_sq(SqList L,ElemType e) int i=0;while(i=L.le ngth-1 &L.ai!=e) i+；if(i=L.le ngth-1)return(i+1);elsereturn(-1);測試結(jié)果為：表元元元運 立入專束 建結(jié)12 3 4 0-專一兀元元元 注熄制據(jù)據(jù)齬據(jù)你的選擇1柱天的長度；40=11-22-33=41 2表兀元元運 線數(shù)數(shù)數(shù)禮 總?cè)胱锸?建結(jié) * L- 12 3 4 0請輸入你的選擇 W 川沁.0坨請輸入插入位置 2請輸入要祐入的數(shù)據(jù)元素值 51S23sin 恚元兀兀運 線數(shù)數(shù)數(shù)程 亠關(guān)錚束 建mm結(jié)1 Z 3 4 0請輸入你的選擇12,3.4.0)3|青輸入刪除位萱：21234刑除數(shù)據(jù)元素為 5素書行 表一亞兀元運 注捱s:fe序 灌12 3 4-0請輸入你的選擇1,2,3.054請輸入蓼查找的數(shù)據(jù)元素值 3 已找至h數(shù)據(jù)元素位置是孑表一兀元 兀運序 線數(shù)數(shù)數(shù)程 立AJ曇束 建結(jié)請輸入你的選擇1.2.3.4,0)0按回車鍵返回*if*ess 理ny key to cantinue六、實驗體會和問題分析運行結(jié)果為：Compili ng.