introduction searching algorithms c
Μια επισκόπηση της αναζήτησης αλγορίθμων στο C ++.
Συνεχίζουμε να ψάχνουμε κάτι ή άλλο στην καθημερινή μας ζωή. Όπως και η καθημερινή μας ζωή, ως επαγγελματίας λογισμικού, πρέπει να αναζητήσουμε πληροφορίες στον υπολογιστή μας. Η ανάκτηση πληροφοριών πρέπει να γίνει γρήγορα, καθώς δεν μπορούμε να χάσουμε μεγάλο μέρος του χρόνου μας αναζητώντας πληροφορίες.
Ως εκ τούτου, χρειαζόμαστε μερικές αποτελεσματικές τεχνικές αναζήτησης ή αλγόριθμους που μπορούν να αναζητήσουν ένα δεδομένο κομμάτι πληροφοριών σε σύντομο χρονικό διάστημα και να δώσουν στον χρήστη έτσι ώστε ο χρήστης να μπορεί να προχωρήσει με τις άλλες εργασίες.
=> Επισκεφθείτε εδώ για την πλήρη λίστα μαθημάτων C ++.
Τι θα μάθετε:
Τεχνικές αναζήτησης
Έχουμε δύο κύριες τεχνικές αναζήτησης που χρησιμοποιούνται κυρίως για την αναζήτηση πληροφοριών.
Αυτά περιλαμβάνουν:
- Γραμμική αναζήτηση
- Δυαδική αναζήτηση
Σε αυτό το σεμινάριο, θα διερευνήσουμε λεπτομερώς και τις δύο αυτές τεχνικές αναζήτησης.
Γραμμική αναζήτηση
Αυτή είναι η πιο βασική τεχνική αναζήτησης και είναι πιο εύκολο να εφαρμοστεί επίσης. Σε μια γραμμική αναζήτηση, το κλειδί προς αναζήτηση συγκρίνεται γραμμικά με κάθε στοιχείο της συλλογής δεδομένων. Αυτή η τεχνική λειτουργεί αποτελεσματικά σε γραμμικές δομές δεδομένων.
Ας εξετάσουμε τον ακόλουθο πίνακα.
Πάνω είναι η σειρά επτά στοιχείων. Αν θέλουμε να αναζητήσουμε το κλειδί = 23, ξεκινώντας από το 0ουστοιχείο, η τιμή κλειδιού θα συγκριθεί με κάθε στοιχείο. Μόλις το στοιχείο κλειδί ταιριάζει με το στοιχείο του πίνακα, τότε θα επιστραφεί η συγκεκριμένη θέση. Σε αυτήν την περίπτωση, το 4 θα επιστραφεί καθώς το κλειδί-τιμή ταιριάζει με την τιμή σε αυτήν την τοποθεσία.
Έχουμε εφαρμόσει μια γραμμική αναζήτηση χρησιμοποιώντας C ++ και Java γλώσσα παρακάτω.
Εφαρμογή C ++
#include #include using namespace std; int main() { int myarray(10) = {21,43,23,54,75,13,5,8,25,10}; int key,loc; cout<<'The input array is'<key; for (int i = 0; i<10; i++) { if(myarray(i) == key) { loc = i+1; break; } else loc = 0; } if(loc != 0) { cout<<'Key found at position '< Παραγωγή:
μετατρέψτε το youtube σε αρχείο wav δωρεάν
Ο πίνακας εισόδου είναι
21 43 23 54 75 13 5 8 25 10
Εισαγάγετε το κλειδί προς αναζήτηση: 3
Δεν ήταν δυνατή η εύρεση δεδομένου κλειδιού στον πίνακα
Ο πίνακας εισόδου είναι
21 43 23 54 75 13 5 8 25 10
Εισαγάγετε το κλειδί προς αναζήτηση: 75
Βρέθηκε κλειδί στη θέση 5 του πίνακα
Εφαρμογή Java
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String() args) { int() myarray = {21,43,23,54,75,13,5,8,25,10}; int key,location=0; Scanner sc = new Scanner(System.in); System.out.println('The input array is'); for(int i=0;i<10;i++){ System.out.print(myarray(i)+' '); } System.out.println('
'); System.out.println('Enter key'); key = sc.nextInt(); for(int i = 0; i<10; i++) { if(myarray(i)==key) { location = i+1; break; } else location = 0; } if(location != 0) { System.out.println('key found at location ' + location); } else System.out.println('Key not found'); } }
Παραγωγή:
Ο πίνακας εισόδου είναι
21 43 23 54 75 13 5 8 25 10
Εισάγετε κλειδί
εφαρμογή κάρτας δωρεάν χρόνου για Android
2. 3
το κλειδί βρέθηκε στην τοποθεσία 3
Η γραμμική αναζήτηση μπορεί να πραγματοποιηθεί σε οποιαδήποτε γραμμική δομή δεδομένων που έχει ταξινομημένα ή μη ταξινομημένα στοιχεία. Χρειάζεται όμως μεγαλύτερος χρόνος εάν υπάρχουν πάρα πολλά στοιχεία και εάν το βασικό στοιχείο είναι προς το τέλος καθώς κάθε στοιχείο συγκρίνεται με την τιμή κλειδιού.
Δυαδική αναζήτηση
Η δυαδική αναζήτηση είναι μια τεχνική που χρησιμοποιεί την τεχνική «διαίρεση και κατάκτηση» για αναζήτηση ενός κλειδιού. Λειτουργεί σε μια ταξινομημένη γραμμική λίστα στοιχείων. Η ταξινομημένη λίστα είναι η βασική απαίτηση για να λειτουργεί μια δυαδική αναζήτηση.
Στη μέθοδο δυαδικής αναζήτησης, η λίστα χωρίζεται επανειλημμένα σε μισό και το βασικό στοιχείο αναζητείται και στα δύο μισά της λίστας έως ότου βρεθεί το κλειδί.
Για παράδειγμα,ας πάρουμε την ακόλουθη σειρά 10 στοιχείων.

Ας πούμε ότι το κλειδί = 21 πρέπει να αναζητηθεί στον πίνακα.
Ας υπολογίσουμε τη μεσαία θέση του πίνακα.
Mid = 0 + 9/2 = 4
Για παράδειγμα,ας πάρουμε την ακόλουθη σειρά 10 στοιχείων.

Κλειδί = 21
Πρώτον, θα συγκρίνουμε την τιμή κλειδιού με το στοιχείο (mid). Βρίσκουμε ότι η τιμή του στοιχείου στα μέσα = 21.

Έτσι βρίσκουμε αυτό το κλειδί = (mid). Εξ ου και το κλειδί βρίσκεται.
κλειδί = 25

Συγκρίνουμε πρώτα την βασική τιμή με τα μέσα. Έτσι (21)<25), we will directly search for the key in the upper half of the array.
c ++ μετατρέψτε τον πίνακα char σε int

Τώρα πάλι θα βρούμε το μέσο για το άνω μισό του πίνακα.
Mid = 4 + 9/2 = 6
Η τιμή στην τοποθεσία (mid) = 25

Τώρα συγκρίνουμε το βασικό στοιχείο με το μεσαίο στοιχείο. Έτσι (25 == 25), έτσι βρήκαμε το κλειδί στην τοποθεσία (mid).
Διαιρούμε επανειλημμένα τον πίνακα και συγκρίνοντας το βασικό στοιχείο με το μέσο, αποφασίζουμε σε ποιο μισό θα αναζητήσουμε το κλειδί.
Παρακάτω παρατίθενται η εφαρμογή C ++ και Java για δυαδική αναζήτηση.
Εφαρμογή C ++
#include #include using namespace std; int binarySearch(int myarray(), int beg, int end, int key) { int mid; if(end >= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<'Key found at location '< Παραγωγή:
Ο πίνακας εισόδου είναι
5 8 10 13 21 23 25 43 54 75
Εισαγάγετε το κλειδί που πρέπει να αναζητήσετε: 21
Βρέθηκε κλειδί στην τοποθεσία 5

Εφαρμογή Java
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String() args) { int() myarray = {5,8,10,13,21,23,25,43,54,75}; int key, location = -1; System.out.println('The input array is'); for(int i=0;i= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) Παραγωγή:
Ο πίνακας εισόδου είναι
5 8 10 13 21 23 25 43 54 75
Εισαγάγετε το κλειδί προς αναζήτηση
είκοσι ένα
η θέση του κλειδιού είναι 5
Η δυαδική αναζήτηση είναι πιο αποτελεσματική από άποψη χρόνου και ορθότητας. Η τεχνική γραμμικής αναζήτησης σπάνια χρησιμοποιείται καθώς είναι πιο δυσκίνητη και πιο αργή. Η δυαδική αναζήτηση είναι πολύ πιο γρήγορη σε σύγκριση με μια γραμμική αναζήτηση.
συμπέρασμα
Οι τεχνικές αναζήτησης μας βοηθούν να αναζητήσουμε πληροφορίες που είναι αποθηκευμένες σε έναν υπολογιστή, έτσι ώστε ο χρήστης να μπορεί να προχωρήσει σε άλλες εργασίες επεξεργασίας πληροφοριών. Η τεχνική γραμμικής αναζήτησης είναι απλή και ευκολότερη, αλλά δεν χρησιμοποιείται ευρέως.
Η τεχνική δυαδικής αναζήτησης είναι πολύ πιο γρήγορη και αποτελεσματική και ως εκ τούτου χρησιμοποιείται εκτενώς.
Στο επερχόμενο σεμινάριό μας, θα διερευνήσουμε λεπτομερώς τις διάφορες τεχνικές ταξινόμησης.
=> Ανατρέξτε στον τέλειο οδηγό εκπαίδευσης C ++ εδώ.
Συνιστώμενη ανάγνωση
- Εισαγωγή στη γλώσσα προγραμματισμού Java - Video Tutorial
- Εισαγωγή στο Appium Studio: Βασικά οφέλη και δυνατότητες
- Αλγόριθμοι στο STL
- Καλύτερη δωρεάν σειρά C # Tutorial: Ο απόλυτος οδηγός C # για αρχάριους
- JMeter Video 1: Εισαγωγή, Λήψη και εγκατάσταση του JMeter
- Διαδικασία εισαγωγής και εγκατάστασης Python
- Τι είναι το Unix: Μια σύντομη εισαγωγή στο Unix
- Εισαγωγή στο Micro Focus LoadRunner - Δοκιμή φόρτωσης με LoadRunner Tutorial # 1