2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩25頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論