《數據結構》課程設計實驗報告---有關查找的操作

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：26 大?。?30.50KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩25頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　《數據結構》課程設計　　實驗報告　　題目有關查找的操作 　　學院 　　專業(yè) 信

2、息管理和信息系統 　　班級 　　學號 　　目錄　　一、問題描述2&l

3、t;/b>　　二、問題分析4　　三、數據結構描述4　　四、算法設計5　　五、詳細程序清單10　　六、程序運行結果24

4、　　七、心得體會26　　一、問題描述　　1、順序表的查找問題描述　　順序查找又稱線性查找，它是一種最簡單、最基本的查找方法。它從順序表的一端開始，依次將每一個數據元素的關鍵字值與給定Key進行比較，若某個數據元素的關

5、鍵字值等于給定值Key，則表明查找成功；若直到所有數據元素都比較完畢，仍找不到關鍵字值為Key的數據元素，則表明查找失敗。　　2、有序表的查找問題描述　　所謂“折半”也稱為“二分”，故二分查找又稱為折半查找。作為二分查找對象的數據必須是順序存儲的有序表，通常假定有序表是按關鍵字值從小到大排列有序，即若關鍵字值為數值，則按數值有序，若關鍵字值為字符數據，則

6、按對應的Unicode碼有序。二分查找的基本思想是：首先取整個有序表的中間記錄的關鍵字值與給定值相比較，若相等，則查找成功；否則以位于中間位置的數據元素為分界點，將查找表分成左、右兩個子表，并判斷待查找的關鍵字值key是在左子表還是在右子表，再在左或右子表中重復上述步驟，直到找待查找的關鍵字值為key的記錄或子表長度為0.　　3、哈希表的查找問題描述

7、在哈希表上進行查找的過程和哈希表構造的過程基本一致。給定要查找的關鍵字K的值，根據構造哈希表時設定的哈希函數求得哈希地址，若此哈希地址上沒有數據元素，則查找不成功；否則比較關鍵字，若相等，則查找成功；若不相等，則根據構造哈希表時設置的處理沖突的方法找下一個地址，直至某個位置上為空或關鍵字比較相等為止。　　從哈希表的查找過程可見，雖然哈希表是在關鍵字和存儲位置之間直接建立了映像，然而由于沖突的產生

8、，哈希表的查找過程仍然是一個和關鍵字比較的過程。因此，仍需用平均查找長度來衡量哈希表的查找效率。查找過程中與關鍵字比較的次數取決于構造哈希表時選擇的哈希函數和處理沖突的方法。哈希函數的“好壞”首先影響出現沖突的頻率，假設哈希函數是均勻的，即它對同樣一組隨機的關鍵字出現沖突的可能性是相同的。因此，哈希表的查找效率主要取決于構造哈希表時處理沖突的方法。　　4、二叉樹排序數的查找問題描述</p&

9、gt;　　在順序表的3中查找方法中，二分查找具有最高的查找效率，但是由于二分查找要求表中記錄按關鍵字有序，且不能用鏈表做存儲結構，因此當表的插入、刪除操作非常頻繁時，為維護表的有序性，需要移動表中很多記錄。這種由移動記錄引起的額外時間開銷，就會抵消二分查找的優(yōu)點。這里討論的不僅是二叉排序樹具有二分查找的效率，同時又便于在查找表中進行記錄的增加和刪除操作。　　5、界面設計模塊

10、問題描述　　設計一個菜單式界面，讓用戶可以選擇要解決的問題，同時可以退出程序。界面要求簡潔明了，大方得體，便于用戶的使用，同時，對于用戶的錯誤選擇可以進行有效的處理。　　二、問題分析　　在這次的課程設計中，我主要負責二叉排序樹查找的這一部分設計，二叉排序樹查找屬于動態(tài)查找表，

11、它不僅具有二分查找的效率，同時也便于在查找表中進行記錄的增加和刪除操作。若將查找表組織為一棵二叉排序樹，則根據二叉排序樹的特點，查找過程的主要步驟歸納如下：　?。?）若查找樹為空，則查找失敗。　?。?）若查找樹非空，則進行如下操作。　　1）若給定值k等于根結點的關鍵字值，則查找成功，結束查找過程，否則轉步驟2）&

