課程設(shè)計(jì)靜態(tài)查找的實(shí)現(xiàn)操作

1、屆課程設(shè)計(jì)課程設(shè)計(jì)論文學(xué)生姓名 學(xué) 號(hào) 所屬學(xué)院 信息工程學(xué)院專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) 計(jì)算機(jī)15-2班 指導(dǎo)教師 教師職稱 講師塔里木大學(xué)教務(wù)處制目錄前言1設(shè)計(jì)背景和意義1數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介1選擇算法的原因1設(shè)計(jì)的原理和內(nèi)容1正文12.1 設(shè)計(jì)的目的和意義12.2 目標(biāo)和總體方案22.3 設(shè)計(jì)方法和內(nèi)容22.3.1 設(shè)計(jì)流程圖2設(shè)計(jì)內(nèi)容32.4 程序的設(shè)計(jì)思想和內(nèi)容4程序設(shè)計(jì)的初始運(yùn)行環(huán)境4靜態(tài)查找中的順序查找4靜態(tài)查找表的折半查找5靜態(tài)查找表的銷毀6靜態(tài)查找表的退出操作62.5 設(shè)計(jì)創(chuàng)新與關(guān)鍵技術(shù)6存在的問題7解決方案7參考文獻(xiàn)7附錄7前言數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論設(shè)

2、計(jì)基礎(chǔ)，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且成為其他理工專業(yè)的熱門選修課。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率的算法。比如在計(jì)算機(jī)中央處理器中，CPU接到一個(gè)中斷請(qǐng)求便會(huì)停下當(dāng)前正在執(zhí)行的指令去處理這個(gè)中斷請(qǐng)求完成中斷操作，首先要做的就是保護(hù)現(xiàn)場(chǎng)。保護(hù)現(xiàn)場(chǎng)需要將下一條指令的地址指針和當(dāng)前指令返回地址等重要的數(shù)據(jù)進(jìn)行存儲(chǔ)。在眾多的數(shù)據(jù)結(jié)構(gòu)中，這些重要的數(shù)據(jù)被存儲(chǔ)到棧這個(gè)數(shù)據(jù)結(jié)構(gòu)中。選擇算法的原因在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是

3、否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。本次程序設(shè)計(jì)采用C語(yǔ)作為描述和實(shí)現(xiàn)算法的程序語(yǔ)言，主要的設(shè)計(jì)思路就是完成對(duì)靜態(tài)查找的操作，如表中元素的查找、元素對(duì)應(yīng)表中的位置等等，這些操作都是通過C語(yǔ)言程序來(lái)實(shí)現(xiàn)的。最后的結(jié)果就是運(yùn)行程序時(shí)能夠完成對(duì)以上設(shè)計(jì)的操作。正文靜態(tài)查找表是查找表的一種，它也就具備了查找表的特點(diǎn)，是有同一類型的數(shù)據(jù)元素構(gòu)成的集合，由于“集合”中的元素之間存在著完全松散的關(guān)系，因此是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)方法。其主要操作查詢某個(gè)特定的元素是

4、否在表中，檢索某個(gè)特定的元素的各種屬性。2.1 設(shè)計(jì)的目的和意義我們是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的本科生，數(shù)據(jù)結(jié)構(gòu)是我們重要的必修課程。當(dāng)代社會(huì)學(xué)要大學(xué)培養(yǎng)出理論扎實(shí)，動(dòng)手實(shí)踐能力強(qiáng)的大學(xué)生。所以，本次課程設(shè)計(jì)的目的就在于通過一次實(shí)踐性的活動(dòng)加深對(duì)這門課程的理解，使我們?cè)诟行缘恼J(rèn)識(shí)上進(jìn)一步升華為理性的認(rèn)識(shí)。為后繼課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。馬克思主義唯物辯證法認(rèn)為，實(shí)踐是連接客觀實(shí)在和人主觀意識(shí)的通道和橋梁。物質(zhì)對(duì)意識(shí)的作用以及意識(shí)對(duì)物質(zhì)的反作用都蘊(yùn)含在實(shí)踐活動(dòng)當(dāng)中。也就是，實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)。對(duì)這門課的學(xué)習(xí)狀況的好壞，用一次課程設(shè)計(jì)便可以檢驗(yàn)出來(lái)。而這，就是本次我們進(jìn)行設(shè)計(jì)的意義之所在。2.2

