1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計設(shè)計題目： 順序表的基本實(shí)現(xiàn)和存儲結(jié)構(gòu) 學(xué)生姓名： 刁二亮 郭敏 顧大勝 吳晴 王瑋專業(yè)班級： 10計算機(jī)應(yīng)用(1)班 指導(dǎo)教師： 余 云 完成時間： 2011年12月3日 信息工程 院 計算機(jī)科學(xué) 系安徽新華學(xué)院課程設(shè)計成績評定表(?？?課題名稱 順序表基本實(shí)現(xiàn)和存儲結(jié)構(gòu)院 系信息工程學(xué)院年級專業(yè)10計應(yīng)1班成員姓名成員學(xué)號承擔(dān)的任務(wù)成 績刁二亮 程序編寫及文檔匯總干敏 程序編寫及文字部分編寫顧大勝 程序編寫及文檔排版吳晴 程序編寫及概述編寫王瑋 程序編寫課題設(shè)計目的與設(shè)計意義1、 課題設(shè)計目的：了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力；

2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。2、課題設(shè)計意義：鍛煉我們的編碼能力，真正理解數(shù)據(jù)結(jié)構(gòu)的編碼思想,并且鍛煉我們的動手能力和成員間的配合，提高程序編寫能力。在信息傳遞時，希望長度能盡可能短，即采用最短碼。順序的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲空間和計算機(jī)網(wǎng)絡(luò)的傳送時間。指導(dǎo)教師：余云2011年 12月 3日目 錄一.目的51、設(shè)計目的：52、試驗(yàn)?zāi)康模?二.實(shí)驗(yàn)環(huán)境7三.實(shí)驗(yàn)學(xué)時

3、7四.實(shí)驗(yàn)內(nèi)容7五.需求分析7六.概述81、順序表的概述：82、.初始化操作：83、.求長度操作：94、.判空操作：95、.清空操作：106、取元素操作：107、按值查找操作：118、插入操作：129、刪除操作：13七、實(shí)驗(yàn)步驟與源程序14八、程序測試結(jié)果18九、順序表的優(yōu)點(diǎn)和缺點(diǎn)191、順序表的優(yōu)點(diǎn)：202、順序表的缺點(diǎn)：20十、總結(jié)20一.目的1、設(shè)計目的：數(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)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲

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

5、設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達(dá)到以下目的：(1)、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力；(2)、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；(3)、提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；(4)、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法

6、和作風(fēng)。2、試驗(yàn)?zāi)康模?(1)、掌握線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)； (2)、熟練掌握順序表和鏈表基本算法的實(shí)現(xiàn)； (3)、掌握利用線性表數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的方法和基本技巧； (4)、按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（編寫、調(diào)試算法程序，提交程序清單及及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果）； (5)、按時提交實(shí)驗(yàn)報告二.實(shí)驗(yàn)環(huán)境計算機(jī)、C語言程序設(shè)計環(huán)境。三.實(shí)驗(yàn)學(xué)時10學(xué)時，必做實(shí)驗(yàn)。四.實(shí)驗(yàn)內(nèi)容1、實(shí)現(xiàn)順序表的基本操作，線性表中數(shù)據(jù)元素類型為 結(jié)構(gòu)體，成員包括學(xué)生的姓名、學(xué)號、若干課程的成績（int型），按照順序存儲結(jié)構(gòu)實(shí)現(xiàn)如下算法： (1)、創(chuàng)建任意線性表，長度限定在100個學(xué)生信息之內(nèi)

7、； (2)、打?。ū闅v）該線性表（依次打印出表中元素值）； (3)、在線性表中查找第i個元素，并返回其值； (4)、在線性表中第i個元素之前插入一已知元素； (5)、在線性表中刪除第i個元素；五.需求分析線性表的順序存儲結(jié)構(gòu)是把線性表中所有數(shù)據(jù)元素，按照其邏輯順序一次存儲到計算機(jī)存儲器中從指定位置開始的一塊連續(xù)的存儲空間中，數(shù)據(jù)元素間的存儲（物理）位置即表示了它的邏輯位置。也就是說，邏輯上的第一個元素就存放在指定的第一個位置，邏輯上的第二個元素就存放在指定的空間的第二個元素，.依次類推。設(shè)線性表L=（a1,a2,a3,.an）,假定L中的每個元素需占用K個存儲單元，則在線性表存儲結(jié)構(gòu)中，L的第

8、i+1個元素的存儲地址Loc(ai+1)和第i個數(shù)據(jù)元素的存儲地址loc（ai）之間滿足下列關(guān)系： Loc(Ai+1)=Loc(Ai)+k一般地，線性表中第i個數(shù)據(jù)元素Ai的存儲地址為： Loc(Ai)=Loc(Ai)+(i-1)*k (1=n)其中，Loc(Ai)為線性表的第一個元素A1的存儲位置，通常又稱作線性表的起始地址或基地址，n為線性表的表長。六.概述1、順序表的概述：通常把使用順序存儲實(shí)現(xiàn)的線性表稱為順序表線性表的順序存儲結(jié)構(gòu)是把線性表中所有數(shù)據(jù)元素，按照其邏輯順序一次存儲到計算機(jī)存儲器中從指定位置開始的一塊連續(xù)的存儲空間中，數(shù)據(jù)元素間的存儲（物理）位置即表示了它的邏輯位置。2、.

