數(shù)據(jù)結(jié)構(gòu)順序表課程設(shè)計--順序表基本實現(xiàn)和存儲結(jié)構(gòu)

1、<p>　　數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計</p><p>　　設(shè)計題目： 順序表的基本實現(xiàn)和存儲結(jié)構(gòu) </p><p>　　課程設(shè)計成績評定表(?？?</p><p><b>　　目 錄</b></p><p><b>　　一.目的5</b></p><p>

2、;<b>　　1、設(shè)計目的：5</b></p><p><b>　　2、試驗?zāi)康模?</b></p><p><b>　　二.實驗環(huán)境7</b></p><p><b>　　三.實驗學(xué)時7</b></p><p><b>　　四.實驗內(nèi)容

3、7</b></p><p><b>　　五.需求分析7</b></p><p><b>　　六.概述8</b></p><p>　　1、順序表的概述：8</p><p>　　2、.初始化操作：8</p><p>　　3、.求長度操作：9</p&g

4、t;<p>　　4、.判空操作：9</p><p>　　5、.清空操作：10</p><p>　　6、取元素操作：10</p><p>　　7、按值查找操作：11</p><p>　　8、插入操作：12</p><p>　　9、刪除操作：13</p><p>　　七、實

5、驗步驟與源程序14</p><p>　　八、程序測試結(jié)果18</p><p>　　九、順序表的優(yōu)點和缺點19</p><p>　　1、順序表的優(yōu)點：20</p><p>　　2、順序表的缺點：20</p><p><b>　　十、總結(jié)20</b></p><p>

6、;<b>　　一.目的</b></p><p><b>　　1、設(shè)計目的：</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)

7、據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。</p><p>　　在當今信息時代，信息技術(shù)己成為當代知識經(jīng)濟的核心技術(shù)。我們時刻都在和數(shù)據(jù)打交道。比如人們在外出工作時找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠程教育報名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實際上，現(xiàn)實世界中的實體經(jīng)過抽象以后，就可以成為計算機上所處理

8、的數(shù)據(jù)。</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p>　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表

9、示出來并對它們進行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：</p><p>　　(1)、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；</p><p>　　(2)、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；</p><p>　　(3)、提高

10、綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；</p><p>　　(4)、訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風。</p><p><b>　　2、試驗?zāi)康模?lt;/b></p><p>　　(1)、掌握線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)；</p><p>　　

11、(2)、熟練掌握順序表和鏈表基本算法的實現(xiàn)；</p><p>　　(3)、掌握利用線性表數(shù)據(jù)結(jié)構(gòu)解決實際問題的方法和基本技巧；</p><p>　　(4)、按照實驗題目要求獨立正確地完成實驗內(nèi)容（編寫、調(diào)試算法程序，提交程序清單及及相關(guān)實驗數(shù)據(jù)與運行結(jié)果）；</p><p>　　(5)、按時提交實驗報告</p><p><b>　　

12、二.實驗環(huán)境</b></p><p>　　計算機、C語言程序設(shè)計環(huán)境。</p><p><b>　　三.實驗學(xué)時</b></p><p>　　10學(xué)時，必做實驗。</p><p><b>　　四.實驗內(nèi)容</b></p><p>　　1、實現(xiàn)順序表的基本操作，線性

13、表中數(shù)據(jù)元素類型為 結(jié)構(gòu)體，成員包括學(xué)生的姓名、學(xué)號、若干課程的成績（int型），按照順序存儲結(jié)構(gòu)實現(xiàn)如下算法： (1)、創(chuàng)建任意線性表，長度限定在100個學(xué)生信息之內(nèi)； (2)、打印（遍歷）該線性表（依次打印出表中元素值）； (3)、在線性表中查找第i個元素，并返回其值； (4)、在線性表中第i個元素之前插入一已知元素； (5)、在線性表中刪除第i個元素；</p><p>

14、;<b>　　五.需求分析</b></p><p>　　線性表的順序存儲結(jié)構(gòu)是把線性表中所有數(shù)據(jù)元素，按照其邏輯順序一次存儲到計算機存儲器中從指定位置開始的一塊連續(xù)的存儲空間中，數(shù)據(jù)元素間的存儲（物理）位置即表示了它的邏輯位置。也就是說，邏輯上的第一個元素就存放在指定的第一個位置，邏輯上的第二個元素就存放在指定的空間的第二個元素，…..依次類推。</p><p>　　

