上機實踐報告期末

1、四、調(diào)試過程調(diào)試的過程很繁雜，有時一個半天都會被代碼弄的焦頭爛額的，不過當真正運行出來后，那種內(nèi)心的喜悅和滿足感，又讓我覺得這些時間花的是值的！在調(diào)試過程中主要遇到如下的問題：1.type redefine：有些時候會遇到 enum 形式的數(shù)據(jù) redefine，很多時候是頭文件 include 出錯了，以至于在實現(xiàn)二叉樹的時候?qū)ｉT用一個.h 文件存放“enum Error_codeunderflow, overflow,sucs;”2.遞歸函數(shù)：遞歸是編寫算法中的難點，在理解序，畫圖等方法可以幫助理解。的時候也會出現(xiàn)問題，不過通過自己走程3.模板類在后半學期也用到很多，在調(diào)試過程中也要注意出

2、現(xiàn)已定義 class 的模板類時，要注意 include 一下其.cpp 文件。4.調(diào)試的技巧還有待提高，以前一直知識死看代碼，“我到底哪兒出問題了??？”但是就是想不出來。一問老師，原來通過分布調(diào)試的方法可以看出在那一步有問題。這種能力要逐漸培養(yǎng)！五、總結(jié)是 include 頭文件總是出問題，一學期很快就過去了，上半期在編程中遇到的最大不過下半學期對老師寫的代碼認真閱讀后，摸清了門道，出問題的次數(shù)明顯減少了。這是一個不斷熟悉的過程。下半學期主要對樹進行了學前面的 Stack，Queue，List 學習的基礎(chǔ)上，對這種新型高效的數(shù)據(jù)結(jié)構(gòu)的學習讓我了解了數(shù)據(jù)結(jié)構(gòu)在一項工程項目中是多么重要。一種高效

3、的數(shù)據(jù)結(jié)構(gòu)是提高效率的關(guān)鍵。在關(guān)注代碼的同時，也更加關(guān)注執(zhí)行過程，通過畫圖幫助理解。除了樹，還學習了圖，雖然在離散數(shù)學里已經(jīng)學過，但只是些基本概念，用編程實現(xiàn)遍歷和求最短路徑是一個“艱難”的過程，但是當真正實現(xiàn)的時候，就會體會到計算機的方便了。學習的過程是一個不斷積累的過程，在今后的學習中一定還會用到數(shù)據(jù)結(jié)構(gòu)的東西。這個學期學到的知識，培養(yǎng)的技能還有待在今后的學習中不斷擴充和提高。同時在編寫代碼的同時還應(yīng)注意算法的分析，以及良好編程的養(yǎng)成。六、附錄（代碼集 / 運行結(jié)果 / 實驗感悟）1.實現(xiàn) Hash_table（說明：此處省略key.h /key.cpp/ record h/ record

4、.cpp 文件）/Hash_table.h*#include Record.henum Error_codenot_present, overflow, duplicate_error, sucs;consthash_size = 97;class Hash_table public:void clear( );Error_code insert(const Record &new_entry);Error_code retrieve(const Key &Error_code remove(const Key &, Record &found) const;, Record &found);

5、private:Record tablehash_size;hash(const Record &new_entry) hash(const Key &new_entry);/Hash_table.cpp*#include Hash_table.hvoid Hash_table : clear()for(i=0; ihash_size; i+) Record tmp; tablei=tmp;Error_code Hash_table : insert(const Record &new_entry)/*t: If the Hash table is full, a code of overfl

6、ow is returned. If the table alreadycontains an item with the key ofnew entry a code of duplicate error is returned.Otherwise: The Record new entry is insertedo the Hash tableand sucs is returned.Uses: Methods for classes Key , and Record . The function hash . */Error_code result = sucs;probe_count,

7、 / Counter to be suret table is not full.increment, / Increment used for quadratic be; /ition currently probedhe hash be = hash(new_entry); probe_count = 0;increment = 1;while (tableprobe != 0 / Is the location empty?& tableprobe != -1 / empty because delete & tableprobe != new_e

8、ntry / Duplicate key?& probe_count (hash_size + 1)/2) / Has overflow occurred?probe_count+;probe = (probe + increment)%hash_size;increment += 2; / Prepare increment for next iteration.if (tableprobe = 0) tableprobe = new_entry;if (tableprobe = -1) tableprobe = new_entry;/ Insert new entry.else if (t

9、ableprobe = new_entry) result = duplicate_error; else result = overflow; / The table is full.return result;Error_code Hash_table : retrieve(const Key &, Record &found) constprobe_count, / Counter to be suret table is not full.increment, / Increment used for quadratic be; /ition currently

