用C語言設(shè)計(jì)順序表的相關(guān)函數(shù)庫

1、 胡 潔 用C語言設(shè)計(jì)順序表的相關(guān)函數(shù) 第16頁 共16 頁 用C語言設(shè)計(jì)順序表的相關(guān)函數(shù)庫學(xué)生姓名：胡潔 指導(dǎo)老師：黃敏摘 要 本課程設(shè)計(jì)主要是設(shè)計(jì)順序表的相關(guān)函數(shù)庫，以便在程序設(shè)計(jì)中調(diào)用。在此課程設(shè)計(jì)中，系統(tǒng)開發(fā)平臺為Windows XP，程序設(shè)計(jì)語言采用面向過程的程序設(shè)計(jì)的C語言，程序運(yùn)行平臺為Visual C+ 6.0。在程序設(shè)計(jì)中，采用了結(jié)構(gòu)化與面向過程兩種解決問題的方法。程序通過調(diào)試運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)，并且經(jīng)過適當(dāng)完善后，將可以應(yīng)用在商業(yè)中解決實(shí)際問題。關(guān)鍵詞 順序表；程序設(shè)計(jì)；函數(shù)庫；Visual C+ 6.01 引 言本課程設(shè)計(jì)主要解決的是設(shè)計(jì)順序表的相關(guān)函數(shù)，以便在程序

2、調(diào)用中調(diào)用，進(jìn)行順序表中元素的輸入、查找、取出、刪除等操作的課程設(shè)計(jì)。順序表是線性表的順序存儲，是指在內(nèi)存中用一段地址連續(xù)的存儲空間來依次順序存放線性表中的各元素的存儲方式。其邏輯上與物理上均相鄰，不會增加額外的存儲開銷；順序表具有按序號隨機(jī)訪問的特點(diǎn)，采取直接存取結(jié)構(gòu)，若提供序號訪問數(shù)據(jù)元素，則其算法簡潔、快速、易讀、易懂。121.1 課程設(shè)計(jì)目的（1） 訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題；（2） 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；（3） 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能

3、力；（4） 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。1.2 課程設(shè)計(jì)任務(wù)和要求（1） 任務(wù)： 設(shè)計(jì)出順序表結(jié)構(gòu)的相關(guān)函數(shù)庫，以便在程序設(shè)計(jì)中調(diào)用。（2）要求： 包括線性表的各種基本函數(shù)以及常用函數(shù)（自己確定函數(shù)、函數(shù)形式及理由）； 最好能借助語言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便能將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運(yùn)行過程以動(dòng)態(tài)方式顯示出來； 給出若干例程，演示通過調(diào)用自己的庫函數(shù)來實(shí)現(xiàn)相關(guān)問題的求解。2 數(shù)據(jù)庫中的函數(shù)2.1 函數(shù)庫中函數(shù)清單在此課程設(shè)計(jì)中主要是設(shè)計(jì)順序表的函數(shù)庫，以便于調(diào)用

