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

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

2、;<b>　　1、設(shè)計(jì)目的：5</b></p><p><b>　　2、試驗(yàn)?zāi)康模?</b></p><p><b>　　二.實(shí)驗(yàn)環(huán)境7</b></p><p><b>　　三.實(shí)驗(yàn)學(xué)時7</b></p><p><b>　　四.實(shí)驗(yàn)內(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>　　七、實(shí)

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

6、;<b>　　一.目的</b></p><p><b>　　1、設(shè)計(jì)目的：</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è)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)

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

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

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

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

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

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

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

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

18、t類型用如下語句定義順序表L：</p><p>　　此時，L實(shí)際上只是一個機(jī)構(gòu)體變量，其有3個分量base、length及l(fā)istSize，但這 3個分量并沒有確切的值，并且base僅為一個指針量，還沒有與之對應(yīng)的順序表所需的存儲空間。因此在使用順序表L時，首先應(yīng)對其進(jìn)行初始化。所以此初始化操作的作用就是從內(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分量的值即為其長度。該操作的實(shí)現(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.該操作的實(shí)現(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即可。該操作的實(shí)現(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>　　當(dāng)順序表L非空時，數(shù)組下標(biāo)為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中的第一個元素（下標(biāo)為0的元素）開始一次與e進(jìn)行比較，若某個元素與e相等則返回其位序（下標(biāo)加1）。若未找到與e相等的元素，因?yàn)轫樞虮碇形恍蜃钚?因此可返回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>　　七、實(shí)驗(yàn)步驟與源程序</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)點(diǎn)和缺點(diǎn)</p><p><b>　　1、順序表的優(yōu)點(diǎn)：</b></p><p>　　(1)、實(shí)現(xiàn)方法簡單,各種高級語言中都有數(shù)組,容易實(shí)現(xiàn);</p><p>　　(2)、訪問元素的速度快,因?yàn)樵陧樞虮碇羞壿嫃埾噜彽膬蓚€元素

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

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

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

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