10、probedhe hash be = hash(); probe_count = 0;increment = 1;while (tableprobe != 0 / Is the location empty?& tableprobe.the_key() !=.the_key() / not found& probe_count (hash_size + 1)/2) / Has overflow occurred? probe_count+;probe = (probe + increment)%hash_size;increment += 2; / Prepare incre

11、ment for next iteration.if (tableprobe.the_key() = found = tableprobe;.the_key()return sucs;else return not_present;Error_code Hash_table : remove(const Key &, Record &found)probe_count, / Counter to be suret table is not full.increment, / Increment used for quadratic be; /ition currently

12、 probedhe hash be = hash();probe_count = 0;increment = 1;while (tableprobe != 0 / Is the location empty?& tableprobe.the_key() !=.the_key() / not found& probe_count (hash_size + 1)/2) / Has overflow occurred? probe_count+;probe = (probe + increment)%hash_size;increment += 2; / Prepare incre

13、ment for next iteration.if (tableprobe.the_key() =found=tableprobe; tableprobe=-1;/attention.the_key()return sucs;else return not_present;hash(const Record &new_entry)return new_entry.the_key()%hash_size;hash(const Key &new_entry)return new_entry.the_key()%hash_size;/Main.cpp*#include Hash_Table.h #

14、include iostream.hvoid main()Hash_table myhash; myhash.insert(Record(3,20); myhash.insert(Record(5,30); myhash.insert(Record(9,50);Record;myhash.retrieve(Key(5),);coutKey: =Record(0,0);.the_key()The other: .the_other()endl;myhash.retrieve(Key(3),);coutKey: .the_key()The other: .the_other()endl;=Reco

15、rd(0,0); myhash.remove(Key(3),);coutKey: .the_key()The other: .the_other()endl;=Record(0,0); myhash.retrieve(Key(3),);coutKey: .the_key()The other: .the_other()endl;cin.get();運行結(jié)果：實驗感悟：這次實驗讓我對 Hash 表的實現(xiàn)更加熟悉和了解了。哈希函數(shù)采用了求余的辦法，即通過余數(shù)確定該 record 放在數(shù)組的那個位置。而解決的方法選擇了開放地址法中的平方探測法。2. /P442 E5 *template Binary

16、_tree :leaves()Binary_node *current=root; return recursive_leaves( current );template Binary_tree :recursive_leaves(Binary_node *current)if(current-left = NULL & current-right = NULL) leaves_count+;elseBinary_node *tmp1=current-left; Binary_node *tmp2=current-right; if(tmp1 != NULL)recursive_leaves(

17、tmp1); if(tmp2 != NULL)recursive_leaves(tmp2);return leaves_count;/Main.cpp void main()Binary_tree mytree;for(i=0; i10; i+)mytree.insert(Record(i);coutThe Preorder of the tree is :endl;mytree.preord coutendl;r);coutThe number of the leaveshe tree is mytree.leaves() . endl;運行結(jié)果：3./P443 E14*template v

18、oid Binary_tree :erchange( )/*t:he tree all pairs of left and right links are swapped round. */recursive_erchange(root);template void Binary_tree : recursive_erchange (Binary_node *sub_root)/*t:he subtree rooted at sub_root all pairs of left and right links are swapped. */if (sub_root != NULL) Binar

19、y_node *tmp = sub_root-left; sub_root-left = sub_root-right;sub_root-right = tmp;recursive_erchange(sub_root-left); recursive_erchange(sub_root-right);/Main.cpp void main()Binary_tree mytree;for(i=1; i=8; i+)mytree.insert(Record(i);coutThe Preorder of the tree is :endl;mytree.preord coutendl;r);mytr

20、ee.erchange();coutAfter theerchange pros:endl;coutThe Preorder of the tree is :endl;mytree.preord coutendl;r);運行結(jié)果：實驗感悟：通過 2 ,3 題中的函數(shù)實現(xiàn)，讓我對樹這一概念理解更加透徹，對樹的結(jié)構(gòu)更加明晰了。而且還知道了，遞歸的作用是多么大，可以使代碼更加簡便。但是遞歸算法想出來確實很難，這需要需多熟悉遞歸算法運用的場合，了解他的實質(zhì)，并且多動手親自寫。4.實現(xiàn)（平衡）二叉查找樹（說明：此處省略去Record，Mystack，Binary_node,Binary_tree 的 h

21、 及.cpp 文件）/Search_tree.h*#include Binary_tree.cpptemplate class Search_tree: public Binary_tree public:Error_code insert(const Record &new_data);Error_code remove(const Record & Error_code tree_search(Record &);) const;private: / Add auxiliary function prototypes here.Binary_node *search_for_node(Bi

22、nary_node* sub_root, const Record & Error_code search_and_insert(Binary_node * &sub_root, const Record &new_data);) const;Error_code search_and_destroy(Binary_node* &sub_root, const Record & Error_code remove_root(Binary_node * &sub_root););/Search_tree.cpp*#include Search_tree.htemplate Binary_node

23、 *Search_tree : search_for_node(Binary_node* sub_root, const Record &if (sub_root = NULL | sub_root-data = return sub_root;) const)else if (sub_root-data right,);else return search_for_node(sub_root-left,);template Error_code Search_tree : tree_search(Record &) constError_code result = sucs;Binary_n

24、ode *found = search_for_node(root, if (found = NULL)result = not_present;else= found-data; return result;);template Error_code Search_tree : insert(const Record &new_data)Error_code result=search_and_insert(root, new_data);if(result=suc return result;s)count+;template Error_code Search_tree : search

25、_and_insert( Binary_node * &sub_root, const Record &new_data)if (sub_root = NULL) sub_root = new Binary_node(new_data);return sucs;else if (new_data data)return search_and_insert(sub_root-left, new_data); else if (new_data sub_root-data)return search_and_insert(sub_root-right, new_data); else return

26、 duplicate_error;template Error_code Search_tree : remove(const Record &)/*t: If a Record wikey matchingt ofbelongs to the Search tree acode of sucs is returned and the corresponding node is removed from thetree. Otherwise, a code of not present is returned. Uses: Function search_and_destroy */Error

27、_code result=search_and_destroy(root,);if(result=suc return result;s)count-;template Error_code Search_tree : search_and_destroy( Binary_node* &sub_root, const Record &)/* Pre: sub root is either NULL or pos to a subtree of the Search tree .t: If the key ofis nothe subtree, a code of not_present is

28、returned.Otherwise, a code of sucs is returned and the subtree node containinghas been removed in such a wayt the properties of a binary searchtree have been p.Uses: Functions search and destroy recursively and remove root */if (sub_root = NULL | sub_root-data = return remove_root(sub_root);)else if

29、 (data)return search_and_destroy(sub_root-left,);elsereturn search_and_destroy(sub_root-right,);template Error_code Search_tree : remove_root(Binary_node * &sub_root)/* Pre: sub root is either NULL or pos to a subtree of the Search tree .t: If sub root is NULL , a code of not_present is returned. Ot

30、herwise, the root ofthe subtree is removed in such a wayt the properties of a binary search treeare p. The parameter sub root is reset as the root of the modifiedsubtree, and sucs is returned. */if (sub_root = NULL) return not_present; Binary_node *to_delete = sub_root;/ Remember node tete at end.if

31、 (sub_root-right = NULL) sub_root = sub_root-left;else if (sub_root-left = NULL) sub_root = sub_root-right;else / Neither subtree is empty.to_delete = sub_root-left; / Move left to find predesor.Binary_node *parent = sub_root; / parent of to_delete while (to_delete-right != NULL) / to_delete is not

32、the predesor.parent = to_delete;to_delete = to_delete-right;sub_root-data = to_delete-data; / Move from to_delete to root. if (parent = sub_root) sub_root-left = to_delete-left;else parent-right = to_delete-left;delete to_delete; / Remove to_delete from tree.return sucs;/Main.cpp*#include iostream.h

33、 #include Search_tree.cpp #include Record.htemplate void pr(Entry &x)coutx;void main()Search_tree mytree; mytree.insert(Record(2); mytree.insert(Record(4); mytree.insert(Record(1); mytree.insert(Record(3);coutTree size is: mytree.size()endl;coutPreorder:endl;mytree.preord coutendl;r);coutinorder:end

34、l;運行結(jié)果：mytree.inord coutendl;r);cout mytree.torder:endl;tordr);coutendl;mytree.remove(Record(4);coutTree size is: mytree.size()endl;coutPreorder:endl;mytree.preord coutendl;r);coutinorder:endl;mytree.inord coutendl;r);cout mytree.torder:endl;tordr);coutendl;cin.get();5.實現(xiàn) AVL 樹（說明：此處省略Record，MyStack