12、lt;/p>　　2）若給定值k小于根結點的關鍵字值，則繼續(xù)在根結點的左子樹上進行，否則轉步驟3）　　3）若給定值k大于根結點的關鍵字值，則繼續(xù)在根結點的右子樹上進行。　　三、數據結構描述　　class BiTreeNode{

13、　　private Object data; //結點的數據域　　private BiTreeNode lchild,rchild; //左、右孩子樹　　public BiTreeNode(){　　this(null);&

14、lt;p>　　}　　//構造一棵左、右孩子域為空的二叉樹　　public BiTreeNode(Object data){　　this(data,null,null);　　}</p&g

15、t;　　//構造一棵數據域和左、右孩子域都不為空的二叉樹　　public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild){　　this.data=data;　　this.lchild=lchild;

16、　　this.rchild=rchild;　　}　　public Object getData() {　　return data;　　}

17、;　　public BiTreeNode getLchild() {　　return lchild;　　}　　public BiTreeNode getRchild() {　　return rchild;<

18、;p>　　}　　public void setData(Object data) {　　this.data = data;　　}　　public void setLchild(BiTreeN

19、ode lchild) {　　this.lchild = lchild;　　}　　public void setRchild(BiTreeNode rchild) {　　this.rchild = rchild;

20、　　}　　}//結點類定義結束　　四、算法設計　　1.程序功能模塊圖　　2. 具體算法設計</

21、p>　　class BiTreeNode{　　private Object data;　　private BiTreeNode lchild,rchild;　　public BiTreeNode(){　　this(null);

22、;　　}　　public BiTreeNode(Object data){　　this(data,null,null);　　}　　public BiTreeNode(Obje

23、ct data,BiTreeNode lchild,BiTreeNode rchild){　　this.data=data;　　this.lchild=lchild;　　this.rchild=rchild;　　}

24、　　public Object getData() {　　return data;　　}　　public BiTreeNode getLchild() {　　return lchild;&

25、lt;p>　　}　　public BiTreeNode getRchild() {　　return rchild;　　}　　public void setData(Object data)

26、{　　this.data = data;　　}　　public void setLchild(BiTreeNode lchild) {　　this.lchild = lchild;<b&

27、gt;　　}　　public void setRchild(BiTreeNode rchild) {　　this.rchild = rchild;　　}　　}

28、;　　class BSTree{　　protected BiTreeNode root;　　public BSTree(){　　root=null;　　}　　public

29、 void inOrderTraverse(BiTreeNode p){　　if(p!=null){　　inOrderTraverse(p.getLchild());　　System.out.print(((RecordNode)p.getData()).toString() +"");<

30、;/p>　　inOrderTraverse(p.getRchild());　　}　　}　　private Object searchBST(Comparable key){<p&g

31、t;　　if(key==null){　　return null;　　}　　return searchBST(root,key);　　}　　private

32、Object searchBST(BiTreeNode p,Comparable key){　　if(key==null||!(key instanceof Comparable)){　　if(key.compareTo(((RecordNode)p.getData()).getKey())==0)<b&g

33、t;　　{　　return p.getData();　　}　　if(key.compareTo(((RecordNode)p.getData()).getKey())<0){　　return searchBS

34、T(p.getLchild(),key);　　}　　else{　　return searchBST(p.getRchild(),key);　　}</p&

35、gt;　　}　　return null;　　}　　public boolean insertBST(Comparable key,Object theElement){　　i

36、f(key==null||!(key instanceof Comparable)){　　return false;　　}　　if(root==null){　　root=new BiTreeNode(new RecordNode(ke

37、y,theElement));　　return true;　　}　　return insertBST(root,key,theElement);　　}

38、private boolean insertBST(BiTreeNode p,Comparable key,Object theElement){　　if(key.compareTo(((RecordNode)p.getData()).getKey())==0){　　return false;

39、　}　　if(key.compareTo(((RecordNode)p.getData()).getKey())<0){　　if(p.getLchild()==null){　　p.setLchild(new BiTreeNode(new RecordNode(key,theElement

40、)));　　return true;　　}　　else{　　return insertBST(p.getLchild(),key,theElement);

41、　　}　　}　　else if(p.getRchild()==null){　　p.setRchild(new BiTreeNode(new RecordNode(key,theElement)));

42、;　　return true;　　}　　else{　　return insertBST(p.getRchild(),key,theElement);　　}&l

43、t;/p>　　}　　public Object removeBST(Comparable key){　　if(root==null||key==null||!(key instanceof Comparable)){　　return null;&l

44、t;/p>　　}　　return removeBST(root,key,null);　　}　　private Object removeBST(BiTreeNode p,Comparable elemKey,B

45、iTreeNode parent){　　if(p!=null){　　if(elemKey)　　}　　}　　}<

