搜尋的應用相當廣泛，例如在文件檔案中尋找相符的字句，在自己的硬碟中尋找過去有存檔的檔案，或是去某個網站查找資料，在搜尋引擎輸入關鍵字等等。搜尋太常用了，所以學習搜尋演算法也會是重要的課題。
可是搜尋演算法跟所用的資料結構關係密切，有排序的資料結構跟沒有排序的資料結構又有差別，就是說可以運用的搜尋演算法也有不同。有排序過的資料結構可以施用更有效率的二元搜尋演算法，然而目前我們的登入程式因為接受使用者新建帳號，所以採用的資料結構為沒有排序過的同質陣列，這無法採用二元搜尋演算法。
不過，有個更簡單的線性搜尋演算法，這是逐一從資料結構中比對資料項目使否與搜尋目標相同。其實，我們已經運用過了，就是在列印帳號名單的時候
95 96 97 98 99 100 101 | for (j = 0; j < SIZE; j++) { if (userID[j][0] == '\0') { break; } printf("%s - %s\n", userID[j], userCODE[j]);} |
如果字元陣列 userID[j] 的第一個字元為 '\0' ，就跳出迴圈，也就是說，程式一部分的任務是找到 '\0' ，這就是典型的線性搜尋的應用，所搜尋的是特定的字元 '\0' 。
我們現在要建置的是讓使用者輸入所要搜尋的帳號，因此程式稍有不同
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | // search 為查詢帳號指令if (!strcmp(instruction, "search")) { state = N; printf("\n請輸入要查找的帳號： "); scanf("%s", searchname); for (j = 0; j < SIZE; j++) { if (!strcmp(userID[j], searchname)) { state = Y; break; } } if (state == Y) { printf("\n帳號 %s 已經註冊，密碼是 %s\n", userID[j], userCODE[j]); } else if (state == N) { printf("\n還沒有 %s 的帳號註冊唷！\n", searchname); } continue; } |
我們仍是以狀態進行控制，若管理員輸入 search 指令，就會先將狀態 state 設成 N ，當然，這要加入之前前面宣告的列舉常數之中
105 | enum STATE {EXIT, RUN, WRONG_NAME, WRONG_CODE, Y, N}; |
然後要求管理員輸入要搜尋的帳號，接著便利用 for 迴圈在陣列中比對每一元素是否與目標值相同，若是有比對到相同的，狀態就會設成 Y 。
最後會依狀態顯示有找到或是沒找到的訊息。
管理模式的程式碼應調整如下
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | if (i == 0 && !strcmp(inputCode, userCODE[i])) { printf("\n\n您成功以管理員模式登入....\n"); printf("將入帳號管理模式，請在提示符號 # 後輸入指令\n"); while (1) { printf("\n# "); scanf("%s", instruction); // exit 為離開管理模式的指令 if (!strcmp(instruction, "exit")) { break; } // list 為列印使用者列表的指令 if (!strcmp(instruction, "list")) { printf("\n以下為所有註冊使用者的帳號及密碼\n"); printf("\n帳號 - 密碼\n"); for (j = 0; j < SIZE; j++) { if (userID[j][0] == '\0') { break; } printf("%s - %s\n", userID[j], userCODE[j]); } continue; } // search 為查詢帳號指令 if (!strcmp(instruction, "search")) { state = N; printf("\n請輸入要查找的帳號： "); scanf("%s", searchname); for (j = 0;j < SIZE; j++) { if (!strcmp(userID[j], searchname)) { state = Y; break; } } if (state == Y) { printf("\n帳號 %s 已經註冊，密碼是 %s\n", userID[j], userCODE[j]); } else if (state == N) { printf("\n還沒有 %s 的帳號註冊唷！\n", searchname); } continue; } // delete 為刪除帳號指令 if (!strcmp(instruction, "delete")) { printf("\n您即將開啟刪除使用者帳號的功能....\n"); continue; } // sort 為排序指令 if (!strcmp(instruction, "sort")) { printf("\n您即將開啟排序使用者帳號列表的功能....\n"); continue; } } printf("\n\n您即將離開管理模式，請重新登入....\n\n"); state = RUN; break;} |
完整的範例程式碼及編譯執行，請繼續參考
問題與討論
- 到網路上查有關二元搜尋演算法的說明，比較二元搜尋跟線性搜尋的優劣。
- 為什麼搜尋的部份要用狀態來控制？
- 還有哪些搜尋演算法呢？跟資料結構又有什麼關係呢？
沒有留言:
張貼留言