35、，Binary_node,Binary_tree,Seach_tree 的 h 和.cpp 文件）/AVL_node.h*#include Binary_node.cpptemplate struct AVL_node: public Binary_node / additional data member: Balance_factor balance;/ constructors:AVL_node( ); AVL_node(const Record &x);/ overridden virtual functions:void set_balance(Balance_factor b);B

36、alance_factet_balance( ) const;/AVL_tree.h*#include Search_tree.cpptemplate class AVL_tree: public Search_tree public:Error_code insert(const Record &new_data); Error_code remove(Record &old_data);private: / Add auxiliary function prototypes here.Error_code avl_insert(Binary_node * &sub_root,const R

37、ecord &new_data, bool &taller); void roe_left(Binary_node * &sub_root);void roe_right(Binary_node * &sub_root); void right_balance(Binary_node * &sub_root); void left_balance(Binary_node * &sub_root);/add for removeError_code avl_remove(Binary_node * &sub_root, Record &new_data, bool &shorter); bool

38、 right_balance2(Binary_node * &sub_root);bool left_balance2(Binary_node * &sub_root);/AVL_node.cpp*#include AVL_node.htemplate AVL_node : AVL_node()left = NULL; right = NULL;balance = equal_height;template AVL_node : AVL_node(const Record &x)data = x;left = NULL; right = NULL;balance = equal_height;

