Binäre Suche mit Schlüssel String

shurik'n

Die folgende binäre Suche soll Strings zu Zahlen abspeichern. Das heisst ich gebe z.B. in der Suche als Schlüssel "abs" an und es kommte als Ergebnis ein Integer. Der folgende Code bricht bei mir ab "abnormal program termination" Seht Ihr einen Fehler?

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

template <class K, class D> class BinSearch 
{

  class Node
  {

  public:
	Node(K key=0, D data=0): m_Key(key), m_Data(data) 
    {}
	K m_Key;
	D m_Data;
  };

  public:
  BinSearch(unsigned uiNrOfEntries): m_cuiNrOfMaxEntries(uiNrOfEntries), 
  m_uiNextFree(0), m_pData(new Node[uiNrOfEntries]) 
  {}
  ~BinSearch()
  {
	  delete m_pData;
  }
  void insert(K key, D data)
  {
	  m_pData[m_uiNextFree++]=Node(key,data);
  }
  Node * search(K key) 
  {
	  unsigned uiL=0;
	  unsigned uiR=m_uiNextFree;
	  while(uiL<uiR)
      {
		  const unsigned cuiMiddle=(uiL+uiR)/2;
		  if (m_pData[cuiMiddle].m_Key==key)
			  return &m_pData[cuiMiddle];
		  else if (m_pData[cuiMiddle].m_Key<key)
			  uiL=cuiMiddle+1;
		  else
			  uiR=cuiMiddle;
	  }
	  return 0;
  }
  void print()
  {
	for(unsigned ui=0; ui<m_cuiNrOfMaxEntries; ui++)
		cout<<"m_Key:"<<m_pData[ui].m_Key<<" m_Data:"<<m_pData[ui].m_Data<<"\n";
  }
  void print(Node * n) 
  {
		cout<<"***Suchergebnis***"<<"\n";
		cout<<"m_Key:"<<n->m_Key<<" m_Data:"<<n->m_Data<<"\n";
  }	
  private:
  const unsigned m_cuiNrOfMaxEntries;
  unsigned m_uiNextFree;
  Node * m_pData;
};

int main() 
{
	unsigned int NrOfEntries = 100;
	BinSearch<string,int> s(NrOfEntries);
	for (unsigned ui=0; ui<NrOfEntries; ui++)
    {
		s.insert("a",ui);
	}
	s.print();
        s.print(s.search("a"));	
	system("pause");
	return 0;
}

CStoll

Ja, du packst die Elemente ungeordnet in deine Array und erwartest dann, daß sie für die binäre Suche in der richtigen Reihenfolge stehen.
Für weitere Analysen könntest du eventuell noch dazusagen, wo der Fehler aufgetreten ist.

(außerdem solltest du m_pData mit delete[] aufräumen, da es mit new[] angelegt wurde)

shurik'n

Wo der Fehler aufgetreten ist kann ich nicht sagen. Die Windows Konsolenanwendung schliesst sich sofort wieder mit "Abnormal Program Termination".

Was heisst unsortiert ins Array gepackt? Muss ich die vorher sortieren und falls ja wie?

CStoll

"unsortiert" bedeutet, daß die Daten in der Reihenfolge eingetragen werden, in der du sie an insert abgibst (wenn du erst ("b",4711) und danach ("a",1234) einträgst, stehen die Einträge in der falschen Reihenfolge für die Suche). Und ja, du mußt sie entweder vor der Suche sortieren oder (noch besser) gleich in alphabetischer Reihenfolge in dein Array einfügen.

Oder noch besser: du nutzt die Möglichkeiten der STL - map/multimap

@Absturz: Jag' das Programm mal durch einen Debugger, dann kannst du besser verfolgen, wo ein Fehler auftaucht.