排序與查找(綜合實驗報告)

PAGE本科學(xué)生實驗報告實驗課程名稱數(shù)據(jù)結(jié)構(gòu)（C語言版）實驗名稱排序與查找開課學(xué)期2009至＿2010學(xué)年＿第二學(xué)期云南師范大學(xué)旅游與地理科學(xué)學(xué)院編印一、實驗準(zhǔn)備實驗名稱：排序與查找實驗時間：2010年6月21日實驗類型：綜合實驗1、實驗?zāi)康暮鸵螅簩嶒災(zāi)康?1)掌握查找的不同方法，并能用c語言實現(xiàn)查找算法。(2)掌握常用的排序方法，并掌握用c語言實現(xiàn)排序算法的方法。(3)熟練掌握順序表的選擇排序、冒泡排序、直接插入排序等算法的實現(xiàn)；(4)了解各種方法的排序過程及其時間復(fù)雜度的分析方法。實驗要求(1)完整理解有關(guān)排序和查找的相關(guān)算法和基本思想以及種種算法使用的數(shù)據(jù)存儲結(jié)構(gòu)；(2)根據(jù)要實現(xiàn)的結(jié)果選擇合適的查找算法和排序算法；(3)編寫完整程序并上機調(diào)試運行；(4)認(rèn)真整理并上交實驗報告。2、實驗材料及相關(guān)設(shè)備：計算機一臺（裝有turboc2軟件）、《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（清華大學(xué)出版社）一本3、實驗理論依據(jù)或知識背景：（1）查找有靜態(tài)查找和動態(tài)查找。①靜態(tài)查找表：僅作查詢和檢索操作的查找表。其定義為：ADTStaticSearchTable{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合?；静僮鱌：Create(&ST,n);操作結(jié)果：構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。Destroy(&ST)；初始條件：靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST。Search(ST,key);初始條件：靜態(tài)查找表ST存在，key為和查找表中元素的關(guān)鍵字類型相同的給定值。操作結(jié)果：若ST中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。Traverse(ST,Visit());初始條件：靜態(tài)查找表ST存在，Visit是對元素操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)T的每個元素調(diào)用函數(shù)Visit()一次且僅一次一旦Visit()失敗，則操作失敗。}ADTStaticSearchTable②動態(tài)查找表：有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。其定義為：ADTDynamicSearchTable{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。基本操作P：InitDSTable(&DT)；操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。DestroyDSTable(&DT)；初始條件：動態(tài)查找表DT存在。操作結(jié)果：銷毀動態(tài)查找表DT。SearchDSTable(DT,key);初始條件：動態(tài)查找表DT存在，key和關(guān)鍵字類型相同的給定值。操作結(jié)果：若DT中存在其關(guān)鍵字等于key數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。InsertDSTable(&DT,e);初始條件：態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素。操作結(jié)果：若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。DeleteDSTable(&T,key);初始條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。TraverseDSTable(DT,Visit());初始條件：動態(tài)查找表DT存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)；操作結(jié)果：按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多一次。一旦Visit()失敗，則操作失敗。}ADTDynamicSearchTable二、實驗內(nèi)容、步驟和結(jié)果一：實驗內(nèi)容：（1）通過線性表對一組數(shù)據(jù)中的某個數(shù)據(jù)進(jìn)行查找；（2）對該組數(shù)據(jù)進(jìn)行從小到大的順序進(jìn)行排序；二：實驗步驟：（1）新建一個txt的文本文檔；（2）在文本文檔中輸入所需程序；（3）調(diào)試并運行；（4）任意輸入不同的10個數(shù)，最后一個數(shù)為-1，回車；（5）得到所需結(jié)果并截圖。輸入的程序如下：#include<stdlib.h>#include"stdio.h"typedefstructnode{intdata;structnode*next;}LNode;LNode*create(){intx,n=0;LNode*h,*p,*q;h=(LNode*)malloc(sizeof(LNode));q=h;scanf("%d",&x);while(x!=-1) { p=(LNode*)malloc(sizeof(LNode)); p->data=x; q->next=p; q=p; n++; scanf("%d",&x); } q->next='\0'; h->data=n;returnh;}/*建立線性表并在里面輸入元素并計數(shù)*/voidout(LNode*h){LNode*p;p=h;printf("\n");while(p!='\0'){printf("%6d",p->data);p=p->next;}}/*如果存在則輸出*/LNode*search(LNode*h,inti){LNode*p;intj=1;p=h->next;while((p!='\0')&&(j<i)){p=p->next;j++;}if((p=='\0')||j>i)return(NULL);returnp;}/*查找已存在元素*/sort(LNode*h){intx;LNode*p,*q,*min;p=h->next;while(p){min=p;q=p->next;while(q){if(q->data<min->data)min=q;q=q->next;}if(min!=p){x=p->data;p->data=min->data;min->data=x;}p=p->next;}}/*排序*/main(){LNode*h,*p;h=create();out(h);p=search(h,5);if(p!=NULL)printf("\n%d",p->data);elseprintf("\ndontfind!");sort(h);out(h);}/*運用上述函數(shù)輸出*/三：實驗截圖：運行程序，輸入10個數(shù)：7,12,16,28,32,50,68,82,98，-1。得到的結(jié)果截圖如下。三、實驗小結(jié)1、實驗中出現(xiàn)過的問題（或錯誤）、原因分析（1）寫程序時常常不知道下一步該寫什么，原因是對課本的基本知識的不熟悉和對程序內(nèi)容的模糊；（2）寫好程序后運行，發(fā)現(xiàn)了很多錯誤，有少了分號、忘記定義等，原因是編程時不夠認(rèn)真，粗心大意；（3）調(diào)試好程序成功運行，發(fā)現(xiàn)程序不夠完善美觀，原因是對這方面的知識了解的還是太少。2、保證實驗成功的關(guān)鍵問題（1）