4、，其函數(shù)清單如表2-1所示。表2-1 順序表函數(shù)庫清單函數(shù)聲明功能聲明int Insert_Seqlist();插入一個(gè)元素到順序表中，若空間已滿及插入位置無效報(bào)錯(cuò)，否則插入成功。int Delete_Seqlist();刪除順序表中的一個(gè)元素，若表為空及刪除位置不合法報(bào)錯(cuò)，否則刪除成功。int Locate_Seqlist();若查找元素存在，則返回元素存儲位置。int Get_Seqlist()；若查找元素存在，則返回元素下標(biāo)。void print();輸出順序表中的所有元素。2.2 函數(shù)實(shí)現(xiàn)的具體算法列舉（1）插入函數(shù)：int Insert_Seqlist(Seqlist *L,int

5、i,datatype e) int j; if(L->len=MAXSIZE-1)printf("表滿溢出n");return -1; /*表空間已滿，不能插入*/ if(i<1|i>L->len+2) /*檢查插入位置i是否有效*/ printf("位置錯(cuò)n");return 0; for(j=L->len;j>=i-1;j-) L->dataj+1=L->dataj; /*節(jié)點(diǎn)往后移動(dòng)一個(gè)位置*/ L->datai-1=e; /*插入新元素e*/ L->len+; /*len仍指向最后一個(gè)元

6、素*/ return 1; /*插入操作成功，返回*/（2）刪除函數(shù)：int Delete_Seqlist(Seqlist *L,int i) int j; if(i<1|i>L->len+1) /*檢查空表及刪除位置的合法性*/ printf("不存在第d%個(gè)元素n,i");return 0; for(j=i;j<L->len;j+) L->dataj-1=L->dataj; /*向前移動(dòng)一個(gè)位置*/ L->len-; return 1; /*刪除成功*/（3）取出一個(gè)元素函數(shù)：int Get_Seqlist(Seqlist

7、 *L,int i) if(i<1|i>L->len+1) /*檢查查找位置的合法性*/ printf("不存在第d%個(gè)元素n",i);return 0; /*查找元素不存在*/ else return L->datai-1; /*查找成功，返回該元素下標(biāo)*/3 課程設(shè)計(jì)思路 一般地說，其過程如下：a.分析順序表特點(diǎn)b.分析順序表功能以及操作c.設(shè)計(jì)函數(shù)庫d.制定調(diào)試計(jì)劃：初步的調(diào)試計(jì)劃e.編寫主函數(shù)，方面后面的測試f.制定完整程序的測試計(jì)劃g.書寫文檔：系統(tǒng)說明h.復(fù)核和審查:從技術(shù)的角度審查，從管理的角度審查。3.1 分析順序表 （1）順序表的優(yōu)

8、點(diǎn)： 方法簡單，各種高級語言中都有數(shù)組，容易實(shí)現(xiàn)；邏輯上相鄰，物理上也相鄰，所以不需要指針來體現(xiàn)數(shù)據(jù)元素間的邏輯關(guān)系，不增加額外的存儲開銷；順序表具有按序號隨機(jī)訪問的特點(diǎn)，采取直接存取結(jié)構(gòu)，若提供序號訪問數(shù)據(jù)元素，則其算法簡潔、快速。易讀、易懂。（2） 順序表的缺點(diǎn)：等概率情況下做插入和刪除操作時(shí)，需要平均移動(dòng)大約表中一半的元素，所以如果n較大，則做插入和刪除的效率較低；一般采用數(shù)組來定義順序表，而數(shù)組是一種靜態(tài)分配結(jié)構(gòu)，不是執(zhí)行時(shí)按需分配空間，所以為了操作方便，一般都會預(yù)先分配足夠大的存儲空間，但如果預(yù)先分配過大，則可能導(dǎo)致順序表后部空間大量閑置，造成空間浪費(fèi)，如果預(yù)先分配過小，則又會因空間

9、不足造成溢出；由于數(shù)組需要占用連續(xù)的空間存儲，所以一些累計(jì)數(shù)量雖然超過所需要存儲空間，但不連續(xù)的零散空間并不能得到利用，造成“碎片”現(xiàn)象，從而導(dǎo)致整個(gè)內(nèi)存空間利用率下降。134而課程設(shè)計(jì)中，我們著重考慮的是順序表的結(jié)構(gòu)，對于順序表，我們可以進(jìn)行的操作有輸入、插入、刪除、取出等。3.2 設(shè)計(jì)函數(shù)庫設(shè)計(jì)函數(shù)庫不能隨心所欲、想編寫什么函數(shù)就編寫什么函數(shù)，而是要根據(jù)分析順序表所得結(jié)果，從分析結(jié)果入手。又分析我們知道順序表可以進(jìn)行的操作有：輸入、輸出、插入一個(gè)元素、刪除一個(gè)元素、查找一個(gè)元素、取出一個(gè)元素。根據(jù)這些操作分別寫出函數(shù)：int Insert_Seqlist(); /*插入元素*/int De

