linearsearch.htm
来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 143 行
HTM
143 行
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>循序搜寻法（使用卫兵）</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 循序搜寻法（使用卫兵）</a></h1>
<h2>说明</h2>
搜寻的目的，是在“已排序的资料”中寻找指定的资料，而当中循序搜寻是最基本的搜寻法，只要从资料开头寻找到最后，看看是否找到资料即可。<br>
<h2>解法</h2>
初学者看到循序搜寻，多数都会使用以下的方式来进行搜寻：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">while(i < MAX) { </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> if(number[i] == k) { </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> printf("找到指定值"); </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> break; </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> } </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> i++; </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">} </span><br>
</div>
<br>
<br>
这个方法基本上没有错，但是可以加以改善，可以利用设定卫兵的方式，省去if判断式，卫兵通常设定在数列最后或是最前方，假设设定在列前方好了（索引0的
位置），我们从数列后方向前找，如果找到指定的资料时，其索引值不是0，表示在数列走访完之前就找到了，在程式的撰写上，只要使用一个while回圈就可
以了。<br>
<br>
下面的程式为了配合卫兵的设置，自行使用快速排序法先将产生的数列排序，然后才进行搜寻，若只是数字的话，通常您可以使用程式语言函式库所提供的搜寻函式。 <br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#include <time.h> <br>#define MAX 10 <br>#define SWAP(x,y) {int t; t = x; x = y; y = t;} <br><br>int search(int[]); <br>int partition(int[], int, int); <br>void quicksort(int[], int, int); <br><br>int main(void) { <br> int number[MAX+1] = {0}; <br> int i, find; <br><br> srand(time(NULL)); <br><br> for(i = 1; i <= MAX; i++) <br> number[i] = rand() % 100; <br><br> quicksort(number, 1, MAX); <br><br> printf("数列："); <br> for(i = 1; i <= MAX; i++) <br> printf("%d ", number[i]); <br> <br> printf("\n输入搜寻值："); <br> scanf("%d", &number[0]); <br><br> if(find = search(number)) <br> printf("\n找到数值于索引 %d ", find); <br> else <br> printf("\n找不到数值"); <br><br> printf("\n"); <br><br> return 0; <br>} <br><br>int search(int number[]) { <br> int i, k; <br> <br> k = number[0]; <br> i = MAX; <br> <br> while(number[i] != k) <br> i--; <br><br> return i; <br>} <br><br>int partition(int number[], int left, int right) { <br> int i, j, s; <br><br> s = number[right]; <br> i = left - 1; <br><br> for(j = left; j < right; j++) { <br> if(number[j] <= s) { <br> i++; <br> SWAP(number[i], number[j]); <br> } <br> } <br><br> SWAP(number[i+1], number[right]); <br> return i+1; <br>} <br><br>void quicksort(int number[], int left, int right) { <br> int q; <br><br> if(left < right) { <br> q = partition(number, left, right); <br> quicksort(number, left, q-1); <br> quicksort(number, q+1, right); <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class LinearSearch {<br> public static int search(int[] number, int des) {<br> int[] tmp = new int[number.length + 1];<br> <br> for(int i = 1; i < tmp.length; i++) {<br> tmp[i] = number[i-1]; <br> }<br> <br> tmp[0] = des;<br> <br> int k = tmp[0]; <br> int i = number.length; <br> <br> while(tmp[i] != k) <br> i--; <br><br> return i - 1; <br> }<br> <br> public static void main(String[] args) {<br> int[] number = {1, 4, 2, 6, 7, 3, 9, 8};<br> <br> QuickSort.sort(number);<br> <br> int find = LinearSearch.search(number, 3);<br> <br> if(find != 0) <br> System.out.println("找到数值于索引" + find); <br> else <br> System.out.println("找不到数值"); <br> }<br>} </pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?