ポインタを使った線形検索の仕方は？

Question

私はまだプログラミングを始めていません。ポインタを使って線形検索を行うにはどのようにすればよいか尋ねたかっただけです。私は本管理プログラムを作りたがっていて、私はポインタを書いたプログラムを作りました。

This is the example of how i want it.

これは私がこのコーディングのためのポインタコードの線形探索を書くにはどうすればよいコーディング

#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; 
} 

のですか？私はウェブ全体で例を見つけようとしましたが、実行するとうまくいかないので空白のままにしました。

Answer 1

まあ、私はあなたがリストを持っているのを見て、あなたはポインタを扱っています。

ます。たとえば、レコードIDで線形検索をしたい場合、あなたはこのようにそれを行うことができます。

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

あなたは通常、一般的なオブジェクトの属性にアクセスするためにobject.attributeを使用しますが、持っていますオブジェクトへのポインタの場合は、pointerToObject->attributeを実行する必要があります。

Answer 2

これを実行するライブラリが既に存在する場合は、必要な場合は書き込むことができます。あなたがリスト構造を使用しているので、私は単純なstd::listを使ってこれを示します。また、これをstd::vectorに変更して、索引表記を使用する簡単なforループの繰り返しを実行することもできます。これは、索引表記を使用する検索の速度が線形ではなく一定であるためです。ここではリストリニアで検索を行う方法の1つです。

#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; 
} 

リンクリストは、彼らが、挿入見つけるまたは削除のいずれかに、リスト内のすべてのエントリNのために最初から最後まで横断する必要があり連想されていませんので。ここでの時間の複雑さは線形である。

大きなリストでの挿入時間を短縮するには、重複するアイテムがある場合は<multiset>、既知のアイテムがすべてユニークな場合は<set>を使用できます。これらは即座に挿入されます。一定の検索が必要で、挿入時間を気にしない場合は、<vector>が好きです。

Answer 3

通常の答えは次のようなものです。リニア検索を自分で書くのではなく、std::find_ifと呼ばれています。しかし、C++では、データ構造がイテレータを公開することを期待しています。イテレータは、レコード（またはリストの最後）を参照します。レコードのoperator*を呼び出して実際のレコードを取得し、operator++を呼び出して次のレコードを取得します。

はい、これはポインタに似ています。それは意図的です。ポインタは、連続した配列の場合はイテレータです。つまり、std::find_ifを配列に呼び出すことができます。しかし、配列の代わりにリンクリストを実装することを選択したので、独自のイテレータクラスを実装する必要があります。