10、lete_Seqlist(); /*刪除元素*/int Locate_Seqlist(); /*查找元素*/int Get_Seqlist()； /*取出元素*/void print(); /*輸出元素*/3.3 編寫主函數(shù)函數(shù)庫設(shè)計(jì)完之后，還要進(jìn)行調(diào)試，就需要編寫一個(gè)主函數(shù)來測試函數(shù)的有效性與正確性。在主函數(shù)中調(diào)用函數(shù)庫中的函數(shù)實(shí)現(xiàn)其功能，主函數(shù)中使用一個(gè)switch功能進(jìn)行條件判斷，當(dāng)輸入選項(xiàng)不一樣的時(shí)候，調(diào)用的函數(shù)不一樣，從而對順序表中的元素實(shí)現(xiàn)不同的操作。3.4 書寫文檔按著格式編寫文檔并檢查，保證論文沒有錯(cuò)誤。4 程序運(yùn)行結(jié)果4.1 確定順序表中元素個(gè)數(shù)在程序中，順序表元素的個(gè)數(shù)以及

11、元素都是自己在運(yùn)行時(shí)進(jìn)行輸入的，輸入完后按Enter進(jìn)入選項(xiàng)選擇。其顯示如圖4-1：4-1輸入元素4.2 顯示順序表中所有元素利用switch的功能輸入1顯示所有元素，結(jié)果如圖4-2:4-2顯示所有元素4.3 在順序表中插入一個(gè)元素利用switch的功能輸入2插入一個(gè)元素，結(jié)果如圖4-3:4-3插入一個(gè)元素4.4 刪除順序表中一個(gè)元素利用switch的功能輸入3刪除一個(gè)元素，結(jié)果如圖4-4:4-4刪除一個(gè)元素4.5 確定順序表中元素個(gè)數(shù)利用switch的功能輸入4按值查找一個(gè)元素，結(jié)果如圖4-5:4-5按值查找一個(gè)元素4.6 取出順序表中一個(gè)元素利用switch的功能輸入5取出一個(gè)元素，結(jié)果如

12、圖4-6:4-6取出一個(gè)元素4.7 退出程序利用switch功能輸入6退出程序。5 結(jié)束語在課程設(shè)計(jì)中，使用C語言來設(shè)計(jì)順序表的相關(guān)函數(shù)庫，C語言是一門面向過程的高級語言。設(shè)計(jì)代碼時(shí)，要盡量考慮完備，把可能出現(xiàn)的情況都想到。順序表的函數(shù)庫中，要考慮順序表的結(jié)構(gòu)，在物理上也是相鄰，所以很容易查找到某個(gè)存在的數(shù)據(jù)的位置、下標(biāo)，若已知序號，也很容易找到元素。將函數(shù)庫寫出來以后，在以后程序需要利用函數(shù)時(shí)，無須每次都寫一次函數(shù)，可以節(jié)約精力與時(shí)間。在之前的學(xué)習(xí)中，就了解了順序表的特點(diǎn)以及功能，通過此次的課程設(shè)計(jì)，更加加深了我對順序存儲這種結(jié)構(gòu)的認(rèn)識，既回顧了以前的東西，也發(fā)現(xiàn)了很多以前都沒遇見過的問題，

