版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、<p> 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p><b> 實(shí)驗(yàn)報(bào)告</b></p><p> 題 目 有關(guān)查找的操作 </p><p> 學(xué) 院 </p><p> 專 業(yè) 信
2、息管理和信息系統(tǒng) </p><p> 班 級 </p><p> 學(xué) 號 </p><p><b> 目 錄</b></p><p><b> 一、問題描述2&l
3、t;/b></p><p><b> 二、問題分析4</b></p><p> 三、數(shù)據(jù)結(jié)構(gòu)描述4</p><p><b> 四、算法設(shè)計(jì)5</b></p><p> 五、詳細(xì)程序清單10</p><p> 六、程序運(yùn)行結(jié)果24</p>
4、<p><b> 七、心得體會26</b></p><p><b> 一、問題描述</b></p><p> 1、順序表的查找問題描述</p><p> 順序查找又稱線性查找,它是一種最簡單、最基本的查找方法。它從順序表的一端開始,依次將每一個(gè)數(shù)據(jù)元素的關(guān)鍵字值與給定Key進(jìn)行比較,若某個(gè)數(shù)據(jù)元素的關(guān)
5、鍵字值等于給定值Key,則表明查找成功;若直到所有數(shù)據(jù)元素都比較完畢,仍找不到關(guān)鍵字值為Key的數(shù)據(jù)元素,則表明查找失敗。</p><p> 2、有序表的查找問題描述</p><p> 所謂“折半”也稱為“二分”,故二分查找又稱為折半查找。作為二分查找對象的數(shù)據(jù)必須是順序存儲的有序表,通常假定有序表是按關(guān)鍵字值從小到大排列有序,即若關(guān)鍵字值為數(shù)值,則按數(shù)值有序,若關(guān)鍵字值為字符數(shù)據(jù),則
6、按對應(yīng)的Unicode碼有序。二分查找的基本思想是:首先取整個(gè)有序表的中間記錄的關(guān)鍵字值與給定值相比較,若相等,則查找成功;否則以位于中間位置的數(shù)據(jù)元素為分界點(diǎn),將查找表分成左、右兩個(gè)子表,并判斷待查找的關(guān)鍵字值key是在左子表還是在右子表,再在左或右子表中重復(fù)上述步驟,直到找待查找的關(guān)鍵字值為key的記錄或子表長度為0.</p><p> 3、哈希表的查找問題描述</p><p>
7、在哈希表上進(jìn)行查找的過程和哈希表構(gòu)造的過程基本一致。給定要查找的關(guān)鍵字K的值,根據(jù)構(gòu)造哈希表時(shí)設(shè)定的哈希函數(shù)求得哈希地址,若此哈希地址上沒有數(shù)據(jù)元素,則查找不成功;否則比較關(guān)鍵字,若相等,則查找成功;若不相等,則根據(jù)構(gòu)造哈希表時(shí)設(shè)置的處理沖突的方法找下一個(gè)地址,直至某個(gè)位置上為空或關(guān)鍵字比較相等為止。</p><p> 從哈希表的查找過程可見,雖然哈希表是在關(guān)鍵字和存儲位置之間直接建立了映像,然而由于沖突的產(chǎn)生
8、,哈希表的查找過程仍然是一個(gè)和關(guān)鍵字比較的過程。因此,仍需用平均查找長度來衡量哈希表的查找效率。查找過程中與關(guān)鍵字比較的次數(shù)取決于構(gòu)造哈希表時(shí)選擇的哈希函數(shù)和處理沖突的方法。哈希函數(shù)的“好壞”首先影響出現(xiàn)沖突的頻率,假設(shè)哈希函數(shù)是均勻的,即它對同樣一組隨機(jī)的關(guān)鍵字出現(xiàn)沖突的可能性是相同的。因此,哈希表的查找效率主要取決于構(gòu)造哈希表時(shí)處理沖突的方法。</p><p> 4、二叉樹排序數(shù)的查找問題描述</p&
9、gt;<p> 在順序表的3中查找方法中,二分查找具有最高的查找效率,但是由于二分查找要求表中記錄按關(guān)鍵字有序,且不能用鏈表做存儲結(jié)構(gòu),因此當(dāng)表的插入、刪除操作非常頻繁時(shí),為維護(hù)表的有序性,需要移動(dòng)表中很多記錄。這種由移動(dòng)記錄引起的額外時(shí)間開銷,就會抵消二分查找的優(yōu)點(diǎn)。這里討論的不僅是二叉排序樹具有二分查找的效率,同時(shí)又便于在查找表中進(jìn)行記錄的增加和刪除操作。</p><p> 5、界面設(shè)計(jì)模塊
10、問題描述</p><p> 設(shè)計(jì)一個(gè)菜單式界面,讓用戶可以選擇要解決的問題,同時(shí)可以退出程序。界面要求簡潔明了,大方得體,便于用戶的使用,同時(shí),對于用戶的錯(cuò)誤選擇可以進(jìn)行有效的處理。</p><p><b> 二、問題分析</b></p><p> 在這次的課程設(shè)計(jì)中,我主要負(fù)責(zé)二叉排序樹查找的這一部分設(shè)計(jì),二叉排序樹查找屬于動(dòng)態(tài)查找表,
11、它不僅具有二分查找的效率,同時(shí)也便于在查找表中進(jìn)行記錄的增加和刪除操作。若將查找表組織為一棵二叉排序樹,則根據(jù)二叉排序樹的特點(diǎn),查找過程的主要步驟歸納如下:</p><p> (1)若查找樹為空,則查找失敗。</p><p> ?。?)若查找樹非空,則進(jìn)行如下操作。</p><p> 1)若給定值k等于根結(jié)點(diǎn)的關(guān)鍵字值,則查找成功,結(jié)束查找過程,否則轉(zhuǎn)步驟2)&
12、lt;/p><p> 2)若給定值k小于根結(jié)點(diǎn)的關(guān)鍵字值,則繼續(xù)在根結(jié)點(diǎn)的左子樹上進(jìn)行,否則轉(zhuǎn)步驟3)</p><p> 3)若給定值k大于根結(jié)點(diǎn)的關(guān)鍵字值,則繼續(xù)在根結(jié)點(diǎn)的右子樹上進(jìn)行。</p><p><b> 三、數(shù)據(jù)結(jié)構(gòu)描述</b></p><p> class BiTreeNode{</p>
13、<p> private Object data; //結(jié)點(diǎn)的數(shù)據(jù)域</p><p> private BiTreeNode lchild,rchild; //左、右孩子樹</p><p> public BiTreeNode(){</p><p> this(null);</p>&
14、lt;p><b> }</b></p><p> //構(gòu)造一棵左、右孩子域?yàn)榭盏亩鏄?lt;/p><p> public BiTreeNode(Object data){</p><p> this(data,null,null);</p><p><b> }</b></p&g
15、t;<p> //構(gòu)造一棵數(shù)據(jù)域和左、右孩子域都不為空的二叉樹</p><p> public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild){</p><p> this.data=data;</p><p> this.lchild=lchild;</p>
16、<p> this.rchild=rchild;</p><p><b> }</b></p><p> public Object getData() {</p><p> return data;</p><p><b> }</b></p><p>
17、; public BiTreeNode getLchild() {</p><p> return lchild;</p><p><b> }</b></p><p> public BiTreeNode getRchild() {</p><p> return rchild;</p><
18、;p><b> }</b></p><p> public void setData(Object data) {</p><p> this.data = data;</p><p><b> }</b></p><p> public void setLchild(BiTreeN
19、ode lchild) {</p><p> this.lchild = lchild;</p><p><b> }</b></p><p> public void setRchild(BiTreeNode rchild) {</p><p> this.rchild = rchild;</p>
20、<p><b> }</b></p><p> }//結(jié)點(diǎn)類定義結(jié)束</p><p><b> 四、算法設(shè)計(jì)</b></p><p><b> 1.程序功能模塊圖</b></p><p><b> 2. 具體算法設(shè)計(jì)</b></
21、p><p> class BiTreeNode{</p><p> private Object data;</p><p> private BiTreeNode lchild,rchild;</p><p> public BiTreeNode(){</p><p> this(null);</p>
22、;<p><b> }</b></p><p> public BiTreeNode(Object data){</p><p> this(data,null,null);</p><p><b> }</b></p><p> public BiTreeNode(Obje
23、ct data,BiTreeNode lchild,BiTreeNode rchild){</p><p> this.data=data;</p><p> this.lchild=lchild;</p><p> this.rchild=rchild;</p><p><b> }</b></p>
24、<p> public Object getData() {</p><p> return data;</p><p><b> }</b></p><p> public BiTreeNode getLchild() {</p><p> return lchild;</p>&
25、lt;p><b> }</b></p><p> public BiTreeNode getRchild() {</p><p> return rchild;</p><p><b> }</b></p><p> public void setData(Object data)
26、{</p><p> this.data = data;</p><p><b> }</b></p><p> public void setLchild(BiTreeNode lchild) {</p><p> this.lchild = lchild;</p><p><b&
27、gt; }</b></p><p> public void setRchild(BiTreeNode rchild) {</p><p> this.rchild = rchild;</p><p><b> }</b></p><p><b> }</b></p>
28、;<p> class BSTree{</p><p> protected BiTreeNode root;</p><p> public BSTree(){</p><p> root=null;</p><p><b> }</b></p><p> public
29、 void inOrderTraverse(BiTreeNode p){</p><p> if(p!=null){</p><p> inOrderTraverse(p.getLchild());</p><p> System.out.print(((RecordNode)p.getData()).toString() +"");<
30、;/p><p> inOrderTraverse(p.getRchild());</p><p><b> }</b></p><p><b> }</b></p><p> private Object searchBST(Comparable key){</p><p&g
31、t; if(key==null){</p><p> return null;</p><p><b> }</b></p><p> return searchBST(root,key);</p><p><b> }</b></p><p> private
32、Object searchBST(BiTreeNode p,Comparable key){</p><p> if(key==null||!(key instanceof Comparable)){</p><p> if(key.compareTo(((RecordNode)p.getData()).getKey())==0)</p><p><b&g
33、t; {</b></p><p> return p.getData();</p><p><b> }</b></p><p> if(key.compareTo(((RecordNode)p.getData()).getKey())<0){</p><p> return searchBS
34、T(p.getLchild(),key);</p><p><b> }</b></p><p><b> else{</b></p><p> return searchBST(p.getRchild(),key);</p><p><b> }</b></p&
35、gt;<p><b> }</b></p><p> return null;</p><p><b> }</b></p><p> public boolean insertBST(Comparable key,Object theElement){</p><p> i
36、f(key==null||!(key instanceof Comparable)){</p><p> return false;</p><p><b> }</b></p><p> if(root==null){</p><p> root=new BiTreeNode(new RecordNode(ke
37、y,theElement));</p><p> return true;</p><p><b> }</b></p><p> return insertBST(root,key,theElement);</p><p><b> }</b></p><p>
38、private boolean insertBST(BiTreeNode p,Comparable key,Object theElement){</p><p> if(key.compareTo(((RecordNode)p.getData()).getKey())==0){</p><p> return false;</p><p><b>
39、 }</b></p><p> if(key.compareTo(((RecordNode)p.getData()).getKey())<0){</p><p> if(p.getLchild()==null){</p><p> p.setLchild(new BiTreeNode(new RecordNode(key,theElement
40、)));</p><p> return true;</p><p><b> }</b></p><p><b> else{</b></p><p> return insertBST(p.getLchild(),key,theElement);</p><p>
41、<b> }</b></p><p><b> }</b></p><p> else if(p.getRchild()==null){</p><p> p.setRchild(new BiTreeNode(new RecordNode(key,theElement)));</p><p>
42、; return true;</p><p><b> }</b></p><p><b> else{</b></p><p> return insertBST(p.getRchild(),key,theElement);</p><p><b> }</b>&l
43、t;/p><p><b> }</b></p><p> public Object removeBST(Comparable key){</p><p> if(root==null||key==null||!(key instanceof Comparable)){</p><p> return null;&l
44、t;/p><p><b> }</b></p><p> return removeBST(root,key,null);</p><p><b> }</b></p><p> private Object removeBST(BiTreeNode p,Comparable elemKey,B
45、iTreeNode parent){</p><p> if(p!=null){</p><p> if(elemKey)</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b><
46、/p><p> class RecordNode{</p><p> private Comparable key; //關(guān)鍵字</p><p> private Object element; //數(shù)據(jù)元素</p><p> pu
47、blic Object getElement(){</p><p> return element;</p><p><b> }</b></p><p> public void setElement(Object element){</p><p> this.element=element;</p&g
48、t;<p><b> }</b></p><p> public Comparable getKey(){</p><p> return key;</p><p><b> }</b></p><p> public void setKey(Comparable key){
49、</p><p> this.key=key;</p><p><b> }</b></p><p> public RecordNode(Comparable key){ //構(gòu)造方法1</p><p> this.key=key;</p><p><
50、b> }</b></p><p> public RecordNode(Comparable key,Object element){ //構(gòu)造方法2</p><p> this.key=key;</p><p> this.element=element;</p><p><b> }</b>
51、;</p><p><b> }</b></p><p> class KeyType implements Comparable<KeyType>{</p><p> private int key; //關(guān)鍵字</p><p>
52、 public KeyType(){</p><p><b> }</b></p><p> public KeyType(int key){</p><p> this.key=key;</p><p><b> }</b></p><p> public int
53、 getKey(){</p><p> return key;</p><p><b> }</b></p><p> public void setKey(int key){</p><p> this.key=key;</p><p><b> }</b><
54、;/p><p> public String toString(){ //覆蓋toString()方法</p><p> return key+"";</p><p><b> }</b></p><p> public int compareT
55、o(KeyType another){ //覆蓋Comparable接口中比較關(guān)鍵字大小的方法</p><p> int thisVal=this.key;</p><p> int anotherVal=another.key;</p><p> return(thisVal<anotherVal?-1:(thisVal==a
56、notherVal?0:1));</p><p><b> }</b></p><p><b> }</b></p><p> class ElementType{</p><p> private String data;</p><p> public Stri
57、ng getdata(){ //用戶可自定義其他數(shù)據(jù)項(xiàng)</p><p> return data;</p><p><b> }</b></p><p> public void setdata(String data){</p><p> this.dat
58、a=data;</p><p><b> }</b></p><p> public ElementType(String data){</p><p> this.data=data;</p><p><b> }</b></p><p> public Elem
59、entType(){</p><p><b> }</b></p><p> public String toString(){ //覆蓋toString()方法</p><p> return data;</p><p><b> }</b
60、></p><p><b> }</b></p><p><b> 五、詳細(xì)程序清單</b></p><p><b> 1、xuanze類</b></p><p> import java.util.Scanner;</p><p> p
61、ublic class xuanze{</p><p> static SeqList ST=null;</p><p> static void createSeachList() throws Exception{</p><p> int maxSize=20;</p><p> ST=new SeqList(maxSize);
62、</p><p> int curlen;</p><p> System.out.print("Please input table length:");</p><p> Scanner sc=new Scanner(System.in);</p><p> curlen=sc.nextInt();</p
63、><p> KeyType[] k= new KeyType[curlen];</p><p> System.out.print("Please input keyword sequence:");</p><p> for(int i=0;i<curlen;i++)</p><p> k[i]=new Key
64、Type(sc.nextInt());</p><p> for(int i=0;i<curlen;i++){</p><p> RecordNode r=new RecordNode(k[i]);</p><p> ST.insert(i, r); //從1號存儲單元開始存放數(shù)據(jù)元素</p><p><b> }}&
65、lt;/b></p><p> static HashTable<String> ht=null;</p><p> public static void main(String args[]) throws Exception</p><p><b> {</b></p><p> Syste
66、m.out.println("/***********************************************/");</p><p> System.out.println(" 1.順序表的查找操作 ");</p><p> System.out.println(&qu
67、ot; 2.有序表的查找操作 ");</p><p> System.out.println(" 3.哈希表的查找操作 ");</p><p> System.out.println(" 4.其它查找算
68、法 ");</p><p> System.out.println(" 5.退出 ");</p><p> System.out.println("/*************************************
69、**********/");</p><p> System.out.println("請選擇1-5,謝謝??!");</p><p> Scanner sc=new Scanner(System.in);</p><p> while(true){</p><p> switch(sc.nextInt()
70、)</p><p><b> {</b></p><p><b> case 1:</b></p><p> createSeachList();</p><p> System.out.print("Please input search keyword:");<
71、/p><p> Scanner sc1=new Scanner(System.in);</p><p> KeyType key1=new KeyType(sc.nextInt());</p><p> KeyType key2=new KeyType(sc.nextInt());</p><p> System.out.println(
72、"seqSearch"+key1.getKey()+")="+ST.seqSearch(key1));</p><p> System.out.println("seqSearch("+key2.getKey()+")="+ST.seqSearch(key2));</p><p> System.out.p
73、rintln("如需其他操作,請繼續(xù)選擇,如不需要,請按5,謝謝!");</p><p><b> break;</b></p><p><b> case 2:</b></p><p> createSeachList();</p><p> System.out.pr
74、int("Please input search keyword:");</p><p> Scanner sc2=new Scanner(System.in);</p><p> KeyType key3=new KeyType(sc.nextInt());</p><p> KeyType key4=new KeyType(sc.nex
75、tInt());</p><p> System.out.println("binaryseqSearch("+key3.getKey()+")="+ST.binarySearch(key3));</p><p> System.out.println("binaryseqSearch("+key4.getKey()+&quo
76、t;)="+ST.binarySearch(key4));</p><p> System.out.println("如需其他操作,請繼續(xù)選擇,如不需要,請按5,謝謝!");</p><p><b> break;</b></p><p> case 3:String[] name ={"Wang&
77、quot;,"Li","Zhang","Liu","Chen","Yang","Huang","Zhao","Wu","Zhou","Du"};</p><p> HashTable<String> h
78、t=new HashTable<String>(7);</p><p> String elem1,elem2;</p><p> System.out.print("插入元素:");</p><p> for(int i=0;i<name.length;i++){</p><p> ht.ins
79、ert(name[i]);</p><p> System.out.print(name[i]+"");</p><p><b> }</b></p><p> System.out.print("\n原哈希表:");</p><p> ht.printHashTable(
80、);</p><p> elem1=name[2];</p><p> System.out.print("查找"+elem1+","+(ht.contain(elem1)?"":"不")+"成功");</p><p> elem2="san"
81、;;</p><p> System.out.print("查找"+elem2+","+(ht.contain(elem1)?"":"不")+"成功");</p><p> System.out.print("刪除"+elem1+","+(ht.r
82、emove(elem1)?"":"不")+"成功");</p><p> System.out.print("刪除"+elem2+","+(ht.remove(elem2)?"":"不")+"成功");</p><p> Sys
83、tem.out.println("新哈希表:");</p><p> ht.printHashTable();</p><p> System.out.println("如需其他操作,請繼續(xù)選擇,如不需要,請按5,謝謝!");</p><p><b> break;</b></p>&
84、lt;p><b> case 4:</b></p><p> BSTree bstree=new BSTree();</p><p> int[]k={50,13,63,8,36,90,5,10,18,70};</p><p> String[] item={"Wang","Li",&quo
85、t;Zhang","Liu","Chen","Yang","Huang","Zhao","Wu","Zhou"};</p><p> KeyType[] key=new KeyType[k.length];</p><p> Elemen
86、tType[] elem=new ElementType[k.length];</p><p> System.out.println("原序列:");</p><p> for(int i=0;i<k.length;i++){</p><p> key[i]=new KeyType(k[i]);</p><p&g
87、t; elem[i]=new ElementType(item[i]);</p><p> if(bstree.insertBST(key[i],elem[i])){</p><p> System.out.print("["+key[i]+","+elem[i]+"]");</p><p><
88、b> }</b></p><p><b> }</b></p><p> System.out.println("\n中根遍歷二叉排序樹:");</p><p> bstree.inOrderTraverse(bstree.root);</p><p> System.ou
89、t.println();</p><p> KeyType keyvalue=new KeyType();</p><p> keyvalue.setKey(63);</p><p> RecordNode found=(RecordNode)bstree.searchBST(keyvalue);</p><p> if(found!
90、=null){</p><p> System.out.println("查找關(guān)鍵碼:"+keyvalue+",成功!對應(yīng)姓氏為:"+found.getElement());</p><p><b> }</b></p><p><b> else{</b></p>
91、<p> System.out.println("查找關(guān)鍵碼:"+keyvalue+",失?。?quot;);</p><p><b> }</b></p><p> keyvalue.setKey(39);</p><p> found=(RecordNode)bstree.searchBS
92、T(keyvalue);</p><p> if(found!=null){</p><p> System.out.println("查找關(guān)鍵碼:"+keyvalue+",成功!對應(yīng)姓氏為:"+found.getElement());</p><p><b> }</b></p>&
93、lt;p><b> else{</b></p><p> System.out.println("查找關(guān)鍵碼:"+keyvalue+",失??!");</p><p><b> }</b></p><p> keyvalue.setKey(13);</p>
94、<p> found=(RecordNode)bstree.removeBST(keyvalue);</p><p> if(found!=null){</p><p> System.out.println("刪除關(guān)鍵碼:"+keyvalue+",成功!對應(yīng)姓氏為:"+found.getElement());</p>
95、<p><b> }</b></p><p><b> else{</b></p><p> System.out.println("刪除關(guān)鍵碼:"+keyvalue+",失??!");</p><p><b> }</b></p>
96、<p> System.out.println("\n刪除關(guān)鍵碼:"+keyvalue+",后的中根遍歷序列:");</p><p> bstree.inOrderTraverse(bstree.root);</p><p> System.out.println("");</p><p>
97、; System.out.println("如需其他操作,請繼續(xù)選擇,如不需要,請按5,謝謝!");</p><p><b> break;</b></p><p><b> case 5:</b></p><p> System.out.println("已成功退出!");
98、</p><p><b> return;</b></p><p><b> }</b></p><p><b> }}}</b></p><p> 2、Record Node類</p><p> class RecordNode {</
99、p><p> private Comparable key; //關(guān)鍵字</p><p> private Object element; //數(shù)據(jù)元素</p><p> public Object getElement() {</p><p> return element;</p><p>
100、<b> }</b></p><p> public void setElement(Object element) {</p><p> this.element = element;</p><p><b> }</b></p><p> public Comparable getKe
101、y() {</p><p> return key;</p><p><b> }</b></p><p> public void setKey(Comparable key) {</p><p> this.key = key;</p><p><b> }</b&g
102、t;</p><p> public RecordNode(Comparable key) { //構(gòu)造方法1</p><p> this.key = key;</p><p><b> }</b></p><p> public RecordNode(Comparable key, Object elemen
103、t) { //構(gòu)造方法2</p><p> this.key = key;</p><p> this.element = element;</p><p><b> }</b></p><p> public String toString() { //覆蓋toString()方法</p>&l
104、t;p> return "[" + key + "," + element + "]";</p><p><b> }</b></p><p><b> } </b></p><p> 3、KeyType類</p><p>
105、 class KeyType implements Comparable<KeyType> {</p><p> private int key; //關(guān)鍵字</p><p> public KeyType() {</p><p><b> }</b></p><p> public KeyTyp
106、e(int key) {</p><p> this.key = key;</p><p><b> }</b></p><p> public int getKey() {</p><p> return key;</p><p><b> }</b></p
107、><p> public void setKey(int key) {</p><p> this.key = key;</p><p><b> }</b></p><p> public int compareTo(KeyType another) { //覆蓋Comparable接口中比較關(guān)鍵字大小方法<
108、/p><p> int thisVal = this.key;</p><p> int anotherVal = another.key;</p><p> return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));</p><p><b>
109、 }</b></p><p><b> }</b></p><p> 4、SeqList類</p><p> class SeqList {</p><p> private RecordNode[] r; //順序表記錄結(jié)點(diǎn)數(shù)組</p><p> private in
110、t curlen; //順序表長度,即記錄個(gè)數(shù)</p><p> // 順序表的構(gòu)造方法,構(gòu)造一個(gè)存儲空間容量為maxSize的順序表</p><p> public SeqList(int maxSize) {</p><p> this.r = new RecordNode[maxSize]; // 為順序表分配maxSize個(gè)存儲單元&l
111、t;/p><p> this.curlen = 0; // 置順序表的當(dāng)前長度為0</p><p><b> }</b></p><p> // 求順序表中的數(shù)據(jù)元素個(gè)數(shù)并由函數(shù)返回其值</p><p> public int length() {</p><p
112、> return curlen; // 返回順序表的當(dāng)前長度</p><p><b> }</b></p><p> public int getCurlen() {</p><p> return curlen;</p><p><b> }</b></p><
113、p> public void setCurlen(int curlen) {</p><p> this.curlen = curlen;</p><p><b> }</b></p><p> // 在當(dāng)前順序表的第i個(gè)結(jié)點(diǎn)之前插入一個(gè)RecordNode類型的結(jié)點(diǎn)x</p><p> //其中i取值范
114、圍為:0≤i≤length()。</p><p> //如果i值不在此范圍則拋出異常,當(dāng)i=0時(shí)表示在表頭插入一個(gè)數(shù)據(jù)元素x,</p><p> //當(dāng)i=length()時(shí)表示在表尾插入一個(gè)數(shù)據(jù)元素x</p><p> public void insert(int i, RecordNode x) throws Exception {</p>
115、<p> if (curlen == r.length) { // 判斷順序表是否已滿</p><p> throw new Exception("順序表已滿");</p><p><b> }</b></p><p> if (i < 0|| i > curlen) { // i小于0
116、或者大于表長</p><p> throw new Exception("插入位置不合理");</p><p><b> }</b></p><p> for (int j = curlen+1; j > i; j--) {</p><p> r[j] = r[j - 1]; //
117、插入位置及之后的元素后移</p><p><b> }</b></p><p> r[i] = x; // 插入x</p><p> this.curlen++; // 表長度增1</p><p><b> }</b></p><p> 5、seqSearch
118、類(順序查找算法)</p><p> public int seqSearch(Comparable key) {</p><p> int i=0,n=length();</p><p> while(i<n&&r[i].getKey().compareTo(key)!=0){</p><p><b>
119、 i++;</b></p><p><b> }</b></p><p><b> if(i<n){</b></p><p><b> return i;</b></p><p><b> }</b></p>&l
120、t;p><b> else{</b></p><p> return -1;</p><p><b> }</b></p><p><b> }</b></p><p> 6、binarySearch類(二分查找算法)</p><p>
121、 public int binarySearch(Comparable key) {</p><p> if (length() > 0) {</p><p> int low = 0, high = length()-1 ; //查找范圍的下界和上界</p><p> while (low <= high) {</p><p&
122、gt; int mid = (low + high) / 2; //中間位置,當(dāng)前比較元素位置</p><p> // System.out.print(r[mid].getKey() + "? ");</p><p> if (r[mid].getKey().compareTo(key) == 0) {</p><p> re
123、turn mid; //查找成功</p><p> } else if (r[mid].getKey().compareTo(key) > 0) { //給定值更小</p><p> high = mid - 1; //查找范圍縮小到前半段</p><p><b> } el
124、se {</b></p><p> low = mid + 1; //查找范圍縮小到后半段</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p>
125、 return -1; //查找不成功</p><p><b> }</b></p><p><b> 7、Node類</b></p><p> class Node {</p><p> private Object data;</p><p> private
126、 Node next;</p><p> public Node(){</p><p> this(null,null);</p><p><b> }</b></p><p> public Node(Object data){</p><p> this(data,null);<
127、;/p><p><b> }</b></p><p> public Node(Object data,Node next){</p><p> this.data=data;</p><p> this.next=next;</p><p><b> }</b><
128、;/p><p> public Object getData(){</p><p> return data;</p><p><b> }</b></p><p> public Node getNext(){</p><p> return next;</p><p&
129、gt;<b> }</b></p><p> public void setData(Object data){</p><p> this.data=data;</p><p><b> }</b></p><p> public void setNext(Node next){<
130、/p><p> this.next=next;</p><p><b> }}</b></p><p> 8、LinkList類</p><p> class LinkList {</p><p> private Node head=new Node();</p><p
131、> public void create(int n) throws Exception{</p><p> Scanner sc=new Scanner(System.in);</p><p> for(int j=0;j<n;j++)</p><p> insert(0,sc.next());}</p><p> p
132、ublic void insert(int i,Object x) throws Exception{</p><p> Node p=head;</p><p><b> int j=-1;</b></p><p> while(p!=null&&j<i-1){</p><p> p=p.
133、getNext();</p><p><b> ++j;</b></p><p><b> }</b></p><p> if(j>i-1||p==null)</p><p> throw new Exception("插入位置不合法");</p>&
134、lt;p> Node s=new Node(x);</p><p> s.setNext(p.getNext());</p><p> p.setNext(s);</p><p><b> }</b></p><p> public void remove(int i)throws Exception{&
135、lt;/p><p> Node p=head;</p><p><b> int j=-1;</b></p><p> while(p.getNext()!=null&&j<i-1){</p><p> p=p.getNext();</p><p><b>
136、++j;</b></p><p><b> }</b></p><p> if(j>i-1||p.getNext()==null)</p><p> throw new Exception("刪除位置不合法");</p><p> p.setNext(p.getNext().
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)-無向圖的操作-課程設(shè)計(jì)-實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)實(shí)踐環(huán)節(jié)實(shí)驗(yàn)報(bào)告(課程設(shè)計(jì))
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告(赫夫曼編碼)
- 數(shù)據(jù)結(jié)構(gòu)-串的存儲表示及基本操作--課程設(shè)計(jì)-實(shí)驗(yàn)報(bào)告
- 06年數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告
- 《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》航班查詢系統(tǒng)實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告--多種排序方式的比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---鏈表操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---鏈表操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)圖書管理系統(tǒng)實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)avl樹實(shí)現(xiàn)及其分析實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)-鄰接表存儲及遍歷-課程設(shè)計(jì)-實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)——串的查找與替換
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---skiplist基本操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-鏈表操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---鏈表操作
- 國開(電大)數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-串
評論
0/150
提交評論