5、 目標(biāo)和總體方案靜態(tài)查找表是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素，若表中存在這樣的一個(gè)記錄或數(shù)據(jù)則便查找成功，此時(shí)查找的結(jié)果為給出的記錄信息或者是指出該記錄在查找表中的位置，表中若不存在關(guān)鍵字與給定值的記錄則查找失敗。本次設(shè)計(jì)的目標(biāo)在于將靜態(tài)查找中的操作用程序語(yǔ)言形象地再現(xiàn)和描述出來(lái)。于是特制訂了一個(gè)總體的方案。由于時(shí)間只有十天，故做了如下的計(jì)劃安排，將這項(xiàng)工程分為兩大部分：程序的設(shè)計(jì)和程序的調(diào)試。首先在程序的設(shè)計(jì)部分由分為幾個(gè)步驟：第一步：查閱有關(guān)數(shù)據(jù)結(jié)構(gòu)靜態(tài)查找操作的資料，用半天的時(shí)間。第二步：設(shè)計(jì)這個(gè)項(xiàng)目的整體架構(gòu)和算法。用一到兩天的時(shí)間。第三步：選擇一

6、門程序設(shè)計(jì)語(yǔ)言進(jìn)行算法的描述。兩天的時(shí)間。其次，進(jìn)行程序的調(diào)試。用一天。2.3 設(shè)計(jì)方法和內(nèi)容“工欲善其事，必先利其器”。有了總體方案后必須用一個(gè)事半功倍的設(shè)計(jì)方法來(lái)提高程序設(shè)計(jì)的效率。在這個(gè)項(xiàng)目的設(shè)計(jì)上，選擇了語(yǔ)言作為算法的描述語(yǔ)言，因?yàn)檎Z(yǔ)言具有豐富的表達(dá)能力以及代碼的高效性，并且有著良好的移植性和靈活性。采用“自頂向下，個(gè)個(gè)擊破”的程序設(shè)計(jì)思路和思想，充分運(yùn)用語(yǔ)言強(qiáng)大的功能。 設(shè)計(jì)流程圖開始輸出元素及其在表中的位置結(jié)束查找某個(gè)元素輸出表中元素創(chuàng)建一個(gè)順序表SWICH語(yǔ)句創(chuàng)建菜單進(jìn)行選擇圖3-1 程序流程圖設(shè)計(jì)內(nèi)容一、程序設(shè)計(jì)的基本算法介紹1、靜態(tài)查找表是一種只能在叫做查找表的一段進(jìn)行查詢操

7、作靈便的數(shù)據(jù)結(jié)構(gòu)。靜態(tài)查找表的主要特點(diǎn)是數(shù)據(jù)元素在順序表中可以任意排列的，表中數(shù)據(jù)元素之間僅存在著“同屬一個(gè)集合”的松散關(guān)系無(wú)邏輯關(guān)系。2、靜態(tài)查找表的基本操作: (1)創(chuàng)建一個(gè)順序表。 (2)輸出表中所有元素 (3)輸入一個(gè)關(guān)鍵字 (4) 比較關(guān)鍵字與表中元素的記錄相等則返回它不等則在表中不存在 (5) 判斷表若表為空，返回1，否則返回03、通常靜態(tài)查找表用順序表存儲(chǔ)，與線性表的順序存儲(chǔ)類似，靜態(tài)查找表中的數(shù)據(jù)元素存放在上述數(shù)組的第1到第n個(gè)單元，第n+1到最后一個(gè)單元為備用區(qū)。不同的是，這里多說明了一個(gè)單元即第0個(gè)單元，該單元被用于設(shè)置崗哨以便簡(jiǎn)化查找運(yùn)算的實(shí)現(xiàn)。二、程序中涉及的基本算法