9、初始化操作： 在程序中，使用SqList類型用如下語句定義順序表L： 此時，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成為一個空表（將其長度 賦值為0）順序表的初始化操作算法見下：void initlist(sqlist *l,int initsize) l-base=(int *)malloc(initsize

10、* sizeof(int);if(l-base=NULL)return -2;l-length=0;l-listsize=initsize;return 1;3、.求長度操作： 順序表L的length分量的值即為其長度。該操作的實(shí)現(xiàn)算法見下：int listlength(sqlist l)return l-length;4、.判空操作：判斷順序表L是否為空即判斷其length分量的值是否為0.該操作的實(shí)現(xiàn)算法見下：status lengthisempty(sqlist l)if(!l-length)return 1else return 05、.清空操作： 將順序表L清空，只需將length值

11、為0即可。該操作的實(shí)現(xiàn)算法見下：void clearlist(sqlist &l)l-length=0;6、取元素操作：當(dāng)順序表L非空時，數(shù)組下標(biāo)為i-1的元素即為其第i個元素。該操作算法見下：status getelem(sqlist l,int i,lelemtype &e)if(!l-length)return 0;e=l-basei-1;return 1;7、按值查找操作：該操作用來在順序表L中查找死一個與給定的數(shù)據(jù)元素e值相等的元素，并返回其位序。所以可從L中的第一個元素（下標(biāo)為0的元素）開始一次與e進(jìn)行比較，若某個元素與e相等則返回其位序（下標(biāo)加1）。若未找到與e相等的元素，因?yàn)轫?/p>

12、序表中位序最小為1因此可返回0表示查找失敗。順序表的按值查找操作算法見下：int locateelem(sqlist l,lelemtype e)int i=0;while(ilength & *(l-base+i)!=e)i+;if(ilength)return i+1;else return 0;8、插入操作：在線性表L的第i個位置插入一個新的元素e，則原來的第i個元素變?yōu)榈趇+1個，原來的第i+1個元素就變?yōu)榈趇+2依次類推。該操作算法見下：void insertlist(sqlist *l,int i,int e)lelemtype *newbase; int j;if(i1 | il

13、ength+1)printf(不合理);return 0;if(l-length=l-listsize)printf(滿表);return 0;for(j=l-length-1;j=i-1;j-)l-basej+1=l-basej;l-basei-1=e;l-length+;return 1; 9、刪除操作：該操作作用于刪除順序表L的第i（0i=ListLength(L)）個數(shù)據(jù)元素并用e返回其值.時原來的長度為n的順序表變成長度為n-1.該操作算法見下:void deletelist(sqlist *l,int i) int j;if(il-length-1)printf(不合理);retu

14、rn 0;if(l-length=0)printf(空表);return 0;for(j=1;jbasej=l-basej+1;l-length-;return 1;七、實(shí)驗(yàn)步驟與源程序#include #define listspaceincr 10typedef structint *base;int length;int listsize;sqlist;void initlist(sqlist *l,int initsize) l-base=(sqlist*)malloc(sizeof(sqlist);if(!l-base)return;l-length=0;l-listsize=ini

15、tsize;void creatlist(sqlist *l)int i;for(i=0;ilength;i+)scanf(%d,&l-basei);void print(sqlist *l) int i;for(i=0;ilength;i+)printf(%6d,l-basei);void insertlist(sqlist *l,int i,int e)int *newbase;int j;if(il-length+1)return 0;if(l-length=l-listsize)newbase=(int*)realloc(l-base,(l-listsize+listspaceincr

16、) *sizeof(int);if(!newbase)return -2;l-base=newbase;l-listsize+=listspaceincr;for(j=l-length-1;j=i-1;j-)l-basej+1=l-basej;l-basei-1=e;l-length+;return 1;void deletelist(sqlist *l,int i)int j;if(il-length)return 0;for(j=i;jlength;j+)l-basej-1=l-basej;l-length-;return 1; void main()int flag=1,a,i,e,n,

17、j;sqlist l;while(flag)printf(ntt1:初始化ntt2:建立順序表ntt3:輸出順序表ntt4:在順序表中插入元素ntt5:在順序表中刪除元素ntt:其他退出n);printf(ntt請選擇:);scanf(%d,&a);switch(a) case 1: printf(n請輸入初始化空間的大小:); scanf(%d,&n); initlist(&l,n); break; case 2: printf(n請輸入順序表的元素個數(shù):); scanf(%d,&l.length); creatlist(&l); break; case 3:print(&l); break

18、; case 4:printf(n請輸入插入的位置與插入的元素:); scanf(%d%d,&i,&e); insertlist(&l,i,e); break; case 5:printf(n請輸入刪除的位置:); scanf(%d,&j); deletelist(&l,j); break; default :flag=0;八、程序測試結(jié)果選擇“從文件讀取信息”，程序?qū)奈募x取信息，如果讀取失?。ú淮嬖谠撔畔⑽募瑒t結(jié)束，如果讀取成功，則輸出讀取成功的提示信息， 九、順序表的優(yōu)點(diǎn)和缺點(diǎn)1、順序表的優(yōu)點(diǎn)：(1)、實(shí)現(xiàn)方法簡單,各種高級語言中都有數(shù)組,容易實(shí)現(xiàn);(2)、訪問元素的速度快,因?yàn)樵陧樞虮碇羞壿嫃埾噜彽膬蓚€元素在存儲位置上也必定相鄰,所以只要知道了第一個元素的地址,其他任何一個元素的地址都可以通過簡單的計算求的,故可實(shí)現(xiàn)隨即存取,即順序表L的第i個元素即為L.basei-1.2、順序表的缺點(diǎn)：(1)、需占用連續(xù)的空間.存儲要求高,不能利用小塊存儲區(qū);(2)、由于在順序表中邏輯上相鄰的兩