39、template void AVL_node : set_balance(Balance_factor b)balance = b;template Balance_factor AVL_node : get_balance( ) constreturn balance;/AVL_tree.cpp*#include AVL_tree.htemplate Error_code AVL_tree : insert(const Record &new_data)bool taller; / Has the tree grown in height? return avl_insert(root, n

40、ew_data, taller);template Error_code AVL_tree : avl_insert(Binary_node * &sub_root, const Record &new_data, bool &taller)Error_code result = sucs; if (sub_root = NULL) sub_root = new AVL_node(new_data); taller = true;else if (new_data = sub_root-data) result = duplicate_error;taller = false;else if

41、(new_data data) / Insert in left subtree. result = avl_insert(sub_root-left, new_data, taller);if (taller = true)switch (sub_root-get_balance( ) / Change balance factors. case left_higher:left_balanub_root);taller = false; / Rebalancing always shortens the tree. break;case equal_height:sub_root-set_

42、balance(left_higher); break;case right_higher:sub_root-set_balance(equal_height); taller = false;break;else / Insert in right subtree.result = avl_insert(sub_root-right, new_data, taller); if (taller = true)switch (sub_root-get_balance( ) case left_higher:sub_root-set_balance(equal_height); taller =

43、 false;break;case equal_height:sub_root-set_balance(right_higher); break;case right_higher:right_balanub_root);taller = false; / Rebalancing always shortens the tree. break;return result;template void AVL_tree : roe_left(Binary_node * &sub_root)if (sub_root = NULL | sub_root-right = NULL) / imsible

44、casescout WARNING: program error detected in roe left endl;else Binary_node *right_tree = sub_root-right; sub_root-right = right_tree-left;right_tree-left = sub_root; sub_root = right_tree;template void AVL_tree : roe_right(Binary_node * &sub_root)if (sub_root = NULL | sub_root-left = NULL) / imsibl

45、e casescout WARNING: program error detected in roe right endl; else Binary_node *left_tree = sub_root-left; sub_root-left = left_tree-right;left_tree-right = sub_root; sub_root = left_tree;template void AVL_tree : right_balance(Binary_node * &sub_root)Binary_node * &right_tree = sub_root-right; swit