13、收獲很大。參考文獻(xiàn)1陳倩詒，鄧紅衛(wèi). 數(shù)據(jù)結(jié)構(gòu)（C語言版）. 武漢：華中科技大學(xué)出版社，20132嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大學(xué)出版社，19973 許卓群，楊冬青，唐世渭，等.數(shù)據(jù)結(jié)構(gòu)與算法M. 北京：高等教育出版社，20064 徐孝凱. 數(shù)據(jù)結(jié)構(gòu)簡明教程. 北京：清華大學(xué)出版社，1995年附錄1：結(jié)構(gòu)化設(shè)計(jì)源程序清單/ 程序名稱：SXB.CPP/ 程序功能：利用C語言設(shè)計(jì)順序表的函數(shù)庫，以便于調(diào)用函數(shù)時(shí)調(diào)用。/ 程序作者：胡潔/ 最后修改日期：2013-7-7#include<stdio.h>#include<stdlib.h>#defin

14、e MAXSIZE 100typedef int datatype;typedef struct datatype dataMAXSIZE; int len;Seqlist; /*將data和len封裝成一個(gè)結(jié)構(gòu)體*/Seqlist *Init_Seqlist() Seqlist *L; L=(Seqlist*)malloc(sizeof(Seqlist); L->len=-1; return L; /*順序表初始化*/int Insert_Seqlist(Seqlist *L,int i,datatype e) int j; if(L->len=MAXSIZE-1)printf(

15、"表滿溢出n");return -1; /*表空間已滿，不能插入*/ if(i<1|i>L->len+2) /*檢查插入位置i是否有效*/ printf("位置錯(cuò)n");return 0; for(j=L->len;j>=i-1;j-) L->dataj+1=L->dataj; /*節(jié)點(diǎn)往后移動(dòng)一個(gè)位置*/ L->datai-1=e; /*插入新元素e*/ L->len+; /*len仍指向最后一個(gè)元素*/ return 1; /*插入操作成功，返回*/int Delete_Seqlist(Seqli

16、st *L,int i) int j; if(i<1|i>L->len+1) /*檢查空表及刪除位置的合法性*/ printf("不存在第d%個(gè)元素n,i");return 0; for(j=i;j<L->len;j+) L->dataj-1=L->dataj; /*向前移動(dòng)一個(gè)位置*/ L->len-; return 1; /*刪除成功*/int Locate_Seqlist(Seqlist *L,datatype e) int i=0; while(i<=L->len && L->data

17、i!=e) i+; if(i>L->len) return -1; /*查找失敗*/ else return i; /*返回存儲位置*/int Get_Seqlist(Seqlist *L,int i) if(i<1|i>L->len+1) /*檢查查找位置的合法性*/ printf("不存在第d%個(gè)元素n",i);return 0; /*查找元素不存在*/ else return L->datai-1; /*查找成功，返回該元素下標(biāo)*/void print(Seqlist *L) int s;for(s=0;s<L->len

18、;s+) printf("%d ",L->datas); /*輸出順序表中所有元素*/ printf("n");main() Seqlist *L; int i,j,s,e,m,flag=1; L=Init_Seqlist(); printf("請輸入表長："); scanf("%d",&i);L->len=i; printf("請輸入%d個(gè)元素值：",i); /*確定表長*/ for(s=0;s<i;s+) scanf("%d",&L-&g

19、t;datas); /*輸入表中元素*/ while(flag) /*使用標(biāo)識flag*/ printf("請選擇：n"); printf("1:顯示所有元素n"); printf("2:加入一個(gè)元素n"); printf("3:刪除一個(gè)元素n"); printf("4:按值查找一個(gè)元素n"); printf("5:取出一個(gè)元素n"); printf("6:退出程序n"); /*輸入順序表元素之后顯示選項(xiàng)*/ scanf("%d",&j); switch(j) /*當(dāng)輸入數(shù)字j時(shí)自動(dòng)調(diào)用函數(shù)庫中的函數(shù)實(shí)現(xiàn)功能*/ case 1:print(L);break; case 2:printf("輸入需要插入的位置和數(shù)值："); scanf("%d %d",&i,&e); m=Insert_Seqlist(L,i,e); if(m) printf("插入之后的線性表："); /*顯示插入元素后的順序表*/ print(L); break; case 3:printf("輸入需要?jiǎng)h除的位置："