15、設(shè)線性表L=（a1,a2,a3,….an）,假定L中的每個元素需占用K個存儲單元，則在線性表存儲結(jié)構(gòu)中，L的第i+1個元素的存儲地址Loc(ai+1)和第i個數(shù)據(jù)元素的存儲地址loc（ai）之間滿足下列關(guān)系：</p><p>　　Loc(Ai+1)=Loc(Ai)+k</p><p>　　一般地，線性表中第i個數(shù)據(jù)元素Ai的存儲地址為：</p><p>　　Loc(

16、Ai)=Loc(Ai)+(i-1)*k (1<=i && i>=n)</p><p>　　其中，Loc(Ai)為線性表的第一個元素A1的存儲位置，通常又稱作線性表的起始地址或基地址，n為線性表的表長。</p><p><b>　　六.概述</b></p><p><b>　　1、順序表的概述：</

17、b></p><p>　　通常把使用順序存儲實現(xiàn)的線性表稱為順序表線性表的順序存儲結(jié)構(gòu)是把線性表中所有數(shù)據(jù)元素，按照其邏輯順序一次存儲到計算機存儲器中從指定位置開始的一塊連續(xù)的存儲空間中，數(shù)據(jù)元素間的存儲（物理）位置即表示了它的邏輯位置。</p><p><b>　　2、.初始化操作：</b></p><p>　　在程序中，使用SqLis

18、t類型用如下語句定義順序表L：</p><p>　　此時，L實際上只是一個機構(gòu)體變量，其有3個分量base、length及l(fā)istSize，但這 3個分量并沒有確切的值，并且base僅為一個指針量，還沒有與之對應(yīng)的順序表所需的存儲空間。因此在使用順序表L時，首先應(yīng)對其進行初始化。所以此初始化操作的作用就是從內(nèi)存中申請一塊可共使用順序表L使用的大小為InitSize的存儲空間。并使L成為一個空表（將其長度 賦值為

19、0）</p><p>　　順序表的初始化操作算法見下：</p><p>　　void initlist(sqlist *l,int initsize)</p><p><b>　　{</b></p><p>　　l->base=(int *)malloc(initsize * sizeof(int));</p

20、><p>　　if(l->base==NULL)</p><p>　　return -2;</p><p>　　l->length=0;</p><p>　　l->listsize=initsize;</p><p><b>　　return 1;</b></p>&l

21、t;p><b>　　}</b></p><p><b>　　3、.求長度操作：</b></p><p>　　順序表L的length分量的值即為其長度。該操作的實現(xiàn)算法見下：</p><p>　　int listlength(sqlist l){</p><p>　　return l->l

22、ength;</p><p><b>　　}</b></p><p><b>　　4、.判空操作：</b></p><p>　　判斷順序表L是否為空即判斷其length分量的值是否為0.該操作的實現(xiàn)算法見下：</p><p>　　status lengthisempty(sqlist l)</

23、p><p><b>　　{</b></p><p>　　if(!l->length)</p><p><b>　　return 1</b></p><p><b>　　else </b></p><p><b>　　return 0</

24、b></p><p><b>　　}</b></p><p><b>　　5、.清空操作：</b></p><p>　　將順序表L清空，只需將length值為0即可。該操作的實現(xiàn)算法見下：</p><p>　　void clearlist(sqlist &l)</p>&

25、lt;p><b>　　{</b></p><p>　　l->length=0;</p><p><b>　　}</b></p><p><b>　　6、取元素操作：</b></p><p>　　當順序表L非空時，數(shù)組下標為i-1的元素即為其第i個元素。該操作算法見下