8、靜態(tài)查找表是只能進(jìn)行記錄或元素在表中的查找看其是否在表中或者是檢索某個(gè)記錄或元素的各種屬性，不能進(jìn)行插入和刪除等操作是一種查找表是同一類型數(shù)據(jù)元素集合數(shù)據(jù)之間存在著完全松散的關(guān)系，無(wú)邏輯上的關(guān)系。1、靜態(tài)查找表的定義及基本操作 StaticSearchTableCreate(&ST,n); /構(gòu)造含有n個(gè)元素的靜態(tài)查找表STDestroy(&ST); /銷毀表Search(ST,key); /查找關(guān)鍵字為key的數(shù)據(jù)元素Traverse(ST,visit(); /遍歷查找表StaticSearchTable(1) 若選擇順序查找則其算法為： Search_Seq(SSTable ST, Key

9、Type key)/順序查找的算法，0號(hào)元素為監(jiān)視哨int i；ST.elem0.key=key;for (i=ST.length; !EQ(ST.elemi.key,key);-i);return i;(2) 若選擇折半查找其算法為：int Search_Bin(SSTable ST,KeyType key) int low,high,mid; low = 1; high=ST.length; while (low high) mid = (low+high)/2; if (EQ(key,ST.elemmid.key) return mid;else if (LT(key,ST.elemmi

10、d.key) high=mid-1; /繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low=mid+1;/繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 return 0; /順序表中不存在待查元素2.4 程序的設(shè)計(jì)思想和內(nèi)容程序設(shè)計(jì)的初始運(yùn)行環(huán)境這個(gè)項(xiàng)目是由主函數(shù)模塊和功能函數(shù)模塊組成的。其中主函數(shù)模塊是項(xiàng)目的控制部分，很重要的一個(gè)作用就是對(duì)整個(gè)程序的初始化功能。在設(shè)計(jì)初始運(yùn)行環(huán)境時(shí)，為了每一次棧操作后都可以進(jìn)行對(duì)程序的初始化，采用了dowhile循環(huán)語(yǔ)句構(gòu)成一個(gè)無(wú)限循環(huán)，使得每一次靜態(tài)查找操作之后都可以將程序初始化重新選擇對(duì)靜態(tài)查找的另一個(gè)操作，例如：選擇3，將順序表銷毀，程序便又回到了初始的菜單界面，我們可以選擇1進(jìn)行靜

11、態(tài)查找中的順序查找。靜態(tài)查找中的順序查找其具體算法如下：void Search_Item(sqlist A)int i,n,k,temp=0,j;printf(請(qǐng)你創(chuàng)建一個(gè)順序表);printf(請(qǐng)你輸入元素的個(gè)數(shù)：);scanf(%d,&n);for(i=1;in+1;i+)printf(輸入第%d個(gè)元素的值:,i);scanf(%d,&Ai);printf(n);for(i=1;in+1;i+)printf(%d,Ai);printf(n);printf(請(qǐng)你輸入要查找的元素:);scanf(%d,&k);for(i=1;in+1;i+)if(Ai=k) j=i;temp=1;if(tem

12、p)printf(你所查找的元素在表中第%d個(gè)元素,j);elseprintf(你所查找的元素不在表中);靜態(tài)查找表的折半查找折半查找的過程事先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或是找不到該記錄為止在處于區(qū)間中間的位置記錄的關(guān)鍵字和給定值比較，若想等，則查找成功，若不等，則縮小范圍，直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或是查找區(qū)間的大小小于零時(shí)（表明查找不成功）為止。具體程序算法及運(yùn)行后的界面如下：int m, l=1, h=n;/置區(qū)間初值 while (l k) /繼續(xù)在前半?yún)^(qū)間進(jìn)行查找h = m - 1; if(Am k) /繼續(xù)在后半?yún)^(qū)間進(jìn)行查找l = m

13、+ 1;靜態(tài)查找表的銷毀當(dāng)需要重新建立順序表或建立新的時(shí)候?yàn)榱藴p少內(nèi)部空間的浪費(fèi)需要對(duì)原來(lái)建有的順序表進(jìn)行銷毀其具體操作算法如下：int Destory(sqlist A); if(1) printf(銷毀順序表);靜態(tài)查找表的退出操作其退出靜態(tài)查找的算法如下：exit(0)；2.5 設(shè)計(jì)創(chuàng)新與關(guān)鍵技術(shù)這個(gè)課程設(shè)計(jì)是一個(gè)簡(jiǎn)單的設(shè)計(jì)，如果說有“設(shè)計(jì)創(chuàng)新與關(guān)鍵技術(shù)”的話，只能勉強(qiáng)說有設(shè)計(jì)創(chuàng)新，至于關(guān)鍵技術(shù)應(yīng)該談不上。談到設(shè)計(jì)創(chuàng)新，只能說在設(shè)計(jì)思路、設(shè)計(jì)方法和設(shè)計(jì)內(nèi)容上有別人沒有的東西。而所用的技術(shù)倒是沒有多少。主要是運(yùn)用了C語(yǔ)言豐富的表達(dá)能力，將靜態(tài)查找表中的順序查找和折半查找等操作形象的反應(yīng)出來(lái)