46、/p>　　class RecordNode{　　private Comparable key; //關鍵字　　private Object element; //數據元素　　pu

47、blic Object getElement(){　　return element;　　}　　public void setElement(Object element){　　this.element=element;</p&g

48、t;　　}　　public Comparable getKey(){　　return key;　　}　　public void setKey(Comparable key){

49、　　this.key=key;　　}　　public RecordNode(Comparable key){ //構造方法1　　this.key=key;<

50、b>　　}　　public RecordNode(Comparable key,Object element){ //構造方法2　　this.key=key;　　this.element=element;　　}

51、;　　}　　class KeyType implements Comparable<KeyType>{　　private int key; //關鍵字

52、　public KeyType(){　　}　　public KeyType(int key){　　this.key=key;　　}　　public int

53、 getKey(){　　return key;　　}　　public void setKey(int key){　　this.key=key;　　}<

54、;/p>　　public String toString(){ //覆蓋toString（）方法　　return key+"";　　}　　public int compareT

55、o(KeyType another){ //覆蓋Comparable接口中比較關鍵字大小的方法　　int thisVal=this.key;　　int anotherVal=another.key;　　return(thisVal<anotherVal?-1:(thisVal==a

56、notherVal?0:1));　　}　　}　　class ElementType{　　private String data;　　public Stri

57、ng getdata(){ //用戶可自定義其他數據項　　return data;　　}　　public void setdata(String data){　　this.dat

58、a=data;　　}　　public ElementType(String data){　　this.data=data;　　}　　public Elem

59、entType(){　　}　　public String toString(){ //覆蓋toString（）方法　　return data;　　}</b

60、>　　}　　五、詳細程序清單　　1、xuanze類　　import java.util.Scanner;　　p

61、ublic class xuanze{　　static SeqList ST=null;　　static void createSeachList() throws Exception{　　int maxSize=20;　　ST=new SeqList(maxSize);

62、　　int curlen;　　System.out.print("Please input table length:");　　Scanner sc=new Scanner(System.in);　　curlen=sc.nextInt();</p

63、>　　KeyType[] k= new KeyType[curlen];　　System.out.print("Please input keyword sequence:");　　for(int i=0;i<curlen;i++)　　k[i]=new Key

64、Type(sc.nextInt());　　for(int i=0;i<curlen;i++){　　RecordNode r=new RecordNode(k[i]);　　ST.insert(i, r); //從1號存儲單元開始存放數據元素　　}}&

65、lt;/b>　　static HashTable<String> ht=null;　　public static void main(String args[]) throws Exception　　{　　Syste

66、m.out.println("/***********************************************/");　　System.out.println(" 1.順序表的查找操作 ");　　System.out.println(&qu

67、ot; 2.有序表的查找操作 ");　　System.out.println(" 3.哈希表的查找操作 ");　　System.out.println(" 4.其它查找算

68、法 ");　　System.out.println(" 5.退出 ");　　System.out.println("/*************************************

69、**********/");　　System.out.println("請選擇1-5，謝謝??！");　　Scanner sc=new Scanner(System.in);　　while(true){　　switch(sc.nextInt()

70、)　　{　　case 1:　　createSeachList();　　System.out.print("Please input search keyword:");<

71、/p>　　Scanner sc1=new Scanner(System.in);　　KeyType key1=new KeyType(sc.nextInt());　　KeyType key2=new KeyType(sc.nextInt());　　System.out.println(

72、"seqSearch"+key1.getKey()+")="+ST.seqSearch(key1));　　System.out.println("seqSearch("+key2.getKey()+")="+ST.seqSearch(key2));　　System.out.p

73、rintln("如需其他操作，請繼續(xù)選擇，如不需要，請按5，謝謝！");　　break;　　case 2:　　createSeachList();　　System.out.pr

74、int("Please input search keyword:");　　Scanner sc2=new Scanner(System.in);　　KeyType key3=new KeyType(sc.nextInt());　　KeyType key4=new KeyType(sc.nex

75、tInt());　　System.out.println("binaryseqSearch("+key3.getKey()+")="+ST.binarySearch(key3));　　System.out.println("binaryseqSearch("+key4.getKey()+&quo

76、t;)="+ST.binarySearch(key4));　　System.out.println("如需其他操作，請繼續(xù)選擇，如不需要，請按5，謝謝！");　　break;　　case 3:String[] name ={"Wang&

77、quot;,"Li","Zhang","Liu","Chen","Yang","Huang","Zhao","Wu","Zhou","Du"};　　HashTable<String> h

78、t=new HashTable<String>(7);　　String elem1,elem2;　　System.out.print("插入元素：");　　for(int i=0;i<name.length;i++){　　ht.ins

79、ert(name[i]);　　System.out.print(name[i]+"");　　}　　System.out.print("\n原哈希表：");　　ht.printHashTable(

80、);　　elem1=name[2];　　System.out.print("查找"+elem1+"，"+(ht.contain(elem1)?"":"不")+"成功");　　elem2="san"

81、;;　　System.out.print("查找"+elem2+"，"+(ht.contain(elem1)?"":"不")+"成功");　　System.out.print("刪除"+elem1+"，"+(ht.r

82、emove(elem1)?"":"不")+"成功");　　System.out.print("刪除"+elem2+"，"+(ht.remove(elem2)?"":"不")+"成功");　　Sys

83、tem.out.println("新哈希表:");　　ht.printHashTable();　　System.out.println("如需其他操作，請繼續(xù)選擇，如不需要，請按5，謝謝！");　　break;&

84、lt;p>　　case 4:　　BSTree bstree=new BSTree();　　int[]k={50,13,63,8,36,90,5,10,18,70};　　String[] item={"Wang","Li",&quo

85、t;Zhang","Liu","Chen","Yang","Huang","Zhao","Wu","Zhou"};　　KeyType[] key=new KeyType[k.length];　　Elemen

86、tType[] elem=new ElementType[k.length];　　System.out.println("原序列：");　　for(int i=0;i<k.length;i++){　　key[i]=new KeyType(k[i]);<p&g

87、t;　　elem[i]=new ElementType(item[i]);　　if(bstree.insertBST(key[i],elem[i])){　　System.out.print("["+key[i]+","+elem[i]+"]");<

88、b>　　}　　}　　System.out.println("\n中根遍歷二叉排序樹：");　　bstree.inOrderTraverse(bstree.root);　　System.ou

89、t.println();　　KeyType keyvalue=new KeyType();　　keyvalue.setKey(63);　　RecordNode found=(RecordNode)bstree.searchBST(keyvalue);　　if(found!

90、=null){　　System.out.println("查找關鍵碼："+keyvalue+",成功！對應姓氏為："+found.getElement());　　}　　else{

91、　　System.out.println("查找關鍵碼："+keyvalue+",失敗！");　　}　　keyvalue.setKey(39);　　found=(RecordNode)bstree.searchBS

92、T(keyvalue);　　if(found!=null){　　System.out.println("查找關鍵碼："+keyvalue+",成功！對應姓氏為："+found.getElement());　　}&

93、lt;p>　　else{　　System.out.println("查找關鍵碼："+keyvalue+",失敗！");　　}　　keyvalue.setKey(13);

94、　　found=(RecordNode)bstree.removeBST(keyvalue);　　if(found!=null){　　System.out.println("刪除關鍵碼："+keyvalue+",成功！對應姓氏為："+found.getElement());

95、　　}　　else{　　System.out.println("刪除關鍵碼："+keyvalue+",失?。?quot;);　　}

96、　　System.out.println("\n刪除關鍵碼："+keyvalue+",后的中根遍歷序列：");　　bstree.inOrderTraverse(bstree.root);　　System.out.println("");

97、;　　System.out.println("如需其他操作，請繼續(xù)選擇，如不需要，請按5，謝謝！");　　break;　　case 5:　　System.out.println("已成功退出！");

98、　　return;　　}　　}}}　　2、Record Node類　　class RecordNode {</

99、p>　　private Comparable key; //關鍵字　　private Object element; //數據元素　　public Object getElement() {　　return element;

100、　　}　　public void setElement(Object element) {　　this.element = element;　　}　　public Comparable getKe

101、y() {　　return key;　　}　　public void setKey(Comparable key) {　　this.key = key;　　}</b&g

102、t;　　public RecordNode(Comparable key) { //構造方法1　　this.key = key;　　}　　public RecordNode(Comparable key, Object elemen

103、t) { //構造方法2　　this.key = key;　　this.element = element;　　}　　public String toString() { //覆蓋toString()方法&l

104、t;p>　　return "[" + key + "," + element + "]";　　}　　} 　　3、KeyType類

105、　class KeyType implements Comparable<KeyType> {　　private int key; //關鍵字　　public KeyType() {　　}　　public KeyTyp

106、e(int key) {　　this.key = key;　　}　　public int getKey() {　　return key;　　}</p

107、>　　public void setKey(int key) {　　this.key = key;　　}　　public int compareTo(KeyType another) { //覆蓋Comparable接口中比較關鍵字大小方法<

108、/p>　　int thisVal = this.key;　　int anotherVal = another.key;　　return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));

109、　}　　}　　4、SeqList類　　class SeqList {　　private RecordNode[] r; //順序表記錄結點數組　　private in

110、t curlen; //順序表長度,即記錄個數　　// 順序表的構造方法，構造一個存儲空間容量為maxSize的順序表　　public SeqList(int maxSize) {　　this.r = new RecordNode[maxSize]; // 為順序表分配maxSize個存儲單元&l

111、t;/p>　　this.curlen = 0; // 置順序表的當前長度為0　　}　　// 求順序表中的數據元素個數并由函數返回其值　　public int length() {<p

112、>　　return curlen; // 返回順序表的當前長度　　}　　public int getCurlen() {　　return curlen;　　}<

113、p>　　public void setCurlen(int curlen) {　　this.curlen = curlen;　　}　　// 在當前順序表的第i個結點之前插入一個RecordNode類型的結點x　　//其中i取值范

114、圍為：0≤i≤length()。　　//如果i值不在此范圍則拋出異常,當i=0時表示在表頭插入一個數據元素x,　　//當i=length()時表示在表尾插入一個數據元素x　　public void insert(int i, RecordNode x) throws Exception {

115、　　if (curlen == r.length) { // 判斷順序表是否已滿　　throw new Exception("順序表已滿");　　}　　if (i < 0|| i > curlen) { // i小于0

116、或者大于表長　　throw new Exception("插入位置不合理");　　}　　for (int j = curlen+1; j > i; j--) {　　r[j] = r[j - 1]; //

117、插入位置及之后的元素后移　　}　　r[i] = x; // 插入x　　this.curlen++; // 表長度增1　　}　　5、seqSearch

118、類（順序查找算法）　　public int seqSearch(Comparable key) {　　int i=0,n=length();　　while(i<n&&r[i].getKey().compareTo(key)!=0){

119、　　i++;　　}　　if(i<n){　　return i;　　}&l

120、t;p>　　else{　　return -1;　　}　　}　　6、binarySearch類（二分查找算法）

121、　public int binarySearch(Comparable key) {　　if (length() > 0) {　　int low = 0, high = length()-1 ; //查找范圍的下界和上界　　while (low <= high) {<p&

122、gt;　　int mid = (low + high) / 2; //中間位置，當前比較元素位置　　// System.out.print(r[mid].getKey() + "? ");　　if (r[mid].getKey().compareTo(key) == 0) {　　re

123、turn mid; //查找成功　　} else if (r[mid].getKey().compareTo(key) > 0) { //給定值更小　　high = mid - 1; //查找范圍縮小到前半段　　} el

124、se {　　low = mid + 1; //查找范圍縮小到后半段　　}　　}　　}

125、　return -1; //查找不成功　　}　　7、Node類　　class Node {　　private Object data;　　private

126、 Node next;　　public Node(){　　this(null,null);　　}　　public Node(Object data){　　this(data,null);<

127、;/p>　　}　　public Node(Object data,Node next){　　this.data=data;　　this.next=next;　　}<

128、;/p>　　public Object getData(){　　return data;　　}　　public Node getNext(){　　return next;<p&

129、gt;　　}　　public void setData(Object data){　　this.data=data;　　}　　public void setNext(Node next){<

130、/p>　　this.next=next;　　}}　　8、LinkList類　　class LinkList {　　private Node head=new Node();<p

131、>　　public void create(int n) throws Exception{　　Scanner sc=new Scanner(System.in);　　for(int j=0;j<n;j++)　　insert(0,sc.next());}　　p

132、ublic void insert(int i,Object x) throws Exception{　　Node p=head;　　int j=-1;　　while(p!=null&&j<i-1){　　p=p.

133、getNext();　　++j;　　}　　if(j>i-1||p==null)　　throw new Exception("插入位置不合法");&

134、lt;p>　　Node s=new Node(x);　　s.setNext(p.getNext());　　p.setNext(s);　　}　　public void remove(int i)throws Exception{&

135、lt;/p>　　Node p=head;　　int j=-1;　　while(p.getNext()!=null&&j<i-1){　　p=p.getNext();

136、++j;　　}　　if(j>i-1||p.getNext()==null)　　throw new Exception("刪除位置不合法");　　p.setNext(p.getNext().

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

《數據結構》課程設計實驗報告---有關查找的操作

文檔簡介

溫馨提示

最新文檔

評論

《數據結構》課程設計實驗報告---有關查找的操作

文檔簡介

溫馨提示

最新文檔

評論

免費下載