46、ch (right_tree-get_balance( ) case right_higher: / single roion left sub_root-set_balance(equal_height); right_tree-set_balance(equal_height); roe_left(sub_root);break;case equal_height: / imsible casecout WARNING: program error in right balance endl;case left_higher: / double roion leftBinary_node

47、*sub_tree = right_tree-left; switch (sub_tree-get_balance( ) case equal_height:sub_root-set_balance(equal_height); right_tree-set_balance(equal_height); break;case left_higher:sub_root-set_balance(equal_height); right_tree-set_balance(right_higher); break;case right_higher:sub_root-set_balance(left_

48、higher); right_tree-set_balance(equal_height); break;sub_tree-set_balance(equal_height); roe_right(right_tree);roe_left(sub_root); break;template void AVL_tree : left_balance(Binary_node * &sub_root)Binary_node * &left_tree = sub_root-left;switch (left_tree-get_balance( ) case left_higher: / single

49、ro ion leftsub_root-set_balance(equal_height); left_tree-set_balance(equal_height); ro e_right(sub_root);break;case equal_height: / imsible casecout WARNING: program error in right balance endl;case right_higher: / double roion leftBinary_node *sub_tree = left_tree-right; switch (sub_tree-get_balanc

50、e( ) case equal_height:sub_root-set_balance(equal_height); left_tree-set_balance(equal_height); break;case right_higher:sub_root-set_balance(equal_height); left_tree-set_balance(left_higher); break;case left_higher:sub_root-set_balance(right_higher); left_tree-set_balance(equal_height); break;sub_tr

51、ee-set_balance(equal_height); roe_left(left_tree);roe_right(sub_root); break;/template Error_code AVL_tree : remove(Record &new_data)bool shorter=true; / Has the tree shorter in height? return avl_remove(root, new_data, shorter);template Error_code AVL_tree : avl_remove(Binary_node * &sub_root, Reco

52、rd &new_data, bool &shorter)Error_code result = sucs; Record sub_record;if (sub_root = NULL) shorter = false; return not_present;else if (new_data = sub_root-data) Binary_node *to_delete = sub_root;/ Remember node tete at end.if (sub_root-right = NULL) sub_root = sub_root-left; shorter = true;delete

53、 to_delete; / Remove to_delete from tree.return sucs;else if (sub_root-left = NULL) sub_root = sub_root-right; shorter = true;delete to_delete; / Remove to_delete from tree.return sucs;else / Neither subtree is empty.to_delete = sub_root-left; / Move left to find predesor.Binary_node *parent = sub_r

54、oot; / parent of to_delete while (to_delete-right != NULL) / to_delete is not the predeparent = to_delete;to_delete = to_delete-right;sor./sub_root-data = to_delete-data; / Move data from to_delete to root. new_data = to_delete-data;sub_record = new_data;if (new_data data) / remove in left subtree.

55、result = avl_remove(sub_root-left, new_data, shorter); if (shorter = true)switch (sub_root-get_balance( ) / Change balance factors. case left_higher:sub_root-set_balance(equal_height); break;case equal_height:sub_root-set_balance(right_higher); shorter = false;break;case right_higher:if(sub_record.t

56、he_key()!=0)sub_root-data = sub_record; / Move data from to_delete to root. shorter = right_balance2(sub_root);break;if (new_data sub_root-data) / remove in right subtree. result = avl_remove(sub_root-right, new_data, shorter); if (shorter = true)switch (sub_root-get_balance( ) / Change balance fact

57、ors. case left_higher:if(sub_record.the_key()!=0)sub_root-data = sub_record; / Move data from to_delete to root. shorter = left_balance2(sub_root);break;case equal_height:sub_root-set_balance(left_higher); shorter = false;break;case right_higher:sub_root-set_balance(equal_height); break;return resul

58、t;template bool AVL_tree : right_balance2(Binary_node * &sub_root)bool shorter;Binary_node * &right_tree = sub_root-right; switch (right_tree-get_balance( ) case right_higher: / single roion left sub_root-set_balance(equal_height); right_tree-set_balance(equal_height); roe_left(sub_root);shorter = t

59、rue; break;case equal_height: / single roion left right_tree-set_balance(left_higher); roe_left(sub_root);shorter = false; break;case left_higher: / double roion left Binary_node *sub_tree = right_tree-left; switch (sub_tree-get_balance( ) case equal_height:sub_root-set_balance(equal_height); right_

60、tree-set_balance(equal_height); break;case left_higher:sub_root-set_balance(equal_height); right_tree-set_balance(right_higher); break;case right_higher:sub_root-set_balance(left_higher); right_tree-set_balance(equal_height); break;sub_tree-set_balance(equal_height); roe_right(right_tree);roe_left(s