14、。本次設(shè)計(jì)進(jìn)展順利，如期完成，并且達(dá)到了預(yù)先的設(shè)計(jì)要求，完全貫徹和執(zhí)行了設(shè)計(jì)的總體方案。對(duì)于靜態(tài)查找表的基本操作的描述和實(shí)現(xiàn)比較成功。然而，限于時(shí)間和水平，這個(gè)設(shè)計(jì)還有很多的不足之處。存在的問題一、所做界面不夠美觀。缺少一定的人性化因素二、所有的對(duì)靜態(tài)查找表的的操作只能當(dāng)表建立后方可進(jìn)行。當(dāng)進(jìn)行順序查找時(shí)，如果表長(zhǎng)太長(zhǎng)平均查找長(zhǎng)度太大浪費(fèi)時(shí)間。 解決方案一、針對(duì)其界面問題，可以到互聯(lián)網(wǎng)上求助高手或自己到圖書館查閱相關(guān)的書籍。二、當(dāng)對(duì)大型數(shù)據(jù)或是記錄的文件進(jìn)行查找時(shí)，這時(shí)候使用折半查找的查找方法會(huì)節(jié)約大量的時(shí)間提高了效率。參考文獻(xiàn)12345楊路明C語(yǔ)言程序設(shè)計(jì)上機(jī)指導(dǎo)與習(xí)題選解. 北京郵電大學(xué)出

15、版附錄#include stdio.h#includestdlib.h#define Maxlen 20typedef int elemtype ;typedef elemtype sqlistMaxlen;typedef int keytype ;void Search_Item(sqlist A);void Search_Middle(sqlist A);void main ()int cord;sqlist A;doprintf(nn);printf(n*主菜單*n);printf(n*1請(qǐng)你創(chuàng)建一個(gè)順序表，進(jìn)行順序查找*n);printf(n*2請(qǐng)你創(chuàng)建一個(gè)有序表，進(jìn)行折半查找*n);

16、printf(n*3銷毀順序表*n);printf(n*4退出*n);printf(n請(qǐng)輸入你的選擇：);scanf(%d,&cord);switch(cord)case 1:Search_Item(A);break;case 2:Search_Middle(A);break;case 3:int Destory(sqlist A);if(1)printf(銷毀順序表);break;case 4:exit(0);break;while (cord=4);int Destory(sqlist A) free(A);A=NULL;return 1;void Search_Item(sqlist A

17、)int i,n,k,temp=0,j;printf(請(qǐng)你創(chuàng)建一個(gè)順序表);printf(請(qǐng)你輸入元素的個(gè)數(shù)：);scanf(%d,&n);for(i=1;in+1;i+)printf(輸入第%d個(gè)元素的值:,i);scanf(%d,&Ai);printf(n);for(i=1;in+1;i+)printf(%d,Ai);printf(n);printf(請(qǐng)你輸入要查找的元素:);scanf(%d,&k);for(i=1;in+1;i+)if(Ai=k) j=i;temp=1;if(temp)printf(你所查找的元素在表中第%d個(gè)元素,j);elseprintf(你所查找的元素不在表中);void Search_Middle(sqlist A)int i,n,k,temp=0;printf(請(qǐng)你創(chuàng)建一個(gè)順序表);printf(請(qǐng)你輸入元素的