26、：</p><p>　　status getelem(sqlist l,int i,lelemtype &e)</p><p><b>　　{</b></p><p>　　if(!l->length)</p><p><b>　　return 0;</b></p><

27、;p>　　e=l->base[i-1];</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　7、按值查找操作：</b></p><p>　　該操作用來在順序表L中查找死一個與給定的數(shù)據(jù)元素e值

28、相等的元素，并返回其位序。所以可從L中的第一個元素（下標為0的元素）開始一次與e進行比較，若某個元素與e相等則返回其位序（下標加1）。若未找到與e相等的元素，因為順序表中位序最小為1因此可返回0表示查找失敗。順序表的按值查找操作算法見下：</p><p>　　int locateelem(sqlist l,lelemtype e)</p><p><b>　　{</b>

29、;</p><p><b>　　int i=0;</b></p><p>　　while(i<l->length && *(l->base+i)!=e)</p><p><b>　　i++;</b></p><p>　　if(i<l->length)&l

30、t;/p><p>　　return i+1;</p><p><b>　　else </b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　8、插入操作：</b&

31、gt;</p><p>　　在線性表L的第i個位置插入一個新的元素e，則原來的第i個元素變?yōu)榈趇+1個，原來的第i+1個元素就變?yōu)榈趇+2……依次類推。該操作算法見下：</p><p>　　void insertlist(sqlist *l,int i,int e)</p><p><b>　　{</b></p><p>

32、;　　lelemtype *newbase;</p><p><b>　　int j;</b></p><p>　　if(i<1 || i<l->length+1)</p><p>　　printf("不合理");</p><p><b>　　return 0;</b

33、></p><p>　　if(l->length==l->listsize)</p><p>　　{printf("滿表");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p&g

34、t;　　for(j=l->length-1;j>=i-1;j--)</p><p>　　l->base[j+1]=l->base[j];</p><p>　　l->base[i-1]=e;</p><p>　　l->length++;</p><p><b>　　return 1;</b&g

35、t;</p><p><b>　　}</b></p><p><b>　　9、刪除操作：</b></p><p>　　該操作作用于刪除順序表L的第i（0<i<=ListLength(L)）個數(shù)據(jù)元素并用e返回其值.時原來的長度為n的順序表變成長度為n-1.該操作算法見下:</p><p>

36、;　　void deletelist(sqlist *l,int i)</p><p><b>　　{</b></p><p><b>　　int j;</b></p><p>　　if(i<0 || i>l->length-1)</p><p><b>　　{</

37、b></p><p>　　printf("不合理");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　if(l->length==0)</p><p><b>　　

38、{</b></p><p>　　printf("空表");</p><p><b>　　return 0;</b></p><p>　　for(j=1;j<l-length-1;j++)</p><p>　　l->base[j]=l->base[j+1];</p&g

39、t;<p>　　l->length--;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　七、實驗步驟與源程序</p><p>　　#include <stdio.h></p><

40、p>　　#define listspaceincr 10</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int *base;</p><p>　　int length;</p><p>　　int listsize;</p

41、><p><b>　　}sqlist;</b></p><p>　　void initlist(sqlist *l,int initsize)</p><p><b>　　{</b></p><p>　　l->base=(sqlist*)malloc(sizeof(sqlist));</p&

42、gt;<p>　　if(!l->base)</p><p><b>　　return;</b></p><p>　　l->length=0;</p><p>　　l->listsize=initsize;</p><p><b>　　}</b></p>

43、<p>　　void creatlist(sqlist *l)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i<l->length;i++)</p><p>　　scanf("%d&qu

44、ot;,&l->base[i]);</p><p><b>　　}</b></p><p>　　void print(sqlist *l)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p&

45、gt;　　for(i=0;i<l->length;i++)</p><p>　　printf("%6d",l->base[i]);</p><p><b>　　}</b></p><p>　　void insertlist(sqlist *l,int i,int e)</p><p>

