当前位置:   article > 正文

建立顺序表,实现顺序查找,折半查找,递归折半查找_建立一个无序表并实现对其顺序查找和折半查找,并对无序表进行插入排序、起泡排序

建立一个无序表并实现对其顺序查找和折半查找,并对无序表进行插入排序、起泡排序
  1. #include<iostream>
  2. using namespace std;
  3. const int MAXSIZE = 100;
  4. typedef int KeyType;
  5. struct datanode
  6. {
  7. KeyType key;
  8. // char ch;
  9. };
  10. class Sqtable
  11. {
  12. private:
  13. datanode r[MAXSIZE];
  14. int n;
  15. public:
  16. Sqtable(int nn);
  17. void Creat();
  18. void Output();
  19. void Sq_Search(KeyType K);
  20. void Binary_Search(KeyType K);
  21. void D_Search(int m, int k,KeyType K);
  22. };
  23. Sqtable::Sqtable(int nn)
  24. {
  25. n = nn;
  26. for(int i=0; i<n; i++)
  27. r[i].key = 0;
  28. }
  29. void Sqtable::Creat()
  30. {
  31. KeyType kk;
  32. cout<<"\n 输入第1个参数,以-1结束";
  33. cin>>kk;
  34. int i=0;
  35. while(kk!=-1 && i<n)
  36. {
  37. r[i].key = kk;
  38. i++;
  39. cout<<"\n 输入第"<<i+1<<"个参数,以-1结束";
  40. cin>>kk;
  41. }
  42. }
  43. void Sqtable::Output()
  44. {
  45. int i=0;
  46. cout<<"\n";
  47. while(r[i].key!=0)
  48. {
  49. cout<<r[i].key<<"\t";
  50. i++;
  51. }
  52. }
  53. void Sqtable::Sq_Search(KeyType K)
  54. {
  55. int i=0;
  56. while(r[i].key != K)
  57. i++;
  58. if(i<n)
  59. {
  60. cout<<"\n查找成功,在位置"<<i+1;
  61. }
  62. else
  63. cout<<"\n 查找失败";
  64. }
  65. void Sqtable::Binary_Search(KeyType K)
  66. {
  67. int m,low,high,find;
  68. low = 0;
  69. high = n-1;
  70. find = 0;
  71. do
  72. {
  73. m = (low+high)/2;
  74. if(K==r[m].key)
  75. {
  76. cout<<"\n查找成功,该数据在位置:"<<m+1;
  77. find = 1;
  78. }
  79. else if(K<r[m].key)
  80. high = m-1;
  81. else
  82. low = m+1;
  83. }while(low<=high && find ==0);
  84. if(find == 0)
  85. cout<<"\n 查找失败";
  86. }
  87. void Sqtable::D_Search(int low,int high, KeyType K)
  88. {
  89. int m = (low+high)/2;
  90. if(r[m].key==K)
  91. cout<<"\n查找成功,位置在:"<<m+1;
  92. else if(low==high && K!=r[m].key)
  93. cout<<"\n查找失败";
  94. else if(K<r[m].key)
  95. D_Search(low, m-1, K);
  96. else
  97. D_Search(m+1,high,K);
  98. }
  99. int main(int argc, char *argv[])
  100. {
  101. int m,K,nn;
  102. cout<<"\n输入顺序表长度";
  103. cin>>nn;
  104. Sqtable ss(nn);
  105. cout<<"\n 1.建立顺序表";
  106. cout<<"\n 2.顺序查找";
  107. cout<<"\n 3.折半查找";
  108. cout<<"\n 4.递归折半查找";
  109. cout<<"\n 5.程序结束";
  110. cout<<"\n请输入你的选择(1,2,3,4,5)";
  111. cin>>m;
  112. while(m>0 && m<5)
  113. {
  114. switch(m)
  115. {
  116. case 1:
  117. ss.Creat();
  118. ss.Output();
  119. break;
  120. case 2:
  121. cout<<"\n请输入要查找的元素";
  122. cin>>K;
  123. ss.Sq_Search(K);
  124. break;
  125. case 3:
  126. cout<<"\n请输入要查找的元素";
  127. cin>>K;
  128. ss.Binary_Search(K);
  129. break;
  130. case 4:
  131. cout<<"\n请输入要查找的元素";
  132. cin>>K;
  133. ss.D_Search(0,nn-1,K);
  134. break;
  135. default:
  136. break;
  137. }
  138. cout<<"\n请输入你的选择(1,2,3,4,5)";
  139. cin>>m;
  140. }
  141. cout<<"\n程序结束";
  142. return 0;
  143. }

 

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号