Wie lineare Suche mit Zeigern zu tun?

Question

Ich bin noch neu in der Programmierung. Ich wollte nur fragen, wie ich lineare Suche mit Zeigern machen soll. Ich wollte ein Buchverwaltungsprogramm machen und habe ein Programm mit Zeigern geschrieben.

This is the example of how i want it.

Dies ist die Codierung

#include <iostream> 
#define MAX 5 
using namespace std; 
struct record 
{ 
int id;//stores id 
float price;//store price 
int qty;//stores quantity 
record* next;//reference to the next node 
}; 

record* head;//create empty record 
record* tail;//the end of the record 
void push(record *& head, record *&tail, int id, float price, int qty) 
{ 
if (head == NULL) 
{ 
    record* r = new record; 
    r->id = id; 
    r->price = price; 
    r->qty = qty; 
    r->next = NULL;//end of the list 
    head = r; 
    tail = r; 
} 
else if (head != NULL && (MAX - 1)) 
{ 
    record* r = new record; 
    r->id = id; 
    r->price = price; 
    r->qty = qty; 
    r->next = head; 
    head = r; 
} 
} 

int pop(record *&head, record *& tail) 
{ 
if (head == NULL) 
{ 
    cout << "No record in memory" << endl; 
} 
else if (head == tail) 
{ 
    cout << "The record "<<"ID: " << head->id << "\nPrice: " << head->price    << "\nQuantity: " << head->qty << "\n" << "was deleted" << endl; //CORRECTION HERE 
} 
else 
{ 
    record* delptr = new record; 
    delptr = head; 
    head = head->next; 
    cout << "The record " << delptr->id << ", " << delptr->price << ", " << delptr->qty << " was deleted" << endl; //CORRECTION HERE 
    delete delptr; 

} 
return 0; 
} 


void display(record *&head) 
{ 
record* temp = new record; //CORRECTION HERE 
temp = head; 
if (temp == NULL) 
{ 
    cout << "No record in memory" << endl; 

} 
else 
{ 


     cout << "Record : " << endl; 
     while (temp != NULL) 
     { 
      cout <<"\nID: "<< temp->id << "\nPrice: " << temp->price << "\nQuantity: " << temp->qty <<"\n"<< endl; //CORRECTION HERE 
      temp = temp->next; 
     } 

    } 
} 

    int LinearSearch(record *&head) { 


} 

char menu() 
{ 
char choice; 

cout << "\t::MENU::\n" << endl; 
cout << "1. Add new record\n" << endl; 
cout << "2. Delete record\n" << endl; 
cout << "3. Show record\n" << endl; 
cout << "4. Quit\n" << endl; 
cout << "-----------------------\n" << endl; 
cout << "\nEnter selection : " << endl; 
cin >> choice; 
return choice; 
} 

int main() 
{ 
record* head; 
record* tail; 
head = NULL; 
tail = NULL; 
char choice; 
do 
{ 
    cout << "---------------------- - \n" << endl; 
    choice = menu(); 
    switch (choice) { //CORRECTION HERE 
    case '1': 
     int id, qty; 
     float price; 
     cout << "Enter ID:"; 
     cin >> id; // Please correct yourself here, what is r here, r is not declared anywhere 
     cout << "\nEnter Price: "; 
     cin >> price; 
     cout << "\nEnter Quantity: "; 
     cin >> qty; 
     push(head, tail, id, price, qty); 
     break; 
    case '2': 
     pop(head, tail); 
     break; 
    case'3': 
     display(head); 
     break; 
    default: 
     cout << "Quiting...\n"; 
    } 

} while (choice != '4'); 

return 0; 
} 

Wie kann ich für diese Codierung lineare Suche der Zeiger Code schreiben? Ich habe versucht, Beispiele im gesamten Web zu finden und wenn ich es ausführe, hat es nicht funktioniert, also lasse ich es leer.

Answer 1

Nun, ich sah, Sie haben eine Liste und Sie haben es mit Zeigern zu tun.

Wenn Sie lineare Suche in einem Datensatz-ID tun wollen, zum Beispiel, können Sie es wie folgt tun:

record *aux = head; 
while(aux != NULL){ 
    if(aux->id == id_you_want_to_find){ 
     printf("I found it\n"); 
    } 
    aux = aux->next; 
} 

Sie in der Regel object.attribute verwenden, um die Attribute der gemeinsamen Objekte zuzugreifen, aber wenn Sie eine haben Zeiger auf ein Objekt, müssen Sie pointerToObject->attribute tun.

Answer 2

Sie können eine schreiben, wenn Sie wollen, aber es gibt keine Notwendigkeit, wenn es bereits Bibliotheken gibt, die das für Sie tun. Da Sie eine Listenstruktur verwenden, zeige ich dies mit einem einfachen std::list. Sie können dies auch in eine std::vector ändern und tun Sie einfach eine einfache for-Schleife Iteration mit Index-Notation, da die Geschwindigkeit der Suche durch sie im Gegensatz zu linear ist. Hier ist eine Methode, um eine Liste linear zu durchsuchen.

#include <list> 

record* searchRecords(std::list<record>& records, int id) { 
    if (records.empty()) { 
     std::ostringstream strStream; 
     strStream << __FUNCTION__ << " Invalid list of records: list is empty."; 
     throw ExceptionHandler(strStream); // Not Written, but what should be done instead of returning. 
     return nullptr; 
    } 

    std::list<record>::iterator it = records.begin(); 
    while (it != records.end()) { 
     if (it->id == id) { 
      return (&(*it)); 
     } 
     ++it;    
    } 

    std::ostringstream strStream; 
    strStream << __FUNCTION__ << " No entry found in search with ID{" << id << "}."; 
    Logger::log(strStream, Logger::LOGGER_INFO); // Not implemented here same as above for ExceptionHandler 
    return nullptr; 
} 

Da verkettete Listen sind nicht assoziativ sie von Anfang an durchlaufen werden muss für jeden Eintrag N in der Liste zu jedem Einsatz zu beenden, finden oder zu löschen. Die zeitliche Komplexität ist hier linear.

Wenn Sie schnellere Zeiteinfügungszeit mit großen Listen möchten, können Sie <multiset> verwenden, wenn es doppelte Elemente gibt, oder <set>, wenn jedes bekannte Element eindeutig ist. Diese haben sofortige Einfügung. Wenn Sie eine konstante Suche wünschen und sich nicht um die Einfügezeit kümmern möchten, dann ist <vector> genau das, was Sie möchten.

Answer 3

Die normale Antwort wäre: Schreiben Sie keine lineare Suche selbst, sie heißt std::find_if. C++ erwartet jedoch, dass Ihre Datenstruktur Iteratoren exponiert. Ein Iterator verweist auf einen Datensatz (oder das Ende Ihrer Liste). Sie erhalten den tatsächlichen Datensatz, indem Sie operator* für den Datensatz aufrufen, und Sie erhalten den nächsten Datensatz, indem Sie operator++ aufrufen.

Ja, das ist vergleichbar mit Zeigern. Das ist beabsichtigt; Zeiger sind Iteratoren für zusammenhängende Arrays. Das heißt, Sie können std::find_if für ein Array aufrufen. Da Sie jedoch eine verknüpfte Liste anstelle eines Arrays implementieren möchten, müssen Sie eine eigene Iterator-Klasse implementieren.