46、;<b>　　{</b></p><p>　　int *newbase;</p><p><b>　　int j;</b></p><p>　　if(i<1||i>l->length+1)</p><p><b>　　return 0;</b></p&g

47、t;<p>　　if(l->length==l->listsize){</p><p>　　newbase=(int*)realloc(l->base,(l->listsize+listspaceincr) *sizeof(int));</p><p>　　if(!newbase)</p><p>　　return -2;<

48、;/p><p>　　l->base=newbase;</p><p>　　l->listsize+=listspaceincr;</p><p><b>　　}</b></p><p>　　for(j=l->length-1;j>=i-1;j--)</p><p>　　l-&g

49、t;base[j+1]=l->base[j];</p><p>　　l->base[i-1]=e;</p><p>　　l->length++;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>

50、　　void deletelist(sqlist *l,int i)</p><p><b>　　{</b></p><p><b>　　int j;</b></p><p>　　if(i<1||i>l->length)return 0;</p><p>　　for(j=i;j&l

51、t;l->length;j++)</p><p>　　l->base[j-1]=l->base[j];</p><p>　　l->length--;</p><p>　　return 1; </p><p><b>　　}</b></p><p>　　void main()

52、</p><p><b>　　{</b></p><p>　　int flag=1,a,i,e,n,j;</p><p><b>　　sqlist l;</b></p><p>　　while(flag)</p><p><b>　　{</b></

53、p><p>　　printf("\n\t\t1:初始化\n\t\t2:建立順序表\n\t\t3:輸出順序表\n\t\t4:在順序表中插入元素\n\t\t5:在順序表中刪除元素\n\t\t:其他退出\n");</p><p>　　printf("\n\t\t請選擇:");</p><p>　　scanf("%d"

54、,&a);</p><p><b>　　switch(a)</b></p><p><b>　　{</b></p><p>　　case 1: printf("\n請輸入初始化空間的大小:");</p><p>　　scanf("%d",&n)

55、;</p><p>　　initlist(&l,n);</p><p><b>　　break;</b></p><p>　　case 2: printf("\n請輸入順序表的元素個數(shù):");</p><p>　　scanf("%d",&l.length);<

56、/p><p>　　creatlist(&l);</p><p><b>　　break;</b></p><p>　　case 3:print(&l);</p><p><b>　　break;</b></p><p>　　case 4:printf("

57、\n請輸入插入的位置與插入的元素:");</p><p>　　scanf("%d%d",&i,&e);</p><p>　　insertlist(&l,i,e);</p><p><b>　　break;</b></p><p>　　case 5:printf(&qu

58、ot;\n請輸入刪除的位置:");</p><p>　　scanf("%d",&j);</p><p>　　deletelist(&l,j);</p><p><b>　　break;</b></p><p>　　default :flag=0;</p><

59、;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　八、程序測試結(jié)果</b></p><p>　　選擇“從文件讀取信息”，程序?qū)奈募x取信息，如果讀取失?。ú淮嬖?/p>

60、該信息文件），則結(jié)束，如果讀取成功，則輸出讀取成功的提示信息，</p><p>　　九、順序表的優(yōu)點和缺點</p><p><b>　　1、順序表的優(yōu)點：</b></p><p>　　(1)、實現(xiàn)方法簡單,各種高級語言中都有數(shù)組,容易實現(xiàn);</p><p>　　(2)、訪問元素的速度快,因為在順序表中邏輯張相鄰的兩個元素

61、在存儲位置上也必定相鄰,所以只要知道了第一個元素的地址,其他任何一個元素的地址都可以通過簡單的計算求的,故可實現(xiàn)隨即存取,即順序表L的第i個元素即為L.base[i-1].</p><p><b>　　2、順序表的缺點：</b></p><p>　　(1)、需占用連續(xù)的空間.存儲要求高,不能利用小塊存儲區(qū);</p><p>　　(2)、由于在順

62、序表中邏輯上相鄰的兩個元素在存儲位置上也必定相鄰,所以在進行插入和刪除操作的時候,需要進行大量的元素移動操作,影響了算法的效率.</p><p><b>　　十、總結(jié)</b></p><p>　　由于本課題中的許多知識點都沒有學(xué)過都要靠自己到課外的資料中去查找。在用的時候難免出現(xiàn)這樣那樣的錯誤。如開始設(shè)計出來的菜單不是預(yù)想的那樣，而是總個窗中出現(xiàn)混亂。解決的這個問題的

63、辦法是調(diào)整。一個系統(tǒng)的菜單和提示信息非常重要。如果沒有這些用戶根本不知道怎么用你設(shè)計的這個系統(tǒng)。在設(shè)計的調(diào)試過程中也無法順利的完成調(diào)試工作。有了一個清晰簡單的菜單和一些提示信息這后，調(diào)試過程完成的非常順利。</p><p>　　回顧起此次課程設(shè)計，至今我仍感慨頗多，的確，從拿到題目到完成整個編程，從理論到實踐，雖然只有幾天，但可以學(xué)到很多的東西，不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的

64、知識。通過這次課程設(shè)計使我懂得了理論與實際相結(jié)合是很重要的，只有理論知識是遠遠不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到問題，難免會遇到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固，比如說結(jié)構(gòu)體……通過這次課程設(shè)計之后，一定把以前所學(xué)過的知識本次課程設(shè)計結(jié)束了，對于我的影響